{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib4pa4ve4osdihzjctkk5hmrjpddzdfetqtgm5qxisl65zjzwgswm",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mof4fxkmzaj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.16139v1",
  "publishedAt": "2026-06-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Ioannis Anagnostides",
    "Ioannis Panageas",
    "Tuomas Sandholm",
    "Jingming Yan"
  ],
  "textContent": "**Authors:** Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, Jingming Yan\n\nA 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.",
  "title": "The Computational Complexity of Team Zero-Sum Games"
}