Approximate Nash equilibria in anonymous games

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.