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.
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 .
@cite_41 @cite_15 @cite_17
2122653474 2950776615
We present a novel polynomial time approximation scheme fortwo-strategy anonymous games, in which the players utilityfunctions, although potentially different, do not differentiateamong the identities of the other players. Our algorithm computesan e-approximate Nash equilibrium of an n-player 2-strategyanonymous game in time @math , which significantly improves uponthe running time @math required by the algorithm ofDaskalakis & Papadimitriou, 2007. The improved running time isbased on a new structural understanding of approximate Nashequilibria: We show that, for any e, there exists ane-approximate Nash equilibrium in which either onlyO(1 e 3) players randomize, or all players who randomizeuse the same mixed strategy. To show this result we employ toolsfrom the literature on Steins Method. 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 Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general PLS -complete. We present a surprisingly simple polynomial-time algorithm that computes @math -approximate Nash equilibria in these games. In particular, for congestion games with linear latency functions, our algorithm computes @math -approximate pure Nash equilibria in time polynomial in the number of players, the number of resources and @math . It also applies to games with polynomial latency functions with constant maximum degree @math ; there, the approximation guarantee is @math . The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium, the existence of such short sequences is interesting in itself. These are the first positive algorithmic results for approximate equilibria in non-symmetric congestion games. We strengthen them further by proving that, for congestion games that deviate from our mild assumptions, computing @math -approximate equilibria is PLS -complete for any polynomial-time computable @math .