Team zero-sum games proven as hard as general-sum games

A new paper by Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, and Jingming Yan settles a long-standing open problem in algorithmic game theory: the computational complexity of team zero-sum games. In these games, two competing teams each contain multiple independent agents who share a common goal but cannot perfectly coordinate. Despite the adversarial structure, the authors prove that computing Nash equilibria is PPAD-complete — the same hardness class as general-sum games. This makes team zero-sum games significantly harder than two-player zero-sum games, which are tractable via linear programming.

The hardness holds even under severe restrictions: each team has only two players, the precision is inverse-polynomial (ruling out a fully polynomial-time approximation scheme unless P=PPAD), and the underlying game class is polymatrix. As a byproduct, the paper resolves the complexity of group-wise zero-sum polymatrix games, introduced by Cai and Daskalakis in 2011 and highlighted recently by Hollender et al. at ICLR 2025. The authors also extend their techniques to min-max optimization, showing that computing a first-order stationary point is PPAD-complete even for quadratic multilinear objectives.