Settling the Complexity of Computing Approximate Two-Player Nash Equilibria
Author:
- Aviad RubinsteinARAviad Rubinstein
- 1 October 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 258-265
Abstract
We prove that there exists a constant ε > 0 such that, assuming the Exponential Time Hypothesis for PPAD, computing an ε-approximate Nash equilibrium in a two-player (n × n) game requires quasi-polynomial time, n log1-o(1) n. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [54]. 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 ε-approximate Nash equilibrium in a game with n players requires 2 Ω(n) oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [43], Babichenko [13], and Chen et al. [28]. In fact, our results for n-player games are stronger: they hold with respect to the (ε,δ)-WeakNash relaxation recently introduced by Babichenko et al. [15].Keywords
All Related Versions
This publication has 49 references indexed in Scilit:
- Settling the complexity of computing two-player Nash equilibriaJournal of the ACM, 2009
- The complexity of computing a Nash equilibriumCommunications of the ACM, 2009
- Two-query PCP with subconstant errorJournal of the ACM, 2008
- 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
- The Relative Complexity of NP Search ProblemsJournal of Computer and System Sciences, 1998
- The complexity of error-correcting codes1997
- IP = PSPACEJournal of the ACM, 1992
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- Arithmetization: A new method in structural complexity theorycomputational complexity, 1991