pith. sign in

arxiv: 2409.07398 · v2 · submitted 2024-09-11 · 💻 cs.GT

The Complexity of Two-Team Polymatrix Games with Independent Adversaries

Alexandros Hollender , Gilbert Maystre , Sai Ganesh Nagarajan This is my paper

Pith reviewed 2026-05-23 21:15 UTC · model grok-4.3

classification 💻 cs.GT
keywords polymatrix gamesNash equilibriaCLS complexitymulti-team gameszero-sum gamescoordination gamesmin-max optimizationstationary points
0
0 comments X

The pith

Two-team polymatrix games are CLS-hard to solve for Nash equilibria.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that computing Nash equilibria in two-team polymatrix games, where each pair of players plays either a zero-sum or coordination game, is CLS-hard. This holds even though the three-team version was already known to be PPAD-complete. The hardness is established via a reduction that preserves the team structure and payoff types. For the special case where one team consists of multiple independent adversaries, the problem is shown to be in CLS as well, establishing CLS-completeness. The authors also prove hardness of finding stationary points for a class of bilinear polynomial min-max problems.

Core claim

Our main contribution is to prove that the two-team version remains hard, namely it is CLS-hard. Furthermore, we show that this lower bound is tight (i.e., CLS-membership) for the setting where one of the teams consists of multiple independent adversaries. By leveraging this result we also obtain a simple algorithm that finds an ε-Nash equilibrium and only has a 1/ε² dependence in ε in its running time. On the way to obtaining our main result, we prove hardness of finding any stationary point in the simplest type of non-convex-concave min-max constrained optimization problem, namely for a class of bilinear polynomial objective functions.

What carries the argument

A reduction from a known CLS-hard problem onto two-team polymatrix games that preserves zero-sum or coordination payoffs and the team partitioning.

If this is right

  • The two-team polymatrix game problem is CLS-hard in the general case.
  • When one team consists of multiple independent adversaries the problem is CLS-complete.
  • An algorithm exists for computing ε-Nash equilibria with only 1/ε² dependence on ε in the running time.
  • Finding stationary points is hard even for bilinear polynomial objectives in min-max problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The distinction between coordinated teams and independent adversaries may affect complexity in other multiplayer game settings.
  • Similar reductions could be explored for stationary-point computation in related optimization problems beyond bilinear cases.
  • The 1/ε² runtime bound may suggest improved practical methods for approximate equilibria in independent-adversary team games.

Load-bearing premise

The reduction used to establish CLS-hardness correctly maps instances of a known CLS-hard problem onto two-team polymatrix games while preserving the zero-sum/coordination payoff structure and team partitioning.

What would settle it

A polynomial-time algorithm for computing Nash equilibria in general two-team polymatrix games would imply a polynomial-time algorithm for the source CLS-hard problem used in the reduction.

Figures

Figures reproduced from arXiv: 2409.07398 by Alexandros Hollender, Gilbert Maystre, Sai Ganesh Nagarajan.

Figure 1
Figure 1. Figure 1: Classes of total search problems. Arrows are used t [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The intuition behind exact (ε = 0) KKT points for minmax problems. The formulation features a min-variable x, a max-variable y and the bounding box constraint (x, y) ∈ [0, 1]2 . Some feasible points together with their respective gradient (q x , qy ) are depicted. Green points are valid KKT points whereas red ones are not. For instance, (x1, y1) is not a KKT point because q y 1 > 0 but y < 1. On the other … view at source ↗
read the original abstract

Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games are a multiplayer setting where Nash equilibria are known to be efficiently computable. Towards understanding the limits of tractability in polymatrix games, we study the computation of Nash equilibria in such games where each pair of players plays either a zero-sum or a coordination game. We are particularly interested in the setting where players can be grouped into a small number of teams of identical interest. While the three-team version of the problem is known to be PPAD-complete, the complexity for two teams has remained open. Our main contribution is to prove that the two-team version remains hard, namely it is CLS-hard. Furthermore, we show that this lower bound is tight (i.e., CLS-membership) for the setting where one of the teams consists of multiple independent adversaries. By leveraging this result we also obtain a simple algorithm that finds an $\varepsilon$-Nash equilibrium and only has a $1/\varepsilon^2$ dependence in $\varepsilon$ in its running time. On the way to obtaining our main result, we prove hardness of finding any stationary point in the simplest type of non-convex-concave min-max constrained optimization problem, namely for a class of bilinear polynomial objective functions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies Nash equilibrium computation in polymatrix games where pairwise interactions are zero-sum or coordination games and players are partitioned into two teams of aligned interests. It proves that the general two-team problem is CLS-hard via reduction from known CLS-complete problems. It shows membership in CLS (hence CLS-completeness) when one team consists of multiple independent adversaries. Using this, the authors derive a simple algorithm for ε-Nash equilibria whose running time depends on 1/ε². As an auxiliary result, they prove that finding stationary points is hard even for bilinear polynomial objectives in the simplest non-convex-concave min-max setting.

Significance. If the reductions and membership arguments hold, the work closes a notable open question on the complexity landscape of polymatrix games, establishing a tight CLS characterization for a natural two-team variant and improving the dependence on ε for approximate equilibria. The auxiliary hardness result for bilinear stationary-point computation broadens the impact to constrained optimization. Strengths include the explicit use of reductions from established CLS-complete problems and the focus on preserving zero-sum/coordination structure under team partitioning.

minor comments (2)
  1. Abstract: the phrase 'a simple algorithm that finds an ε-Nash equilibrium and only has a 1/ε² dependence in ε in its running time' should specify whether the algorithm is polynomial-time in the input size for fixed ε or the precise setting (e.g., independent-adversaries case) in which the bound applies.
  2. The manuscript would benefit from an explicit statement, early in the introduction or preliminaries, of the precise payoff structure (zero-sum vs. coordination) that is preserved by the team partitioning in the hardness reduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our paper, the assessment of its significance in resolving the complexity of two-team polymatrix games, and the recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; hardness via external reduction

full rationale

The paper's central claims are CLS-hardness of two-team polymatrix games (via reduction from known CLS-complete problems) and CLS-membership for the independent-adversaries case. These are standard complexity reductions that map external problem instances while preserving payoff structure; no self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear. The additional bilinear stationary-point hardness result is likewise obtained by reduction and does not reduce to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard definitions of CLS and PPAD together with the correctness of a reduction that preserves game structure; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (2)
  • standard math Standard definitions and completeness results for the CLS complexity class
    Invoked to classify the two-team game problem.
  • domain assumption The constructed reduction from a known CLS-hard problem preserves the polymatrix zero-sum/coordination structure and team partitioning
    Load-bearing for the hardness claim.

pith-pipeline@v0.9.0 · 5764 in / 1307 out tokens · 24988 ms · 2026-05-23T21:15:08.148087+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    [BCDNG17] Nicola Basilico, Andrea Celli, Giuseppe De Nitti s, and Nicola Gatti

    doi:10.1145/3580507.3597776. [BCDNG17] Nicola Basilico, Andrea Celli, Giuseppe De Nitti s, and Nicola Gatti. Team-maxmin equi- librium: Efficiency bounds and algorithms. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI) , pages 356–362,

    work page doi:10.1145/3580507.3597776

  2. [2]

    [BCI+08] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Ad am Tauman Kalai, Vahab Mir- rokni, and Christos Papadimitriou

    doi:10.1609/aaai.v31i1.10560. [BCI+08] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Ad am Tauman Kalai, Vahab Mir- rokni, and Christos Papadimitriou. The myth of the folk theo rem. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC) , pages 365–372,

    work page doi:10.1609/aaai.v31i1.10560

  3. [3]

    [BPR15] Nir Bitansky, Omer Paneth, and Alon Rosen

    doi:10.1145/1374376.1374429. [BPR15] Nir Bitansky, Omer Paneth, and Alon Rosen. On the cry ptographic hardness of finding a Nash equilibrium. In Proceedings of the 56th Symposium on Foundations of Compute r Science (FOCS), pages 1480–1498,

    work page doi:10.1145/1374376.1374429

  4. [4]

    [BR21] Yakov Babichenko and A viad Rubinstein

    doi:10.1109/focs.2015.94. [BR21] Yakov Babichenko and A viad Rubinstein. Settling the complexity of Nash equilibrium in congestion games. In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), pages 1426–1437,

    work page doi:10.1109/focs.2015.94 2015

  5. [5]

    [BS18] Noam Brown and Tuomas Sandholm

    doi:10.1145/3406325.3451039. [BS18] Noam Brown and Tuomas Sandholm. Superhuman AI for hea ds-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424,

    work page doi:10.1145/3406325.3451039

  6. [6]

    [BS19] Noam Brown and Tuomas Sandholm

    doi:10.1126/science.aao1733. [BS19] Noam Brown and Tuomas Sandholm. Superhuman AI for mul tiplayer poker. Science, 365(6456):885–890,

    work page doi:10.1126/science.aao1733

  7. [7]

    [CD11] Yang Cai and Constantinos Daskalakis

    doi:10.1126/science.aay2400. [CD11] Yang Cai and Constantinos Daskalakis. On minmax theo rems for multiplayer games. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algori thms (SODA) , pages 217–234,

    work page doi:10.1126/science.aay2400

  8. [8]

    [CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng

    doi:10.1137/1.9781611973082.20. [CDT09] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of com- puting two-player Nash equilibria. Journal of the ACM , 56(3):14:1–14:57,

    work page doi:10.1137/1.9781611973082.20

  9. [9]

    [CG18] Andrea Celli and Nicola Gatti

    doi:10.1145/1516512.1516516. [CG18] Andrea Celli and Nicola Gatti. Computational result s for extensive-form adversarial team games. In Proceedings of the 32nd AAAI Conference on Artificial Intellig ence (AAAI) , pages 965–972,

    work page doi:10.1145/1516512.1516516

  10. [10]

    [CHK+19] Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzy sztof Pietrzak, Alon Rosen, and Guy N

    doi:10.1609/aaai.v32i1.11462. [CHK+19] Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzy sztof Pietrzak, Alon Rosen, and Guy N. Rothblum. Finding a Nash equilibrium is no easier t han breaking Fiat-Shamir. In Proceedings of the 51st ACM Symposium on Theory of Computing ( STOC), pages 1103– 1114,

    work page doi:10.1609/aaai.v32i1.11462

  11. [11]

    [DFG20] Constantinos Daskalakis, Dylan J

    doi:10.1145/3313276.3316400. [DFG20] Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In Proceedings of the 34th Con- ference on Neural Information Processing Systems (NeurIPS) , pages 5527–5540,

    work page doi:10.1145/3313276.3316400

  12. [12]

    [DFHM24] Argyrios Deligkas, John Fearnley, Alexandros Hol lender, and Themistoklis Melissour- gos

    URL: https://proceedings.neurips.cc/paper/2020/hash/3b2acfe2e38102074656ed938abf4ac3-Abstract.html. [DFHM24] Argyrios Deligkas, John Fearnley, Alexandros Hol lender, and Themistoklis Melissour- gos. Pure-circuit: Tight inapproximability for PPAD. Journal of the ACM ,

    work page 2020

  13. [13]

    [DGP09] Constantinos Daskalakis, Paul W

    doi:10.1145/3678166. [DGP09] Constantinos Daskalakis, Paul W. Goldberg, and Chr istos H. Papadimitriou. The complex- ity of computing a Nash equilibrium. SIAM Journal on Computing , 39(1):195–259,

    work page doi:10.1145/3678166

  14. [14]

    14 [DP09] Constantinos Daskalakis and Christos H

    doi:10.1137/070699652. 14 [DP09] Constantinos Daskalakis and Christos H. Papadimitr iou. On a network general- ization of the minmax theorem. In Proceedings of the 36th International Collo- quium on Automata, Languages, and Programming (ICALP) , pages 423–434,

    work page doi:10.1137/070699652

  15. [15]

    [DP11] Constantinos Daskalakis and Christos Papadimitrio u

    doi:10.1007/978-3-642-02930-1_35 . [DP11] Constantinos Daskalakis and Christos Papadimitrio u. Continuous local search. In Proceed- ings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SO DA), pages 790–804,

    work page doi:10.1007/978-3-642-02930-1_35

  16. [16]

    [DSZ21] Constantinos Daskalakis, Stratis Skoulakis, and M anolis Zampetakis

    doi:10.1137/1.9781611973082.62. [DSZ21] Constantinos Daskalakis, Stratis Skoulakis, and M anolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC) , pages 1466–1478,

    work page doi:10.1137/1.9781611973082.62

  17. [17]

    [FCGS18] Gabriele Farina, Andrea Celli, Nicola Gatti, and T uomas Sandholm

    doi:10.1145/3406325.3451125. [FCGS18] Gabriele Farina, Andrea Celli, Nicola Gatti, and T uomas Sandholm. Ex ante coordination and collusion in zero-sum multi-playe r extensive- form games. In Proceedings of the 32nd Conference on Neural Infor- mation Processing Systems (NeurIPS) , pages 9661–9671,

    work page doi:10.1145/3406325.3451125

  18. [18]

    [FGHS22] John Fearnley, Paul Goldberg, Alexandros Hollend er, and Rahul Savani

    URL: https://proceedings.neurips.cc/paper/2018/hash/c17028c9b6e0c5deaad29665d582284a-Abstract.html. [FGHS22] John Fearnley, Paul Goldberg, Alexandros Hollend er, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. Journal of the ACM , 70(1):7:1–7:74,

    work page 2018

  19. [19]

    [FGHS24] John Fearnley, Paul W

    doi:10.1145/3568163. [FGHS24] John Fearnley, Paul W. Goldberg, Alexandros Holle nder, and Rahul Savani. The complexity of computing KKT solutions of quadratic programs. In Proceedings of the 56th ACM Sympo- sium on Theory of Computing (STOC) , pages 892–903,

    work page doi:10.1145/3568163

  20. [20]

    [GPAM+20] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing X u, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio

    doi:10.1145/3618260.3649647. [GPAM+20] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing X u, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adve rsarial networks. Communi- cations of the ACM , 63(11):139–144,

    work page doi:10.1145/3618260.3649647

  21. [21]

    [HBP23] Aamal Abbas Hussain, Francesco Belardinelli, and G eorgios Piliouras

    doi:10.1145/3422622. [HBP23] Aamal Abbas Hussain, Francesco Belardinelli, and G eorgios Piliouras. Asymptotic con- vergence and performance of multi-agent Q-learning dynami cs. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagen t Systems (AAMAS) , pages 1578–1586,

    work page doi:10.1145/3422622

  22. [22]

    [Jan68] Elena Janovskaja

    doi:10.1007/978-3-540-92185-1_74 . [Jan68] Elena Janovskaja. Equilibrium points in polymatri x games. Lithuanian Mathematical Journal, 8(2):381–384,

    work page doi:10.1007/978-3-540-92185-1_74

  23. [23]

    [JCD+19] Max Jaderberg, Wojciech M

    doi:10.15388/lmj.1968.20224. [JCD+19] Max Jaderberg, Wojciech M. Czarnecki, Iain Dunning, Luk e Marris, Guy Lever, Anto- nio Garcia Castaneda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, A vraham Ru- derman, et al. Human-level performance in 3D multiplayer ga mes with population-based reinforcement learning. Science, 364(6443):859–865,

    work page doi:10.15388/lmj.1968.20224 1968

  24. [24]

    [JKKZ21] Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang

    doi:10.1126/science.aau6249. [JKKZ21] Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. SNARGs for bounded depth computations and PPAD hardness from sub-expo nential L WE. In Proceed- ings of the 53rd ACM Symposium on Theory of Computing (STOC) , pages 708–721,

    work page doi:10.1126/science.aau6249

  25. [25]

    [KAP+23] Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Pana geas, Emmanouil-Vasileios Vlatakis- Gkaragkounis, Vaggos Chatziafratis, and Stelios Stavroul akis

    doi:10.1145/3406325.3451055. [KAP+23] Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Pana geas, Emmanouil-Vasileios Vlatakis- Gkaragkounis, Vaggos Chatziafratis, and Stelios Stavroul akis. Efficiently comput- ing Nash equilibria in adversarial team Markov games. In Proceedings of the 11th International Conference on Learning Representations (IC LR),

    work page doi:10.1145/3406325.3451055

  26. [26]

    [LTZJ21] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadba baie

    URL: https://proceedings.neurips.cc/paper/2021/hash/dd1970fb03877a235d530476eb727dab-Abstract.html. [LTZJ21] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadba baie. Complexity lower bounds for nonconvex-strongly-concave min-max optimization. In Proceedings of the 35th Con- ference on Neural Information Processing Systems (NeurIPS) , pages 1792–1804,

    work page 2021

  27. [27]

    [NBP20] Sai Ganesh Nagarajan, David Balduzzi, and Georgios Piliouras

    doi:10.2307/1969529. [NBP20] Sai Ganesh Nagarajan, David Balduzzi, and Georgios Piliouras. From chaos to or- der: Symmetry and conservation laws in game dynamics. In Proceedings of the 37th International Conference on Machine Learning (ICML) , pages 7186–7196,

    work page doi:10.2307/1969529

  28. [28]

    [SY91] Alejandro A

    doi:10.1137/15M1039274. [SY91] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing , 20(1):56–87,

    work page doi:10.1137/15m1039274

  29. [29]

    Sch \" a ffer and Mihalis Yannakakis

    doi:10.1137/0220004. [VBC+19] Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinfo rcement learning. Nature, 575(7782):350–354,

    work page doi:10.1137/0220004

  30. [30]

    Liar” ends the game, then both players reveal their dice. If the last bid is not satisfied, then the player who called “Liar

    doi:10.1038/s41586-019-1724-z . [vNM47] John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior . Princeton University Press,

    work page doi:10.1038/s41586-019-1724-z

  31. [31]

    [ZAČ21] Youzhi Zhang, Bo An, and Jakub Čern` y

    doi:10.1006/game.1997.0527. [ZAČ21] Youzhi Zhang, Bo An, and Jakub Čern` y. Computing ex a nte coordinated team- maxmin equilibria in zero-sum multiplayer extensive-form games. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI) , pages 5813–5821,

    work page doi:10.1006/game.1997.0527 1997

  32. [32]

    [ZCC+22] Brian Zhang, Luca Carminati, Federico Cacciamani, Gabr iele Farina, Pierric- cardo Olivieri, Nicola Gatti, and Tuomas Sandholm

    doi:10.1609/aaai.v35i6.16728. [ZCC+22] Brian Zhang, Luca Carminati, Federico Cacciamani, Gabr iele Farina, Pierric- cardo Olivieri, Nicola Gatti, and Tuomas Sandholm. Subgame solving in ad- versarial team games. In Proceedings of the 36th Conference on Neural In- formation Processing Systems (NeurIPS) , pages 26686–26697,

    work page doi:10.1609/aaai.v35i6.16728

  33. [33]

    doi:10.1609/aaai.v36i5.20461. 16

    work page doi:10.1609/aaai.v36i5.20461