Name
Abstract | ||
|---|---|---|
We present efficient approximation algorithms for finding Nash equilibria in anonymous games, that is, games in which the players utilities, though different, do not differentiate between other players. Our results pertain to such games with many players but few strategies. We show that any such game has an approximate pure Nash equilibrium, computable in polynomial time, with approximation {\rm O}(s^2 \lambda ), where s is the number of strategies and \lambda is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an\in- approximate Nash equilibrium when the number of strategies is two. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/FOCS.2007.19 | foundations of computer science |
Keywords | DocType | Volume |
anonymous game,approximate nash equilibrium,nash equilibrium,computing equilibria,approximate pure nash equilibrium,anonymous games,rm o,polynomial time,efficient approximation algorithm,players utility,nash equilibria,game theory,computational complexity | Conference | abs/0710.5582 |
ISSN | ISBN | Citations |
0272-5428 | 0-7695-3010-9 | 61 |
PageRank | References | Authors |
3.49 | 20 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Constantinos Daskalakis | 1 | 1179 | 85.25 |
| Christos H. Papadimitriou | 2 | 16671 | 3192.54 |