publication . Preprint . Conference object . 2007

Computing Equilibria in Anonymous Games

Constantinos Daskalakis; Christos Papadimitriou;
Open Access English
  • Published: 30 Oct 2007
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 O(s^2 L), where s is the number of strategies and L is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an epsilon
Subjects
arXiv: Computer Science::Computer Science and Game Theory
ACM Computing Classification System: ComputingMilieux_PERSONALCOMPUTINGTheoryofComputation_MISCELLANEOUSTheoryofComputation_GENERALTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
free text keywords: Computer Science - Computer Science and Game Theory, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics
Related Organizations
Funded by
NSF| Research on Games, Networks, and Algorithms
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0635319
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations

[1] T. Abbott, D. Kane, P. Valiant. On the Complexity of Two-Player Win-Lose Games. FOCS, 2005. [OpenAIRE]

[2] A. D. Barbour, L. Holst and S. Janson. Poisson Approximation. Oxford University Press, New York, 1992.

[3] A. D. Barbour and T. Lindvall. Translated Poisson Approximation for Markov Chains. Journal of Theoretical Probability, 19(3), July 2006.

[4] M. Blonski. Characterization of Equilibria in Large Anonymous Games. University of Mannheim, 2000.

[19] R. Lipton, E. Markakis, and A. Mehta. Playing Large Games Using Simple Strategies. Electronic Commerce, 2003. [OpenAIRE]

[5] M. Blonski. Equilibrium Characterization in Large Anonymous Games. University of Mannheim, 2001.

[23] C. H. Papadimitriou and T. Roughgarden. Computing Equilibria in Multi-Player Games. SODA, 2005.

[25] A. Ro¨ llin. Translated Poisson Approximation Using Exchangeable Pair Couplings. ArXiv Report, 2006.

[26] B. Roos. Multinomial and Krawtchouk Approximations to the Generalized Multinomial Distribution. Theory of Probability and Its Applications, 46(1):103-117, 2001.

Any information missing or wrong?Report an Issue