Towards convergence to Nash equilibria in two-team zero-sum games
Authors: Fivos Kalogiannis
Ioannis Panageas
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Venue: ICLR 2023 poster (2023)
Keywords: no-regret-learning
no-regret
optimization
learning-in-games
nash-equilibrium
game-theory
min-max-optimization
min-max

Abstract: Contemporary applications of machine learning raise important and overlooked theoretical questions regarding optimization in two-team games. Formally, two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents, each experiencing a utility identical to that of their teammates and opposite to that of the opposing team. We focus on the solution concept of Nash equilibria and prove $\textrm{CLS}$-hardness of computing them in this class of games. To further examine the capabilities of online learning algorithms in games with full-information feedback, we propose a benchmark of a simple ---yet nontrivial--- family of such games. These games do not enjoy the properties used to prove convergence for relevant algorithms. In particular, we use a dynamical systems perspective to demonstrate that gradient descent-ascent, its optimistic variant, optimistic multiplicative weights update, and extra gradient fail to converge (even locally) to a Nash equilibrium. On a brighter note, we propose a first-order method that leverages control theory techniques and under some conditions enjoys last-iterate local convergence to a Nash equilibrium. We also believe our proposed method is of independent interest for general min-max optimization.

Published as a conference paper at ICLR 2023
TOWARDS CONVERGENCE TO NASH EQUILIBRIA IN TEAM ZERO-SUM GAMES
Fivos Kalogiannis UC Irvine
Toannis Panageas UC Irvine
Emmanouil V. Vlatakis-Gkaragkkunii Columbia University
ABSTRACT
Contemporary applications of machine learning in two-team e-sports and the su- perior expressivity of multi-agent generative adversarial networks raise important and overlooked theoretical questions regarding optimization in two-team games. Formally, two-team zero-sum games are defined as multi-player games where players split into two competing sets of agents, each experiencing utility identical to that of their teammates and opposite to that of the opposing team. We focus on the solution concept of Nash equilibria (NE). We first show that computing NE for this class of games is hard for the complexity class CLS. To further examine the capabilities of online learning algorithms in games with full- information feedback, we propose a benchmark of a simple -yet nontrivial family of such games. These games not enjoy the properties used to prove convergence for relevant algorithms. In particular, we use dynamical systems perspective to demonstrate that gradient descent-ascent, its optimistic variant, op- timistic multiplicative weights update, and extra gradient fail to converge (even lo- cally) to a Nash equilibrium. On a brighter note, we propose a first-order method that leverages control theory techniques and under some conditions enjoys last- iterate local convergence to a Nash equilibrium. We also believe our proposed method is of independent interest for general min-max optimization.
INTRODUCTION
Online learning shares an enduring relationship with game theory that has very early onset dat- ing back the analysis of fictitious play by (Robinson, 1951) and Blackwell's approachability theorem (Blackwell, 1956). A key question within this context is whether self- elff-interested agents can arrive at a game-theoretic equilibrium an independent and decentralized manner with only limited feedback from their environment. Learning dynamics that converge to different notions of equilibria are known to exist for two-player zero-sum games (Robinson, 1951; Arora et al., 2012; Daskalakis et al., 2011), potential games (Monderer & Shapley, 1996), near-potential games (Anagnostides et al., 2022b), socially concave games (Golowich et al., 2020), and extensive form games (Anag- nostides al., 2022a). We try push the boundary further and explore whether equilibria in particular, Nash equilibria- can be reached by agents that follow decentralized learning algorithms in two-team zero-sum games.
Team competition has played a central role in the development of game theory (Marschak, 1955; von Stengel & Koller, 1997: Bacharach, 1999; Gold, 2005), economics (Marschak, 1955; Gottinger, 1974), and evolutionary biology (Nagylaki, 1993; Nowak et al., 2004). Recently, competition among teams has attracted the interest of the machine learning community due to the advances that multi- agent systems have accomplished: e.g. multi-GAN's (Hoang et al., 2017; Hardy et al., 2019) for generative tasks, adversarial regression with multiple learners (Tong al., 2018), AI agents com- peting in e-sports (e.g., CTF (Jaderberg et al., 2019) or Starcraft (Vinyals et al., 2019)) as well as card games (Moravčík et al., 2017; Brown & Sandholm, 2018; Bowling et al., 2015).
Our class of games. We turn our attention to two-team zero-sum games a quite general class of min-max optimization problems that include bilinear games and wide range of nonconvex- nonconcave games as well. In this class of games, players fall into two teams of size n, m and submit their own randomized strategy vectors independently. We note that the games that focus

---

Published as a conference paper at ICLR 2023
not restricted to team games in the narrow sense of the term "team" as we it in sports, games, and so on; the players play independently and do not follow a central coordinating authority. Rather, for the purpose of this paper, teams constituted by agents that merely enjoy the same utility function. This might already hint that the solution concept that we engage with is the Nash equilibrium (NE). Another class of games that is captured by this framework is the class of adversarial potential games. In these games, the condition that all players of the same team experience the same utility is weakened as long as there exists a potential function that can track differences in the utility of each player when they unilaterally deviate from given strategy profile (see Appendix A.2 for a formal definition). A similar setting has been studied in the context of nonatomic games (Babaioff et al., 2009).
Positive duality gap. In two-player zero-sum games, i.e., n = m = 1, min-max (respectively max-min) strategies are guaranteed form a Nash equilibrium due to Von Neumann's 's minmax theorem (Von Neumann, 1928); ultimately endowing the game with a unique value. The challenges arise for the case of n, m > 1; Schulman & Vazirani (2019b) prove that, in general, two-team games do not have a unique value. They do so by presenting a family of team games with a positive duality gap, together with bounds concerning this gap. These bounds quantify the effect of exchanging the order of commitment to their strategy either between the teams as whole or the individual players.
Solution concept. In this work, we examine the solution concept of Nash equilibrium (NE). Under Nash equilibrium, no player can improve their utility by unilaterally deviating. The main downside of NE for team games is the fact that such an equilibrium can be arbitrarily suboptimal for the team (Basilico et al., 2017a).
This is one of the reasons that the solution concept of team-maxmin equilibrium with a coordination device (TMECor) has dominated contemporary literature of team games, especially in regard to applications (Farina et al., 2018; Zhang et al., 2020; Cacciamani et al., 2021). Under TMECor, players are allowed to communicate before the game and decide upon combinations of strategies to be played during the game using an external source of randomness.
The undeniable advantage of a TMECor that the expected utility of the team under greater than the expected utility under a NE (Basilico et al., 2017a). Nevertheless, this favorable property of TMECor can by no means render the study of NE irrelevant. In fact, the study of NE is always of independent interest within the literature of algorithmic game theory especially questions corre- sponding to computational complexity. Moreover, there exist settings in which ex ante coordination cannot be expected to be possible even sensible; for example in (i) environments where the exter- nal sources of randomness are unreliable or nonexistent or visible to the adversarial team, (ii) games in which players cannot know in advance who they share common utility with, (iii) adversarial potential games. These games can model naturally occurring settings such as (a) security games with multiple uncoordinated defenders versus multiple similarly uncoordinated attackers, (b) the load balancing "game" between telecommunication service providers trying to minimize the maxi- mum delay of service experienced by their customers versus the service users that try to individually utilize the maximum amount of broadband possible, and (c) the weak selection model of evolution- ary biology where species as a whole a team, the genes of its population are the players and the alleles of each gene are in turn the actions of player; the allele frequencies are independent across genes (Nagylaki, 1993; Nowak et al., 2004; Mehta et al., 2015).
Concluding, we could not possibly argue for single correct solution concept for two-team games; there is no silver bullet. In contrast, one has to assess which is the most fitting based on the con- straints of given setting. A Nash equilibrium is cornerstone concept of game theory and examin- ing its properties in different games is always important.
The optimization point of view. We focus on the solution concept of NE and we first note that computing local-NE in general einconvex-nonconaav games is PPAD-complete (Daskalakis et al., 2009; 2021). Thus, all well-celebrated online learning, first-order methods like gradient descent- ascent (Lin et al., 2020; Daskalakis & Panageas, 2019), its optimistic (Popov, 1980; Chiang et al., 2012: Sridharan & Tewari, 2010), optimistic multiplicative weights update (Sridharan, 2012), and the extra gradient method (Korpelevich, 1976) would require exponential number of steps in the parameters of the problem in order to compute an approximate NE under the oracle optimization model of (Nemirovskij & Yudin, 1983). Additionally, in the continuous time regime, similar classes
2

---

Published as a conference paper at ICLR 2023
of games exhibit behaviors antithetical to convergence like cycling, recurrence, or chaos (Vlatakis- Gkaragkounis et al., 2019). Second, even if a regret notion within the context of cam-competition could be defined, no-regret dynamics are guaranteed to converge only to the set of coarse correlated equilibria (CCH) (Fudenberg, 1991; Hannan, 2016). CCE is a weaker equilibrium notion whose solutions could potentially be exclusively supported on strictly dominated strategies, even for simple symmetric two-player games (See also (Viossat & Zapechelnyuk, 2013)).
Surely, the aforementioned intractability remarks for the general case of innconvx-mooccncaae min-max problems provide a significant insight. But, they cannot per se address the issue of com- puting Nash equilibria when the game is equipped with a particular structure, i.e., that of two-team zero-sum games. In fact, our paper addresses the following questions:
Can get provable convergence guarantees to NE of decentralized first-order methods in two-team zero-sum games?
Our results. First, with regards to computational complexity, we prove that computing an approx- imate (and possibly mixed) NE in two-team zero-sum games is CLS-hard (Theorem 3.1); i.e., is computationally harder than finding pure NE in a congestion game or computing approximate fixed point of gradient descent.
Second, regarding online learning for equilibrium computation, prove that number of estab- lished, decentralized, first-order methods are not fit for the purpose and fail to converge even asymp- totically. Specifically, we present simple -yet nontrivial- family of two-team zero-sum games (with each team consisting of two players) where projected gradient descent-ascent (GDA), opti- mistic gradient descent-ascent (OGDA), optimistic multiplicative weights update (OMWU), and the extra gradient method (EG) fail to locally converge to a mixed NE (Theorem 3.3). More broadly, in the case of GDA in nondegenerate team games with unique mixed NE, one could acquire an even stronger result for any high- high-dimensional configuration of actions and players (Theorem 3.2). To the best of our knowledge, the described family of games the first-of-its-kin kind in which all these methods provably fail to converge at the same time.
Third, we propose a novel first-order method inspired by adaptive control (Bazanella et al., 1997; Hassouneh et al., 2004). In particular, we use a technique that manages to stabilize unstable fixed points of a dynamical system without prior knowledge of their position and without introducing new ones. It is important note that this method is a modification of GDA that uses stabilizing feedback which maintains the decentralized nature of GDA.
Finally, in Section 4 we provide series of experiments in simple two-team zero-sum GAN's. We also show that multi-Gal architectures achieve better performance than single-agent ones, relative to the network capacity when they are trained synthetic or real-world datasets like CIFAR1O.
Existing algorithms for NE in multiplayer games. The focus of the present paper is examining algorithms for the setting of repeated games (Cesa-Bianchi & Lugosi, 1999, Chapter 7). If we do not restrict ourselves to this setting, there are numerous centralized algorithms (Lipton et al., 2003; Berg& & Sandholm, 2017) and heuristics (Gemp et al., 2021) that solve the problem of computing Nash equilibria in general multi-player games.
PRELIMINARIES
Our setting. A nwo-team game in normal form is defined as tuple (W,,MAA (UA.U
The tuple is defined by
(i) finite set of n = [W\ players belonging to team A, as well as a finite set of m [ players belonging to team B:
(ii) finite set of actions (or pure strategies) A, = {ai.... Onn per player i E N; where
A := II; A, denotes the ensemble of all possible action profiles of team A, and respectively, finite set of actions (or pure strategies) B, {BI..... 3,..) per player i M, where
B = II. B3-
(iii) utility function for team A, UA A B R (resp. UB A + for team B)
We also use a = (a)...., ax)) to denote the strategy profile of team A players and B =
(B), (B1,... ........ Sm the strategy profile of team B players.
3

---

Published as a conference paper at ICLR 2023
Finally, each team's payoff function is denoted by UB : A B - R, where the individual utillity of a player is identical to her teammates, i.e. U, = UA & U,- = UB Vi E N and j E M. In this general context. players could also submit mixed strategies, ie, probability distributions over actions. Correspondingly, we define the product distributions x: = (æI...... In), y = (y)....., ym) as team A and B's strategies respectively, in which D; E (AA.) and yj E A(B,) ). Conclusively, will write X := Ilev X; = HheN A(A)),) J == IIie V = II A(B,) the space of mixed strategy profiles of teams A, B. two-team game is called two-team zero-sum if UB - which is the main focus of this paper. Moreover, we assume that the game is succinctly representable and satisfies the polynomial expectation property (Daskalakis et al., 2006). This means that given a mixed strategy profile, the utility of each player can be computed in polynomial time in the number of agents, the sum of the number of strategies of each player, and the bit number required to represent the mixed strategy profile.
A Nash equilibrium (NE) is a strategy profile (x", E X x y such that U(*", : v²) S Un, a= y)); Va, E X; U(x" v*) 2 U(x", vy, v-,), Vy; E 33
{
1
(NE)
A first approach to computing NE in Two-Team Zero-Sum games. Due to the multilinearity of the utility and the existence of a duality gap, the linear programming method used in two-player
zero-sum games cannot be used to compute Nash equilibrium. For the goal of computing Nash equilibrium in two-team zero-sum games, we have experimented with a selection of online learn- ing, first-order methods that have been utilized with varying success in the setting of the two-person zero-sum case. Namely, we analyze the following methods: (i) gradient descent-ascent (GDA) (ii) optimistic gradient descent-ascent (OGDA) (iii) extra gradient method (EG) (iv) optimistic mul- tiplicative weights update method (OMWU), For their precise definitions, we refer to Appendix B.
The below folklore fact will play key role hereafter.
Fact 2.1. Any fixed point of the aforementioned discrete-time dynamics (apart from OMWU) on the utility function necessarily corresponds to a Nash Equilibrium of the game.
Hence, an important test for the asymptotic behavior of GDA, OGDA, EG, and OMWU methods is to examine whether these methods stabilize around their fixed points which effectively constitute the Nash equilibria of the game. In Section 3.2, we show that in the absence of pure Nash equilibria, all the above methods fail to stabilize their fixed points even for simple class of two-team game with (n = 2,m = 2). Consequently, they fail to converge to the mixed Nash equilibrium of the game.
The presence of these results demonstrates the need for a different approach that lies outside the scope of traditional optimization techniques. Inspired by the applications of washout filters sta- bilize unknown fixed points and the adaptive control generalizations of the former, we design new variant of GDA "vaned" with a feedback loop dictated by a pair of two matrices. In contrast to the aforementioned conventional methods, our proposed technique surprisingly accomplishes asymp- totic last-iterate convergence its fixed point, i.e., the mixed Nash equilibria of the team game.
(K, vanadded GDA Method.
After concatenating the vectors of the minimizing and the maxi- - z (8) = (x (k) } our method for appropriate matrices K, P reads:
mizing agents-
# (k+1) = 11 z (k) + a (V=1(x(())) + (=( - )(0)} v)(()(())
(KPV-GDA)
0 ((++1)= = II
o (8) + (2(((())) 0()))
Intuitively, the additional variable ((*) holds estimate of the fixed point, and through the feedback law (*)) (())) the vector z stabilizes around that estimate which slowly moves towards the real fixed point of the GDA dynamic.
2.1 TWo ILLUSTRATIVE EXAMPLES
Our first example plays dual role: first, it demonstrates how two-team min-max competition can capture the formulation of multi-agent GAN architectures; second, it hints at the discrepancy be-
We are using here the shorthand x= (or y-i ) highlight the strategy of all agents N (or M) but
4

---

Published as a conference paper at ICLR 2023
Prpped Notted
Figure Parameter training of the configuration under different algorithms
tween the results of optimization methods, since -as will see- GDA will not converge to the Nash equilibrium/ground min max solution of the objective function (Goodfellow al., 2014) which are NP-hard to com- pute in the general case (Borgs et al., 2008); nevertheless, applications of GANs have proven that first-order stationary points of the objective function suffice to produce samples of very good quality.
distribution. Generally, the solution that is sought after is the
2.1.1 LEARNING A MIXTURE OF GAUSSIANS WITH MULTI-AGENT GAN'S
Consider the case of O, mixture of gaussian distribution with two components, C1 ~ NW I) and C2 ~N-NN-W, I 1) and mixture weights T1, #2 to be positive such that म + π2 and TI, 722 # 1
To learn the distribution above, we utilize instance of Team-WGAN in which there exists generating team of agents Gp IR - R, Gg IR" - R", and a discriminating team of agents D. R" - Dw IR" R, all described by the following equations:
Generators: G₂(C) = p + <
Go(E) = E +
Discriminators: Do(y) (v. y) (w) E, w.y
The generating agent Gø maps random noise & (O. I) to samples while generating agent Gp(C), utilizing independent source of randomness ( (0, 1), probabilistically controls the sign of the output of the generator Gg. The probability of ultimately generating a sample = c + 0 is in expectation equal to p. while the probability of the sample being y -
equal p.p. p.
On the other end, there stands the discriminating team of De, Dw. Discriminators, (z) (y) map any given sample y scalar value accounting for the "realness" or "fakeness" of it negative meaning fake, positive meaning real. The discriminators are disparate in the way they measure the realness of samples seen their definitions.
We follow the formalism of the Wasserstein GAN to form the optimization objective:
G2(S) ( D. (Gooo))) +D (Colui))
max min w,w 0.P
Eyno Doly)= + Dwll)) E EE-A(O. {~A((0,1)
+ (I-O,(0) (1-c,,to)((aaaaaa (D.(-Gol)))+ Dmm
(2)
Equation (2) yields the simpler form:
max min m 72) 2pp T - Σn wi wi( 02)
(3)
3030 O.
It is easy to check that Nash equilibria of (2) must satisfy:
(
μ, p = 12
μ, p p=
Figure demonstrates both GDA's failure and OGDA, EG, and our proposed method, KPY-GDA succeeding to converge the above Nash equilibria and simultaneously discovering the mixture of the ground-truth.
2.1.2 MULTIPLAYER MATCHING PENNIES
Interestingly enough, there are non-trivial instances of two-team competition settings in which even OGDA and EG fail converge. Such is the case for team version of the well-known game of
5

---

Published as a conference paper at ICLR 2023
matching pennies. The game can be shortly described as such: "coordinate with your teammates to play a game of matching pennies against the opposing team, coordinate not and pay a penalty". (We note that this game is special case of the game presented in Section 3.3.) As in Figures 2a and 2b, this multiplayer generalized matching pennies game constitutes an excellent benchmark which all traditional gradient flow discretizations fail under the perfect competition setting. Interestingly, we are not aware of similar example in min-max literature and it has been our starting point for seeking new optimization techniques inspired by Control theory. Indeed, the KPV-GDA variation with (K,P) Equilibrium of the game. In the following sections, we provide theorems that explain formally the behavior of the examined dynamics.
1--11-1.11 0.3 0.3-I) II achieves to converge to the unique mixed Nash
0.10
(b) Projected Trajectory of Team A under differ- ent algorithms. The sketched surface is not part of the feasible team strategy profiles (product of distributions).
(a) Generalized matching pennies under different algorithms. For the precise definition of the game, we refer appendix C.4
3 MAIN RESULTS
In this section, will prove that computing Nash equilibrium in two-team zero-sum games is computationally hard and thus getting a polynomial-time algorithm that computes a Nash equilib- rium is unlikely. Next, will demonstrate the shortcomings of array of commonly used online learning, first-order methods, and then we will provide a novel, decentralized, first-order method that locally converges NE under some conditions.
3.1 ON THE HARDNESS OF COMPUTING NE IN TWO-TEAM ZERO-SUM GAMES
As promised, our first statement characterizes the hardness of NE computation in two-team zero-sum games:
Theorem 3.1 (CLS-hard), Computing a Nash equilibrium in a succinetly represented two-team zero-sum game is CLS-hard.
The main idea of the proof of Theorem 3.1 relies on reduction of approximating Nash equilibria in congestion games, which has been shown to be complete for the CLS complexity class. The class CLS contains the problem of continuous optimization. We defer the proof of the above theorem to the paper's supplement.
3.2 FAILURE OF COMMON ONLINE, FIRST-ORDER METHODS
The negative computational complexity result we proved for two-team zero-sum games (Theo- rem 3.1) does not preclude the prospect of attaining algorithms (learning first-order methods) that converge to Nash equilibria. Unfortunately, we prove that these methods cannot guarantee conver- gence to Nash equilibria in two-team zero-sum games in general.
In this subsection, we are going to construct a family of two-team zero-sum games with the property that the dynamics of GDA, OGDA, OMWU, and EG are unstable on Nash equilibria. This result is indicative of the challenges that lie in the min-max optimization of two-team zero-sum games and the reason that provable, nonasymptotic convergence guarantees online learning have not yet been established.
Before defining our benchmark game, we prove an important theorem which states that GDA does not converge mixed Nash equilibria. This fact is stepping stone in constructing the family of team-zero sum games later. We present the proof of all the below statements in detail in the paper's appendix (Appendix B).

---

Published as a conference paper at ICLR 2023
Weakly-stable Nash equilibrium. (Kleinberg al., 2009; Mehta et al., 2015) Consider the set of Nash equilibria with the property that if any single randomizing agent of one team is forced to play any strategy in their current support with probability one, all other agents of the same team must remain indifferent between the strategies in their support. This type of Nash equilibria is called weakly-stable. We note that pure Nash equilibria are trivially weakly-stable. It has been shown that mixed Nash equilibria are not weakly-stable in generic games*
We can show that Nash equilibria that not weakly-stable Nash are actually unstable for GDA. Moreover, through standard dynamical systems machinery, that the set of initial conditions that con- verges to Nash equilibria that are not weakly- stable should be of Lebesgue measure zero. Formally, we prove that:
Theorem 3.2 (Non weakly-stable Nash are unstable). Consider a two-team zero-uum game with the ulility function of Team B (y vector) being [ y) and Team A (x: vector) being (U y). Moreover, assume that "x"y")) is a Nash equilibrium of full support that is not weakly-stable. It follows that the set of initial conditions so that GDA converges (x*, ,y") is of measure zero for step size 1j < r. where L is the Lipschitz constant of VU.
3.3 GENERALIZED MATCHING PENNIES (GMP)
Inspired by Theorem 3.2, in this section we construct a family of team zero-sum games so that GDA, OGDA, OMWU, and EG methods fail to converge (if the initialization is a random point in the simplex, the probability of convergence of the aforementioned methods is zero). The intu- ition is construct family of games, each of which has only mixed Nash equilibria (that not weakly-stable), i.e., the constructed games should lack pure Nash equilibria; using Theorem 3.2, it would immediately imply our claim for GDA. It turns out that OGDA, OMWU, and EG also fail to converge for the same family.
Definition of GMP. Consider a setting with two teams (Team A. Team B), each of which has n = 2 players. In- spired by the standard matching pennies game and the game HT/TH defined in (Schulman & Vazirani, 2019a), agent é to have two strategies/actions that is S = {H,T) for both teams with 2 possible strategy profiles. In case all the members of a Team choose the same strategy say H or T then the Team "agrees" to play H or T' (otherwise the Team "does not agree").
HH
HT/TH
TT
HH
1,-1
Wy Wy-
0,0
allow each
TT
-1,1
m@
1,
Thus, in the case that both teams "agree", the payoff of each team is actually the payoff for the two-player matching pennies. If one team "agrees" and the other does not, the team that ""agrees" enjoys the payoff w E (0. 1) and the other team suffers penalty w. If both teams fail to "agree", both teams get payoff zero. Let z, with i {1,2] be the probability that agent of Team A chooses H and 1 - x; the probability that she chooses T. We also denote as the vector of probabilities for Team A. Similarly, we denote yi for i E {1, 2) be the probability that agent of Team B chooses H and 1 y the probability that she chooses T and y the probability vector.
Properties of GMP. An important remark on the properties of our presented game is due. Existing literature tackles settings with (i) mooottoittt (Mertikopoulos et al., 2019; Diakonikolas et al., 2021), (ii) cocoercivity (Zhu & Marcotte, 1996), (iii) zero-duality gap (Von Neumann, 1928), (iv) unconstrained solution space (Golowich although it has distinct structure and is nonconvex noncnncce only due to multilinearity- satisfies none of the latter properties. This makes the (local) convergence of our proposed method even more surprising. (See also Appendix B.6.)
al., 2020). Our game is carefully crafted and-
The first fact about the game that we defined is that for w E (0. 1), there is only one Nash equilibrium (x", (e",""), ,y"), which is the uniform strategy, f.e., 2; = x5 = yî = y = 1/ for all agents i.
Lemma 3.1 (GMP has a unique Nash). The Generalized Matching Pennies game exhibits a unique Nash equilibrium which is (x* "²) ((), 1), (1, 1)).
'Roughyy speaking. generic games where we add small Gaussian noise to perturb slightly every payoff only so that we preclude any payoff ties. In these games, all Nash equilibria in all but a measure-zero set of games exhibit the property that all pure best responses are played with positive probability.
7

---

Published as a conference paper at ICLR 2023
Remark 1. The fact that the game defined has unique Nash equilibrium that is in the interior of [0, 1 is really crucial for our negative convergence results later in the section as we will show that it is not weakly-stable Nash equilibrium and the negative result about GDA will be a corollary due to Theorem 3.2. We also note that if w = then there are more Nash equilibria, in particular the (0, 0), (1, 0) (0, 1), (1, which pure.
The following Theorem is the main (negative) result of this section.
Theorem 3.3 (GDA, OGDA, EG, and OMWU fail). Consider GMP game with w E (0. 1). Assume that TIGDA < 3. TOGGDA < min(w, } 1EE < タ/ and Nouww < min (3: 5) (bound on the stepsize for GDA, OGDA, OMWU, and EG methods respectively). It holds that the set of initial conditions so that GDA, OGDA, OMWU, and EG converge (stabilize to any point) is of measure zero.
Remark 2. Theorem 3.3 formally demonstrates that the behavior of algorithms mentioned in Sec- tion 2.1.2 are not a result of "bad parametrization" and in fact, the probability that any of them converges to the NE is equal to the probability that the initialization of the variables coincides with the NE (Lebesgue measure zero).
(Average iterate also fails). One might ask what happens when we consider average iterates instead of the last iterate. It is well-known fact (Syrgkanis et al., 2015) that the average iterate of no-regret algorithms converges to coarse correlated equilibria (CCE) so we expect that the average iterate stabilizes. Nevertheless, CCE might not be Nash equilibria. Indeed we can construct examples in which the average iterate of GDA, OGDA, OMWU, and EG experimentally fail to stabilize Nash equilibria. In particular, consider slight modification of GMP; players and strategies are the same but the payoff matrix has changed and can be found reads
Remark 3
Shoied
HH
HT/TH
TT
HH
2, 2
2,2
0.4
HT/TH
5.5
0,0
2.
TT
-1.1
1
0.2
2.
7
1000
2000
3000
1000
5800
Figure 3: GDA, OGDA, OMWU, & EG fail to converge Nash Equilibrium even in average
Figure 3 shows that the average iterates of GDA, OGDA, OMWU, and EG stabilize to points that are not Nash equilibria. We note that since our method (see next subsection) converges locally, the average iterate should converge locally to Nash equilibrium.
3.4 OUR PROPOSED METHOD
The aforementioned results prove that the challenging goal of computing two-team zero-sum games calls for an expansion of existing optimization techniques. The mainstay this effort and our positive result is the KPV-GDA method defined in (KPV-GDA) which is inspired by techniques of adaptive control literature. The first statement we make is that KPV-GDA stabilizes around any Nash equilibrium for appropriate choices of matrices K, P:
Theorem 3.4 (KPV-GDA stabilizes). Consider team zero-sum game that the utility of Team B is (xx y) and hence the utility of Team (U(x, y) and a Nash equilibrium (x",y") of the game, Moreover, assume
V2 Ua" v*) Ve U( y")
- y") )
is invertible.
V2 Ux*
For any fixed step size 1) > in (KPV-GDA) converges locally to (x", ,y").
always find matrices K, P so that KPV-GDA method defined
This is an existential theorem and cannot be generally useful in practice. Further, this dynamic would not be necessarily uncoupled and the design of matrices K and P could necessitate knowledge of the NE we are trying to compute. Instead, our next statement provides sufficient conditions under which simple parametrization of matrices K, P results in uncoupled, converging dynamic:
8

---

Published as a conference paper at ICLR 2023
Theorem 3.5. Consider two-team zero-sum game that the utility of Team B is (x, y). the utility of Team A is (x, y). and a Nash equilibrium (x" ,y"). Moreover, let
- Ui=" .²) ya U2""
-Va, V U0
H ==
and E be the set of eigenvalues p of H with real part positive, that is E (Eigenvalues of matrix H. p: Re(p) 0}. We assume that H is invertible and moreover
Re(p)² + +m(p)2
B min PEE
> mmax Re(p) = =
(4)
Re(p)
PEE
set K = - There exist small enough step size nj > 0 and scalar p > 0 and for any kE E (-B.-a) that (KPV-GDA) with chosen K. converges locally (x*, yy"
EXPERIMENTS
In this section, perform series of experiments further motivate the study of two-team zero- sum games, especially in the context of multi-agent generative adversarial networks (multi-GANs). A multi-agent generative adversarial network (multi-GAN) (Arora al., 2017: Hoang et al., 2017: 2018; Zhang et al., 2018; Tang, 2020; Hardy et al., 2019; Albuquerque et al., 2019) is generative adversarial network (GAN) that leverages multiple "agents" (generators and/or discriminators) in order achieve statistical and computational benefits. In particular, Arora et al. formally proved the expressive superiority of meltiigenerrtor adversarial network architectures something that we em- pirically verify in Section 4. In this direction, researchers strive to harness the efficacy of distributed processing by utilizing shallower networks that can collectively learn more diverse datasets..
At first, the superiority of multi-GAN GANN might appear to contrast our theoretical findings; but in re- ality, the superiority comes from the quality solutions that are attainable from multi-agent archi- tectures (expressivity) and the fact that hardness (complexity) translates to rates of convergence but not non-convergence. Single agent GANs quickly converge to critical points that are not guaranteed to capture the distribution very well. In figure 4 see the fast convergence of single-agent GAN to solutions of bad quality versus the convergence of a multi-GAN to an obviously better solution. Due to space constraints, defer further discussion of the experiments at Section D.I.
Figure 4: From left right: (i) Each generator of MGAN learns mode of the mixture of 8 gaussians, (ii) Mode Collapse of single-agent GANs, (iii) Single-agent GAN can't 't't discriminate between the modes.
5 CONCLUSIONS AND OPEN PROBLEMS
In this work we study the wide class of competition, inspired broadly by the structure of the complex competition between multi-agent gen- erators and discriminators in GAN's. Furthermore, in this setting of (wo-team zero-sum games, we have presented number of negative results about the problem of computing a Nash equilibrium. Moreover, through a simple family of games that we construct, we prove the inability of commonly used methods for min-max optimization such as GDA. OGDA, OMWU, and EG to converge both in average and in the last iterate to Nash Equilibria which comes to a stark contrast to recent litera- ture that is concerned with simpler games. We have also presented an optimization method (called KPV-GDA) that manages to stabilize around Nash equilibria.
games that express the two-team
3 As long aforementioned conditions satisfied, (KPV-GDA) locally converges in any nonconvex- nonconcave game. Indeed, GMP with any w satisfies the sufficient conditions of 3.5. See also, Appendix B.7. 'Indeed, is preferable from computational standpoint to back- propagate through two equally sized neural networks rather than through single that would he twice as deep (Tang, 2020).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Ioannis Panageas would like to acknowledge a start-up grant. Emmanouil V. VG is grateful for the financial support by FODSI Postdoctoral Fellowship. This work was partially completed while IP and EVVG were visiting research fellows at the Simons Institute for Theory of Computing during Learning and Games Semester.
REFERENCES
Isabela Albuquerque, João Monteiro, Thang Doan, Breandan Considine, Tiago Falk, and loannis Mitliagkas. Multi-objective training of generative adversarial networks with multiple discrimina- tors. In International Conference on Machine Learning, pp. 202-211. PMLR, 2019.
loannis Anagnostides, Gabriele Farina, Christian Kroer, Andrea Celli, and Tuomas Sandholm. Faster no-regret learning dynamics for extensive-form correlated and coarse correlated equilib- ria. arXiv preprint S.ti::2202.0544444 2022a.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games, arXiv preprint arXiv:2203.22050 2022b.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning-Volame Voluuee 70, pp. 214- 223, 2017.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Computing. 8(1):121-164, 2012.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In International Conference on Machine Learning, pp. 224- 232. PMLR, 2017.
Moshe Babaioff, Robert Kleinberg, and Christos H Papadimitriou. Congestion games with malicious players. Games and Economic Behavior, 67(1):22-35, 2009.
Yakov Babichenko and Aviad Rubinstein. Settling the complexity of nash equilibrium in congestion games. In Samir Khuller and Virginia Vassilevska Williams (eds.), STOC '21: 53rd Anmual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 1426- 1437. ACM, 2021.
Michael Bacharach. Interactive team reasoning: A contribution to the theory of co-operation. Research in Economics, 53(2):117-477, 1999. ISSN 1090-9443. doi: https://oi..og//1 1006/reec. 1999.0188, URL https:ttt//o /wwww//wwww//////////////..////. sciencedi rect. com/ cttc/ccccccc///c//e/oeeecc wwwaecc/eeeeccciic/ee//.. 886.
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Computing the team-maxmin equilibrium in single-team single-adversary team games. Intelligenza Artificiale, 11(1):67-79, 2017a.
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Team-maxmin equilibrium: ef- ficiency bounds and algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017b.
A. S. Bazanella, P. V. Kokotovic, and S. Silva. On the control of dynamic systems with unknown operating point. In 1997 European Control Conference (ECC), pp. 3434-3439, 1997. doi: 10. 23919/ECCC.997..08822
Alexandre S. Bazanella, Petar V. Kokotovic, and Aguinaldo S. E Silva. On the control of dynamic systems with unknown operating point. International Journal of Control, 73(7): 600-605, 2000. doi: 10. 00010000000770001111110 002071700219482
URL https:/ http:/icioo//////// 0ttp//1..100... 1080/
Kimmo Berg and Tuomas Sandholm. Exclusion method for finding nash equilibrium multiplayer games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
10

---

Published as a conference paper at ICLR 2023
David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathe- matics, 6(1):1-8, 1956.
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou. The myth of the folk theorem. In Proceedings of the fortieth anmual ACM symposium Theory of computing, pp. 365-372, 2008.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218)) (4:46619))445414 2015.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(63774 2018.
Federico Cacciamani, Andrea Celli, Marco Ciccone, and Nicola Gatti. Multi-agent coordination in adversarial environments through signal mediated strategies. In Proceedings of the 20th Interna- tional Conference on Autonomous Agents and MultiAgent Systems, pp. 269-278, 2021.
Yongcan Cao, Wenwu Yu, Wei Ren, and Guanrong Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informatics, 9(1): 427-438, 2012.
Andrea Celli and Nicola Gatti. Computational results for extensive-form adversarial team games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
N. Cesa-Bianchi and G. Lugosi. On prediction of individual sequences. Annals of Statistics, pp- 1865-1895, 1999.
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu, Online optimization with gradual variations. In Conference on Learning Theory, pp. 6-1. JMLR Workshop and Conference Proceedings, 2012.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances in Neural Information Processing Systems, 31, 2018.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. Innovations in Theoretical Computer Science, 2019.
Constantinos Daskalakis and Christos Papadimitriou. Continuous local search. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 790-804. SIAM, 2011.
Constantinos Daskalakis, Alex Fabrikant, and Christos Papadimitriou. The game world is flat: The complexity of nash equilibria in succinct games. In International Colloquium on Automata, Languages, and Programming, pp.
Springer, 2006.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195 259, 2009.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 235-254. SIAM, 2011.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan. Efficient methods for struc- tured senconvvx-noncooccaa min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754. PMLR, 2021.
Ishan Durugkar, Ian Gemp, and Sridhar Mahadevan. Generative multi-adversarial networks. arXiv preprint 16v .01673, 2016.

---

Published as a conference paper at ICLR 2023
Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 612, 2004.
Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Ex ante coordination and collu- sion in zero-sum multi-player extensive-fore games. Advances in Neural Information Processing Systems, 31, 2018.
John Fearnley, Paul W Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gra- dient descent: CLS = PPAD NPLS. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp- 46-59, 2021.
Lampros Flokas, Emmanouil-Vasiin min-max optimization with hidden structure via gradient descent ascent. In Advances in Neu- ral Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 2021, virtual, 2021.
Vlatakis-Giarrakkouiii, and Georgios Piliouras. Solving
Drew Fudenberg. Jean tirole game theory, 1991.
Ian Gemp, Rahul Savani, Mare Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, An- drea Tacchetti, Tom Eccles, and János Kramár. Sample-based approximation of nash in large many-player games via gradient descent. arXiv preprint AXiv:2106.00288: 2021.
Natalie Gold. Introduction: Teamwork in theory and in practice. In Teamwork, pp. 1-21. Springer, 2005.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Advances in neural information processing systems, 33:20766-20771 2020.
lan Goodfellow, Jean Pouget-Abade Abadie, Mehdi Mirza, Bing Xu, David Warde- Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative Adversarial Nets. In Advances in Neural In- formation Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 2672-2680, 2014.
Hans Gottinger. J. marschak and roy radner," economic theory of teams"(book review). Theory and Decision, 5(3):349, 1974.
James Hannan. 4. approximation to rayes risk in repeated play. In Contributions to the Theory of Games (AM-39), Volume III, pp. 97-140. Princeton University Press, 2016.
Corentin Hardy, Erwan Le Merrer, and Bruno Sericola. Md-gan: Multi-discriminator generative adversarial networks for distributed datasets. In 2019 IEEE international parallel and distributed processing symposium (IPDPS), pp. 866-877. IEEE, 2019.
Munther A Hassouneh, Hsien-Chiarn Lee, and Eyad H Abed. Washout filters in feedback control: Benefits, limitations and extensions. In Proceedings of the 2004 American control conference, volume 5. pp. 3950-3955. IEEE, 2004.
Quan Hoang, Tu Dinh Nguyen, Trung Le, and Dinh Phung. Multi-generator generative adversarial nets. arXiv preprint 17X8v:170..02556 2017.
Quan Hoang, Tu Dinh Nguyen, Trung Le, and Dinh Phung. Mgan: nets with multiple generators. In International conference on learning representations, 2018.
Training generative adversarial
Max Jaderberg, Wojeiech M Czarnekki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population- based reinforcement learning. Sci- ence, 364(6444)) 865, 2019.
Jeongbin Kim, Thomas Palfrey, and Jeffrey Zeidel. A theory of games played by teams of players. 2019.
12

---

Published as a conference paper at ICLR 2023
R. Kleinberg, G. Piliouras, and É. Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In STOC, 2009.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Jason D. Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I. Jordan, and Ben- jamin Recht. First-order methods almost always avoid strict saddle points. Math. Program., (76(1-2)311-333)) 2019, doi: 10. 10.1077/110007-019-0037444 URL https:t///oooo ott////i.og/1.... 1007 1007/s10107-019 01374-3.
Joel Z Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint arXiv: arXiv:1702.00337, 2017.
Dan Li, Dacheng Chen, Baihong Jin, Lei Shi, Jonathan Goh, and See-Kiong Ng. Mad-gan: Multi- variate anomaly detection for time series data with generative adversarial networks. In Interna- tional Conference on Artificial Neural Networks, pp. 703-716. Springer, 2019.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-come coneave mini- max problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020.
Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, pp. 36-41, 2003.
Jakob Marschak. Elements for theory of teams. Management science, 1()):127-377, 1955.
Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pp. 2003.3300003.
R. Mehta, I. Panageas, and G. Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and conjecture of haploid genetics. In ITCS, 2015.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703-2717. SIAM, 2018
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR'19-ittrraational Conference on Learning Representations, pp- 1-23, 2019.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124- 143, 1996.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence heads-up no-limit poker. Science, 356(6337::508-513, 2017.
Mohammad Sal Moslehian. Ky fan inequalities. CoRR, abs/l 108.1467, 2011.
Thomas Nagylaki. The evolution of multilocus systems under weak selection. Genetics, 134(2): 627-647, 1993.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Martin A Nowak, Akira Sasaki, Christine Taylor, and Drew Fudenberg. Emergence of cooperation and evolutionary stability in finite populations. Nature, 428(6983) 2004.
Christos H Papadimitriou. The complexity of the lin kernighan heuristic for the traveling salesman problem. SIAM Journal on Computing, 21(3):550-465 1992.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points.
Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-844 1980.
13

---

Published as a conference paper at ICLR 2023
Julia Robinson. An iterative method of solving game. Annals of mathematics, pp. 296-301, 1951.
R.W. Rosenthal, A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, 1973.
Tim Roughgarden. Intrinsic robustness of the price of anarchy. In Proceedings of the forty-first anmual ACM symposium on Theory of computing, pp. 513-522, 2009.
Leonard Schulman and Umesh V. Vazirani. The duality gap for two-team zero-sum games, Games
Econ. Behav. 115:336-345 345, 2019a. doi: 10.1016fj.ccb22019.33.011 URL https::/ddo org/10 1tte/10.116//// / geb 2019. 19111.000 03.00..00 .011.
Leonard Schulman and Umesh V Vazirani. The duality gap for two-team zero-sum games. Games and Economic Behavior, 15:333-344, 2019b.
Hassam Ullah Sheikh, Mina Razghandi, and Ladislau Boloni. Learning distributed cooperative policies for security games via deep reinforcement learning. In 2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC), volume 1, pp. 489-49494 IEEE, 2019.
Karthik Sridharan. Learning from an optimization viewpoint. arXiv preprint arXiv:1204.4145 2012.
Karthik Sridharan and Ambuj Tewari. Convex games in banach spaces. COLT 2010, pp- 1, 2010.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regu- larized learning in games. In Advances in Neural Information Processing Systems, pp. 2989-9999999999 2997, 2015.
Shichang Tang. Lessons learned from the training of gans on artificial datasets. IEEE Access, 8: 165044-165055, 2020.
Liang Tong, Sixie Yu, Scott Alfeld, et al. Adversarial regression with multiple learners. In Interna- tional Conference on Machine Learning, pp. 4946 4954. PMLR, 2018.
Oriol Vinyals, Igor Babuschkin, Wojeiech Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev. et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):50-335,, 2019.
Yannick Viossat and Andriy Zapechelnyuk. No-regret dynamics and fictitious play. Journal of Economic Theory, 148(2):225882. 2013.
Emmanouil-Vasileee Vlatakis Kattakis-Gkragkkuniii Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradiemt-dexennt-sseet for non-convex non- concave zero-sum games. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pp. 10460- 2019. URL attps:/proccecings neurips. wwwrips.cc/papee.... cc/paper/2019/ html.
hash/ /athh//67a 6c7cd9044 110004122e555 2222e622e66221111eef31111-------
John Von Neumann. Zur theorie der gesellschaftssiell.. Math, 100:295-320, 1928.
Bernhard Stengel and Daphne Koller. Team-maxmin equilibria. Games and Economic Behavior, 21(1-2):309 321, 1997.
Hongyang Zhang, Susu Xu, Jiantao Jiao, Pengtao Xie, Ruslan Salakhutdinov, and Eric P Xing. Stackelberg gan: Towards provable minimax equilibrium via multi-generator architectures. arXiv preprint arXiv: 1.00010, 2018.
Youzhi Zhang and Bo An. Converging to team-maxmin equilibria in zero-sum multiplayer games. In International Conference on Machine Learning, pp. 11033-11043, PMLR, 2020.
Youzhi Zhang, Bo An, and Jakub Černy. Computing ex ante coordinated team-maxmin equilibria in zero-sum multiplayer extensive-form games. arXiv preprint arXiv:2009, ntt.:2009...229.. /2629, 2020.
Dao Li Zhu and Patrice Marcotte. Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities. SIAM Journal Optimization, 6(3):714-726, 1996.
14


Reviews:
[{"review_id": "cC2QM3RIDz", "reviewer": "Reviewer_1M7d", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies two-team zero-sum multiplayer games, where there are two teams of players, and team members in each team share the same payoff function. This paper focuses on computing a Nash equilibrium in these games, and they show that finding a Nash equilibrium in these two-team zero-sum games is CLS-hard based on the result of computing a Nash equilibrium in two-team zero-sum games. The result then will follow since computing Nash equilibria in congestion games is CLS-hard (Babichenko & Rubinstein 2021). They show that, with some specific settings, some gradient-based algorithms fail to converge (even locally) to a Nash equilibrium. They then provide a new version of gradient-based algorithms, which converges locally to Nash equilibria with some assumptions.", "summary_of_the_review": "This paper shows that finding a Nash equilibrium in these two-team zero-sum games is CLS-hard and theoretically proposes a new version of gradient-based algorithms, which converges locally to Nash equilibria with some assumptions. However, many things about this algorithm are unclear: the performance relative to existing algorithms, the reason (intuition) why it converges, whether the assumption is realistic in the real world, and how it connects to GAN.", "strength_and_weaknesses": "This paper shows that finding a Nash equilibrium in these two-team zero-sum games is CLS-hard and theoretically proposes a new version of gradient-based algorithms, which converges locally to Nash equilibria with some assumptions. However, many things about this algorithm are unclear: the performance relative to existing algorithms, the reason (intuition) why it converges, whether the assumption is realistic in the real world, and how it connects to GAN.\nTwo-team zero-sum games (Schulman & Vazirani 2019b) have been studied. This paper aims to compute a Nash in these games. Schulman & Vazirani (2019b) proposed using a multilinear program to compute a maxmin equilibrium, which is a Nash equilibrium as well. In addition, there are other algorithms for computing a Nash equilibrium in general multiplayer games [1,2], which can solve two-team zero-sum games. Particularly, the proposed algorithm in this paper is not the first gradient-based algorithm guaranteeing to converge for Nash equilibrium in two-team zero-sum games because gradient-based algorithms with theoretical guarantee in general games were proposed [2], which can solve two-team zero-sum games. It is well-known that a gradient-based algorithm cannot guarantee convergence for Nash equilibrium. For convergence, some assumptions/operations should be added to the algorithm. Then, this paper needs to show that the proposed algorithm is better than existing algorithms in terms of theoretical results and/or experimental results.\n \n \n \nSection 3 studies the reason why some settings of gradient-based algorithms cannot converge in GMP. Unfortunately, they only show that their proposed algorithm KPV-GDA can converge in GMP but do not show the reason why their algorithm KPV-GDA can converge in GMP. That is, it is unclear why KP-GDA converges in GMP. Understanding the reason why the proposed algorithm KPV-GDA converges in MPG is also important. \n \n \nTheorems 3.4 and 3.5 are the main results of this paper about the convergence of the proposed algorithm. However, both theorems assume that the matrix of Jacobian related to the Nash equilibrium is invertible. It is unclear if this assumption is realistic. Particularly, it is not easy for us to know the property of a Nash equilibrium before we can obtain it. That is, before we obtain a Nash equilibrium by using the proposed algorithm, we usually do not know its property. Then this requirement seems unrealistic.\n \nIn section 2.1 and Section 4, this paper uses GAN to motivate the study of two-team zero-sum games. However, it is unclear how to model that GAN by using the proposed two-team game. For example, it is unclear what a pure strategy in a Team-WGAN is, and it is unclear what the utility function in a Team-WGAN. I believe continuous games of GAN and discrete games of two-team games have different properties.\n \n\n \n\n\n[1] Berg, K. and Sandholm, T., 2017, February. Exclusion method for finding Nash equilibrium in multiplayer games. In AAAI.\n\n[2] Gemp, I., Savani, R., Lanctot, M., Bachrach, Y., Anthony, T., Everett, R., Tacchetti, A., Eccles, T. and Kramár, J., 2022. Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent.  In AAMAS\n\nMinor:\n\n‘lFurthermore’ -> Furthermore\n\n‘a NE’ -> an NE\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JPHe-2B6h0f", "reviewer": "Reviewer_m964", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors investigate the problem of computing Nash equilibrium in (normal-form) two-team zero-sum games. The authors argue that the problem is CLS-hard, and give an algorithm guaranteeing local convergence. ", "summary_of_the_review": "The paper presents new and interesting results on a problem of obvious interest. I have one major concern regarding the technical part of the paper. If it is addressed, I will raise my score.", "strength_and_weaknesses": "The premise of the paper is interesting, but I have nontrivial concerns about the technical results. In particular:\n\n1. The CLS-hardness proof seems problematic. The game used in the reduction has $|S_i|$ actions for each of $n$ players, so the normal form of the game has representation size $n \\cdot \\prod_{i} |S_i|$, which could be exponential in the representation size of the congestion game instance. (Indeed, if we allowed ourselves an algorithm with that runtime, congestion games would become trivial, since one could directly compute the minimizer $\\boldsymbol s \\in \\bigtimes_i S_i$ of the potential!) If the goal is to show that Nash computation is hard for zero-sum team games in some *succinct* game representation, the authors should formally specify exactly what that succinct representation is and why it is interesting. This is my main concern about the paper.\n\n1. I am also unconvinced regarding the solution concept. In particular, in the GAN example (Sec 2.1.1) that seems like a fundamental motivating example in this paper, it seems that the correct solution concept should be TME. The natural goal is to find $G_p$ and $G_\\theta$ maximizing the discriminator loss, which is exactly what TME does. Also recall that the gap in solution between an arbitrary Nash and a TME can be arbitrarily bad in general. Especially given that the game is already highly nonconvex-nonconcave, I do not see the benefit of using Nash instead of TME here.\n\nMinor things not affecting my evaluation:\n\n1. The probability expressions after Eq (1) are wrong, since $\\zeta$ is a normal variable and therefore $\\zeta+p$ may not be in $[0, 1]$.\n\n1. Section 3.2: \"[Theorem 3.1] does not preclude the prospect of attaining algorithms (learning first-order methods) that converge to Nash equilibria.\" I understand that this because you draw the distinction between $\\text{poly}(1/\\epsilon)$ convergence to $\\epsilon$-Nash (which at this point in the paper could still be achieved learning methods) and $\\log(1/\\epsilon)$ convergence (which would be achieved by an exact method), correct? I think this is worth making explicit, and stating in any hardness result that you are showing hardness for the $\\log(1/\\epsilon)$ version of convergence.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1XMCDIBTzDG", "reviewer": "Reviewer_fCR8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the computation of Nash Equilibrium for two-team zero-sum games, and\n\n1. proves that computing an approximate (possibly mixed) NE in two-team zero-sum games is CLS-hard.\n\n2. gives a simple family of two-team zero-sum games where some common online, first-order min-max optimization methods (GDA, OGDA, OMWU, EG) fail to converge to NE (regardless of convergence time) except for a measure zero set of initial conditions.\n\n3. gives a new first-order method (KPV-GDA) to stabilize the dynamics around unstable Nash Equilibria in certain class of well-behaved games and converge to them.\n\n4. argues that the study of two-team zero-sum games applies to multi-agent GANs, which performs better than a single-agent GAN on learning a mixture of 8 Gaussians in an experiment.", "summary_of_the_review": "The paper contributes to the study of two-team zero-sum games, and this reader recommends acceptance.", "strength_and_weaknesses": "What I like:\n* The reduction to show CLS-hardness is very simple.\n* The counter example (Generalized Matching Pennies) showing non-convergence is very simple and intuitive.\n* The motivation for the new first-order method (KPV_GDA) to stabilize Nash Equilibria in certain general class of well-behaved games is also intuitive.\n\nWhat might be improved:\n* The argument connecting (the results in this paper concerning) two-team zero-sum games with (the real world performance of) multi-agent GANs, while interesting, may need stronger evidence.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster