Computing Equilibria in Anonymous Games

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 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 isin-approximate Nash equilibrium when the number of strategies is two.

Authors

• Constantinos Daskalakis
• Christos H. Papadimitriou

Keywords

• Nash equilibrium
• Game theory
• Computer science
• Polynomials
• Approximation algorithms
• Sprites (computer)
• Internet
• Equilibrium Of The Game
• Anonymous Games
• Number Of Strategies
• Approximate Equilibrium
• Random Variables
• Poisson Distribution
• Fixed Point
• Total Distance
• Best Response
• Convex Hull
• Subintervals
• Mixed Strategy
• Triangle Inequality
• Multinomial Distribution
• Mixed Profile
• Pure Strategy
• Sum Of Distributions
• Total Variation Distance
• Class Of Games
• Poisson Approximation
• Subset Of Indices
• Original Game