The Complexity of Two-Team Polymatrix Games with Independent Adversaries
Authors: Alexandros Hollender
Gilbert Maystre
Sai Ganesh Nagarajan
Venue: ICLR 2025 Oral (2025)
Keywords: algorithmic game theory
Nash equilibrium
minmax optimization
Primary area: optimization

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 for the setting where one of the teams consists of multiple independent adversaries. 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.

Published as a conference paper at ICLR 2025
THE COMPLEXITY OF TWO-TEAM POLYMATRIX GAMES WITH INDEPENDENT ADVERSARIES
Alexandros Hollender
Gilbert Maystre EPFL
University of Oxford
alexandros. hol lender@cs ac.uk
gi w.lbert.masttreeeee
Sai Ganesh Nagarajan
Zuse Institute Berlin
nagarajan0 de
ABSTRACT
Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games 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 for the setting where one of the teams consists of multiple independent adversaries. 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.
INTRODUCTION
Game theory is a fundamental tool to encode strategic agent interactions and has found many applications in the modern AI landscape such as Generative Adversarial Networks (Goodfellow jet al., 22200), obtaining agents with expert level play in multiplayer games such as Starcraft and Quake III (Vinyals et al. Jaderberrrrrrr al. 2019) and superhuman performance in poker (Brown & Sandholm] 2018 2019). Computing a Nash equilibrium or a saddle point (when considering general minmax optimization problems) computational task of central importance in these applications. The celebrated minmax theorem of voo Neumann & Morgenstern (1947) established that two-player zero-sum games have efficient algorithms. However, was shown that three- player zero-sum games (Daskalakis et al. 2009) two-player general games (Chen et al. 2009) are computationally intractable (formally PPAD-hard) and the hardness also known to hold for computing approximations.
Consequently, Daskalakis Papadimitriou (0099 proposed a tractable class of multiplayer zero-sum games, where the players are placed the nodes of a graph and play matrix zero-sum game with each adjacent player. In this setting, the total utility that a player gets is the sum of the utilities from each game that they participate in. It is to be highlighted that removing the zero-sum game assumption between each player makes the problem hard. Indeed, computing Nash equilibria in general polymatrix games is known to be PPAD-hard (Daskalakis al. 2009 Chen et al. 2009 Rubinstein 2018 Deligkas et al. 2024). Cai & Daskalakis (2011) studied an intermediate setting where every edge of the polymatrix game can be either a zero-sum game or a coordination game. They showed PPAD-hardness, even for the special case where the players can be grouped into three
Authors contributed equally to this work.

---

Published as a conference paper at ICLR 2025
teams, such that players within the same team play coordination games, and players in different teams play zero-sum games.
Adversarial Two-team Games With a Single Adversary: The general notion of adversarial team games introduced by von Stengel & Koller (197) studies two teams that are playing zero-sum game with each other, meaning each team member gets the same payoff as the whole team and the sum of the team payoff' is zero. The primary motivation here is study strategies for companies against adversaries. What makes the "team" aspect special is that the team members cannot coordinate their actions and must play independent mixed strategies. This captures imperfect coordination within companies. Indeed, if the teams instead had perfect coordination, then the setting would simply reduce two player zero-sum game. Von Stengel and Koller showed that there exists a team maxmin equilibrium, that can be extended to a Nash equilibrium for this setting when the team is playing against single adversary. Moreover, they showed that this is the best Nash equilibrium for the team, thereby alleviating equilibrium selection issues. However, it was later shown that finding a team maxmin equilibrium in fact FNP-hard and the problem does not become easier if one allows approximate solutions (Hansen et al.) 2008: Borgs et al., 2008). Recently, |Anagnostides et al.) (2023) studied the single adversary setting, and were able to show that finding a Nash equilibrium in this setting is in fact CLS-complete. The CLS- CLS-hardness immediately follows from the work of Babichenko & Rubinstein (202T), } but importantly it requires a sufficiently general game structure and so does not apply to the polymatrix setting. The CLS- CLS-memberhhip on the other hand applies to any adversarial game with single adversary. The main idea is to obtain a Nash equilibrium from an approximate stationary point of the max Moreau envelope of the function x + maxyey U(r,)) y) (where x is the min variable, y is the max variable and U is the payoff function).
Connections to Complexity of Minmax Optimization: Two-team games are special case of general nonconvex-nonconcave constrained minmax problems. Daskalakis et al. (202T) recently studied this general setting and showed that finding a stationary point is PPAD PPAD-comple complete. Crucially, their PPAD-hardness only applies when the constraint sets are coupled between the min and the max player. However, games usually induce minmax problems with uncoupled constraints. The complexity of the problem for uncoupled constraints remains open, although it is known to be CLS-hard, since it is at least as hard as finding stationary points of standard non-convex minimization problems (Fearnley et al.) 2022). As we discuss below, our results also have implications for uncoupled minmax optimization, where we obtain a CLS- result for a particularly simple family of objective functions. We note that Li et al. (2021) showed a query lower bound of 2 d2 for smooth nonconvex- monconvex-strongly-ooe strongly-concan minmax optımızation problems, but these results do not apply to the simple objective functions that we study (and which can only be studied from the perspective of computational complexity).
Connections to Multiagent Learning: From learning dynamics perspective, qualitative results focus on understanding the limit behavior of certain no-regret learning dynamics in polymatrix games. In particular, some works focus on obtaining asymptotic convergence guarantees for Q-learning and its variants (Leonardos et al. 2021 Hussain et al. 2023). In similar vein, some other works studied the limit behaviors of replicator dynamics for polymatrix games, particularly with zero-sum and coordination edges (Nagarajan et al. 2018 8 2020). In these works, the focus was on trying to identify network topologies under which the learning dynamics exhibited simple (non-chaotic) behaviors. Surprisingly. there were works that could obtain non-asymptotic convergence guarantees using discrete time algorithms in multiagent reinforcement learning as well, with Leonardos et al. (2022) establishing convergence to Nash policies in Markov potential games. In adversarial settings, Daskalakis et al. (2020) studied independent policy gradient and proved convergence to Nash policies. Moreover, some recent works establish convergence to Nash policies in Markov zero-sum team games (Kalogiannis et al. 2023) and Markov polymatrix zero-sum games (Kalogiannis & Panageas] 2023). This further establishes the need to theoretically study the computational challenges in the simplest polymatrix settings which allow for both zero-sum and coordination edges, in order to understand convergence guarantees in more complicated multiagent reinforcement learning scenarios.
This leads us to the following main question that had been open from the work of Cai & Daskalakis 1
What is the complexity of finding Nash equilibria in two-team zero-sum polymatrix games?
2

---

Published as a conference paper at ICLR 2025
1.1 OUR CONTRIBUTIONS
Our main contribution is the following computational hardness result.
Theorem 1.1 (Informal), It is CLS hard to find an approximate Nash equilibrium of a rwo-team zero-sum polymatrix game, even when one of the teams does not have any internal edges.
Our result is incomparable to the CLS-hardness result proved by AAnagnsstides et al. (2023) (which essentially immediately follows from the work of [Babichenko & Rubinstein (2021) On the one hand, our result stronger because it applies to games with a simpler structure, namely polymatrix games, whereas their result only applies to the more general class of degree-5 polytensor games. On the other hand, our (hardness) result is weaker because it requires the presence of multiple adversaries, instead of just single adversary. The case of two-team polymatrix games with single adversary remains open. If one could prove CLS S--hardnees for that version of the problem, then this would constitute a strengthening of both our result and the result of Anagnostides et al. Proving Theorem I.I requires a novel construction that takes advantage of the max-variables to introduce additional constraints the variabeia This step is crucial to obtain the required bilinear form for the objective and constitutes our main technical contribution.
As our second contribution, we complement the hardness result in Theorem 1.1 by showing that the problem is in fact CLS-complete in this particular case where the adversaries are independent (i.e., when there are no internal edges in the second team). Namely, the problem of finding an approximate Nash equilibrium in two-team zero-sum polymatrix game with multiple independent adversaries lies in the class CLS. The polymatrix setting allows us to provide a simple proof of this fact, in particular avoiding the use of more advanced machinery, such as the Moreau envelope used in the ELS-mmmmershhp of Anagnostides et al. (2023). We note that if the adversaries are not independent, then the problem is only known to lie in PPAD, and it remains an important open problem to determine whether it also lies in CLS or is in fact PPAD-complete.
Going back to our main result, Theorem 1.1 for minmax optimization in general. Namely, we obtain that computing a stationary point, i.e., a Karush- Kuhn-Tucker Tucker (KKT) point of
we note that it also has some interesting consequences
min max f(x 8)
is CLS-hard, and thus intractable in the worst case, even when / is bilinear polynomia that is concave in y. This is somewhat surprising, as these objective functions are the simplest case beyond the well-known tractable setting of convex-concave.
The meaning of CLS-hardness. The complexity class CLS was introduced by Daskalakis & Papadimitriou (2011) to capture the complexity of problems that are guaranteed to have a solution both by fixed point argument and local search argument. This class is subset of two well- known classes: PPAD and PLS. While PPAD is mainly known for capturing the complexity of computing Nash equilibria in general games (Daskalakis al.) 2009 Chen et al.) 2009). PLS captures the complexity of various hard local search problems, such as finding locally maximal cut in graph (Schätter & Yannakakis 199T>. Recently, following the result by Fearnley et al. (2022) that CLS PPAD n PLS, it has been shown that the class captures the complexity of computing mixed Nash equilibria in congestion games (Babichenko & Rubinstein (002)), and KKT points of quadratic
polynomials (Fearnley et al. 2024). See Figure for an illustration of the relationship between the classes.
A CLS-hardness result indicates that the problem is very unlikely to admit polynomial-time algorithm. To be more precise, our results indicate that we should not expect an algorithm to exist which can find an a-approximate Nash equilibrium in these two-team polymatrix games in time polynomial in log(1/e). In contrast, if the team had perfect coordination? then our setting reduces to istar-network zero-sum game which was shown to have a polynomial time algorithm to compute Nash equilibrium| Daskalakis & Papadimitriou 2009).
Previous CLS- SLS-handssss results required more general objective functions, namely f had to a quadratic (non-bilincar) polynomial (Fearley et al. 2024).
With perfect coordination, one can that the team effectively acts as single player.
3

---

Published as a conference paper at ICLR 2025
TFNP
PLS
PPAD
CLS
P
Figure 1: Classes of total search problems. Arrows used denote containment. For example, CLS is contained in PLS and in PPAD. The class TFNP contains all total search problems, i.e., problems which are guaranteed have efficiently checkable solutions. P contains all such problems solvable in polynomial time.
Furthermore, our hardness result for the minmax problem with bilinear polynomial objective functions establishes the fact that we should not expect an algorithm that finds an 6-KKT point in time polynomial in (og(1/e) (1)) The evidence that CLS is hard class is supported by various eryptographic
lower bounds, which apply to both PPAD and CLS (Bitansky et al. 2015) Choudhuri et al. 2019 Jawale et al. 2021).
1.2 OTHER RELATED WORK
is worth mentioning that the computation team maxmin equilibria for the two-team adversarial game has been studied where the team members are allowed to coordinate ex ante, which different from what polymatrix coordination game would induce, as we study in this paper. There it was shown that the game can reduced to a two-player game with imperfect-recal (Farina al. 2018 Celli & Gatti 2018 ZZhang et al., 2022) and that efficient algorithms exist under some assumptions about players' information sets (Zhang et al. 202T). Finally, similar notions have been studied for extensive-form games too (Zhang & Sandhoim 2022). Please see Appendix B for additional context with respect to minmax optimization and polymatrix games.
PRELIMINARIES
2.1 POLYMATRIX GAMES
polymatrix game (Janovskaja] 1968) is a type of multiplayer game in which the payoff function can be succinetly represented. More precisely, there is of players N and set of pure strategies S; for each player E W. Moreover, players are represented by the vertices an undirected graph G (N, E)) with the intent that a matrix game is played between each pair of players (i, j} E E; the pair of payoff matrices being denoted by A E RSx55; and A E 12 xS. Players are allowed randomize over their pure strategies and play a mixed strategy the probability simplex of their action, which we denote by A(S;) for player i. Hence, mixed strategy profile is some XIENA(S,)) We also use the standard notation æ . to represent the mixed strategies of all players other than i. In polymatrix games, the utility U, X - R for player E N the sum her payoffs, so that
(I), Z2, .... xiv) E
Ux(x) Σ Z.A'IZ
H(UEE
where F; is understood to be x;-- we drop the transpose when it is clear from the context for case of presentation. As a well-defined class of games, polymatrix games always admit Nash equilibrium (Nash 1951). In this work, we are interested in approximate Nash equilibria which we define next. Definition 1. Let 2 0 be approximation guarantee. The mixed strategy profile is approximate Nash equilibrium of the polymatrix game defined above for any i E NN,
U,(r,, 7-)) & Ue(T., x-1) Vx, E (SS))
4

---

Published as a conference paper at ICLR 2025
In this paper, we focus polymatrix games with particular structure where players are grouped into two competing teams with players within teams sharing mutual interests.
Definition 2 (Two-team Polymatrix Zero-Sum Game). A two-team polymatrix zero-sum game is polymatrix game {At) Ji.jEN where the players can be split into two teams X KUY N so that any game between the leams is zero-sum and any game within team a coordination game. More precisely for any i, &' E X and j. EY;
A A (A' A = (A A A
If there is no coordination within team Y, that is AsS' = -8; for every j.J' E EY, we further say that it is two-team zero-sum game with independent adversaries.
In the restricted context of two-teams games, another useful equilibrium concept is that of team- maxmin equilibria (von Stengel Koller 1997). While originally defined for single adversary only, it is generalizable to multiple independent adversaries in such way that any meam- equilibria can be converted to Nash-equilibrium one efficiently. Unfortunately, similarly to the Songle-adversan case, such equilibriums suffer from intractability issues and are FNP-hard to compute
(Basilico et al. 2017 Hansen et al. 2008 Borgs et al. 2008
2.2
KKT POINTS OF CONSTRAINED OPTIMIZATION PROBLEMS
We now turn attention to solution concepts for optimization problems and in particular of Garush-Kuhn-Tuckee (KKT) points. We only define the required notions for the special case where each variable is constrained to be in [0, 1J, since this will be sufficient for us. Under those box constraints the expression of the Lagrangian simplifies greatly and we obtain the following definition of approximate KKT point for a minimization problem.
Definition 3. Let E 2 O be approximation parameter, f :R + continuously differentiable function and consider the optimization problem minzee00.11 f(x). The point 3 E [0, 1)"h is an e e-approximate KKT point of the formulation if the gradient g fā) satisfies for each [n]:
1. If E (0, 1). then 19s1 S
2. If = 0, then 9: 2 -E
3. if = 1, then gi S c.
Thus, an exact (s = 0) KKT point can be thought of as a fixed point of the gradient descent algorithm. Using this intuition, we can extend this to minmax problems fixed points of the gradient descent-ascent algorithm. See Figure 2 for the geometric intuition of minmax KKT points.
Definition 4. Let 0 be approximation parameter, f R² R + R continuously differentiable function and consider the optimization problem min fo, max f(x, y). Let (z. 7) E [0, 1]2d and let (g. q) = v fā. V) where g is the gradient with respect to a-variables and with respect to y-variables. Then, (ī, D) is an e-approximate KKT point for each [n]]
1. If:; (0, 1), then 19:l S
4. If E (0, 1), then |gsl
2. x; 0, then gi 2 -E.
5. If y/ then qi
3. If r, 1, then 9: S E.
If y/ 1, then qi -c
2.3 CONNECTION BETWEEN TWO-TEAM GAMES AND MINMAX OPTIMIZATION
Given two-team polymatrix zero-sum game with matrices Aasees we can define the following common utility function
V(x,))
Σ
IT
Σ ,,
TEX,EEY
and the corresponding game where players on the X-team all have the same utility function -U, and players the -tem all have the same utility function U. It is easy to check that this new game is
5

---

Published as a conference paper at ICLR 2025
y
(322, y2)
(21
x
(0,0)
Figure 2: The intuition behind exact (8 = 0) KKT points for minmax problems. The formulation features muinvariable æ, max-variable y and the bounding box constraint (z, y) [o, 1Ja. Some feasible points together with their respective gradient (4" gg)) are depicted. Green points are valid KKT points whereas red ones are not. For instance. (I1, Y11 not KKT point because of but < 1. On the other hand, (z2, 3/2 is valid KKT point because o = 0 and q < 0 with x = 1.
equivalent to the previous one, namely strategy profile (xx, y) an e-Nash equilibrium in the latter game if and only if it is in the former. Now, if we consider the minmax optimization problem
min max U (xx 3)
=EA yEy
is not hard show that its KKT points exactly correspond to the of Nash equilibria of the game with common utility, and thus also of the original polymatrix game. This connection also extends to approximate solutions. We develop this relation greater detail section [ecctinn where we first prove hardness result for minmax problem and then use the equivalence above to extend it to polymatrix games.
CLS-HARDNESS OF TWO-TEAM GAMES WITH INDEPENDENT ADVERSARIES
In this section, we give a proof of our main hardness result which we re-state formally next.
Theorem 3.1 (Precise formulation of Theorem 1.Tp. CLS-hard to find an E-approximate Nash equilibrium of a two-team zero-sum polymatrix game with independent adversaries where e is inverse exponential the description of the game.
We show that this true even when each player can only choose from two pure strategies. This lower bound result is obtained by reducing from the problem of finding some KKT point of quadratic minimization problem. In detail, an instance of MinQuadKKT consists of quadratic polynomial Q R + R together with an approximation parameter > 0. A solution to such instance is any e-approximate KKT point of minn Q(x) (see Definition 3). MinQuadKKT is known to be CLS-complete for inverse exponential in the description of the instance (Fearnley et al. 2024). The reduction from MinQuadKKT T to two-team games is performed in two stages which we describe next.
Stage
As first step, we show how reduce MinQuadKKT to the intermediate problem MinmaxIndKKT. An instance of MinmaxIndKKT consists of an approximation parameter > 0 together with a polynomial M 2 - IR satisfying the following three properties:
1. M is multilinear.
2. M has degree at most 2.
3. (xx.) v) has no monomial of type yeu, for i.j E [n]].
In this section, we conveniently refer to those three conditions as the independence property. A solution to such an instance is any e-approximate KKT point of min max M y) Definitinn 4). Let us highlight that this step already establishes the CLS-hardness of uncoupled minmax multilinear formulations for simple class of objectives.

---

Published as a conference paper at ICLR 2025
Stage II. We exploit the independence property of the polynomial generated by the first stage reduction to reduce it further to a two-team zero-sum polymatrix game with independent adversaries. This is achieved through generalizing the equivalence between zero-sum games for two players and some class minmax formulations.
3.1
STAGE I: FROM QUADRATIC TO MULTILINEAR
Lemma 3.1. MinQuadKKT reduces to MinmaxIndKKT
By "reduces to", mean the usual definition of polynomial-time TFNP reduction. We begin by describing the reduction in detail, then highlight that yields an objective with the independence property and finally prove correctness. Let Q 1 R and > 0 be the MinQuadKKT instance. Write the coefficients of Q explicitly as follows:
Q(x) 9 Σ
qi
Σ 4yzz
Σ EE(n]
quad
KE(n))
Let Z 2
1 be an upper bound on the sum of the absolute values of all coefficients Q and note that since Q is quadratic polynomial, it holds that for every [0, 1]" and E [n]:
(Q(z)
[Q(x) < Z and
S 2z
Or;
Fix 7 == 10Z and 17 2=2 /Z For each min-variable of the MinQuadKKT instance, we introduce two min-variables v; and x and max-variable y; in the MinmaxIndKKT instance, We also define the following multilinear "copy" gadget:
COPY(I,, 2/, v.) [2) I, (1-2n)= -1) (y: 1/2)
The role of COPY is force xy be close to x/ at any KKT point, thus effectively duplicating i; into 4t This allows us to remove square terms of the objective function. To make this formal, let Q' [0, R be a copy of Q where every occurrence of the form xf is replaced by 2,r4;
Q'(x,x')== = q Σ
Exp, PofTy + Σ Lie(n) qusaa
R:z; + sE(n]
The full formulation of the MinmaxIndKKT instance is stated below. We note that the objective M of the formulation indeed satisfies the independence property The proof of Lemma 3.1 now follows from Claim 3.1
min max ((,x'' where M( x' = Q' =,,11 vE[0.]"
Σ T Co AE/n]
Claim 3.1. For any (0,1/13), if (x, is an (6²1Z) -approoxiiii KKT point of the MinmaxIndKKT instance, then is an E-approximate KKT point of the MinQuadKKT instance.
The proof relies crucially on being a large constant so that the copy gadgets dominate Q'xx, x') and the objective M. This forces any KKT point (z,x', y) to have y (0, 1)" and ultimately Rs x'. second step shows that (Q(x)) (Q(x)/Or; /0x; zs (M, x', 22, uy/0x, which is enough to conclude that x is KKT point of the MinQuadKKT instance. Readers can find the full proof in Appendix A.
3.2 STAGE II: FROM MINMAX TO TWO-TRAM GAMES
To prove Theorem I.I we use stage I Lemma 3.1 and show how to reduce an instance of MinmaxIndKK two-team zero-sum game with independent adversaries. Let > be the approximation parameter of the instance and its objective be M I - R. Since M has the independence property, we can explicitly write its coefficient as:
M (I, v) a Σ iE[n)
8,
Σ
PijTT + Engios Soy + Σ (.JElm)) OCfIiy/
Additional dummy max-variables can he added to ensure that the number of min- and max-variables are the
7

---

Published as a conference paper at ICLR 2025
We construct a polymatrix game with two teams, each consisting of n players. In the first (cooperative) team, there is one player a; corresponding to each variable 24. The second team consists of n independent adversaries, where player b, corresponds to variable yı. The intent is that an optimal strategy profle of the players roughly corresponds to a KKT point (r, y) of M. As stated earlier, we reduce to very restricted setting where each player only has actions. We thus specify the utility matrices of the game as elements of g with:
-yts 0
0 0
A Aqria
for all i, [m] with + j (2)
[ois +
/
G
n Be/n B:/n
(//m) 0
A -AA
for all ú.j E [n]]
Any other utility matrix is set to 02x2 Observe that this payoff setting indeed yields a proper two-team zero-sum polymatrix game with independent adversaries. Let Z 2 be an upper bound on the sum of absolute coefficients of M and let ò == s² /44)) be the target approximation ratio for the polymatrix game. If (p,g q) is 6-approximate Nash equilibrium of the polymatrix game, we define a candidate KKT point (z, y) E 2 as follows:
0
pf < e/(2Z)
J
0
if q < <
32
pf > 1 - E/(22))
and
y:
if > 1 - 5/(22)
else
else
Here pN E [0, 1] represents the probability that player o, plays its first action, and similarly qi for player by. The correctness of the reduction is treated in [laim and thus Theorem 1.1 follows.
Claim 3.2. (z, y) an E-approximate KKT point of the MinmaxIndKKT instance.
Proof. We only show that a-variables satisfy the KKT conditions the proof is similar for the y-variables. follows from equation 2 and equation that for any Pt E (0, 1] the utility for player as can be written as:
T
(Pi)) Σ
P.
Aaiay
Pj
+
Σ jE(m)
P:
Aat.by
9 1 O
Ps
P-P5
[
Pi
=
Bi +
Σ j&z
Pipl +
Σ jEju
Ozj9l) - E jE(n)
Gas/n
Since (p.9) 5-approximate Nash equilibrium, we can use the above expression twice and Definition to get that:
(p: (p--pe) pi) (B+ Σ ESe Pols + Σ Eyenn) lu ) S8 e
E [0.1]
Fix some variable and let us verify that it satisfies the e-approximate KKT condition. The partial derivative of M with respect to 24
aM (M, = Bi +
Σ
Σ 0zyyi
Oz,
371
JE[m)
= Bi +
Thj (D. + F. - pT) + Σ Oig (4j Uo 9z)
jE(m]
B:
+
ThjPi +
Σ
Ozg9i +
Σ
hail - |ar, Pz +
Σ
10
lu5
jE[m)
je(m)
= 3
+
TijPi
+
Σ
Ozg4j
+
27 Z
341
JE[n]
Where in the last equality, used the fact that xr (respectively y) is close to p (respectively q).
8

---

Published as a conference paper at ICLR 2025
We now finish the proof by considering two cases for 24. First, consider the case where 2; < 1. By definition of 24, this implies that p; 1 1/22 Thus, setting i; == in equation we get:
(1 - p.) ( B + Σ jyii Nops + Σ jE(m)
2 -
6 2Z 8
B Σ
jji Popp Σ jEIn] 0.
2 -E/2
1-p: p:
and thus (M,, /) 2 -6/2- 1122-/22- 2 -. Next, consider the case where 2; > 0. By definition
of æi, this implies that pi 2 s/2Z. Now, setting p. = 0 in equation we get:
Pi
| + Σ
Yippj
Σ jE(N]
0 2
jti
8
2z 8
Bi + Σ jti
YopPi + Σ jElm) 0g0
S 68/2
pj
and thus (Mr y)/Oz; S S + E/2 f E. This shows that 2; always satisfies the e- KKK conditions. In partieular, when x; E (0, JM (z, /)x Se.
CLS-MEMBERSHIP FOR INDEPENDENT ADVERSARIES
In this section we prove the following. Theorem 4.1. The problem of computing a Nash equilibrium two-team zero-sum polymatrix games with independent adversaries lies in CLS.
In particular, this implies that the CLS-hardness result proved in the previous section tight for such games.
Reformulation as a minimization problem. The main idea to prove the theorem is start from the minmax formulation of the problem and to rewrite it as a minimization problem by using duality. Let two-team polymatrix zero-sum game with independent adversaries be given. Without loss of generality, we assume that every player has exactly m strategies. Recall that by the structure of the game we have A A)T,), A (A and AiJ = 0 for all i, E j.j.J' E Y with i f and j + jr. We can write
Σ L.E'E
Σ
min max sEX yEy
yi
EEX,JEY
min max- xE yEy
Σ i.eeiic
A Iz
Σ rEX,JEY
Aj Zi
(5)
min #EX
Σ
+ max DEY
Σ
A x4
IEX,EE
Now consider the "max" part of the above objective written the following I.P in y variables:
Σ CeJy
max
JEY
Ujk
Vj Y
k=1
Uyk 2 Vj Y and Ak E [m]
where C = Eiex A for all j Y. Then the dual of the above program can be written as:
min Σ 7/
JEY
Czk
Y and Vk E [m]
9

---

Published as a conference paper at ICLR 2025
Thus replacing the max part in equation
by the equivalent dual formulation obtain:
min
Σ
T,A
Σ
JEY
7 Σ
c A
Vj Y and vk e [m]
ix
(6)
75 M VjEY
7 E RM
E X
where e/ E 1. is the kth unit vector. We have introduced additional of constraints 7 S M to ensure that the feasible region is bounded. M is chosen to be sufficiently large such that M > ma Eiex Cg A' x,. Note that in order obtain the formulation equation 6 we have crucially used the fact that the original game is polymatrix and has independent adversaries.
For what comes next, we will need the following definition of KKT points, which generalizes Definiton to arbitrary linear constraints.
Definition 5. Consider an optimization problem of the form
min f(x)
s.t. Az < b
I IR"
where f :R" + R. is continuously differentiable, A B and E R" A point x" R is KKT point of this problem if there exists E IRm such that
1. V fx(x*) AA
2. Ax bb
3. p 122 0
4. p T -x) 0
We can now continue with our proof of Theorem 4.1
The problem of finding an exact KKT point of equation 6 lies in CLS. Indeed, is known that finding an approximate KKT point of such a program lies in CLS (Fearnley et al. 2022, Theorem 5.1), and, given that the objective function is a quadratic polynomial, an approximate KKT point (with sufficiently small approximation error) can be turned into an exact one in polynomial time (see, e.g., (Fearnley et al. 2024, Lemma A.1)).
Theorem 4. I now simply follows from the following claim, the proof of which Appendix A.2
Claim 4.1. Given a KKT point of equation 0 we can compute a Nash equilibrium of the original game in polynomial time.
OPEN PROBLEMS
What is the complexity of the two-team polymatrix setting when there is a single adversary? Recently, Anagnostides et al. (2025) show CLS-hardness, with two players in the team and one adversary (players have non-constant number of actions). But, hardness of the two action case is still open. Note that CLS- CLS-membership still applies these cases.
Our CLS-membership result only applies the setting where the adversaries are independent. If interactions between adversaries are allowed then the problem is only known to lie in PPAD, so there gap with the ELS-hardness that we show. Is the problem CLS-complete, PPAD-complete, or neither?
Our hardness result provides strong evidence that no algorithm with running time (poly(( log(1/e)) (1/=))) exists. However, there gradient-based based approaches that yield algorithms with running time O(poly(1/E)) (can be adapted from the algorithm of Anagnostides et al. (023)). What is the optimal polynomial dependence in 1 1/8 for such algorithms?
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
AH and GM were supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00026. SGN would like to thank Ioannis Panageas and colleagues at ZIB for discussions pertaining to this project.
REFERENCES
loannis Anagnostides, Fivos Kalogiannis, Toannis Panageas, Emmanouil- Vasiillis Vlatakis- Gkaragkounis, and Stephen McAleer. Algorithms and complexity for computing Nash equilibria in adversarial team games. In Proceedings of the 24th ACM Conference on Economics and Computation (EC). pp. 89, 2023. 00p/10.1145//50057..59777
Joannis Anagnostides, loannis Panageas, Tuomas Sandholm, and Jingming Yan. The complexity of symmetric equilibria in min-max optimization and team zero-sum games. arXiv preprint DrXiv:2502.085190 2025.
Krzysztof R. Apt, Bart de Keijzer, Mona Rahn, Guido Schäfer, and Sunil Simon. Coordination games graphs. International Journal of Game Theory, 46(3):851-877, 2017. doi 10.1007/550182-016 0560-8
Krzysztof R. Apt, Sunil Simon, and Dominik Wojtezak. Coordination games weighted directed graphs. Mathematics of Operations Research, 47(2):995-022,, 2022.
Yakov Babichenko and Aviad Rubinstein. Settling the complexity of Nash equilibrium congestion games. In Proceedings the 53rd ACM Symposium Theory of Computing (STOC), pp. 1426- 1437, 2021. doi /5/1111444/40254455155
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti, Team-maxmin equilibrium: Efficiency bounds and algorithms. In Proceedings of the 3/st AAAI Conference on Artificial Intelligence (AAAI), pp. 356-362, 2017. 10.10..100//aai.v33ii 10560
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. CoRR, abs/1912.06660 2019. URL htthhtt::/ http//axxiv../ http//axxx..../aaaaaa/aa/ 1912. 06680
Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS), pp. 1480-1498, 2015. doi 10.1 199///0s..00..5..09
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou. The myth of the folk theorem. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 365-372, 2008. db110..145//374466..74422
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):4188 2018. doi [00001126/sciennc..a011..
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019. doi 10. 100.1116/cceecceaayy22...
Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In Proceed- ings of the 22nd ACM-SIAM Symposium Discrete Algorithmss (SODA), pp. 217-234, 2011. doi 10.1 10.1113//1.78166 07111/99788111177082222
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum polyma- trix games: generalization of minmax. Mathematics of Operations Research, 41(():648-66 655,
2016. do. 28000o0/ 2015.0745
11

---

Published as a conference paper at ICLR 2025
Andrea Celli and Nicola Gatti. Computational results for extensive-form adversarial team games. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 965-972, 2018.
doi111. 1ww.0...//.aa........ v3211. 1462
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settlng the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):14:1-14:5) 2009. 145/100.14/1151612..111666
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. Finding Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51 ACM Symposium on Theory of Computing (STOC), pp. 1103-1114, 2019. doi 1111100115//31122633366663
Constantinos Daskalakis and Christos Papadimitriou. Continuous local search. In Proceed- ings of the 22nd ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 790-804, 2011
Constantinos Daskalakis and Christos H. Papadimitriou. On network generalization of the minmax theorem. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 423 423-434, 2009. doi 1001000000/77----10 1107//97-3-642-0229 6-2---090-------1-1
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complex- ity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-55, 2009. doi
Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich. Independent pol- icy gradient methods for competitive reinforcement learning. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurlPS), pp. 5527- 5540, 2020. URL https:: /ttpp:://proceedding neurips weeeurips.ccppapee/22222. cccpppper/222//aaaee
Abst .tml
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), pp. 1466-1478, 1478, 2021. 10.11.111..1111111 00011444/34033553451123
Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos, Pure- circuit: Tight inapproximability for PPAD. Journal of the ACM, 2024. doi 10. [O. 1445366666
Aykut Erdem and Marcello Pelillo. Graph transduction as a non-cooperative game. In Xiaoyi Jiang, Miquel Ferrer, and Andrea Torsello (eds.), Graph-Based Based Representations in Pattern Recognition, pp. 195-204. Springer Berlin Heidelberg, 2011. 1. ISBN 978-3-642-2084477,
Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Ex ante dination and collusion in zero-sum multi-player extensive-form games. In Proceed- ings of the 32nd Conference on Neural Information Processing Systems (NeurIPS), pp. 9661-9671, 2018. URL httpppss/ppooceeelngg...eee http://ccw.....oooooooooo//////a
html
John Fearnley, Paul Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS PPAD PLS. Journal of the ACM, 70(1):7:1-7:74, 2022. doi 10. 145/3568 163
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of computing KKT solutions of quadratic programs. In Proceedings of the 56th ACM Symposium on Theory of Computing (STOC), pp. 892-903, 2024. doi 10. 1455/115/36111 002553618260.000 8260.3649677
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139-144 2020. 1..10...45/342222
Kristoffer Arsfell Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen. Approximability and parameterized complexity of minmax values. In Proceedings of the 4th International Workshop on Internet nad Network Economics (WINE), pp. 684-695, 2008.
10. 100110007777788335449921333 74
12

---

Published as a conference paper at ICLR 2025
Aamal Abbas Hussain, Francesco Belardinelli, and Georgios Piliouras. Asymptotic convergence and performance of multi- agent Q-learning dynamics. In Proceedings of the 22nd International Conference Autonomous Agents and Multiagent Systems (AAMAS), pp. 1578-1586, 2023.
Max Jaderberg. Wojeiech M. Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, al. Human- level performance in 3D multiplayer games with population based reinforcement learning. Science, 364(64433:859-865, 2019. doi 10. 126/science
Elena Janovskaja. Equilibrium points in polymatrix games. Lithuanian Mathematical Journal, 8(2): 381-384, 1968. 133888/// 1968.2021
Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. Proceedings of the 53rd ACM Symposium Theory of Computing (STOC), pp. 708-721, 2021.
Fivos Kalogiannis and loannis Panageas. Zero-sum polymatrix Markov games: Equi- librium collapse and efficient computation of Nash equilibria. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), pp.
2023. URL https::/pproeeedinggg newrips...ennrireeooeee.e wwwpppapeeelllleepappppeppepppee Absto44ttbtttttttCnoaaao
htm
Fivos Kalogiannis, Ioannis Anagnostides. Ioannis Panageas. Emmanouil- Vasileios Vlatakis- Gkaragkounis, Vaggos Chatziafratis, and Stelios Stavroulakis. Efficiently computing Nash equi- libria adversarial team Markov games. Proceedings of the 11th International Conference on Learning Representations (ICIR), 2023. UtI.https:/ http:::////////err//eee ew net. forum?id m 2m6btqgV
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, al. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In International Conference on Artificial Intelligence and Statistics, pp. 1441-1449. PMLR, 2021.
Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. Exploration-exploittiio in multi-agent competition: convergence with bounded rationality. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS), pp. 26318- 26331, 2021. URL ddl
neurips ccc/paper//22//hahh
html
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in Markov potential games. In Proceedings of the 10th International Conference on Leurning Representations (ICLR), 2022. URL http:::://ppereeeee ew net/ Eorum? wwamiiiddggwwwtn Amm4
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex-strongly-oneee min-max optimization. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurlPS), pp. 1792-1804, 2021. URL htttpps://proceeediii neer wttppss.ccppppp..ppceeeeep fol.ffiessffe wtt.ffee//appe//22111111 ote5://2553.00022222/////0eeeee0
Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive-fome games. arXiv preprint arXiv:2206.09495, 2022.
Sai Ganesh Nagarajan, Sameh Mohamed, and Georgios Piliouras. Three body problems evolu- tionary game dynamics: Convergence, periodicity and limit cycles. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 685-693, 2018.
Sai Ganesh Nagarajan, David Balduzzi. and Georgios Piliouras. From chaos to order: Symmetry and conservation laws in game dynamics. In Proceedings of the 37th International Conference mlr
on Machine Learning (ICML), pp. 7186-7196, 2020. URL htttss::/ t html
13

---

Published as a conference paper at ICLR 2025
John Nash. Non-cooperative games. doi110.330/11999229
The Annals of Mathematics, 54(2):266 295, 1951.
Aviad Rubinstein. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3):
917-959, 2018. 1o.
Alejandro Schäffer and Mihalis Yannakakis. Simple local search problems that are hard solve. SIAM Journal on Computing, 20(1):56-87, 1991. doi [0.1137/0220004
Samuel Sokota, Ryan D'Orazio. J Zico Kolter, Nicolas Loizou, Mare Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games, arXiv preprint arXiv:2206.0582) 2022.
Oriol Vinyals. Igor Babuschkin, Wojciech M. Czamneci, 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 reinforcement learning. Nature, 575(7782)3350-3355 2019.
doi 100010008//1115666111177774
John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1947.
Bernhard von Stengel and Daphne Koller. Team-maxmin equilibria. Games and Economic Behavior, 21(1-2):309-32 -211, 1997. doi 10.1006/gamm. 1997.0527
Chen-Yo Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. arXiv preprint arXiv:2006.09511 09517, 2020.
Brian Zhang, Luca Carminati, Federico Cacciamani, Gabricle Farina, Pierriccardo Olivieri, Nicola Gatti, and Tuomas Sandholm. Subgame solving in adversarial team games. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), pp. 26686-26697 2022. URL https: httt:::///ccceeeeeeeeeeooe neur wwtppper.pppeeeeceeeee.eeeee...e wwwesfffleeeapppeee fitps//appppep//2/// hash/ httt:/esffccceffffeeeee222212222 ott.apacceeeaaaaaaaaaaaaaaaaaaar Cesttraact-ooofeencee....t. ore.aaaeee........a..o..ooooooo.
Brian Hu Zhang and Tuomas Sandholm. Team correlated equilibria in zero-sum extensive-form games via tree decompositions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. $252-5259 2022. doi 10. http:/aaa..3635.222422
Youzhi Zhang, Bo An, and Jakub Cerný. Computing ex ante coordinated mam-maxmin equilibria in zero-sum multiplayer extensive-form games. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5813-5821, 2021. doi [0. 100.1609/ama..33555 16728
A MISSING PROOFS
A.1 PROOF OF CLAIM 3.1
Proof. Let 8 = s²/Z be the MinmaxIndKKT approximation guarantee for the remainder of this argument. As a first step, show that E (0, 1) for each i E [n]. Towards contradiction, let us first suppose that = O and observe that:
(M x'
aQ'(x, x')
+ (1-2n) 2n) (1/2 v:)
Ox;
Ox:
aQ' (x,x') x²)
+ T.T. (2/5)
as y/ = 0 and 1) S 1/10
dx:
27 + T (2/5)
using equation as T = 10Z and Z 2
But as (x, x', .''.)) y) is 6-approximate KKT point and x; is min-variable, it must that x; = (see
Definition 4). A similar computation shows that if y, 0, then x²} 1 and so:
a (x, x', v. 1/ -1 2n) + + 17 5
Dy
14

---

Published as a conference paper at ICLR 2025
Because Ue is max- mariabriable and (z, zz, y) a 6-KTT point, it must be that y, 1: contradiction to the assumption that y/ O. One can rule out the possibility of y, = in a similar way and we may thus conclude that yi (0, 1). This fact, together with the KKT conditions, further implies that the partial derivative of M with respect to vanishes for each E [x]] and thus:
@M (ar, x' .v)
|2| 22- (1 2n) ?!
Ky:
This shows that z! E [n KKT conditions imply:
6,
and combining with it follows that x E (0, 1) and the
(M,
8Q' (-r x') + T. (y:
T (1/2 v) (Q'
82
1/2)
+
Or,
Ox²
Where we use the notation a = b + å to mean [b - 6, + 6). We can now show that the partial derivative of M at (x, x', y) is very close the one of Q for all coordinates 2;;
0M x', (Q'(x, 2')
+ 21)) T (1/2 ys)
2n)
Ox;
da;
aQ' (Q' + - 2n))
(00'(z, (x,,x
+
Ox
dr,
(Q'(x,
(Q((xx)))
(x' x²)
2n
+
dr,
Oud
(Q'(x,2)) x²)
0Q'(xx1''
(An) + 5)
Oz:
dr,
aQ' (x)
0Q'(xxx')
9s²
as =/ / and < 2
Ou:
0x!
Observe that equation 7 also implies that x; and a& must be close with |a, - x1| S 8 + 17, hence:
(2'(xxx'))
(Q'(x,xx)
9s + Σ Ri + qu + qazt
dx:
dr!
171
8Q(x)
+ qu(2z² -x,)
Oz;
aQ(x) + 3
qui S Z and 36 362/Z
dz.
Combining the two previous observations, we have aQ(x)/Ox; = (M x', y)/Ox; + 12 With this fact established, may finally show that is indeed an k-KKT point of the MinQuadKKT formulation. If x4 = 0, then note that:
aQ(x) @M(x,'' x'.4) Ōx;
12 -- 12
-13e2 -
Ox;
A similar computation shows that the KKT conditions are also satisfied if r; 1. On the other hand, if a; E 1):
aQ(x)
BM (z.
x'.
+ 12e² S 8 12s² Se.
0x;
Ox,
A.2 PROOF OF CLAIM
Proof. Let (x", (")) be KKT point of equation
6
We define notation for the following multipliers:
For all j E and E [m], Uis
Ryo
corresponding to the constraint 7/ >
Σiex of Ald2,
For all i X, E R corresponding to the constraint ExE(m) Fik
For all i X and & [m). vie Rzo corresponding the constraint zit
15

---

Published as a conference paper at ICLR 2025
Note that have not included multipliers for the constraints Y, I M. This is because none of these constraints will ever be tight at KKT point (x*, y²) ) by construction M.
Now, since (=*,"") ) is KKT point, we compute such multipliers that satisfy the following KKT conditions (which are derived from Definition 5) in polynomial time
1. For all i E X
E
Σ A
+ 23
1m
17 =0
JEY
where Lm denotes vector of m ones, and where we used the fact that A -(A..) Additionally, we have that for all & E [m]] V/x 0 zia O.
2. For all j Y
1
Σ
Uis = O.
RE(m)
3. For all j E Y and E [m]. u9x
=
7j = Eiex exAi
Now, we claim that (x",,") property 2 we have Lke(m] Mijk = 1 and thus μú is indeed valid mixed strategy for player j Y. Next, property 3 can be rewritten
14) forms a Nash equilibrium of the original game, First all, note that by
Mijk 0
Σ TEX
max k Elm
eV A = max Uy(0" "("",,""; WE(mm
:p=z: ew)
which means that the strategy of player j. namely μº, is a best-response. Finally, property can be reinterpreted as saying that x7 a KKT point the following optimization problem (in variables a;))
min
Σ SEAL
Σ JEY
[= ==1((1
S.t. D3 E
Since this an LP, any KKT point is also a global solution. Thus, xz is global minimum of this LP, which means that player i is also playing best-response.
B ADDITIONAL RELATED WORK
Linear Convergence for CatiheaarCCnvex-Connaee Minmax Although we study this problem motivated by two-team polymatrix games with adversaries, the hardness results that we show also apply to the simplest non-convex concave minmax problem. i.c., bilinear non-convex concave. Our results strictly rule out the possibility of obtaining linear convergence. In contrast, bilinear zero-sum games and convex-concave games admit algorithms that converge linearly to the NE, for example
Wei et al. 2020): Lei et al. 2021 Sokota et al. (2022) Liu et al. (2022).
Why two-feam adversarial gaames/polymatrts games are interesting? The study of team games was initiated by von Stengel & Koller (197)). to model "imperfect" coordination within a company, when having to take strategic decisions the presence of adversaries. In the field of Al agents, one can imagine such interactions are natural in settings where AI agents are trained to play team games, such as Starcraft (Vinyals et al. 2019) and DoTA (Berner et al. 2019).
Meanwhile, polymatrix games are used to model pairwise interactions between players and these interactions can be specified as a graph. In some cases, polymatrix games offer tractable alternative models for multiplayer games, as NE in polymatrix zero-sum games efficiently computable (Daskalakis & Papadimitriou 2209) Cai et al. 2016). More generally, polymatrix games are used to model problems such coordination games graphs (Apt al. 2017, 2022) and this has applications semi-supervised learning methods such as graph transduction (Erdem & Pelillo 2011
Indeed, it is easy check that given (x", ,-") such multipliers then he found by solving an L.P.
16


Reviews:
[{"review_id": "P9JTVKBHnU", "reviewer": "Reviewer_m3Yt", "summary": "In this work, the authors investigate the computational complexity of computing a Nash equilibrium in two-team zero-sum polymatrix games where one team consists of independent players (i.e., players who do not interact with one another). Specifically, they prove that this problem is complete for the complexity class CLS. To demonstrate hardness, they first reduce from MinQuadraticKKT—the problem of computing a KKT point of a quadratic function with box constraints—to MinmaxIndKKT, a min-max problem with an independence property they define. In a second step, they reduce this problem to a two-team zero-sum polymatrix game. Membership in CLS follows fairly straightforwardly from the recent result that QuadraticKKT is complete for the class CLS, as shown in [1], and using LP duality for transforming a min-max problem into a minimization.", "questions": "- **Line 386**: In the reduction from MinmaxIndKKT, the authors define the candidate KKT point $(x_i, y_i)$ for the case where neither $x_i$ nor $y_i$ is in ${0, 1\\}$ as $x_i = a_i$ and $y_i = d_i$. I assume that $a_i$ is simply a typo, as $a_i$ is already used to denote player $i$ on the first team. I think the authors likely intended to use $p_i$ and $q_i$ for $x_i$ and $y_i$, which would also align with the statement in line 415 indicating that these variables are close to their respective counterparts, $p_i$ and $q_i$.\n\nReferences  \n[1] The complexity of computing KKT solutions of quadratic programs.\n\n[2] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written, though there are areas where phrasing could be improved. The problem under consideration is quite interesting and represents a step forward in establishing complexity results for two-team (zero-sum) games, i.e., min-max optimization problems beyond the case of having coupled constraints as in [2]. Of course, the more general case of having dependent adversaries (or that of a single adversary) remains open, as the authors highlight in Section 5.", "weaknesses": "I cannot identify any obvious weaknesses. Although the techniques and ideas are not particularly complex—as is often the case in results of this kind—this should not in itself be considered a weakness. However, the simplicity of the proof and the lack of novel ideas makes me more skeptical about my final score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "etIPeZlxbR", "reviewer": "Reviewer_xMtH", "summary": "The paper studies the problem of finding Nash Equilibria in two-team polymatrix games. Polymatrix games are a special class of n-player games with a succinct representation of the payoff functions. Each player's payoff is a sum of payoffs resulting from two-player games played with all the other players. This problem is known to be tractable when all interactions are zero-sum, and to be PPAD-hard in general. A special subclass of these games are team games, where each pair of interactions are either zero-sum (different teams) or coordination games (same team). Three team games are known to be PPAD complete. The main result of the paper is in showing that two team games are CLS hard (CLS is a structured subclass of PPAD).  This result holds even when one of the team consists of independent adversaries (their games consist of the zero matrix for all the payoffs). They also show that computing the minimax/ KKT point of a bilinear polynomial is also CLS hard.", "questions": "Could you add some discussion about the broader landscape of team games, why we might care about them (if not necessarily the two-player polymatrix team games), and about the best-known algorithmic results in this space, particularly in the context of learning dynamics?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper solves a well formulated problem about the complexity of finding Nash equilibria. This problem is a natural continuation of prior results about team polymatrix games. The technical proofs and reductions are interesting and well written.", "weaknesses": "The main weakness is in the lack of appeal to a broader ICLR audience. The paper has solid results in complexity theory and game theory but requires some connection to the machine learning audience. That such a connection exists is not in itself in question, there are a plethora of papers about learning equilibria in team games, but the paper offers no discussion about the broader significance of studying team games. The open problems section also mentions gradient based methods that converge to equilibria in time poly(1/epsilon), but there is not further discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XBJnsy2ciW", "reviewer": "Reviewer_XrcJ", "summary": "This paper studies the complexity of finding a Nash equilibrium in two-team polymatrix zero-sum games. They show that this problem is CLS-hard, and is in CLS if the adversaries are independent (thus establishing CLS-completeness in the latter case).", "questions": "Perhaps the most obvious gap in this paper is the CLS-membership without the independent adversaries assumption. Do you think there is any hope to extend your techniques to that case?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I think this is a good paper and vote to accept. The paper is clearly written and presents an interesting result. The hardness result about minimax KKT points is also rather clean, and may be of independent interest as a CLS-complete problem that may be relatively easy to make reductions from. The concerns below are very minor.", "weaknesses": "The section about ex-ante coordination contains some strange choices of phrasing. For example, all of the papers in that paragraph study extensive-form games (not just the last one), and the paper that shows \"efficient algorithms exist under some assumptions about the players’ information set\" is Zhang and Sandholm (2022), not Zhang et al. (2021).\n\nTo get parenthetical citations like (Lastname et al. 2023) instead of Lastname et al. (2023), use \\citep.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)