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

Ioannis Panageas (UC Irvine) · Ioannis Anagnostides (Carnegie Mellon University) · Tuomas Sandholm (CMU, Strategy Robot, Optimized Markets, Strategic Machine) · Jingming Yan (University of California, Irvine)

$\epsilon$-nash equilibriaadversarial team gamescls-completenesscomplexity theoryfirst-order equilibriafnp-hardnessmin-max optimization nash equilibrianon-symmetric equilibriapolymatrix gamesppad-completenessquadratic functionsstationary pointssymmetric dynamicssymmetric gameszero-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 $\epsilon$-Nash equilibria in $3$-player $\text{\emph{adversarial}}$ team games