Playing Anonymous Games using Simple Strategies

We investigate the complexity of computing approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any n-player anonymous game with a bounded number of strategies and any constant δ>0, an O(1/n1-δ)-approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if there exists any constant δ>0 such that an O(1/n1+δ)-approximate equilibrium can be computed in polynomial time, then there is a fully polynomial-time approximation scheme for this problem. We also present a faster algorithm that, for any n-player k-strategy anonymous game, runs in time tilde O((n+k) k nk) and computes an tilde O(n-1/3 k11/3)-approximate equilibrium. This algorithm follows from the existence of simple approximate equilibria of anonymous games, where each player plays one strategy with probability 1-δ, for some small δ, and plays uniformly at random with probability δ. Our approach exploits the connection between Nash equilibria in anonymous games and Poisson multinomial distributions (PMDs). Specifically, we prove a new probabilistic lemma establishing the following: Two PMDs, with large variance in each direction, whose first few moments are approximately matching are close in total variation distance. Our structural result strengthens previous work by providing a smooth tradeoff between the variance bound and the number of matching moments.