text: We show that the problem of finding an -approximate Nash equilibrium in an anonymous game with seven pure strategies is complete in PPAD, when the approximation parameter is exponentially small in the number of players.
  @cite_41: We show that there is a polynomial-time approximation scheme for computing Nash equilibria in anonymous games with any fixed number of strategies (a very broad and important class of games), extending the two-strategy result of Daskalakis and Papadimitriou 2007. The approximation guarantee follows from a probabilistic result of more general interest: The distribution of the sum of n independent unit vectors with values ranging over e1,...,ek , where ei is the unit vector along dimension i of the k-dimensional Euclidean space, can be approximated by the distribution of the sum of another set of independent unit vectors whose probabilities of obtaining each value are multiples of 1 z for some integer z, and so that the variational distance of the two distributions is at most eps, where eps is bounded by an inverse polynomial in z and a function of k, but with no dependence on n. Our probabilistic result specifies the construction of a surprisingly sparse epsi-cover- under the total variation distance - of the set of distributions of sums of independent unit vectors, which is of interest on its own right.
  @cite_15: 
  @cite_17: 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
summary: In @cite_17 , Daskalakis and Papadimitriou presented a PTAS for finding an @math -approximate Nash equilibrium in an anonymous game with two pure strategies, with running time @math , where @math denotes the number of bits required to describe the payoffs. The running time was subsequently improved in @cite_15 to @math . The first PTAS in @cite_17 is based on the existence of an @math -approximate Nash equilibrium consisting of integer multiples of @math , while the second PTAS in @cite_15 is based on the existence of an @math -approximate Nash equilibrium satisfying the following special property: either at most @math players play mixed strategies, or all players who mix play the same mixed strategy. Later @cite_41 extended the result of @cite_17 , giving the only known PTAS for anonymous games with any bounded number of pure strategies with time @math for some function @math of @math , number of pure strategies, and @math .