The Computational Complexity of Team Zero-Sum Games
2026-06-15 • Computer Science and Game Theory
Computer Science and Game TheoryComputational Complexity
AI summaryⓘ
The authors study a type of game called team zero-sum games, where groups of players work together against an opposing team but can't perfectly coordinate. They show that finding Nash equilibria in these games is computationally very hard (PPAD-complete), similar to the difficulty in general-sum games. This remains true even for simple cases with just two players per team and special game formats called polymatrix games. They also prove that finding stationary points in related min-max optimization problems with quadratic objectives is equally hard. Their results clarify the complexity landscape for this class of games and optimization problems.
team zero-sum gamesNash equilibriumPPAD-completenesstwo-player zero-sum gamespotential gamespolymatrix gamesmin-max optimizationstationary pointalgorithmic game theoryapproximation schemes
Authors
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, Jingming Yan
Abstract
A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side comprises multiple independent agents who share a common objective but cannot perfectly coordinate their actions. Such settings can be modeled as \emph{team zero-sum games}, a natural generalization of both two-player zero-sum games and potential games -- the two most well-studied classes of games in algorithmic game theory. In this paper, we settle the complexity of team zero-sum games by establishing that computing Nash equilibria is \PPAD-complete. As a result, despite the global adversarial structure, team zero-sum games are as hard as general-sum games. Our hardness result holds even when i) the precision is inverse polynomial, thereby ruling out a fully polynomial-time approximation scheme (unless $¶= \PPAD$); ii) each team consists of only two players; and iii) the underlying class of games is polymatrix. As a byproduct, we resolve the complexity of group-wise zero-sum polymatrix games, a class introduced and examined in the seminal work of Cai and Daskalakis (SODA '11), and more recently highlighted by Hollender, Maystre, and Nagarajan (ICLR '25). Moreover, we show that computing a first-order stationary point in min-max optimization is \PPAD-complete even for quadratic (multilinear) objectives. From a technical standpoint, we develop a series of team zero-sum game gadgets that allow us to simulate the breakthrough reduction of Bernasconi and Castiglioni (STOC '26). Moreover, to obtain hardness results for quadratic objectives, we make use of a general technique based on linear local approximation, which is of independent interest.