An Efficient PTAS for Two-Strategy Anonymous Games
| dc.creator | Daskalakis, Constantinos | |
| dc.date | 2008-12-12 | |
| dc.date.accessioned | 2026-07-07T12:12:22Z | |
| dc.date.available | 2026-07-07T12:12:22Z | |
| dc.description | We present a novel polynomial time approximation scheme for two-strategy anonymous games, in which the players' utility functions, although potentially different, do not differentiate among the identities of the other players. Our algorithm computes an $eps$-approximate Nash equilibrium of an $n$-player 2-strategy anonymous game in time $poly(n) (1/eps)^{O(1/eps^2)}$, which significantly improves upon the running time $n^{O(1/eps^2)}$ required by the algorithm of Daskalakis & Papadimitriou, 2007. The improved running time is based on a new structural understanding of approximate Nash equilibria: We show that, for any $eps$, there exists an $eps$-approximate Nash equilibrium in which either only $O(1/eps^3)$ players randomize, or all players who randomize use the same mixed strategy. To show this result we employ tools from the literature on Stein's Method. | |
| dc.identifier | https://arxiv.org/abs/0812.2277 | |
| dc.identifier | http://arxiv.org/abs/0812.2277 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/210522 | |
| dc.subject | Computer Science and Game Theory | |
| dc.title | An Efficient PTAS for Two-Strategy Anonymous Games | |
| dc.type | text |