The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
Authors: Ioannis Anagnostides
Ioannis Panageas
Tuomas Sandholm
Jingming Yan
Venue: NeurIPS 2025 spotlight ()
Keywords: min-max optimization
adversarial team games
PPAD
CLS
Primary area: theory
TL;DR: We consider the computational complexity of computing stationary points in min-max optimization, with a particular focus on the special case of computing Nash equilibria in (two-)team zero-sum games.

Abstract: We consider the problem of computing stationary points in min-max optimization, with a focus on the special case of Nash equilibria in (two-)team zero-sum games. We first show that computing $\epsilon$-Nash equilibria in $3$-player $\text{\emph{adversarial}}$ team games---wherein a team of $2$ players competes against a $\text{\emph{single}}$ adversary---is $\textsf{CLS}$-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from $\text{\emph{symmetric}}$ $\epsilon$-Nash equilibria in $\text{\emph{symmetric}}$, identical-payoff, two-player games, by suitably leveraging the adversarial player so as to enforce symmetry---without disturbing the structure of the game. In particular, the class of instances we construct comprises solely polymatrix games, thereby also settling a question left open by Hollender, Maystre, and Nagarajan (2024). 

Moreover, we establish that computing $\text{\emph{symmetric}}$ (first-order) equilibria in $\text{\emph{symmetric}}$ min-max optimization is $\textsf{PPAD}$-complete, even for quadratic functions. Building on this reduction, we show that computing symmetric $\epsilon$-Nash equilibria in symmetric, $6$-player ($3$ vs. $3$) team zero-sum games is also $\textsf{PPAD}$-complete, even for $\epsilon = \text{poly}(1/n)$. As a corollary, this precludes the existence of symmetric dynamics---which includes many of the algorithms considered in the literature---converging to stationary points. Finally, we prove that computing a $\text{\emph{non-symmetric}}$ $\text{poly}(1/n)$-equilibrium in symmetric min-max optimization is $\textsf{FNP}$-hard.

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games*
Ioannis Anagnostides! Toannis Panageas Tuomas Sandholm and Jingming Yan?
Carnegie Mellon University
2 University of California, Irvine Strateg Robot, Inc. Strategic Machine, Inc. 'Opimizzed Markets, Inc.
{i (ianagnos, sandholmm@eeeeee cmu edu, (ipanagea, janigga,,jnnnnnn jingmy Hucii edu
Abstract
We consider the problem of computing stationary points min-max optimiza- tion, with focus the special case of Nash equilibria in (two-)tean zero-sum games. We first show that computing e-Nash equilibria 3-player adversarial team games- wherein team of 2 players competes against single adversary is CLS-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from symmetric e-Nash equilibria in symmetric, Adentical-payofi two-player games, by suitably leveraging the adversarial player so enforce symmetry tiithut disturbing the structure of the game. In particular, the class of instances we construct comprises solely polymatrix games, thereby also settling question left open by Hollender, Maystre, and Nagarajan (2024).
Moreover, we establish that computing symmetric (first-order) equílibria in sym- metric min-max optimization is PPAD-complete, even for quadratic functions. Building on this reduction, we show that computing symmetric c-Nash equilibria in symmetric, 6-player (3 vs. 3) team zero-sum games is also PPAD-complete, even for e poly(1/1g (1/n). As corollary, this precludes the existence of symmetric dynamics-wiir which includes many of the algorithms considered in the literature- converging to stationary points. Finally, we prove that computing non-symmetric -oquil//n- in symmetric min-max optimization is FNP-hard.
Introduction
We consider computing local equilibria in constrained min-max optimization problems of the form
min max f(x y), x yE
(I)
where X' C ddd and C Rdy are convex and compact constraint sets, and f X'xy + R is a smooth objective function. Tracing all the way back Von Neumann's 's celebrated minimax theorem [von Neumann, 1928] and the inception of game theory, such problems are attracting renewed interest in recent years propelled by a variety of modern machine learning applications, such as generative model- ing [Goodfellow et al., 2014], reinforcement learning [Daskalakis et al., 2020, Bai and Jin, 2020, Wei al., 2021], and adversarial robustness [Madry et al., 2018, Cohen et al., 2019, Bai et al., 2021. Car- lini et al., 2019]. Another prominent class of problems encompassed by (1) concerns computing Nash equilibria in (two-)tean) zero-sum games [Zhang et al., 2023, 2021, Basilico et al., 2017, von Stengel
'The authors ordered alphabetically.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

and Koller. 1997, Carminati et al., 2023, Orzech and Rinard, 2023, Farina et al., 2018, Zhang and An, 2020, Celli and Gatti, 2018, Schulman and Vazirani. 2017], which a primary focus of this paper.
to always persttiiriiiing to (1), when f is pair of strategies (ar", ,y*) such that both players (approximately) satisfy the associated first-order optimality conditions [Tsaknakis and Hong, 2021, Jordan et al., 2023, Ostrovskii et al., 2021, Nouiched et al., 2019], as formalized in the definition below.
Perhaps the most natural solution is
Definition 1.1. A point (x',y" E X Y is an e-first-order Nash equilibrium of (1) if
(x= - x², Væf(x' .y)) 2 - and y - y², Vyf(x" .y)) S v(z.y) E X V.
Definition 1.1 can be equivalently recast as a variational inequality (VI) problem: if 2 = (x. y) and F: z - F()) == (Vz y), - f y)). we are searching for point x" E = X x y such that (===2,,(2")) on approximate fixed points of gradient descent/ascent (GDA); namely, Definition 1.1 amounts to bounding the gradient mappings
22 for all 2 E Z. Yet another equivalent definition is instead based
~>xx""Ixxxx" [=' y')Ill S 11 -Ty V yy"))l é (Fixed points of GDA)
for some approximation parameter c' 0 that is (polynomially) dependent on >> O, where || is the (Euclidean) & norm and (T(.) is the projection operator. Other definitions that differentiate between the order of play between players- on the notion of Stackelberg equilibrium--aav also been considered in the literature [Jin et al., 2020].
The complexity of min- max optimization is well-understood in certain special cases, such when is convex-concave (e.g., Korpelevich [1976], Mertikopoulos et al. [2019], Cai et al. [2022], Choud- hury et al. [2023], Gorbunov et al. [2022]. and references therein). or more broadly, nonconvex- concave [Lin et al., 2020, Xu et al., 2023, Luo et al., 2020]. However, the complexity of general min-max optimization problems, when the objective function f is nonconvex-nonccoeaay has re- mained wide open despite intense efforts in recent years. Daskalakis et al. [2021] made progress by establishing certain hardness results targeting the more challenging setting in which there is joint (that is, coupled) set of constraints. In fact, it turns out that their lower bounds apply even for linear-nonconcave objective functions (ef. Bernasconi et al. [2024]), showing that their hardness result is driven by the presence of joint constraints-inee
under uncoupled constraints, many efficient algorithms attaining Definition 1.1 (for Iinear-nonconcave problems) have been documented in the literature. In the context of min-max optimization, the most well-studied setting posits that players have independent constraints; this is the primary focus of our paper.
1.1 Our results
We establish new complexity lower bounds in min-max optimization for computing equilibria in the sense of Definition 1.1; our main results are gathered in Table 1.
Table I:
The main results of this paper. NE stands for Nash equilibrium and FONE for first-order Nash equilibrium (Definition I.I), We also abbreviate symmetric to "sym." (sccond column).
Class problems
Eq. concept
Complexity
Even
Adversurial team games
.N
CLS comppllee (Theorem 1.3)
3-player (2 1), polymarrix
sym. e-FONE non-sym. e-PONE
PPAD-complate (Thoorem 1.7)
polymatrix, team O-sum, e 1/1."
Symmetric min-max
NP-lard (Theorem
quadratics, 1/n"
Adversarial team games We first examine an important special case of (I): adversarial team games [von Stengel and Koller, 1997]. Here, team of n players with identical interests is competing against single adversarial player. (In such settings, Definition 1.1 captures precisely the Nash equilibria of the game.) The computational complexity of this problem was placed by Anagnostides et al. [2023] in the complexity class CLS whhch stands for continuous local search [Daskalakis and Papadimitriou, 2011]. Further, by virtue of a result of Babichenko and Rubinstein [2021], computing Nash equilibria in adversarial team games when >>>>>> 1 is CLS-complete. In the context of this prior work, an important question left open by Anagnostides et al. [2023] concerns the case where n is a small constant, regime not captured by the hardness result of Babichenko and Rubinstein [2021]

---

pertaining to ceantical-inteeess games in such games, one can simply identify the strategy leading to the highest payoff, which is tractable when is small.
We show that even when n = 2, computing an e-Nash equilibrium in adversarial team games is CLS-complete. (The case where
amounts to two-player zero-sum games, known to be in P.) Theorem 1.2. Computing an e-Nash equilibrium in 3-player (that is, 2 vs. 1) adversarial team games CLS-complete.
Coupled with earlier results, Theorem 1.2 completely characterizes the complexity landscape for computing Nash equilibria in adversarial team games.
Our proof is based on recent hardness result of Ghosh and Hollender [2024] (cf. Tewolde al. [2025]), who proved that computing a symmetric e-Nash equilibrium in a symmetric two-player game with identical payoff's is CLS-complete. The key idea in reduction is that one leverage the adversarial player so as to enforce symmetry between the team players, without affecting the equilibria of the original game; the basic gadget underpinning this reduction is analyzed in Section 3.1.
Incidentally, our CLS-hardness reduction hinges on a polymatrix adversarial team game, thereby addressing another open question left recently by Hollender et al. [2025].
Theorem 1.3. Theorem 1.2 holds even when one restricts to polymatrix, 3-player adversarial team games.
We complement the above hardness result by further characterizing the complexity of deciding whether an adversarial team game admits a unique (approximate) Nash equilibrium (Theorem 3.5).
Symmetric min-max optimization As we have seen, symmetry plays key role in the proof of Theorem 1.2, but that result places no restrictions on whether the equilibrium is symmetric or this is indeed the crux of the argument. The next problem we consider concerns computing symmetric equilibria in symmetric min-mas optimization problems, in the following natural sense.
Definition 1.4 (Symmetric min-max optimization). A function f X Y R is called antisym- metric X = y and
f(x y) -f æ)
V( E X' x V.
Furthermore, point (a, y) E X y is called symmetric if y. The associated min-max
optimization problem is called symmetric if the underlying function f is antisymmetric.?
Symmetric zero-sum games are ubiquitous in the literature and in practical applications alike. Many popular recreational games used for Al benchmarking. such as poker and battleship, are symmetric when roles are assigned at random; the symmetry assumption is particularly natural as it ensures that no player has an a priori advantage before the game begins.
The study of symmetric equilibria has a long history in the development of game theory, propelled by Nash's pathbreaking PhD thesis [Nash, 1950] (cf. Gale al. [1951]), and has remained a popular research topic ever since [Tewwodd et al., 2025, Emmons et al., 2022, Garg et al., 2018, Ghosh and Hollender, 2024, Mehta, 2014]. Classic examples in game theory, including rock- wwt--ppppppsssseeeee and matching pennies, are also symmetric; these games were already discussed in the original work of von Neumann [1928].
It is not hard to see that symmetric min-max optimization problems, in the sense of Definition 1.4, always admit symmetric first-order Nash equilirri.. What is more, we show that computing such a symmetric equilibrium is in the complexity class PPAD [Papadimitriou, 1994]; this is based on an argument of Etessami and Yannakakis [2010], and complements Daskalakis et al. [2021], who proved that the problem of computing approximate fixed points of gradient descent/ascent which they refer to as GDAFIXEDPOINT lies in PPAD. In a celebrated series of work, it was shown that PPAD captures the complexity of computing Nash equilibria in finite games [Daskalakis et al., 2009, Chen et al., 2009]. In this context, we establish that PPAD also characterizes the complexity of computing symmetric first-order Nash equilibria in symmetric min-max optimization problems:
Theorem 1.5. Computing a symmetric 3/-" -pproximmate first-order Nash equilibrium in symmetric n n-dimensional min-mat max optimization is PPAD compleeee for any constant e > 0.
'The nomenclature of this definition is consistent with the usual terminology in the context of (two-player) zero-sum games: a symmetric zero sum game is one in which the the underlying game matrix A is antisymmetric (that is, nee-syymetriic,, that (æ, Ay) (y, Ax) for all (xc, y).
3

---

Barring major complexity breakthroughs. Theorem 1.5 precludes the existence of algorithms with complexity polynomial in the dimension and 1/c, where >> O measures the precision (per Defini- tion 1.1), under the symmetry constraint of Definition 1.4. This stands in contrast to (nonconvex) minimization problems, wherein gradient descent converges to stationary points at a rate of poly(1/<);
even in the regime where in CLS [Daskalakis and Papadimitriou, 2011], which is a subclass of PPAD [Fearnley et al., 2023]. In fact, our reduction also rules out the existence of polynomial-time algorithms even when = (1) under some well-believed complexity assumptions (Corollary 4.3).
1/ exp(n). computing stationary point of smooth function is
The proof of Theorem 1.5 is elementary, and is based on the Nash equilibria in symmetric two-player games. Importantly, our reduction gives an immediate, and significantly simpler, proof (Theorem 4.4) of the PPAD-hardnes result of Daskalakis et al. [2021] I. while being applicable even with respect to quadratic and anti-symmetric functions defined on a product of simplexes.
of computing symmetric
Independent and concurrent work Bernasconi al. [2024] also considerably simplified the proof of Daskalakis et al. [2021]. Our hardness result hinges on the intermediate problem of finding a Nash equilibrium in symmetric two-player games [Chen et al., 2009], whereas Bernasconi et al. [2024] showed their hardness result via the problem of finding Nash equilibrium in (multi -laytrr polymatrix two-action games. The main qualitative difference between the two is that ours applies to simplex domains while the result of Bernasconi et al. [2024] to box domains. The basic idea of both reductions then that one can enforce the symmetry constraint 2 F y via coupled constraints.
As byproduct of Theorem 1.5 and the result of Bernasconi et al. [2024], it follows that any sym- metric dynamics- tion 4.5 cannot converge to a first-order Nash equilibrium in polynomial time, subject to PPAD of P (Theorem 4.6). This already captures many natural dynamics for which prior papers in the litera- ture (e.g., Kalogiannis et al. [2023b]) have painstakingly shown lack of convergence; Theorem 4.6 provides a complexit-thheoree justification for such prior results, while precluding a much broader family of algorithms.
both players follow the same online algorithm, formalized in Defini-
The complexity of non-symmetric equilibria Remaining on symmetric min-max optimization, one natural question arising from Theorem 1.5 concerns the complexity of non-symmetric equilibria- defined having distance at least ō 0. Unlike their symmetric counterparts, non-symmetric first-order Nash equilibria are not guaranteed to exist. In fact, we establish the following result.
Theorem 1.6. For a symmetric min-max optimization problem, constants 01, C2 > O, and c n it is hard to distinguish between the following two cases under the promise that one of them holds:
any e-first-order Nash equilibrium (a=", yy" satisfies ||æe" - yy S =2, and there is an e-first-order Nash equilibrium (x" yy" such that | 3² 2 2(1).
The main technical piece is Theorem 4.7, which concerns symmetric, adentical-interes. two-player games. It significantly refines the hardness result of McLennan and Tourky [2010] by accounting even for poly(1 (1/)) -nnssNash equilibria.
Team zero-sum games Finally, building on the reduction of Theorem 1.5 coupled with the gad- get behind Theorem 1.2, we establish similar complexity results for team zero-sum games, which generalize adversarial team games by allowing the presence of multiple adversaries. In particular, a symmetric two-team zero-sum game and symmetric equilibrium thereof are in accordance with Def- inition 1.4-no no symmetry constraints are imposed within the same team, but only across teams. We obtain a result significantly refining Theorem 1.5.
Theorem 1.7. Computing a symmetric -Nash equilibrium in symmetric, 6-player (3 vs. 3) team zero-sum polymatrix games is PPAD-complete for some constant e 0.
Unlike our reduction in Theorem 1.5 that comprises quadratic terms, the crux in team zero-sum games is that one needs to employ solely multilinear terms. The basic idea is to again use the gadget underpinning Theorem 1.2, which enforces symmetry without affecting the equilibria of the game, thereby (approximately) reproducing the objective function that establishes Theorem 1.5.
is interesting to note that the class of polymatrix games we construct to prove Theorem 1.7 belongs to certain family introduced by Cai and Daskalakis [2011]] one can partition the players into 2

---

groups so that any pairwise interaction between players of the same group is a coordination game, whereas any pairwise interaction across groups a zero-sum game. Cai and Daskalakis [2011] I] showed that computing Nash equilibrium is PPAD-han hard- in the more general case where there are 3 groups of players. While the complexity of that problem under 2 groups remains wide open, Theorem 1.7 shows
for computing symmetric Nash equílibria in such games.
Taken together, our results bring us closer to characterizing the complexity of computing equilibria in min-max optimization.
1.2 Further related work
Adversarial team games have been the subject of much research tracing back to the influential work of von Stengel and Koller [1997], who introduced the concept of team maxmin equilibrium (TME); a TME can be viewed as the best Nash equilibrium for the team. Notwithstanding its intrinsic appeal, turns out that computing a TME is FNP-hard [Borgs al., 2010]. Indeed, unlike two-player zero-sum games, team zero-sum games generally exhibit a duality gap characterized in the work of Schulman and Vazirani [2017].
This realization has shifted the focus of contemporary research to exploring more permissive solution concepts. One popular such relaxation is TMECor, which enables team players to ante correlate their strategies [Zhang et al., 2023, 2021, Basilico et al., 2017, Carminati et al., 2022, Farina et al., 2018, Zhang and An, 2020, Celli and Gatti, 2018]. Yet, in the context of extensive-form games, computing a TMECor remains intractable; Zhang et al. [2023] provided an exact characterization of its complexity. Team zero-sum games can be thought of as two-player zero-sum games but with imperfect recall, and many natural problems immediately become hard without perfect recall (e.g., Tewolde al. [2023]). Parameterized algorithms have been developed for computing a TMECor based on some natural measure of shared information [Zhang et al., 2023, Carminati et al., 2022]. Beyond adversarial team games, Carminati et al. [2023] recently explored hidden-role games, wherein there is uncertainty regarding which players belong in the same team, feature that often manifests itself in popular recreational games and used certain cryptographic primitives solve them.
In contrast, this paper focuses on the usual Nash equilibrium concept, being thereby orthogonal to the above line of work. One drawback of Nash equilibria in adversarial team games is that the (worst-case) value of the team can be significantly lower compared to TME [Basilico et al., 2017]. On the other hand, Anagnostides et al. [2023] showed that c-Nash equilibria in adversarial team games admit an FPTAS, which stands in stark contrast to TME, and indeed, Nash equilibria in general games [Daskalakis et al., 2009, Chen al., 2009]. This was further strengthened by Kalogiannis et al. [2023a, 2024] for computing e-Nash equilibria in adversarial team Markov games- the natural generalization to Markov (aka. stochastic) games.
Related to Definition 1.1 is the natural notion of a local min-max equilibrium [Daskalakis and Panageas, 2018, Daskalakis et al., 2021]. It is easy to that any local min-max equilibrium-wwe with respect to a sufficiently large neighborhood of (x"" y satisfy Definition 1.1 [Daskalakis al., 2021]. Unlike first-order Nash equilibria, local min-max equilibria not guaranteed to exist.
Finally, Mehta et al. [2015] showed that in two-player symmetric games, deciding whether a non- symmetric Nash equilibrium exists is NP-hard, which directly relates to our Theorem 1.6.
2 Preliminaries
Notation We use boldface lowercase letters, such as y. to represent vectors, and boldface capital letters, such as A, C, for matrices. We denote by x; the ith coordinate of vector
R.. We n). A = fx E R Σi=1 2; = 1} is the probability simplex on R", For i E [n], e, E A is the ith unit vector. (---) denotes the inner product. For vector R", |2||| (z, æτ) is its Euclidean norm. For m n, 2 [I..m]]
use the shorthand notation [n] ==
R is the vector containing the first m coordinates of æ. We sometimes use the 0(.). O()). notation to suppress absolute constants. continuously differentiable function f is L-smoooh if its gradient I.-Lipschitz
continuous with respect to || ||2: that is, f[) fx(')) - L|[x x' || for all x. x'.
5

---

Two-player games In two-player game, represented in normal-form game, each player has finite set, let [n]. of actions. Under a pair of actions (i,j) [n] x [n]. the utility of the row player is given by Rij. where R E Quxm is the payoff matrix of the row player. Further, we let C E Qaxx be the payoff matrix of the column player. Players are allowed to randomize by selecting mixed prrategies-poinee in A Under pair of mixed strategies (æ, y) E A x A", the expected utility of the players is given by (x, Ry) and (x, Cy), respectively. The canonical solution concept in such games is the Nash equilibrium [Nash, 1951], which is recalled below.
Definition 2.1. pair of strategies (xx y²) an e-Nash equilibrium of (R,C) (ar Ryy 2 (ac, Ry") -E and (a* Cy") (a" CC) V(r, E A
Symmetric two-player games One of our reductions is based on symmetric two-player games, meaning that R C A basic fact that any symmetric game admits symmetric Nash equilibrium (a', x*). Further, computing a Nash equilibrium in a general game can be reduced to computing a symmetric Nash equilibrium in a symmetric game [Nisan et al., 2007. Theorem 2.4]. In conjunction with the hardness result of Chen et al. [2009], we state the following consequence.
Theorem 2.2 (Chen et al., 2009). Computing symmetric S/n--Nshh equilibrium in symmetric two-player game is PPAD-hard for any constant c > O.
Team zero-sum games A (two-)team zero-sum game is multi-player game-reepeesented in normal form for the purposes of this paper-in which the players' utilities have a certain structure; namely, we can partition the players into two (disjoint) subsets, such that each player within the same team shares the same utility, whereas players in different teams have opposite utilities under any possible combination of actions. An adversarial team game is specific type of team zero-sum game wherein one team consists of a single player. As in Definition 2.1 for two-player games, an e-Nash equilibrium is tuple of strategies such that unilateral deviation yields more than additive improvement the utility of the deviator.
3
Complexity of adversarial team games
We begin by examining equilibrium computation in adversarial team games.
3.1 CLS-completeness for 3-player games
Computing c-Nash equilibria in adversarial team games was placed in CLS by Anagnostides et al. [2023], but whether CLS tightly characterizes the complexity of that problem remained open- that was only known when the number of players is large, so that the hardness result of Babichenko and Rubinstein [2021] can kick in. Our reduction here answers this question in the affirmative.
We rely recent hardness result of Ghosh and Hollender [2024] concerning symmetric, two-player games with identical payoffs. We summarize their main result below.
Theorem 3.1 (Ghosh and Hollender, 2024). Computing e-Nash equilibrium in symmetric, -uyoof,, two-player game is CLS-complete
Now, let A E Qnx" be the common payoff matrix a two-player game, which satisfies A = A so that the game is symmetric. Without loss of generality, will assume that A., I -1 for all j E [r)]. We denote by Amin and Amax the minimum and maximum entry of A, respectively (which satisfy Amax, Amin < -1). The basic idea of our proof is suitably use the adversarial player as to force the other two players to play roughly the same strategy (Lemma 3.2), while (approximately) maintaining the structure of the game (Lemma 3.3). The formal proofs are in Section A.
Definition of the adversarial team game Based on A, we construct a 3-player adversarial team game as follows. The utility function of the adversary reads
u(ar y. 2) == (ar, Ay) + Amiin Σ (zi( - vi) + 2n+i(U: - x;)) + 22 |
i=1
The adversary selects strategy z E A 2n+1 while the team players, who endeavor to minimize (2), select strategies æ E A and y E A", respectively. (While the range of the utilities in (2) grows with 1/e, normalizing to [-1, maintains all of the consequences by suitably adjusting the approximation.)

---

The first important lemma establishes that, in equilibrium, a == The basic argument proceeds as follows. By construction of (2), the adversary would be able secure large payoff whenever there is coordinate E [n] such that [r; yil > O-by virtue of the second term in (2). But that cannot happen in equilibrium, for Player æ (or symmetrically Player y) can simply neutralize that term in the adversary's s utility by playing = y.
Lemma 3.2 (Equilibrium forces symmetry). Consider an -Nash equilibrium (a", , 2²) of the adversarial team game (2) with e² == 1/2. Then, || yy"ll S 2e.
Having established that s y. the next step is make sure that the adversarial player does not distort the original game by much. In particular, we need to make sure that the effect of the second term in (2) is negligible. We do so by showing that 22n+1 1 (Lemma 3.3).
The argument here is more subtle; roughly speaking, goes as follows. Suppose that 2; > 0 or 2n+z > 0 for some i [nz]. Since Player is approximately best responding, it would then follow that y - > 0 Otheerrise Player would prefer to switch to action 2n+1. 1. But, jy; -xx] > 0, Player could profitably deviate by reallocating probability mass by either removing from adding to (depending on whether yf x > 0), which leads to a contradiction.
Lemma 3.3 (Most probability mass in 02n+1). Given any --Nash equilibrium ,"","" ",,"",)) of the adversarial team game (2) with 1/10, 2j S for all E [2m]. particular, 22n+1 2 18nc.
By combining Lemmas 3.2 and 3.3, we can complete the reduction from symmetric two-player games with common payoffs to 3-player adversarial team games, as stated below.
Theorem 3.4. Given any 2-Nash equilibrium (x" (x",y", yy" 2²) in the adversarial team game (2), with I 1/10, (y" y²) is a symmetric (21n + A)) l-Nss equilibrium of the symmetric, two-player game (A, A) (that is, A ).
3.2 The complexity of determining uniqueness
Another natural question concerns the complexity of determining whether an adversarial team game admits unique Nash equilibrium. Our next theorem establishes NP-hardness for a version of that problem that accounts for approximate Nash equilibria.
Theorem 3.5. For polymatrix, 3-player adversarial team games, constants C1, > 0, and e n " is Na-hard to distinguish between the following two cases under the promise that one of them holds:
any two e-Nash equilibria have É disitttnce at most n =aa, and c-Nash equilibria that have Ea-distance 1?(1).
there
We will discuss more about the proof of this theorem later in Section 4.2 when we examine the complexity of computing non-symmetric equilibria symmetric min-max optimization problems. It is also interesting to point out that an adversatial team game can have unique Nash equilibrium supported on irrational numbers, as we show in Section A.2.
4 Complexity of equilibria in symmetric min-max optimization
This section characterizes the complexity of computing symmetric first-order Nash equilibria (Defini- tion 1.1) in symmetric min-max optimization problems in the sense of Definition 1.4; namely, when f(x v) - fly æ) for all (x, y) E X' x y and X' = y.
4.1 Problem definitions and hardness results for symmetric equilibria
Given a continuously differentiable function f 'D - R. we set FODA D - D to be
FGDA (z, y) = x vaf(x,y) y V (xf(x, for (x. y) E E
the norm of which measures the fixed-point gap and corresponds to the update rule of GDA with stepsize equal to one; we recall that Player æ the minimizer, while Player y the maximizer. The domain D is compact subset of d for some d E N. Moreover, the projection operator I[ is applied
7

---

jointly on D. When D can be expressed as a Cartesian product X' X V, the domain set is called uncoupled (and the projection can be done independently), otherwise it is called coupled (or (orjoin))
We begin by introducing the problem of computing fixed points of gradient descent/ascent (GDA) for domains expressed the Cartesian product of polytopes, modifying the computational problem GDAFIXEDPOINT introduced by Daskalakis et al. [2021].
GDAFinedPoINT Problem.
INPUT:
Precision parameter e > 0 and smoothness parameter L,
Polynomial-time -ime Turing machine y evaluating L-smooth function f Xxx - R and its gradient V A' x y + Rd, where X' {x: A_ I b,} and {y An y I by) are nonempty, bounded polytopes described by input matrices Az Rm,, xd, Ag Rm and vectors b₂ E I by E R, with d == dg + dy.
OUTPUT: A point (x",, ,y") X x y such that I|( )²) Fana(æ" y2))l2 Se.
Based on GDAFIXEDPOINT, we introduce the problem SYMGDAFIXEDPOIT the problem of computing symmelric (approximate) fixed points of GDA for symmetric min-max optimization problems. We define our computational problems as promise problems.
which captures
SYmGDAFINEDPONT Problem.
INPUT:
Precision parameter e >> 0 and smoothness parameter L,
Polynomial-time Turing machine Cy evaluating L-smooth, antisymmetric function f X' x X' IR and its gradient V X X' RR2d, where X (x Aa: & b) is nonempty, bounded polytope described by an input matrix A E gmmx and vector b E R
OUTPUT: A point (x", xx)) ")E E X x X' such that [|(x", x²) - FGDA(W" x2)) S.
We start by showing that SYMGDA SYMGIDFFXEDPONN FIXEDPOINT also lies in PPAD; the fact that GIDFFIEEPPINT is in PPAD-ens even under coupled domains- was shown be the case by Daskalakis al. [2021]. The detailed proof is included in the appendix.
Lemma 4.1. SYMGIDFFINDPPORT
a total search problem and lies in PPAD.
Having established that SYMGDAFIXEDPOINT belongs in PPAD, we now state the first main hardness result of this section.
Theorem 4.2 (Complexity for symmetric equilibrium). SYMGDAFIXEDPOINT is PPAD cPoDecomplete even for quadratic functions.
The basic idea of the proof is to consider the objective
1 y. Ay) (1p, Ar)) (g,, Car),
f(x y)
where A is symmetric and C is skew-symmetric. Theorem 4.2 then follows from some elementary calculations, as we show in Section A.3.
For symmetric first-order Nash equilibria, our argument establishes PPAD-hardness for any c S 1/n", where e 0 (as claimed in Theorem 1.5). Moreover, leveraging the hardness result of Rubinstein [2016]. we can also immediately obtain constant inapproximability under the so-called exponential- time hypothesis (ETH) for PPAD-which postulates than any algorithm for solving ENDOFALINE, the prototypical PPAD-complete problem, requires 20(n) time.
Corollary 4.3. Computing ( -approximate first-order Nash equilibrium in symmetric dimensional min-max optimization requires n ((logn) time, assuming for PPAD.
'This is the "safe" version of GDA because it ensures that the mapping always lies in D. One could also project independently on P(y) (x' : (æ', .y) E D) and D(x)= = {v' (æ, d')e E D): see Daskalakis et al. [2021] for further details and the polynomial equivalence for finding fixed points for both versions.

---

The argument of Theorem 4.2 can be slightly modified to imply the main result of Daskalakis et al. [2021] with simplex instead of box constraints- as stated below. Theorem 4.4 (PPAD-hardness for coupled domains), The problem GDAFIXEDPOINT is PPAD-hard when the domain a joint polytope, even for quadratie functions.
The main idea is to add coupled constraints in order to force symmetry: - - x I for all i [n], where, if the approximation accuracy, 8 is of order O (c)/4). Compared to the equilibrium studied in Daskalakis et al. [2021], the symmetric equilibrium considered in our work is stronger in that it accounts for all deviations, not merely ones on the coupled feasibility set. We present the proof of Theorem 4.4 in Section A.3.
Hardness results for symmetric dynamics Another interesting consequence of Theorem 4.2 is that it precludes convergence under broad class of algorithms in general min-max optimization.
Definition 4.5 (Symmetric learning algorithms for min-max). Let T E N. A deterministic, polynomial-time learning algorithm A proceeds as follows for any time t E [T]- It outputs a strategy as a function of the history 7(0 it has observed so far (where 7(11) = 0 ), and then receives as feedback gX), It then updates ((+1) = (H(1), ())). A symmetric learning algorithm in min-max optimization consists of Player æ employing algorithm A with history H.! = aV y ())) and Player y employing the same algorithm with history H: = ff y ())
Note that a consequence of the above definition is that both players initialize from the same strategy. Many natural and well-studied algorithms in min-max optimization adhere to Definition 4.5. Besides the obvious example of gradient descent/ascent, we mention extragradient descent(/ascent) opti- mistic gradient descent(/ascent), and optimistic multiplicative weights-al all assumed to be executed simultaneously. A simple non-example is alternating gradient descent(/ascent) [Wibisono et al., 2022, Bailey et al., 2020], wherein players do not update their strategies simultaneously.
Theorem 4.6. No symmetric learning algorithm (per Definition 4.5) can converge to c-first-onder Nash equilibria in min-max optimization in polynomial time when 1/n", unless PPAD P.
This consequence of our argument in Theorem 4.2: under Definition 4.5 and the min-max optimization problem (3), it follows inductively that (1) = ()( and H H/ for all & E [7]. But computing symmetric first-order Nash equilibrium is PPAD-hard when e 1/x= (Theorem 4.2).
Assuming that P * PPAD, Theorem 4.6, and in particular its instantiation in team zero-sum games (Theorem 1.7), significantly generalizes some impossibility results shown by Kalogiannis et al. [2023b] concerning certain algorithms, such as optimistic gradient descent(/ascent) our hardness result goes much further, precluding any algorithm subject to Definition 4.5, albeit being conditional.
4.2 The complexity of non-symmetric fixed points
An immediate question raised by Theorem 4.2 concerns the computational complexity of finding non-symmetrii fixed points of GDA for symmetric max optimization problems. Since totality not guaranteed, unlike SYMGDAFIXEDPOINT we cannot hope to prove membership in PPAD. In fact, we show that finding nom-symmetric fixed point of GDA is FNP-hard. To do so, we first define formally the computational problem of interest. NONSYMDDAFINEDPONG Problem. INPUT:
Parameters 0 0 and Lipschitz constant L and
Polynomial-time Turing machine C, evaluating a L-smooth antisymmetric function f X' x X + R and its gradient Vf: X' x X' + Ig2dd where X = (x Aa < b) is a
nonempty, bounded polytope described by a matrix A mx and vector E I
OUTPUT: A point (x".y") [1(x", .y") - FGDA(a", y²)l22 "ana(""""")l" S e it exists, otherwise return NO.
X' X such that ||=: 1a=--"" y
8 and
We establish that NONSYMGDAFFXEDPONN is FNP-hard. Our reduction builds on the hardness result of McLennan and Tourky [2010]- turn based on earlier work by Gilboa and Zemel [1989].

---

Conitzer and Sandholm [2008]-which we significantly refine in order to account for poly(1/n) //n/nnn-Nasss -Nsh equilibria. Our result, which forms the basis for Theorem 1.6 and Theorem 3.5, summarized below.
Theorem 4.7. For symmetric, slentical-interesst, two-player games, constants C1, 0, and é - nt = is NP-hurd to distinguish between the following two cases under the promise that one of them holds:
any two symmetric e-Nash equilibria have ( distance at most n -2, and
* there are two symmetric c-Nash equilibria that have Ey-distance (2(1).
The proof of Theorem 1.6 now follows by considering the antisymmetric function f(z, y) = By x: Ba for suitable matrix B (defined per the hard instance from Theorem 4.7 based k-clique). FNP-hardness follows similarly by considering a search version of maximum clique.
Finally, the proof of Theorem 3.5 that was claimed earlier follows immediately by combining Theorem 4.7 with the reduction of Section 3.1, and in particular, Lemmas 3.2 and 3.3.
4.3 Team zero-sum games
Our previous hardness result concerning symmetric min-max optimization problems does not have any immediate implications for (normal-form) team zero-sum games since the class of hard instances we constructed earlier contains a quadratic term. Our next result provides such a hardness result by combining the basic gadget we introduced in Section 3.1 in the context of adversarial team games; the basic pieces of the argument are similar to the ones we described in Section 3.1, and so the proof deferred to Section A.5. Our goal prove the following.
Theorem 1.7. Computing symmetric -Nash equilibrium in symmetric, 6-player (3 vs. 3) team zero-sum polymatrix games is PPAD-complete for some constant c >> O.
Let us describe the class of 3 vs. 3 team sero-sum games upon which our hardness result is based on. Based on (2), we define the auxiliary function
A mial
8 x x
2n+1 (x, 2)
Σ (2((1; - 11) + Zn+i(y xz)) + Amin |22n+1-
In what follows, the 3 players of the team will be identified with (x: y, =), while the 3 players of the other team with (œ, ÿ, 2). We define the utility of the latter team to be
u(2: y, at, ÿ. 2) (x,, Ay) (it, A + (ax, Ca) + 5(x, y, 2) 8( 9. z), where A is symmetric and C is skew-symmetric. The rest of the argument follows Section 3.1.
(4)
5 Conclusion and open problems
We have provided a number of new complexity results concerning min-max optimization in general, and team zero-sum games in particular (see Table 1). There are many interesting avenues for future re- search. The complexity of computing first-order Nash equilibria (cquivalently, the GDAFIXED problem) remains wide open, but our hardness results suggest a possible approach: as we have seen, in symmetric min-max optimization, computing either symmetric or non-symmetric equilibria is intractable, so would be enough one could establish this using the same underlying function that is, somehow combine our two reductions into one. It would also be interesting to see whether our hardness results can be extended to more structured min max optimization problems, such as adversarial training and GANs.
Acknowledgments
I.P. and J.Y. were supported by NSF grant CCF-2454115. I.P. would like acknowledge ICS research award and start-up grant from UCI. Part of this work was done while I.P. and J.Y. were visiting Archimedes Research Unit. T.S. is supported by the Vannevar Bush Faculty Fellowship ONR 000014-23-1-2874 National Science Foundation grants RI-231 24322223222 and RI-1901403, ARO award W91 1NF2210266, and NIH award 02401085001. We are grateful to Alexandros Hollender for many valuable discussions.
10

---

References
loannis Anagnostides, Fivos Kalogiannis, Toannis Panageas, Emmanouil- Vasileios Vlatakis- Gkaragkounis, and Stephen McAleer. Algorithms and complexity for computing Nash equilibria in adversarial team games. In Conference on Economics and Computation (EC), 2023.
Yakov Babichenko and Aviad Rubinstein. Settlig the complexity of Nash equilibrium congestion games. In Symposium on Theory of Computing (STOC), 2021.
Tao Bai, Jinqi Luo, Jun Zhao, Bihan Wen, and Qian Wang, Recent advances in adversarial training for adversarial robustness. In International Joint Conference on Artificial Intelligence (IJCAI), 2021.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, 2020.
James P. Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference on Learning Theory (COLT), 2020.
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Team-maxmil equilibrium: Efficiency bounds and algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), 2017.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Gabriele Farina. On the role of constraints in the complexity of min-max optimization, 2024.
Marie Louisa Tølhøll Berthelsen and Kristoffer Amnselt Hansen. On the computational complexity of decision problems about multi-player Nash equilibria. In Dimitris Fotakis and Evangelos Markakis, editors, Algorithmic Game Theory, pages 153-167, Cham, 2019. Springer International Publishing. ISBN 978-3-030-30473-7,
Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, and Christos H. Papadimitriou. The myth of the folk theorem. Games and Economic Behavior, 70(1): 34-43, 2010.
Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In Symposium on Discrete Algorithms (SODA), 2011.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian J. Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness, 2019.
Luca Carminati, Federico Cacciamani, Marco Ciccone, and Nicola Gatti. A marriage between adversarial team games and 2-player games: Enabling abstractions, no-regret learning, and subgame solving. In International Conference on Machine Learning (ICML), 2022.
Luca Carminati, Brian Hu Zhang, Gabriele Farina, Nicola Gatti, and Tuomas Sandholm. Hidden- role games: Equilibrium concepts and computation. In Proceedings of the ACM Conference Economics and Computation (EC), 2023.
Andrea Celli and Nicola Gatti, Computational results for extensive-form adversarial team games. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 36(3):14:11 1::1:14777 2009.
Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient methods for structured non-monotone variational inequalities: Improved analysis under weaker conditions. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2023.

---

Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning (ICML), pages 1310-1320, 2019.
Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):221-641, 2008
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2018.
Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In Symposium Discrete Algorithms (SODA), 2011.
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1)1195-259 2009.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS). 2020.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Symposium on Theory of Computing (STOC), 2021.
Scott Emmons, Caspar Oesterheld, Andrew Critch, Vincent Conitzer, and Stuart Russell. For learning in symmetric teams, local optima are global Nash equilibria. In International Conference on Machine Learning (ICML), 2022.
Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM J. Comput., 3966):5511-2599 2010.
Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Ex ante coordination and collusion in pero-sum multi- extensive-form games. In Proceedings the Annual Conference on Neural Information Processing Systems (NeurIPS), 2018
John Fearnley Paul Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD PLS. ACM, 70(1):7:1-7:74, 2023.
D. Gale, H. W. Kuhn, and A. W. Tucker. On Symmetric Games, pages 81-88. Princeton University Press, 1951.
Jugal Garg, Ruta Mchta, Vijay V. Vazirani, and Sadra Yazdanbod. Fr-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput., 6(1), 2018.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Mathematical Programming, 156(1):59-99, 2016.
Abheek Ghosh and Alexandros Hollender. The complexity of symmetric bimatrix games with common payoffs. In Conference on Web and Internet Economics (WINE), 2024.
Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-93, 1989.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Proceedings of the Annual Conference Neural Information Processing Systems (NIPS), 2014.
Eduard Gorbunov, Adrien B. Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Alexandros Hollender, Gilbert Maystre, and Sai Ganesh Nagarajan. The complexity of two-team polymatrix games with independent adversaries. International Conference on Learning Repre- sentations (ICLR), 2025.
12

---

Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex nonconcave minimax optimization? In International Conference on Machine Learning (ICML), 2020.
Michael I. Jordan, Tianyi Lin, and Manolis Zampetakis. First-order algorithms for nonlinear gen- eralized Nash equilibrium problems. Journal of Machine Learning Research, 24:38:1-388 18::46,, 2023.
Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas, Himmanoull-Vasieeie Vlatakis- Gkaragkounis, Vaggos Chatziafratis, and Stelios Andrew Stavroulakis. Efficiently computing Nash equilibria in adversarial team markov games. In International Conference on Learning Representations (ICLR), 2023a.
Fivos Kalogiannis, Joannis Panageas, and Emmanouil- Vasileios Viatakis-GKaragkounii.. Towards convergence to Nash equilibria in two-team zero-sum games. ICLR, 2023b.
Fivos Kalogiannis, Jingming Yan, and Ioannis Panageas. Learning equilibria in adversarial team markov games: A nonconvex-hicdden-connny min-max optimization problem. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-coneee minimax problems. In International Conferecne on Machine Learning (ICML., 2020.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-sie manconvex-strongyyooomm -trongyy-cooncve minimax problems. In Advances in Neural Information Processing Systems, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICLR), 2018.
Andrew McLennan and Rabee Tourky. Simple complexity from imitation games. Games and Economic Behavior, 68(2):683668, 2010.
Ruta Mehta. Constant rank bimatrix games are ppad-hard. In Symposium on Theory of Computing (STOC), 2014.
Ruta Mehta, Vijay V Vazirani, and Sadra Yazdanbod. Settling some open problems on 2-player symmetric Nash equilibria. In International Symposium Algorithmic Game Theory, pages 272-284. Springer, 2015.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR), 2019.
John Nash. Non-cooperative games. PhD thesis, Princeton University, 1950.
John Nash. Non-cooperative games. Annals mathematics, pages 286-295, 1951.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, USA, 2007.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, and Meisam Razaviyayn. Solving class non-convex min-max games using iterative first order methods. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2019.
Idan Orzech and Martin C. Rinard. Correlated vs. uncorrelated randomness in adversarial congestion team games, 2023.
Dmitrii M. Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex nonconvex-concav concave smooth min-max problems. SIAM J. Optim., 31(4):2508-2538 2021.
13

---

Chen-Yu Yu Wei, Chung-War Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of competitive markov games, In Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-555 5328 1994.
Aviad Rubinstein. Setling the complexity computing approximate two-player Nash equilibria. In Symposium Foundations of Computer Science (FOCS), 2016.
Leonard Schulman and Umesh V Vazirani. The duality gap for two-team zero-sum games. In Innovations in Theoretical Computer Science Conference (ITCS), 2017.
Ke Sun. Some properties of the Nash equilibrium 2 x 2 zero-sum games, 2022.
Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, and Paul W. Goldberg, The computational
complexity of poagleplayeer imperfect-recal games. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2023.
Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, and Vincent Conitzer. Computing game symmetries and equilibria that respect them. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), 2025.
Ioannis C. Tsaknakis and Mingyi Hong. Finding first-order Nash equilibria of zero-sum games with the regularized nikaido-isoda function. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
John von Neumann. Zur Theorie der Gesellschaftsspicl.. Mathematische Annalen, 100:295-320, 1928.
Bernhard von Stengel and Daphne Koller. Team-maxmin equilibria. Games and Economic Behavior, 21(1):309-321, 1997.
decentralized optimistic gradient descent/ascent in Conference on Learning Theory (COLT), 2021.
Andre Wibisono, Molei Tao, and Georgios Piliouras. Alternating mirror descent for constrained min-max games. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2022.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projec- tion algorithm for nonconvex-conean and convex monee--nonconcaee minimax problems. Mathematical Programming, 201(1):635-700 -766)66666-666---- 2023.
Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief DAG: generalizing the sequence form to team games for fast computation of correlated team max-min equilibria via regret minimization. In International Conference on Machine Learning (ICML), 2023.
Youzhi Zhang and Bo An. Converging team-maxmin equilibria in zero-sum multiplayer games. In International Conference on Machine Learning (ICML), 2020.
Youzhi Zhang, Bo An, and Jakub Cerný. Computing ex ante coordinated team-maxmin equilibria in zero-sum multiplayer extensive-form games. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), 2021.
14

---

A Omitted proofs
This section contains the proofs omitted from the main body.
A.1 Proofs from Section 3.1
We begin by stating and proving simple auxiliary lemma.
Lemma A.I. Let (x) x" an e2-Nash equilibrium of normal-form game, and aj any action of player If (u(a,, x";))= I xa(aj,=";) - c some с and [nl] then x (ax) S e//c
Proof. For the sake of contradiction, suppose that az (ax) a for some E [n] such that u,(0k, x= S uı(aj, Consider the strategy A x x + + (ax)e, 2 (ax)er. Then,
we have
un(a), x=1))= (n,
(ax)) x= x. (ax)) (ax)); x"1.)
(ax)
2
That is, deviating to z yields a utility benefit strictly larger than e², which contradicts the assumption that (x), x" is an e² --Nahh equilibrium.
We move on to the proof Lemma 3.2.
Proof of Lemma 3.2. For the sake of contradiction, suppose that xt V/ >> 2e for some E [n] (the case where Vr" x. > 2e is symmetric, and can be treated analogously). Player z could then choose action a; (with probability 1), which secures utility of
u(x", yy" a..) (x", Ayy) Amiul
(x, vi) > (x" Ayy" + + 2|mmml
since x;- Vi > 2e. At the same time, Player could choose action 02n-1, which secures a utility of u(x", y", (2n+1) = (x0 Ayy) + Amiil So,
u(x", y ,²,aa))))))))) u(x", y" a2n+1) 2 Amin|-
Applying Lemma A.I,
22n+1 Amiul
(5)
Also, using the fact that (x" y", 2²) an 2-Nash equilibrium,
u(x y² u(x", yy,a,) 2
(a", Ay") + 2 A 2
Amin + A 2
Amin| - 2
(6)
since we have assumed that A Ain Now, consider the deviation of Player æ (from strategy x²))
to x'' == y" Then, u(x', y"; z²) (v" Ag") + 22n+1 A Thus, combining with (6) and (5),
u( ,²"²") u(x' yy
(y Ay
2 |Amiul |Amin c²
(1) Ay
2 |Aminl |miil 2
Amax A ([Amiul + 1)
$ <
where we used that A Amax; Amin < -1 and 2 < 1/2. But (7) contradicts the fact that (x= ,y""""" =²) is an ea-Nash equilibrium since deviating to x' yields a utility improvement (equivalently, decrease in cost) strictly larger than e., This completes the proof.
15

---

We proceed with the proof of Lemma 3.3.
Proof of Lemma 3.3. From Lemma 3.2 it holds that - S 2c. Let E [n]. We assume that i is such that x -,," 2 O; the contrary case is symmetric. We consider two cases. First, suppose that b v.l I 4/2. Then, we have
Amin
u(x", y", a2n+1) - u(x" yy az) 2 Aminl
(x) Vs+)
1
min
Thus, by Lemma A.I, we conclude that 2; S 2c.. Similarly, u(x", yy, a2m+1) u(x", y an+4) 2 Amiil
|Amin
(u/ x;) 2 Amial 2 1,
since 27 Vr 2 O. Again, Lemma A.1 implies that 2n4i S..
It thus suffices treat the case where | - 5/2 (assuming that x; - 0). follows that there
exists j E [n] such that x; - yj < O. In addition, we observe that u(æ", 4 (22++1) = (ar", " Ay") |Amin 2 Ayy) + 1, whereas u(x", ,y" a,) < , Ay") and u(x", y", ,,ans) < (x" Agy)
As result, Lemma A.1 implies that 2 I e² and 23 ee.
Now, consider the deviation
a' x.' + (ut - x; es + (af - yi es;
that is, w' is the strategy that results from æ by reallocating (x - y/) probability mass from action to action aj- The difference u(x', =²) u(x", yy =²) can be expressed as
|miil
(x' xx, Agy" +
(z) 22) (1 23) 20t100; - x/)) + 2 1 xzj))
=a'- xx Ay") + |mmill (zi(1t xx) + 2
vi) + 2 vi) + 5 x;))
Ammil (zz (-5) + 22 22 22+ 22 2
S 4e (Amimill
(8)
S 1
2 462 4e Amii,;
where (8) uses the following:
2r x. S -//2;
x vt S 2e (Lemma 3.2);
2 s ² and 2] S 2: and
(x' x Ayy) < || 1011 1o S 2|2; |Amin < 4e Amin (since A has
negative entries);
Moreover, given that (x", y", x²) is assumed to be an 2-Nash equilibrium, we have
u( y" 2²) + u(x", y x") S e
(10)
(The utility of Player æ given by u.) Combining (10) and (9),
462 - Amiil 5 2
(11)
2 8c 10c² < 9c for
(12)
10"
,/ 2 0, we have shown that x S 9c and 2 S 62. The case where y/ - xx 2 0 can be treated similarly.
In summary, when x; -
D
16

---

We continue with the proof of Theorem 3.4, which combines Lemmas 3.2 and 3.3 to complete the CLS-hardness reduction of Section 3.1.
Theorem 3.4. Given any -N-assh equilibrium "="")""²²) in the adversarial team game (2), with ) is a symmetric (21n + AminleNassh equilibrium of the symmetric, two-player game (A, A) (that is, A )
S 1/10, (y" .y""")
Proof. Since (a: , 2²) is an -Nash equilibrium, have that for any for any deviation y' E A of Player y.
x Ay") S ( Ayy)
Aminl
Σ 2z
s/1) - 2ntilll -2/)) x7)) - e..
(13)
Moreover, by considering deviation of Player again to y',
(x' Ay") (z'. Ay") + Aminl
Σ
n
2lll vi) + 2nt1 v/1 t²
(14)
Adding (13) and (14), and using the fact that A is a symmetric matrix,
2(x;", Ay") < (y', A(x" + ))") +
Aminl
Σ 2<(0; - v/) + 2ntel13 -x;) aii) + 26
i=1
Amin
S (y' A2yy") )) + 2eneenAAe Amiil
(2n -e-99-2) (e-2e) + 26²
(15)
- 2(y', Ay") + (38n + 2)| Aminle,
(16)
where in (15) we use Lemmas 3.2 and 3.3. Also,
(y' Ay") (x Ay") + (y" xx" Aby")
S (x" Ay") 2enl Amiil-
(17)
Finally, combining (16) and (17), we conclude that for any y' A
(y' Ay") s (y/, Ay") + (21n + Amin
This concludes the proof.
We now restate Theorem 1.2, which establishes the main complexity implication of Theorem 3.1. Theorem 1.2. Computing an c-Nash equilibrium in 3-player (that is, 2 vs. 1) adversarial team games CLS-complete.
Proof. CLS-hardness follows directly from Theorem 3.4 and Theorem 3.1 (due to Ghosh and Hollen- der [2024]). The inclusion was shown by Anagnostides et al. [2023].
A.2 Irrational Nash equilibria in adversarial team games
We next describe an interesting property for adversarial team games. Namely, similar to general-sum 3-player games [Nash, 1950], there exist adversarial team games that admit unique irrational Nash equilibrium, stated below.
Proposition A.2 (Berthelsen and Hansen, 2019). There exists a 3-player adversarial team game with a unique Nash equilibrium that supported on irrationals.
Although the paper of Berthelsen and Hansen [2019] provides such instance, proof is given. Here, as a complement to their work, we provide a relatively simple and general way to analyze the irrational Nash equilibrium in 3-player adversarial team games.
We consider 3-player adversarial team game in which the utility function of the adversary u {1, 2) {1,2} x {1,2} (x, y, x) IR reads
17

---

[; y)
(I
(1,
(2, 1)
(2, 2)
1
3
99
1
100
100
9
10
10
The proof of this result makes of characterization of Nash equilibria in 2 x 2 two-player zero-sum games, stated below; for the proof, we refer to, for example, Sun [2022, Theorem 1.2].
Lemma A.3. Let A R2x2 such that
(A1.1 (A22 A2,1 > 0 and (A1,1 (2,1) A1,2)
Then, the two-player zero-sum game minges? max (IE, Az) admits unique (exact) Nash equilibrium with value
A221 A1,2A21
A1,1
A1, 22 A2,
Furthermore, the unique Nash equilibrium (a=" 2²)) satisfies
A
A2,
A1,1 A1,2
A1,1 A12
A2,1 + A222 A1,1
A1,2 A + 22,
2 A1,2
A1,1
A2,1
A1,1
A122 - A2,1 + A2,2 A1,1
A12
A2,1 + A
Proof of Proposition A.2. By construction of the adversarial team game, the mixed extension of the utility can be expressed as
99
2 (9) + 3yz) + 21
10 11
10 1/2
+
22
100
V1
100 1/2
+ xz22 (3y2 + 91))
Suppose that we fix y E Then, Players a and y are engaged in (two-player) zero-sum game with payoff matrix
A
1 2y2
10 1/2
(18)
U22
+
2y2
We now invoke Lemma A.3. Indeed, we have
(A(v)1.1 - (Ay)2)) - A(v)2.1 = 3yy +
3y2 +
> 0
(19)
10
100
and
(A(v),.1 A())):)(A())))) (2))22) = 3y2 +
3y2
+
>
0:
(20)
100
10
that is, the precondition of Lemma A.3 satisfied, and so the value of (18) reads
109 + 5890y² + 3000yy
v ( = min max (ar, A(y)z) = 110 + 6000yz
(21)
=E zEA?
easy to verify that v strictly convex function in [o, 1]. and admits unique minimum cor- 9v3-11) which is irrational. Now, suppose that (x: yy" 2²)
responding y =(013 (611-9/3
600
600
is Nash equilibrium of the adversarial team game. We will first argue that (x* (x". =²) is the unique Nash equilibrium of A(y*). Indeed, suppose that there exists x' E A2 such that A(y)))²) or equivalently, u(w', yy, z²) u(x", """ z²);");; this is con- tradiction since (x", "." z=" >²) is assumed to be Nash equilibrium. Similar reasoning applies with respect to Player z. Thus, (xo", =²*) is Nash equilibrium of A A(y") and thereby uniquely deter- mined by bb Lemma A.3 coupled with (19) and (20). Furthermore, given the value of y", we 3-13 Now, consider the utility Player y
(ae' A(y*)=))
get that xx
33/33 34/3 and = /34/3
6
18

---

when playing the first action or the second action 02; plugging in the value of x and z", we have u(æ= e1, x²) 57849v3 and u(x", e2, 2²) 57849v/ Since u(x" E1, (e122*) u(æ", e2 z*), (x", y" =²) ) is Nash equilibrium.
600
Moreover, suppose there exists another Nash equilibrium (x', yy','' 2') that is different from (a", yy, ).). As shown above, (a', x') is the unique equilibrium of the zero-sum game induced by y'. Thus, if we have two different Nash equilibria, implies that y o y". We consider the following three cases:
First, let y' be a (fully) mixed strategy. Since x' and z' forms the unique NE in of A we have
300y 10 300y2
11 + 600y1
11 + 600y
+ 300y
+ 300y
11 + 600y
11 + 600y2
Further, for Player y,
1199 130800y2 3501000y3
e1,
10(11 + 600g2)
589 + 196800y2 + 5301000y3
u(æ', e2 z')
10(11 + 600g2)
Since y' is mixed strategy, we have (1,,', u(x', e2, z'); solving the equality we get y = 6111-9/3s 9v3-11) which contradicts the assumption that y + zy.
600
If y = (1, 0), we have u(x', G1, by unilaterally deviating play (0, 1), Player y can decrease the utility of the adversary, contradicting the fact that (x', y z²) is a Nash equilibrium.
, x²) 1199 and u(x', e2, e2, z') = 589
1210 Thus, it follows that
1210
Finally, suppose that y = (0, 1). Similarly to the second case, we get u(æ', e1, 2') < u(x', C2 e2, z'), which contradiction.
Thus, we conclude that (æ* y", =²) is the unique Nash equilibrium of the 3-player adversarial team game defined above, completing the proof.
natural question arising from Proposition A.2 concerns the complexity of determining whether an adversarial team game admits unique Nash equilibrium. Theorem 3 was presented earlier in the main body-establishee NP-hardness for a version of that problem that accounts for approximate Nash equilibria.
A.3 Proofs from Section 4.1
We continue with the proofs from Section 4.1. We first apply Brouwer's fixed point theorem show that symmetric min-max max optimization problems always admit symmetric equilibrium.
Lemma A.4. Let X be convex and compact set. Then, any L-smooth, antisymmetrie function (Defmitiion 1.4) f X
R. admits symmetric first-order Nash equilibrium (=*xx").
Proof. We define the function M X X' to be
M(x') = II x
x' Vef(x,
(22)
(Ix.))((='(=")))
Given that f is T-smooth, we conclude that ((x') (I. 1)--ss-iishhhir hence continuous. Therefore, from Brouwer's fixed point theorem, there exists x" so that M (xx") Moreover, the symmetry
19

---

of f implies that V Vyf(x,
vef 3))
for all w X: as a result,
(x.z) (mmw)
(1. (w.w)
x²
= IIx
x
v
(2, y)
(a. (mt,m²)
Ixx
x
(x.y)=(x",e"
Therefore, (e",x") is first-order Nash equilibrium of the symmetric min-max problem with function f.
We now present the proof of Lemma 4.1
Proof of Lemma 4.1. We first define the function (as in Lemma A.4) M X X
M(x') = II x'' vaJ(x, ( (#x)))(a''=")
where we recall that is the projection operator on X. Assuming that the input function f is L-- smooth, it follows that M (x') (L + 1)-Lipschitz. Furthermore, projecting the polytope X' takes polynomial time, and so .M is polynomial-time computable. As result, we can use Etessami and Yannakakis [2010, Proposition 2, part 2] (see also Fearnley al. [2023, Proposition D.1]), where it was shown that finding an e-approximate fixed point of Brouwer function that is efficiently computable and continuous, when the domain bounded polytope, lies in PPAD.
We proceed with the proof of Theorem 4.2
Proof of Theorem 4.2. We P-time reduce the problem of finding approximate symmetric NE in two-player symmetric games to SYMGDAFINEDPOINT. Given any two-player symmetric game with payoff matrices (R. R of size n, we set
1 R R (symmetric matrix) and C (R (R- (R-RJ) (skew-symmetric matrix). (23)
A
2
We define the quadratic, antisymmetric function
f(z, v) = 1 - Ay) Avy
J (2. Ax) + (y. Ca)
(24)
with domain A n x A Indeed, to see that f is antisymmetric, one can observe that
1
1 (y, Ag) + (ac, Cу) 2
1 , Ax) (y Ay) (y, C ()))= = f(x, (x, y).
f .) 2 (ar, Az)
2
Assuming that all entries of R lie in [-1, 1, 1], it follows that the singular values of A and C are bounded by n. As result and V
-Ax Cy. Vuf Ay Ca are polynomial time computable and continuous, and V Vaf. V are L-Lipschitz for L < 2n, thus f is 4n-smooth.
We assume is the minimizer and y is the maximizer, and let (x". xx)) be e-approximate fixed point of GDA. We shall show that (æ=" xx) is an 4ne-approximate NE of the symmetric two-player
game (R, R T). Since (a",x")) is an e-approximate fixed point of GDA, we can use Lemma A.5 and obtain the following variational inequalities:
max
8 +Aa"+Car
+Cx" (2n + 1),
+ 5E =
implying that (since the diameter of A / in E2)
(xr xx" (A C)=*) 2e (2n 1) for any A
(VI for NE)
Now, we observe that (VI for NE) implies that (x" xx) is a /2 (2n + 1)-approximate symmetric NE in the two- two-player symmetric game with payoff matrices (A C, A C) (recall Definition (2.1)).
Since /2e (2n 1) < 4ne for 2, our claim follows.
By Theorem 2.2 and Lemma 4.1, we conclude that SYMGIDFFXEDPPOIT is PPAD-complete, even for quadratic functions that are Omn)-smooth ((n) Lipschitz and S 1/1 for any > 0. D
20

---

We next state standard lemma that connects first-order optimality with the fixed-poii gap of gradient ascent.
Lemma A.5 (lGhadimi and Lan, 2016), Lemma 3 for 1). Let ((x) be an L-smooth function in a E A Define the gradient mapping
G(w) = II Vaf(2)) a.
n
If I|IG(""))22 S e, that is, x² an e-approximate fixed point of gradient ascent with stepsize equal to one, then
max +0EA" 1611
Vaf(x*) S c(L
Similarly, the next lemma makes such connection for min-max optimization problems with coupled constraints; it is mostly extracted from Daskalakis et al. [2021, Section B.2].
Lemma A.6. Let f(x, y) be G-Lischiitz, L-smooth function defined some polytope domain D x R of diameter D. Define the mapping
G(x, y)
II {I Vaf(x, y). v vyf(x, (x, D
If (GG("",y")] S e, that is, (x", (x",y") is an e-approximate fixed point of (the safe version) of GDA with stepsize equal to one, then
(x xx=x', Vnf(x" (af()),y")) 2 - VVK for x E D(y") and (y y", Vuf(x" yy)) & VcK for E D(x*),
where D(x*)= = ty: (x""9) E D(y)) = {o (x, y²) D) and K = (L+ 1) 1)
D(y")
4V+
Proof. Let (IS, ya) = (x* Vn/(w" y y) 3 + V yy)). )). In Daskalakis et [2021, Claim B.2], it was shown that for all (a, y) E D, we have
((os, ya) (x" (x,z) (x", y S (G (G+27 2D)e.
Using the above inequality, it was concluded that (x",, y²) is an approximate fixed point of the "unsafe" version of GDA; specifically,
II fx" - V=l(x") $ VVG++DD) D(v")
x
and
y
II D(
(v' Vys("" yy)} S SV(G +00+200 +D)e.
We now Lemma A.5 for both inequalities above, together the fact that D 2v2, conclude that
(x - x Vaf(x" y²)) 2 - for æ E D(y").
and
y" V Vyf(#' v²)) V ( for y D(x*).
We proceed to establish Theorem 4.4.
Proof of Theorem 4.4. The proof follows similar steps with Theorem 4.2, namely, P-time reduce the problem of finding approximate symmetric NE in two-player symmetric games to GDAFIXEDPOINT with coupled domains. Given two-player symmetric game with payoff matrices (R, R of size n x n, we set A = [R+R] (R+R)), C= [R RR) and define again the quadratic, antisymmetric function
1 y,, Av) (c. Az) (y. Cx).
f(x, 4) 2
2
21

---

Moreover, given a parameter å > 0 (to be specified shortly). we define the joint domain of f to be = { y) A x A - z;- - y S for all e [n]]
(joint Domain)
Let (a", yy) be c-approximate fixed point of GDA. We will show that 2: 2-"-"" 2*
is
2
-appo-aaaaoo (symmetric) NE of the game (R, RT) for an appropriate choice of
We set D(x") {y yx D) and D(y") fx (æ. y²) E D). In words, D(z*) and D(y")
capture the allowed deviations for y and æ respectively. It also holds that f is G-Lipschitz continuous with G 4n and also 4n-smooth (using the same reasoning as in Theorem 4.2).
Since (x" yy) is an e-approximate fixed point of GDA, using Lemma A.6, the following VIs must hold for some positive constant K 10 and n sufficiently large:
(x - x², - Ax + C yTy") 2 KKn Ve for any E DDy")) and yy - y Ay + Cx") < Kn3/2 Ve for any D(x*).
(25)
Let D { 2 A":
| トリ
-
S 2 By triangle inequality, it follows that D S D(y*)
00
D(x*). We express the VIs of (25)
using single variable and common deviation domain:
(z x², Aa + C y") 2 - K K2 VE and (z y² Ay" + Cx*) Kn for any E D.
Multiplying the first inequality by - -1/2 and the second with 1/2 and adding them up gives
x' + x
x + y
(A
S 4
(x* y, A((x" y²)) + Kn Ve.
(26)
2
2
Since x,, y E D, it follows that (x* - y² A(xx - -y')) s n||x0* - y S n28 Combining this fact with (26), conclude that
x² " 2
Ex + y²
2 (A+C)
S n2²p² + Kn3/2 Vc for any 2 E D.
(VImedian)
2
(VImedian) shows that by deviating from x =" by more than (n²8² + Kn3/2 Vt) in the two-player symmetric game with matrices (R. T.). We consider any pure strategy ej for j E [n]]. If ej captured by (VImedian). Suppose that [ej x= +y
+ 2
to some z in D, the payoff cannot increase
ty"
< then ej E D and it is
and consider the point z' E D on the line segment between ej and * *' that intersects the boundary of 'D. It holds that ej x +y"
12'-='0 tv for some positive < (it cannot be larger because otherwise the infinity norm of the difference between e, and x² -v would exceed one, which impossible they both belong to A)). Therefore,
xx''=tt""
2
x
+ 2 (A+C)
x + y
2Kn Vé
e
< 2n
for any pure strategy j. (27)
2
8
From (27), we conclude that x * is (2n28+ + 2kn -approximate NE of the symmetric 5
two-player game (R, JJ). We choose approximate NE for (R. R T), and thus the hardness result holds for of order O (+++) for any constant e > O. We note that if instead of an e-approximate fixed point of GDA, we were given an 6-approximate first-order NE, then the hardness result would hold for any of order " with 0.
e//4n= 1/4 and we get that 2'+y" is an O(n7/4
D
22

---

0
0
-2
2
0
-2
0
0
0
0
0
2- 0
-1
Figure 1: An example of matrix A AG) (right) for graph G' (left).
A.4 Proofs from Section 4.2
The main result we want to show is restated below.
Theorem 1.6. For symmetric min-max optimization problem, constants C1, O2 >> O, and n n it is NP-hard to distinguish between the following two cases under the promise that one of them holds:
any e-first-order Nash equilibrium (x",y") .y") there an e-first-order Nash equilibrium (xx yy) such that a y (11).
satisfies ||a=* - y S n2, and
Our reduction builds on the hardness result of McLennan and Tourky [2010] in turn based on earlier work by Gilboa and Zemel [1989]. Conitzer and Sandholm 2008]-which we significantly refine in order to account for poly (1/n) -aNsh equilibria. We begin by describing their basic approach. Let G = ([m], F.) be an n-node, undirected, unweighted graph, and construct
if if [i.j] otherwise.
Aij
(28)
(Figure 1 depicts an illustrative example.) Based on this matrix, McLennan and Tourky [2010] consider the symmetric, -aantff, two-player game (A, b) construction, A and so this game is indeed symmetric. They were able to show the following key property.
Lemma A.7 (IMcLennan and Tourky, 2010]). Let Cs S [n] a maximum clique of G with size k and x² = E e. Then, (x"xx") is Nash equilibrium of (A, A) that allains value T Furthermore, any symmetric Nash equilibrium not in the form described above has value at most
)
The idea now is to construct new symmetric, identical- game (B, B), for
A1,1
A A
B =
(29)
A A
V
where V -- and r (-1 (1)
2k 1 2(k-1)k 1)k- Coupled with Lemma A.7, this new game
yields the following NP-hardness result.
Theorem A.8 ([McLennan and Tourky, 2010]). It is NP-hard to determine whether a symmetric, identical-payy payofff. two-player game has unique symmetric Nash equilibrium.
Our goal here to prove a stronger result, Theorem 4.7, that characterizes the set of e-Nash equilibria even for 1/ne; this will form the basis for our hardness result in min-max optimization and adversarial team games. To do so, we first derive some basic properties of game (29).
Game (29) always admits the trivial (symmetric) Nash equilibrium (ea+1, en+1). Now, consider any symmetric Nash equilibrium (x* x²)) with 2;+1 # If x O, it follows that (af....)) ) a Nash equilibrium of (A, A), which in turn implies that admits clique of size k; this follows from Lemma A.7, together with the fact that -1/(k-1) r -1/k.
We now analyze the case where +1 (0, 1). then follows that (#fi...t/ (1-mm//111=1100)) -x (1 is (symmetric) Nash equilibrium of (A, A). Furthermore, the utility of playing action an-1 is
23

---

(1 1)t1)r + z 2 V > a value of V and G admits a clique of size k. As result, the utility of playing any action d₁ with i supp(æ") and i A n is J +++1VV +V + At the same time, the urility of playing action an+1 reads (1 - +1 + + V. Equating those two quantities, it follows that xhat x+11 = 1/2.
By Lemma A.7, it follows that (si 1)), -ft..n//(1ss (1)) has
In summary, G contains a clique of size k if and only if game (29) admits a unique symmetrie Nash equilibrium, which implies Theorem A.8. What more, have shown stronger property. Namely, any symmetric Nash equilibrium of (B, B) has to be in one of the following forms:
1. (a"" x²) with x= = En+li 2. (x",,") with x=' = 1 à: LiEc, e₁, where Ck S [n]] is a clique in G of size k;
3. (#", with x= = jent1 + 1 Eiec, e,, where Ck S [rx] is a clique in G of size k. 2n
In particular, the equilibria in Items 2 or w-which exist iff G contains a clique of size k-are far from the one in Item 1. However, this characterization only applies exact Nash equilibria. In any two-player game r, when e is sufficiently small with log(1/c) s poly([r)), Etessami and Yannakakis [2010] have shown that any e-Nash equilibrium is within & diddistnnce ó from an exact one, and so the above characterization can be applied; unfortunately, this does not apply (for general poly(1/n).
are always
games) in the regime we are interested, namely
We address this challenge by refining the result of McLennan and Tourky [2010]. Our main result, which forms the basis for Theorem 1.6 and Theorem 3.5, is recalled below.
Theorem A.9. For symmetric, identical -intreest, two-player games, constants C1, C2 > 0, and E = 72 9, it is NP-hard to distinguish between the following two cases:
any two symmetric c-Nash equilibria have & didistance at most n -0, and there are two symmetric c-Nash equilibria that have Ey-distance 12(1).
Our reduction proceeds similarly, but defines to be the adjacency matrix of G with ó E (0, 1) in each diagonal entry. Using A, we show that we can refine Lemma A.7 of McLennan and Tourky [2010]. Before we state the key property prove in Lemma A.11, we recall the following definition.
Definition A.10 (Well-supported NE), A symmetric strategy profile (æ, æ) is an e-well-supported Nash equilibrium of the symmetric, ddentical-payoff game (A, A) if for all E [n].
J3 0 (Ax); 2 max (Ax); -e
JE(n)
Lemma A.11. Suppose that the maximum clique in G is of size k. For any symmetric c-well-supporte NE (á, .t) of (A, A) not supported on clique of size k, we have u(@ Ø) <
n + 2e.
Equipped with this property, we will see shortly that similar argument to the one described earlier concerning game (29) establishes Theorem 4.7. We proceed now with the proof of Theorem 1.6.
Proof of Theorem 1.6. suffices to consider the antisymmetric function f(x y) = y TBy BBy=' x Tax where symmetric matrix B defined as in (29), using our new matrix A instead of A (see (32)). Any e-first-order Nash equilibrium (x",y") ) of this (separable) min-mat optimization problem induces, two symmetric e-Nash squilbbria-namele (x", ,x") and (y", y " the symmetric, identical- interest, game (B, B). Using Theorem 4.7, the claim follows.
B).
In what follows, our goal is to establish Theorem 4.7, which forms the basis for Theorems 1.6 and 3.5.
We consider the symmetric game (A,A)) ), where A E gnxn is symmetric matrix. In particular, since A = A the two players in the game share the same payoff matrix. The payoff matrix A is constructed based on an underlying graph G ([n], E¹) and a parameter å (0, 1) as follows:
8 if j,
Aij
1 if (i.j) E E, otherwise.
24

---

Lemma A.12. Let (ž, be an e-well-supported NE of the game where & is supported on max clique of size k, denoted as Ck. then the value u ②) is at least + | 100 S &- where x² 1 Eiec e.
&
B k-d
T ) and
Proof. Since d is supported on Ck. let i be coordinate that o puts the least probability mass that is, E argmingec. .y. Considering the utility of playing action ús we have
u(e;, ab) = f 5 + (1 - - 1 = 1 c + 5.6.
Moreover, let E Cg be a coordinate such that 3; 2 1 E. should hold that
8
" " x)) = (1 880, S
+
k
Since (.) is an e-well-supported NE, have
u(ej. ②)
2 u(e, .) -
1
1
+ + 2 1 - 24 + 22,0
k
8 z k 1-6
Thus, for all coordinates E Cs we have
1
S 8; S
1 (k - 1). then holds that
u( x) 2 u(ei, 3)
(1
1
+ 1
(k - 1)
8 +
(h: 1)
k 1-8
1 i
k 6
2
+
k
K
Assumption A.13. For the rest of this subsection, we set the parameters as follows:
n 2 k 2 10;
8(1 - 8)/nn?
6 1/2.
(Using the symbolic value of 5 is more convenient in our derivations below.)
Proof of Lemma A.II. We let x= 1/4 Eiec, e,, The proof considers the following three cases:
The symmetric c-elol-sppported NE (#, .) has support size less than k.
The symmetric w-eel-suppoorted NE (#, .) has support size greater than
The symmetric e-wel--sppported NE (œ, a has support size equal but is not supported clique.
We proceed to show that for any of the three cases above, we would not be able to have symmetric e-well-supported NE that achieves value greater than
25 . + 2e, which a contradiction.
For the first case, since the support has size less than k. we can find a coordinate i [n] such that o; > --.. Therefore, the value of playing that action is
1
6
u( x) S
4:
25

---

Since (ž, is symmetric e-well-supported NE, we have
u( Φ) u(e; 2) +
1
8
$ 1
+
+
k
1
k
8
20
<
+
2e,
k
n²k4
where in the last step we use Assumption A.13.
For the second case, suppose |supp())] = > k. By Lemma A.1 since the maximum
clique size is k, we can find set S supp(Ø) with at least m k + 1 elements such that for each coordinate i S, can find coordinate j S such that Aij A,,i 0. Now we consider the utility of playing action dg and aj. we have
u(e; ())
Σ
f1 A., + 2; . 0 2.. Aiii
lEsuPp( (t,}}
u u(e,, .t) =
Σ
ă1 A + 83 + +2; Ai.j
[E (1.)
Since (á. .) is symmetric c-well-supporte NE, we have
Ai, 3t. 8 8 .t.
Aij
Σ
$1 Aj 5.. δ +
Aij
lEsipp (i.i)
(Exupp( hb) (1.)
Σ
31 A.,
Σ
St A 2 $g 5 - 2; 5 -.
(Esupp(a)
(i,j)
(Esupp(d)) (1.1)
Now, by moving all the probability mass from action j to action i, we form new strategy x' + 2.. e; 2;- e, such that
u(x', x²)) - u( = 24,
Σ
i1 Ai,
Σ
it
A.A A
+ 28: â 8
(Espp(()) (b) (3,1)
(Empp(()) (t.j)
2 2.. ((i, - 2::6 c) + 2 ... -8
2 2530 0 2e.
(30)
Suppose there is coordinate i E S such that 21 2
I
then, from (30), we have
nkz
u(t 2) u(x
2 xx=)-
) 88 2c
nk2
8
28
2c.
k
n² K-
If 2.
for any E S. then there exists coordinate 1 & S such that â1 > 1 (m - A+ 1): me2
Then, considering the utility when playing action as,
M [m - k+1)
1
1
u(er, x) S 1 (1
+
K
122
k2
1
8
+
k
222
122
1
8
28
+
(31)
k
where in (31) we used Assumption A.13.
Since the /th action is played with positive probability and (át, .)) is e-well-supported NE, we have u( .) u(ei, .) +
1
+
26
+ 2c.
n
26

---

For the third case, since the support is not on clique, the exists at least coordinates i, such that 0, > 0, 2. > O, and A = A = 0. Similarly as case two, if ã; 2 _ then we have
1. uहे or F.y 2 nkz
u( ④)) S u(x", ,x") - 22 )2
5 26
nk.
5 28
2c
k
n² k-
1-2 ub?
If i; nxz and 3 WEz then there exists an coordinate I such that 21 2
k-2
t + RZ. Same as (31), we conclude that u(t; ()) is at most $ + E n + 2e.
The proof is complete.
We now construct new symmetric identical payoff game (B, B), where B is defined as
A1,1
A
(32)
A
An,
Above, = + and = 1-
+
g + 3e. Similarly to our discussion after
Theorem A.8, it follows that the symmetric (exact) Nash equilibria of this game can only be in one of the following forms:
1. (w", w²) with x² = Entli
2. (a",x") with x=" = Lieo Ci where Cs S [n]] is a clique in G size k;
3. (x* x²) with x en= + z Eiec, ei where Ck S [m]] is clique in G of size k.
We now show the following lemma.
Lemma A.14. For any e-well-upported NE (æ, .)) game (B, B), holds that ||é 11o0 S 2n where (x"xx") is an exact NE in one of the three cases above (1,2,3).
Proof. First, we observe that since V т, clearly (en+1, en+1) is a e-well-supported NE; in Furthermore, since r
this case, ||x' x 1loo not attain any e-NE with value less than symmetric e-well-supported NE (z. 2) where is supported only on the first actions. Since u( ()) | x0' 11. } 2n from Lemma A.
+ ममरर 3e, the game does & n2g4 + 2e. Suppose the game admits an
+ 1 nя 2E 1 - & + 8
5
лスं + 2e, taking x' in (2), we conclude that K
28
We proceed to the case where there is mixed symmetric c-well-supported Nash (æ, #) between the last action and the rest of actions such that < fz41 < 1. Denote 4x+1 = a and 17(-) to denote the renormalization operation. Since (,(())...)) (((1) is symmetric strategy profile, from McLennan and Tourky [2010, Proposition 4), we conclude that there is at least one coordinate i supp(@) {n + 1} such that
1
U (et, ((Q( S
=
K
where U is the utility when the payoff matrix is A. Since (n(() n(((..)))))) is c-well- supported NE, we have
up(e, 2) ug(ent1. -
(1-a) V a (1 air - +oV
(33)
2 2(V r)
where up is the utility function when the payoff matrix is B. Plugging in the value of V and r and using Assumption A.13, find that < }/2 + 2m < 2
27

---

Now, observe that for any action in the support other than the last action the utility of playing such action un un ②) u (a,, (0,, T()..)) ) + ra. Since (i, a) is an e-well-supported Nash Equilibrium, we have uB( uB(a,, ②) 2 max, up(aj. ②) - -e for all pairs (i,j) E supp(á). Since a S 3' it follows that WA (as, 77 (()))))))) 2 max; un (a ((111.)))))))))))))))))))))))))) - 3e for any pairs (i E supp(#) (n Thus,, we conclude that (n(()....)) ( (((())))))) forms a symmetric 3c-well-supporte Nash Equilibrium in game (A, A). Further, the value of playing the last action (1 a)r + aV т, and so the only situation where there is mixed Nash between the last action and the rest actions is when uA ((1(d) (...)) ((())))))))) 2 e. Therefore, by Lemma A.12 and Lemma A.11, we conclude that [1...n supported on clique of size k. There exits at least one coordinate E [n], with &;
and &; 2 F such that
8 V.
u.A MA(es, ((0 21 1 k
Since (œ. à) is an e-well-supported Nash, we have u(e, 2) 1 u enn+1 3) + e, and so this gives
(1 (1-a) V +a (1a- Vc
(34)
= a 2 2(V - r)
(35)
Using Assumption A.13 and combining with (33),
2 - 2m S a 2
+ c
By taking x² in (3), we conclude that | - x x=1l 11:0 S 2
Theorem A.15. For any c-NE (ar, x)) in game (B, it holds that || =x0ll S no ne,e, where (x", x²) is an exact NE in one of the forms specified above (1,2,3).
Proof. Chen et al. [2009, Lemma 3.2] showed that from any e2/8-NE (x, y) in any two player bimatrix game, one can construct (in polynomial time) an e-well-supported NE (a', 3') such that 2
|| x'll S and |yy y'lloc S 4. Setting e' == g for the e defined in Lemma A.14, the proof follows.
The proof of Theorem 4.7 follows directly by observing that having two symmetric e-NE (æ, x) and (y, y) such that || - ylloo > 2n /e would imply that the game (B, B) has two distinct exact NE, which in turn implies that there a clique of size in the graph.
We next state and prove an auxiliary lemma that was used earlier.
Lemma A.16. For any graph G = EV, with n vertices, if the maximum clique has size k. then we 1 such that for any vertex E S, there exists a vertex
can form set S C V of size at least j E S such that i and are not connected.
Proof. Suppose the largest set S we can form has cardinality |S| < n k 1, this implies there is 8 V S with at least (n k) k vertices such that each vertex S' connected to all other vertices in G. However if this is the case, there is at least one vertex & S' that are connected all vertices in S'. This contradicts the fact that maximum clique has size k.
We proceed now with the proof of Theorem 1.6.
Proof of Theorem 1.6. It suffices to consider the antisymmetric function f(x y) = y TBy Ba. where symmetric matrix B defined as (29), using our new matrix instead A (see (32)). Any e-first-order Nash equilibrium (x", of this (separable) min-max optimization problem induces, two symmetric 6-Nash equilibria-nmmely (a=", x .x*) and (y* (y",y")= --i the symmetric, identical- interest, game (B, B). Using Theorem 4.7, the claim follows.
D
28

---

A.5 Proofs from Section 4.3
conclude with the missing proofs from Section 4.3. We first introduce two lemmas which are useful in later proofs.
The first key lemma, which mirrors Lemma 3.2, shows that, an approximate Nash equilibrium of (4), x y and & x ÿ. This is crucial as it allows us to construct-up to some small error-quain quadraiiiiiic terms in the utility function, in our hardness result for symmetric min-max optimization.
Lemma A.17. Let (x² yy 2", 2", "", 2²) )) be an e2-Nash equilibrium of (4) with e² S 1/2.. Then, | - y oo I 2E and -| - "" 1ooo S 2e.
Proof. For the sake of contradiction, suppose that ||= "y'l''l 1/0 > 2e. Without loss of generality, let us further assume that there is some coordinate such that x; Vr > 2e. The payoff' difference for Player when playing the ith action compared to action 42n+1 reads
Amiil
u(x",y", z" ,,,""" " a:) u(x",,0"0 ,2, ,2",," ; " a2n+1)
(x] - --,))= - |Aminl
6 A min|-
By Lemma A. it follows that 2 an e2-Nash equilibrium, we have u(x", .y 4. 2 x= 06 ) u(x yy 2² "², . 10 a.) -
<
Amin Se Moreover, given that (x", y.," 2"" ,0'0"""""" 2²)
(x" Ay") - " AA")) ) +
(a", Ca")
Amin
(---w,) 8(Ø, 0,
Amin
Ag") + (a", Ca") + 2 8( 2)
A
( + (x", Ca*) -
2
Now, considering the deviation of Player y to y x²,
u(x", y 2", .t" ",,""""""" 2²) uuxx", 3" 2" 2- "0' 2) < (w", Aax) + + |Aminl E²
S 2 + 2c
< -
which contradicts the fact that (x* ,,,"" x", 5², " 2²) is an
e² --Nash equilibrium. We conclude that
x y 10 I 2c; the proof for the fact that - " 1oc S 2e follows similarly.
Next, following the argument of Lemma 3.3, show that, in equilibrium, Players and & place most of their probability mass on action 02n-1, thereby having only small effect on the game between Players and y & and ÿ.
Lemma A.18. Let (x+ y², x=, x=, """"""""" 2) be an e-Nash equilibrium of (4) with S 1/10. Then, Zg, < 9E for all E [2m].
Proof. We will prove that zj < 9E for all [2n]; the corresponding claim for Player & follows similarly. Fix i [n]. Lemma A. shows that ly, x;1 < 2e. We shall consider two cases.
First, suppose that ly? 2;1 < 1/2. Then,
Amial
u(x" y² x" x= U" a2)+1) u(x" ,,,"","""0000 4", U" aa) Amiul
(x) vi)
A Amin
1
2
By Lemma A. it follows that ž; < 262, and similar reasoning yields ănti < 26 On the other
hand, suppose that ly x > s/2. Without loss of generality, we can assume that y/ x 2 O: the contrary case is symmetric. Since x" A and y A there is some coordinate j [n] such that
29

---

0 - < 0. As before, by Lemma A.I, it follows that 27 < and Entz S.. Now, we consider the deviation
A" 3 y' =y" + (x ve)e; + (vt 2z)es
Then, we have uxx",
y', x x², 0 2* u(x", ,y, 2²" ,,2",,0 ,", "8" )
A
A'y' y²)) +
(x) V/1 - [z] v()) + (z) 1/j (2] - 9J]))
Aminl
E (V = - (vt xf)) + E (1/) 2j - (v3 xz)))
(x=", Aly' yy')) + Aminl
(2) v/i) + [2] v/) 0 vl) + t (v/ w;))
Amiul (2-2c+ Entss : (-2) + 2² 26)
S
Ac||Aminl
5 - Ati - 462 - 4E /Aminl.
At the same time, since (x", y 2,=""" "0" G =*) is an e"-Nash equilibrium, we have
2) 2 2 u(x"; ,0,,",,"00 """""""" 2)) u(x" y 2 2= x "" ,,,²)
Thus,
1 b 4ea 4e |Aminl S 2 (
zx S 9c.
We conclude that द S 6 and 7/ S 9e. The case where ot Ve 2 0 can be treated similarly.
Armed with those two basic lemmas, we ready complete the proof of Theorem 1.7.
Proof of Theorem 1.7. Suppose that (x", yy" z", xt, D" 2² is an ea-Nash equilibrium. We have that for any y' E A
(a' Ay S (a",A))) Av) + Amiul
Σ " vi) + #04 vt') + +
(36)
Moreover, considering a deviation from x² to y',
(x' Ayy) + (a", Ca*) Sly', Ayy) + (y), Ca*)
Amin
n
(o - x;)) + Ehtsa - v/3 2.
(37)
Summing (36) and (37), 2(x",, Ayy) + (x=", Cá.) < (y'' A A(x + +y²)) + -C*"
Amill
Σ 2 (1g - x;) + 2m (x - vii)
+ 26
$ 2(x", Agy) + (y', Ca*) + 2en Aminl + Aminl
(2n 9c 92. 2e) + 26"
< 2(x", Agy) + (y', Cā*) + (38n + 2m]/miile..
(38)
Moreover,
(a", Ax') = (x= Ay") + (a A(a - vn)) <
+ 2|Ammn
(39)
Combining (38) and (39), we get that for all y' E A
(x,AA"') Axx) + 2 f Ct") S (v' Ax") + 2
(v/ Ct*) + (21n + Amimme
(40)
30

---

Similarly, we can show that for all ø' E A",
(- Aæ") ( Ca*) 2 - Aá") 2 (a', CC') (21n + A)jmmi (41)
Taking y' = '' in (40) and summing with (41), we get that for all '' E A",
} ( (#', Ax" + ( At") ((t', C#") + (ø', C2 ((2n)
(x" Axx) + Aū""
where used the fact that C is skew-symmetric. Now, using the fact that the Nash equilibrium is symmetric, so that x = x², we have
1 (á', Ca*) (21n + A 2 (x=" Ax") 2 Ax=", + (x" (x") (42)
(ø' Ax") + 2
2
Setting - RT) and R.T R. (42) shows that
(d' Rø < (a" RR=" + (21n + Amin|
for any #' E A ergo, (x xx is symmetric (21n+ 1)) Amiu |c-Nas Je-Nash equilibrium the symmetric (two-player) game (R, R ), and the proof follows from Theorem 2.2.
31

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We provide proofs for all the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We formally state all assumptions needed for our results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
All assumptions are stated in the main body and the proofs are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
ooniiicy))))) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.cooc wwtppppplcggcpiieeceeeeeooocoppe gttee/gggee///eee CCodeSubmiieeeeece
/ttpa////ggiieeeeeeeuubbiiiiiiii ierpommsssiiooooooiiiooooo (eionnolccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
34

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //te:r//n.....// cwwpurips.ccpuuueeeeeee
Answer: [Yes]
Justification: Ethics.
The research conducted in the paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do foresee any direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
37

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The development of the paper does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https htttps:/nneurps: http://rppp.cccoooffeerrreee//// cccc//omferrecccee222///1// for what should or should not be described.
38


Reviews:
[{"review_id": "ONH3xg4PV5", "reviewer": "Reviewer_3Gg9", "summary": "The paper considers several problems that arise in the context of\ncomputing approximate Nash equilibria (or stationary points) in\ngames that involve two teams. Such problems are important in game\ntheory and they been studied by a number of researchers.  The current\npaper settles the complexity of several problems that were left\nopen by previous work on the topic. The results make a nice\ncontribution to the area.", "questions": "(1) The footnote on page 3 mentions that symmetric zero-sum games are\nubiquitous in practical scenarios. It will be very helpful to\ncite a few references to emphasize that point.\n\n(2) Lines 125--132: In discussing the work of Bernasconi et al. [2024]\n(who established Theorem 1.5 in the current paper independently)\nyou mention that your proof applies to simplex domains while their proof\napplies to box domains. Can you please clarify the difference between the\ntwo domains? In particular, is your proof applicable to a larger class of\nproblems compared to that of Bernasconi et al.?\n\n(3) Theorem 1.7: You show this result for 6-player games (i.e., 3 in each team).\nAre there any known complexity results for games with a smaller number of\nplayers? Or is that an open problem as well?\n\nA minor suggestion: In the bibliography, many references don't have complete\ncitations.  For example, many references are missing page numbers,\nsome arXiv papers don't have their arXiv IDs, etc. Since there is no limit\non the number of pages devoted to references, please include complete\ncitations.  Also, in some of the titles, words like \"Nash\" are not\ncapitalized. Please correct these in a future version of the paper.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n(a) The problems are of importance in game theory, a topic that\nhas assumed a lot of importance in AI. The paper provides a very good\ndiscussion on the current state of the art regarding the problems \nconsidered.\n\n(b) The paper settles the complexity of several open problems on\nthe topic of approximate Nash equilibria for games involving teams. \n\n(c) The proofs (inlcuded in the supplement) are quite non-trivial.\n\nWeakness:\n\nAs far as this reviewer can tell, the paper doesn't appear to have any\nmajor weakness. There are two (very) minor weaknesses due to the nature of\nthe results.\n\n(a) The results are likely to be of interest to a limited group \nof researchers. \n\n(b) The paper provides a fair amount of intuition regarding the results\nand constructions. Despite this, readers not familiar with the technical\nideas may find the paper somewhat difficult to understand.", "was_revised": true, "final_justification": "I have read all the reviews, rebuttals and the subsequent discussion. I am glad to see that  the reviewers are unanimous  in recommending the acceptance of this paper. It s indeed an excellent contribution to the literature on game theory.", "rebuttal": "We thank the reviewer for their valuable time and positive comments. \n\n> \"The results are likely to be of interest to a limited group of researchers.\"\n\nAlthough some of the techniques we employ are specialized, we believe that the main takeaways of our results should be of interest quite broadly to the NeurIPS community. Many central problems in machine learning and reinforcement learning can be cast as min-max optimization problems, such as adversarial training and GANs. Our results contribute to understanding the fundamental barriers concerning min-max optimization problems and adversarial team games, and provide an explanation for why natural gradient-based algorithms often fail to stabilize in nonconvex-nonconcave settings. \n\n> \"The paper provides a fair amount of intuition regarding the results and constructions. Despite this, readers not familiar with the technical ideas may find the paper somewhat difficult to understand.\"\n\nWe thank the reviewer for this feedback. We will provide further details concerning the key technical ideas in the main body in order to make the paper more accessible in the revised version.\n\n> \"The footnote on page 3 mentions that symmetric zero-sum games are ubiquitous in practical scenarios. It will be very helpful to cite a few references to emphasize that point.\"\n\nMany popular recreation games commonly used for AI benchmarking, such as poker and battleship, are symmetric games; the symmetry assumption is especially natural since it guarantees that no player has an a priori advantage before the game begins. Also, the most common examples in game theory, such as rock-paper-scissors and matching pennies, are symmetric; such games were already present in the original work of Von Neumann [1, p.303]. We will include this discussion in the revised version.\n\n> \"Lines 125--132: In discussing the work of Bernasconi et al. [2024] (who established Theorem 1.5 in the current paper independently) you mention that your proof applies to simplex domains while their proof applies to box domains. Can you please clarify the difference between the two domains? In particular, is your proof applicable to a larger class of problems compared to that of Bernasconi et al.?\"\n\nThe starting point of our reduction and the resulting hard class of min-max optimization problems is different from that considered by Bernasconi et al., both in terms of the domain and the underlying objective function. It is important to note that the domain crucially affects the complexity of the problem. For box constraints, solving linear VIs with even a constant accuracy is PPAD-hard [2]. On the other hand, for constant accuracy and under simplex constraints, there is a well-known quasipolynomial-time algorithm [3]; one needs to have inverse polynomial accuracy to get PPAD-hardness under simplex constraints [4]. Besides the difference in the domain, our class of problems is symmetric, which enables us to prove hardness for computing symmetric equilibria. \n\n> \"Theorem 1.7: You show this result for 6-player games (i.e., 3 in each team). Are there any known complexity results for games with a smaller number of players? Or is that an open problem as well?\"\n\nThe basic reason we are only able to obtain hardness results for 3 vs. 3 (instead of 2 vs. 2) team zero-sum games is that the symmetry gadget we introduce (Line 223) requires two players ($x, y$) on one team and another player ($z$) to be on the other team. As a result, in team zero-sum games, since we need to enforce symmetry in both teams, a total of 6 players is the best we can achieve. It is an interesting open problem to see if we can extend the hardness result to 2 vs. 2 team games, but we believe this would require additional technical ideas.\n\n> \"In the bibliography, many references don't have complete citations. Also, in some of the titles, words like \"Nash\" are not capitalized. Please correct these in a future version of the paper.\"\n\nWe thank the reviewer for pointing this out. We will correct the inconsistencies in the bibliography in the revised version.\n\n________\n\nReferences:\n\n[1]  Von Neumann J, Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100:295–320, 1928.\n\n[2] Aviad Rubinstein. Inapproximability of Nash equilibrium. In Proceedings of the fortyseventh annual ACM symposium on Theory of computing, pp. 409–418, 2015.\n\n[3] Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM conference on Electronic commerce, pages 36–41, 2003.\n\n[4] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14:1–14:57, 2009."}, {"review_id": "qN8pWmFHUR", "reviewer": "Reviewer_BBrE", "summary": "The paper makes significant progress in understanding the complexity of special classes of min-max optimization. In particular:\n\n**Team zero-sum games (of which team adversarial games are a special case)** The authors show that this class of problems is CLS-complete by reducing to an earlier result from (Ghosh and Hollender, 2024) for symmetric identical-payoff 2-player games.\n\nMoreover, they show that deciding whether an adversarial team game has an approximate unique equilibrium is NP-hard.\n\n**Symmetric minmax games** They define the computational problem SymGDAFixedPoint and show that it is PPAD-Complete. \nFor the computational problem NonSymGDAFixedPoint, they show it is NP-hard.", "questions": "1. The paper is motivated with examples in robust ML, GAN training etc. Do the special classes of games considered directly apply to these settings? If not, what insights can extrapolate to practical settings? \n\n2. How do the results extend to more than two teams, or games with overlap between teams?", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n**Significance** Understanding the complexity of min-max equilibria is both a very interesting problem from a theoretical perspective, and has relevance to the many places that such problems are now deployed in machine learning over the past few years.\n\n**Originality** The reductions that the authors design to obtain their results is interesting, novel and presented clearly.\n\n**Quality** The authors resolve questions about both small-constant adversarial team games and symmetric min-max problems, achieving tight CLS- and PPAD-completeness results where only partial bounds were known previously.\n\nThe authors provide a very comprehensive set of results, covering both existence (search) and uniqueness (decision) problems, two- and multi-team games, polymatrix and quadratic objectives, and both symmetric and non-symmetric equilibria, giving a unified view of the landscape.\n\n## Weaknesses\n\n**Clarity** The paper is quite difficult to read with each result presented twice -- first informally in the introduction and then in more detail in the main technical sections. I am not immediately sure how to address this, but it would be useful to make it more accessible to a broader NeurIPS audience", "was_revised": true, "final_justification": "The authors address my concerns in the rebuttal so I stick with my score.", "rebuttal": "We thank the reviewer for their valuable time and positive comments.\n\n> \"The paper is quite difficult to read with each result presented twice -- first informally in the introduction and then in more detail in the main technical sections. I am not immediately sure how to address this, but it would be useful to make it more accessible to a broader NeurIPS audience\"\n\nWe provided informal versions of the main results in the introduction with the intention to make the paper more accessible and highlight the key takeaways without having to dive into the rigorous statement and technical details. We are happy to make any changes as the reviewer sees fit.\n\n> \"The paper is motivated with examples in robust ML, GAN training etc. Do the special classes of games considered directly apply to these settings? If not, what insights can extrapolate to practical settings?\"\n\nThe main insight of our paper concerning such settings is that it is unlikely that there are general-purpose gradient-based algorithms that converge in a reasonable amount of time without making strong assumptions regarding the underlying optimization landscape. That being said, our hardness results do not rule out having efficient algorithms for more structured objectives and specific domains. For example, our current approach encompasses simplex or box constraints (hypercubes), but some problems are more naturally expressed in terms of $\\ell_2$ ball constraints, such as GANs. Extending our hardness results to such settings is an interesting direction for future research.\n\n> \"How do the results extend to more than two teams, or games with overlap between teams?\"\n\nFirst, regarding games with more than two teams, three-player zero-sum games (that is, each team comprising a single player) are known to capture two-player general-sum games by adding a “dummy player.” So PPAD-hardness follows directly in that more general setting.\n\nWhen it comes to games with overlap between teams, we assume that the reviewer refers to situations where some players can change teams, either due to a strategic choice or because of some external stochasticity. This seems to us a very interesting direction for future research."}, {"review_id": "lxJk0E6kq5", "reviewer": "Reviewer_1qji", "summary": "The authors considered the hardness of computing symmetric equilibria in zero-sum games and utilized the hardness result in this area to show the hardness of computing equilibria in 3-player (2 versus. 1) adversarial team games. Using a carefully-designed adversarial team game that enforces the strategy of the two players in the same team to be approximately the same, the authors showed that 3-player adversarial games, and in particular 3-player adversarial polymatrix games, can be reduced from calculating a symmetric equilibrium in a symmetric two-player games, which is known to be CLS-complete. The authors then considered the problem of computing Nash equilibria in symmetric n-dimensional min-max optimizations, and showed that the problem is PPAD-complete, by providing a polynomial-time reduction from calculating symmetric Nash Equilibrium in two-player symmetric games, which is known-to be PPAD- complete. Based on this, the authors constructed a 6-player team (3 versus 3) zero-sum polymatrix game, and provided a polynomial-time reduction to computing Nash equilibria in symmetric min-max optimizations, therefore demonstrating that computing Nash equilibrium in this 6-player team zero-sum game is PPAD-complete. Finally, the authors demonstrated that for certain games, it is NP-hard to determine whether or not there exists a approximately symmetric $n^{-c}$-approximate Nash equilibrium.", "questions": "* It is interesting that for symmetric games, all accurate Nash equilibria must be symmetric, whereas some approximate Nash equilibria are allowed to be slightly asymmetric. If some regulations are enforced on a symmetric game (say Lipschitz continuity of the payoff), can one understand a bit more about the hardness landscape?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The proof of this paper is sound. The authors provided a complete characterization of the hardness of calculating Nash equilibrium in two-team zero-sum games, and made progress towards understanding the hardness of calculating symmetric Nash equilibrium in general symmetric yet nonconvex-nonconcave setting.\n* The results are important from game-theoretic perspectives.\n* The reductions the authors provided are indeed original interesting.\n\nWeaknesses:\n* When overviewing the results in Section 1, it might be helpful to refer directly to the theorems in later sections. For example, I find the discussion around Theorem 1.5, as well its demonstration, to be a bit confusing; it might help if the authors could relate it more directly with Theorem 4.2. Furthermore, the author could provide a more clear contrast between their settings and the settings considered by Daskalakis et al. in 2021, when they discussed Theorem 4.4 in Section 1.", "was_revised": true, "final_justification": "The authors addressed my questions and concern, and thus I will maintain my score.", "rebuttal": "We thank the reviewer for their valuable time and positive comments.\n\n> \"When overviewing the results in Section 1, it might be helpful to refer directly to the theorems in later sections. Furthermore, the author could provide a more clear contrast between their settings and the settings considered by Daskalakis et al. in 2021, when they discussed Theorem 4.4 in Section 1.\"\n\nWe thank the reviewer for the suggestion. In the revised version, we will spell out the relation between the statements in Section 1 and the subsequent statements.\n\nWith regard to the comparison with Daskalakis et al. [1], as we highlight in Lines 298-299, the equilibrium notion we consider in our work is stronger compared to theirs. Specifically, if one takes a symmetric constraint $x \\approx y$ in their notion, Player $x$ is only allowed to deviate to a specific set of strategies nearby $y$ (in order to satisfy the symmetry constraint), whereas our hardness results allow $x$ to unilaterally deviate to any other strategy. In other words, our reduction captures what Daskalakis et al. [1] refer to as “safe GDA fixed points,” which can be different from the usual GDA fixed points. We will highlight this difference in more detail in the revised version.\n\nMoreover, our work improves on the results of Daskalakis et al. in the following key ways: i) our reduction and proof are significantly simpler, making it easier for follow-up research to build on it; ii) our hardness result applies even when the accuracy parameter is constant, which is relevant in modern ML applications where one is often content with a crude solution quality; and iii) our class of functions comprises only simple quadratic functions, whereas the class of functions constructed by Daskalakis et al. is very involved.\n\n> \"It is interesting that for symmetric games, all accurate Nash equilibria must be symmetric, whereas some approximate Nash equilibria are allowed to be slightly asymmetric. If some regulations are enforced on a symmetric game (say Lipschitz continuity of the payoff), can one understand a bit more about the hardness landscape?\"\n\nMany of our reductions leverage the symmetry gadget we design (Line 223), which can be thought of as a “regularizer” that enforces symmetry. One limitation of that gadget is that it can only enforce symmetry between players in the *same* team. As the reviewer alludes to, it would be very interesting to create a gadget that enforces symmetry between players from *different* teams; this is indeed the crux to showing PPAD-hardness for min-max optimization, and would go a long way to settling the hardness landscape.\n\n________\n\nReferences:\n\n[1] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Symposium on Theory of Computing (STOC), 2021."}, {"review_id": "9b8sqpKvAP", "reviewer": "Reviewer_JDAf", "summary": "The paper provides many lower bounds related to the problem of computing equilibria of team zero-sum games and min-max optimization, with a focus on symmetric solutions. The authors show that computing $\\epsilon$-Nash equilibria in 3-players adversarial team games is CLS-complete. Moreover, they show that computing symmetric first-order equilibria in symmetric min-max optimization is PPAD-complete and computing symmetric $\\epsilon$-Nash in symmetric team zero-sum games is PPAD-complete. As a consequence, they show that symmetric dynamics cannot converge to stationary points. Finally, they show that computing non-symmetric equilibrium in min-max optimization is FNP-hard.", "questions": "None.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper includes a large set of interesting results. All the results are on very simple instances, e.g., small number of players or quadratic functions, making the results stronger. Moreover, the proofs are simple and easy to follow. \n\nWeaknesses: \n\n- Some results are very similar to or heavily based on previous works and not technically very involved.\n\n- The paper could do a better job highlighting the similarities and differences with previous/concurrent works, especially with the other works in the min-max optimization literature.\n\nFor instance, Theorem 4.6 should already follow from the reduction in Daskalakis et al. [2021]. Indeed, if the two dynamics start with $x=y$, the two players observe the same gradient also in their construction. Even if not explicitly stated, their hardness result should hold for symmetric equilibria in unconstrained domains.\n\nThe differences and similarities with the works of Bernasconi et al. [2024] are not very clear. At least at a high level the construction is very similar. It seems that the main difference  is in the domain, which requires to reduce from different problems and leads to different approximations.", "was_revised": true, "final_justification": "My positive evaluation of the work is unchanged.", "rebuttal": "We thank the reviewer for their valuable time and positive comments.\n\n> \"Some results are very similar to or heavily based on previous works and not technically very involved.\"\n\nWe consider the relative simplicity of our approach as a strength since it will make it easier for future research to build on our paper. In particular, among others, we are able to recover and strengthen the results of Daskalakis et al. [1] that were especially involved. We believe that our simpler framework will enable building on our approach for this fundamental problem.\n\n> \"The paper could do a better job highlighting the similarities and differences with previous/concurrent works, especially with the other works in the min-max optimization literature.\"\n\nRegarding the differences between our work and Daskalakis et al. [1], we highlight the following key improvements: i) as we pointed out above, our reduction and proof are significantly simpler; ii) our hardness result applies even when the accuracy parameter is constant, which is relevant in modern ML applications where one is often content with a crude solution quality; and iii) our class of functions comprises only simple quadratic functions, whereas the class of functions constructed by Daskalakis et al. is very involved.\n\nAlso, we point out that the equilibrium notion we consider is stronger. The main issue is that in their setting, when a symmetry constraint $x \\approx y$ is enforced, Player $x$ can only unilaterally deviate to a small set of strategies nearby $y$ in order to satisfy the constraint. On the other hand, our notion allows Player $x$ to unilaterally deviate to any other strategy. Essentially, our reduction captures what Daskalakis et al. [1] refer to as a “safe” version of GDA fixed points, which can be different from usual GDA fixed points — Bernasconi et al. [2] provide an explicit separation in Appendix B.1 of their paper. For this reason, we do not believe that our Theorem 4.6 follows directly from the reduction of Daskalakis et al.\n\nRegarding the differences with Bernasconi et al. [2], the starting point of our reduction and the resulting hard class of min-max optimization problems is different from that paper, both in terms of the domain and the underlying objective function. It is important to note that the domain crucially affects the complexity of the problem. For box constraints, solving linear VIs with even a constant accuracy is PPAD-hard [3]. On the other hand, for constant accuracy and under simplex constraints, there is a well-known quasipolynomial-time algorithm [4]; one needs to have inverse polynomial accuracy to get PPAD-hardness under simplex constraints [5]. Besides the difference in the domain, our class of problems is symmetric, which enables us to prove hardness for computing symmetric equilibria.\n\nWe will highlight at greater length those differences in the revised version.\n\n________\n\nReferences:\n\n[1] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Symposium on Theory of Computing (STOC), 2021.\n\n[2] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Gabriele Farina. On the role of constraints in the complexity of min-max optimization, 2024.\n\n[3] Aviad Rubinstein. Inapproximability of Nash equilibrium. In Proceedings of the fortyseventh annual ACM symposium on Theory of computing, pp. 409–418, 2015.\n\n[4] Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM conference on Electronic commerce, pages 36–41, 2003.\n\n[5] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14:1–14:57, 2009."}]

Author rebuttal:

Meta-review: This work investigates the computational complexity of equilibrium computation in adversarial team games. Compared to related works such as Daskalakis et al, the authors develop a reduction technique to provide some new contributions; in particular, the class of functions they use comprises only quadratic functions, which is potentially modular and helps lead to a simpler proof. Their results include the computational hardness result of computing equilibria in 3-player adversarial team games (2 versus 1) and that of Nash equilibria computation in symmetric n-dimensional min-max optimization. For the latter, the authors proved PPAD-completeness through polynomial-time reduction from symmetric Nash equilibrium calculation in two-player symmetric games, which is known to be PPAD-complete.

All reviewers unanimously support accepting this paper, and hence it is put into the acceptance category. Still, I encourage the authors to incorporate some of the feedback from the reviewers (e.g., the ones by Reviewer 1qji and JDAf) and their responses during the rebuttal phase into the next version.
Decision: Accept (spotlight)