Approximate Nash equilibria in anonymous games

Constantinos Daskalakis and Christos H. Papadimitriou

Journal of Economic Theory, 2015, vol. 156, issue C, 207-245

Abstract: We study from an algorithmic viewpoint anonymous games[22,4,5,19]. In these games a large population of players shares the same strategy set and, while players may have different payoff functions, the payoff of each depends on her own choice of strategy and the number of the other players playing each strategy (not the identity of these players). We show that, the intractability results of [12] and [10] for general games notwithstanding, approximate mixed Nash equilibria in anonymous games can be computed in polynomial time, for any desired quality of the approximation, as long as the number of strategies is bounded by some constant. In addition, if the payoff functions have a Lipschitz continuity property, we show that an approximate pure Nash equilibrium exists, whose quality depends on the number of strategies and the Lipschitz constant of the payoff functions; this equilibrium can also be computed in polynomial time. Finally, if the game has two strategies, we establish that there always exists an approximate Nash equilibrium in which either only a small number of players randomize, or of those who do, they all randomize the same way. Our results make extensive use of certain novel Central Limit-type theorems for discrete approximations of the distributions of multinomial sums.

Keywords: Anonymous games; Nash equilibrium; Approximation algorithms (search for similar items in EconPapers)
JEL-codes: C72 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0022053114000209
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jetheo:v:156:y:2015:i:c:p:207-245

DOI: 10.1016/j.jet.2014.02.002

Access Statistics for this article

Journal of Economic Theory is currently edited by A. Lizzeri and K. Shell

More articles in Journal of Economic Theory from Elsevier
Bibliographic data for series maintained by Catherine Liu ().