The Complexity of Exact and Approximate Nash Equilibria in Anonymous Games

We prove that, for every fixed rational $c>0$, computing a $2^{-n^c}$-approximate Nash equilibrium in an $n$-player two-strategy anonymous game is $\mathsf{P}\mathsf{P}\mathsf{A}\mathsf{D}$-complete. This holds even when one strategy always pays $1\mathrm{/}2$ and, for all but two players, the other is constant outside at most five opponent counts. The reduction uses coefficient estimates to simulate circuit constraints approximately. Exact computation requires eliminating the simulation error: with three strategies, a separate construction uses polynomial roots to implement circuit gates exactly. This yields $\mathsf{F}\mathsf{I}\mathsf{X}\mathsf{P}$-completeness of exact equilibrium computation under separable-linear reductions and ${\mathsf{F}\mathsf{I}\mathsf{X}\mathsf{P}}_a$-completeness of approximation in distance to an exact equilibrium.