Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players

For every fixed $\epsilon \in (0,1)$ and $\eta \in [0,1)$, we prove that computing an $(\epsilon ,\eta )$-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 $\eta$ fraction of players to gain more than $\epsilon$ by deviating unilaterally. The main technical result is an unconditional error-amplification reduction from bimatrix games. For every fixed $\delta \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 $\delta ,\epsilon ,\eta$. Every $(\epsilon ,\eta )$-weak approximate equilibrium of the constructed game yields a $\delta$-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.