Computing approximate Nash equilibria with few players takes quasipolynomial time
Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players
Computer Science and Game TheoryComputational Complexity
Summary
Finding approximate solutions where players in a game have little incentive to change strategy is important but can be very hard. This paper shows that even when there are only a few players and simple payoffs, solving a certain kind of approximate equilibrium problem is still very complex and requires quasipolynomial time, assuming a standard computational hardness hypothesis. The authors provide a new way to translate difficult problems from two-player games to games with more players, preserving the hardness. This helps better understand the limits of how fast we can compute these game solutions.
What this means in practice
- •For algorithm designers: Avoid attempts to create fast exact or weak approximate Nash equilibrium solvers for small-player games, as they require quasipolynomial time under standard hardness assumptions.
- •For game theory software developers: Use these complexity limits to guide expectations and design of approximation heuristics when implementing equilibrium computations for games with few players.
A theory result. No direct application yet.
Authors
Xiaotie Deng, Ningyuan Li, Zihe Wang, Jie Zhang
Abstract
For every fixed $\varepsilon\in(0,1)$ and $η\in[0,1)$, we prove that computing an $(\varepsilon,η)$-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH, even in symmetric binary-payoff games with a constant number of players. The games are given by complete payoff tables, and the player count depends only on the tolerances. The weak approximate Nash equilibrium allows at most an $η$ fraction of players to gain more than $\varepsilon$ by deviating unilaterally. The main technical result is an unconditional error-amplification reduction from bimatrix games. For every fixed $δ\in(0,1)$, it transforms a rational bimatrix game with payoffs in $[0,1]$ into a symmetric binary-payoff game with a polynomial-size complete table and a player count depending only on $δ,\varepsilon,η$. Every $(\varepsilon,η)$-weak approximate equilibrium of the constructed game yields a $δ$-approximate Nash equilibrium of the bimatrix game. Construction and recovery take polynomial time in their explicit inputs. Combining this reduction with the bimatrix hardness result of Rubinstein [FOCS 16] gives a deterministic worst-case running-time lower bound of $N^{(\log N)^{1-o(1)}}$, where $N$ is the constructed table's binary encoding length.