Computing approximate Nash equilibria provably requires very high time
The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games
Computer Science and Game TheoryComputational Complexity
Summary
Finding an approximate balance point in games with many actions can be very slow. The authors show that any algorithm must take a huge amount of time as the number of choices grows and the approximation gets more precise. This confirms that a known method from 2003 is basically the fastest possible for many cases. They also prove a similar result for another problem called free games. These findings rely on some widely believed but unproven assumptions in computer science about problem difficulty.
Nash equilibriumapproximation algorithmsnormal-form gamescomputational complexityETH (Exponential Time Hypothesis)PPAD complexity classPCP theoremfree gamesLipton-Markakis-Mehta algorithmadditive value estimation
Authors
Noah Golowich
Abstract
We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under the PCP for PPAD and ETH for PPAD conjectures, we show that computing $\varepsilon$-approximate Nash equilibria in 2-player $N$-action normal-form games requires time $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$, thus showing that the classical Lipton-Markakis-Mehta algorithm (2003) is optimal through all regimes of $\varepsilon = ω(1/\sqrt{N})$. While such optimality was known in the constant-$\varepsilon$ regime (Rubinstein, 2016), previous work could only rule out significantly smaller running times of $N^{O(\log(N)/\varepsilon)}$ in the regime $\varepsilon = o(1)$. Using similar techniques, we then establish an analogous tight lower bound of $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$ under ETH for $\varepsilon$-additive value estimation in free games, when $\varepsilon \geq 2^{-o(\sqrt{\log N})}$, answering a question of Aaronson, Impagliazzo, and Moshkovitz (2014).