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 textsfCLS-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 textsfPPAD-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 textsfPPAD-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 non-symmetric poly(1/n)-equilibrium in symmetric min-max optimization is textsfFNP-hard.