On oblivious PTAS's for nash equilibrium

ABSTRACT

If a class of games is known to have a Nash equilibrium with probability values that are either zero or Ω(1) -- and thus with support of bounded size -- then obviously this equilibrium can be found exhaustively in polynomial time. Somewhat surprisingly, we show that there is a PTAS for the class of games whose equilibria are guaranteed to have small --- O(1/n) -- values, and therefore large -- Ω(n) -- supports. We also point out that there is a PTAS for games with sparse payoff matrices, a family for which the exact problem is known to be PPAD-complete [Chen, Deng, Teng 2006]. Both algorithms are of a special kind that we call oblivious: The algorithm just samples a fixed distribution on pairs of mixed strategies, and the game is only used to determine whether the sampled strategies comprise an ε-Nash equilibrium; the answer is "yes" with inverse polynomial probability (in the second case, the algorithm is actually deterministic). These results bring about the question: Is there an oblivious PTAS for finding a Nash equilibrium in general games? We answer this question in the negative; our lower bound comes close to the quasi-polynomial upper bound of [Lipton, Markakis, Mehta 2003]. Another recent PTAS for anonymous games [Daskalakis, Papadimitriou 2007 and 2008, Daskalakis 2008] is also oblivious in a weaker sense appropriate for this class of games (it samples from a fixed distribution on unordered collections of mixed strategies), but its running time is exponential in 1/ε. We prove that any oblivious PTAS for anonymous games with two strategies and three player types must have 1/ε^α in the exponent of the running time for some α ≥ 1/3, rendering the algorithm in [Daskalakis 2008] (which works with any bounded number of player types) essentially optimal within oblivious algorithms. In contrast, we devise a poly n • (1/ε)^{O(\log2(1/ε))} non-oblivious PTAS for anonymous games with two strategies and any bounded number of player types. The key idea of our algorithm is to search not over unordered sets of mixed strategies, but over a carefully crafted set of collections of the first O(log 1/ε) moments of the distribution of the number of players playing strategy 1 at equilibrium. The algorithm works because of a probabilistic result of more general interest that we prove: the total variation distance between two sums of independent indicator random variables decreases exponentially with the number of moments of the two sums that are equal, independent of the number of indicators.

REFERENCES

• 1: . Althöfer. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and Applications, 199:339--355, 1994.
• 2: . Blonski. Anonymous Games with Binary Actions. Games and Economic Behavior, 28(2): 171--180, 1999.
• 3: . Blonski. The women of Cairo: Equilibria in large anonymous games. Journal of Mathematical Economics, 41(3): 253--264, 2005.
• 4: H. Bosse, J. Byrka and E. Markakis. New Algorithms for Approximate Nash Equilibria in Bimatrix Games. WINE, 2007.
• 5: X. Chen and X. Deng. Settling the Complexity of Two-Player Nash Equilibrium. FOCS, 2006.
• 6: X. Chen, X. Deng and S.-H. Teng. Sparse Games Are Hard. WINE, 2006.
• 7: C. Daskalakis. An Efficient PTAS for Two-Strategy Anonymous Games. WINE, 2008.
• 8: C. Daskalakis. An Efficient PTAS for Two--Strategy Anonymous Games. ArXiv Report, 2008.
• 9: C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. STOC, 2006.
• 10: C. Daskalakis, A. Mehta, and C. H. Papadimitriou. A Note on Approximate Nash Equilibria. WINE, 2006.
• 11: C. Daskalakis, A. Mehta, and C. H. Papadimitriou. Progress in Approximate Nash Equilibria. EC, 2007.
• 12: C. Daskalakis and C. H. Papadimitriou. Three--Player Games Are Hard. Electronic Colloquium in Computational Complexity, TR05-139, 2005.
• 13: C. Daskalakis and C. H. Papadimitriou. Computing Equilibria in Anonymous Games. FOCS, 2007.
• 14: C. Daskalakis and C. H. Papadimitriou. Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. FOCS, 2008.
• 15: R. Durrett. Probability: Theory and Examples. Second Edition, Duxbury Press, 1996.
• 16: P. W. Goldberg and C. H. Papadimitriou. Reducibility Among Equilibrium Problems. STOC, 2006.
• 17: E. Kalai. Partially-Specified Large Games. WINE, 2005.
• 18: R. Lipton, E. Markakis, and A. Mehta. Playing Large Games Using Simple Strategies. EC, 2003.
• 19: . Milchtaich. Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior, 13:111--124.
• 20: . Roos. Binomial Approximation to the Poisson Binomial Distribution: The Krawtchouk Expansion. Theory of Probability and its Applications, 45(2):258--272, 2000.
• 21: H. Tsaknakis and P. G. Spirakis. An Optimization Approach for Approximate Nash Equilibria. WINE, 2007.
• 22: . M. Zolotarev. Random Symmetric Polynomials. Journal of Mathematical Sciences, 38(5):2262--2272, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Economics

Keywords:
PTAS, anonymous games, bimatrix games, oblivious algorithms