Computing approximate Nash equilibria is nearly optimally slow
The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games
Computer Science and Game TheoryComputational Complexity
Summary
Finding approximate Nash equilibria, a way for players to predict stable strategies in games, is very hard when the approximation needs to be very precise. The authors show that existing algorithms are essentially the fastest possible for a wide range of precisions. They also prove a similar hardness for estimating values in special two-player games called free games. This means that speeding up calculations in these areas is likely impossible without major breakthroughs.
What this means in practice
- •For algorithm designers: Rule out faster algorithms for computing approximate Nash equilibria in large games at fine approximation levels.
- •For complexity analysts: Eliminate possibilities of improved polynomial-time approximations for free games' value estimation within certain precision ranges.
A theory result. No direct application yet.
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).