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 $ε$-Nash equilibria in $3$-player adversarial team games -- wherein a team of $2$ players competes against a single adversary -- is \textsf{CLS}-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from symmetric $ε$-Nash equilibria in 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 symmetric (first-order) equilibria in symmetric min-max optimization is \textsf{PPAD}-complete, even for quadratic functions. Building on this reduction, we further show that computing symmetric $ε$-Nash equilibria in symmetric, $6$-player ($3$ vs. $3$) team zero-sum games is also \textsf{PPAD}-complete, even for $ε= \text{poly}(1/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 non-symmetric $\text{poly}(1/n)$-equilibrium in symmetric min-max optimization is \textsf{FNP}-hard.