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 particular focus on the special case of computing Nash equilibria in (two-)team zero-sum games. We first show that computing $\epsilon$-Nash equilibria in $3$-player \emph{adversarial} team games – wherein a team of $2$ players competes against a \emph{single} adversary – is $\mathsf{\text{CLS}}$-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from \emph{symmetric} $\epsilon$-Nash equilibria in \emph{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). We also provide some further results concerning equilibrium computation in adversarial team games. Moreover, we establish that computing \emph{symmetric} (first-order) equilibria in \emph{symmetric} min-max optimization is $\mathsf{\text{PPAD}}$-complete, even for quadratic functions. Building on this reduction, we further show that computing symmetric $\epsilon$-Nash equilibria in symmetric, $6$-player ($3$ vs. $3$) team zero-sum games is also $\mathsf{\text{PPAD}}$-complete, even for $\epsilon =\text{poly}(1\mathrm{/}n)$. As an immediate 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 \emph{non-symmetric} $\text{poly}(1\mathrm{/}n)$-equilibrium in symmetric min-max optimization is $\mathsf{\text{FNP}}$-hard.