Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

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, nlog1-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].

Authors

• Aviad Rubinstein

Keywords

• Games
• Complexity theory
• Nash equilibrium
• Encoding
• Error correction codes
• Probabilistic logic
• Approximation algorithms
• Exponential Time
• Two-player Game
• Equilibrium Of The Game
• Hardness Results
• Approximate Equilibrium
• High Probability
• Lower Bound
• Conjecture
• Fixed Point
• Equilibrium Time
• Mixed Strategy
• Codeword
• Complex Communication
• Follow-up Work
• Local Computing
• Finite Field
• Identically Zero
• Local Construction
• Random Bits
• Class Of Games
• Input Bits
• Random String
• Output Bits
• Computational complexity