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, n log1-o(1) n. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, a...

Full description

Saved in:
Bibliographic Details
Main Author: Rubinstein, Aviad
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Complexity theory
Computational complexity
Encoding
Error correction codes
Games
Nash equilibrium
Probabilistic logic
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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].
ISSN:0272-5428
DOI:10.1109/FOCS.2016.35