Settling the complexity of computing approximate two-player Nash equilibria
Author:
Preprint
Abstract
We prove that there exists a constant $\epsilon>0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player (nXn) game requires quasi-polynomial time, $n^{\log^{1-o(1)} n}$. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD. En route, we also prove new hardness results for computing Nash equilibria in games with many players. In particular, we show that computing an $\epsilon$-approximate Nash equilibrium in a game with n players requires $2^{\Omega(n)}$ oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [HN13], Babichenko [Bab14], and Chen et al. [CCT15]. In fact, our results for n-player games are stronger: they hold with respect to the $(\epsilon,\delta)$-WeakNash relaxation recently introduced by Babichenko et al. [BPR16].
Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- The query complexity of correlated equilibriaGames and Economic Behavior, 2018
- Lower Bounds Based on the Exponential-Time Hypothesis2015
- A combination of testability and decodability by tensor productsRandom Structures & Algorithms, 2013
- Tolerant property testing and distance approximationJournal of Computer and System Sciences, 2006
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- The Relative Complexity of NP Search ProblemsJournal of Computer and System Sciences, 1998
- Approximating Probability Distributions Using Small Sample SpacesCombinatorica, 1998
- On sparse approximations to randomized strategies and convex combinationsLinear Algebra and its Applications, 1994
- Arithmetization: A new method in structural complexity theorycomputational complexity, 1991