Abstract
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 \emph{adversarial} team games -- wherein a team of 2 players competes against a \emph{single} adversary -- is \textsf{CLS}-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from \emph{symmetric} ε-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 \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 ε = 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 \emph{non-symmetric} poly(1/n)-equilibrium in symmetric min-max optimization is \textsf{FNP}-hard.