The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games

We consider the problem of computing stationary points in min-max optimization, with a focus on the special case of Nash equilibria in (two-)team zero-sum games. We first show that computing $ϵ$-Nash equilibria in $3$-player $\text{adversarial}$ team games---wherein a team of $2$ players competes against a $\text{single}$ adversary---is $\text{CLS}$-complete, resolving the complexity of Nash equilibria in such settings.

Our proof proceeds by reducing from $\text{symmetric}$ $ϵ$-Nash equilibria in $\text{symmetric}$, identical-payoff, two-player games, by suitably leveraging the adversarial player so as to enforce symmetry---without disturbing the structure of the game. In particular, the class of instances we construct comprises solely polymatrix games, thereby also settling a question left open by Hollender, Maystre, and Nagarajan (2024). Moreover, we establish that computing $\text{symmetric}$ (first-order) equilibria in $\text{symmetric}$ min-max optimization is $\text{PPAD}$-complete, even for quadratic functions.

Building on this reduction, we show that computing symmetric $ϵ$-Nash equilibria in symmetric, $6$-player ($3$ vs. $3$) team zero-sum games is also $\text{PPAD}$-complete, even for $ϵ=\text{poly}(1/n)$. As a corollary, this precludes the existence of symmetric dynamics---which includes many of the algorithms considered in the literature---converging to stationary points. Finally, we prove that computing a $\text{non-symmetric}$ $\text{poly}(1/n)$-equilibrium in symmetric min-max optimization is $\text{FNP}$-hard.