Teamwork makes von Neumann work:Min-Max Optimization in Two-Team Zero-Sum Games
Authors: Fivos Kalogiannis
Ioannis Panageas
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Venue: ICLR 2022 Submitted (2022)
Keywords: Min-max Optimization
Non-convex Optimization
Multi-agent learning
Multi-agent GANs
Game Theory
Duality Gap

Abstract: Motivated by recent advances in both theoretical and applied aspects of multiplayer games, spanning from e-sports to multi-agent generative adversarial networks, we focus on min-max optimization in team zero-sum games. In this class of games, players are split in two teams with payoffs equal within the same team and of opposite sign across the opponent team. Unlike the textbook two player zero-sum games, finding a Nash equilibrium in our class can be shown to be $\textsf{CLS}$-hard, i.e., it is unlikely to have a polynomial time algorithm for computing Nash equilibria. Moreover In this generalized framework, we establish that even asymptotic last iterate or time average convergence to a Nash Equilibrium is not possible using Gradient Descent Ascent (GDA), its optimistic variant and extra gradient. Specifically, we present a family of team games whose induced utility is non-multilinear with non-attractive $\textit{per-se}$ mixed Nash Equilibria, as strict saddle points of the underlying optimization landscape. Leveraging techniques from control theory, we complement these negative results by designing a modified GDA that converges locally to Nash equilibria. Finally, we discuss connections of our framework with AI architectures with team competition structure like multi-agent generative adversarial networks.

Under review as a conference paper at ICLR 2022
TEAMWORK MAKES VON NEUMANN WORK: MIN-MAX OPTIMIZATION IN TWO-TEAM ZERO-SUM GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
Motivated by recent advances in both theoretical and applied aspects of multi- player games, spanning from e-sports to multi-agent generative adversarial net- works, we focus on min-max optimization in team zero-sum games. In this class of games, players are split into two teams with payoffs equal within the same team and of opposite sign across the opponent team. Unlike the textbook two- player zero-sum games, finding a Nash equilibrium in our class can be shown to CLS-hard, i.e., is unlikely to have a polynomial-tine algorithm for computing Nash equilibria. Moreover, in this generalized framework, we establish that even asymptotic last iterate or time average convergence to a Nash Equilibrium not possible using Gradient Descent Ascent (GDA), its optimistic variant, and extra gradient. Specifically, we present a family of team games whose induced utility is con-multilinear with non-attractive per-se mixed Nash Equilibria, as strict saddle points of the underlying optimization landscape. Leveraging techniques from con- trol theory, we complement these negative results by designing a modified GDA that converges locally to Nash equilibria. Finally, we discuss connections of our framework with AI architectures with team competition structures like multi-agent generative adversarial networks.
INTRODUCTION
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), however, the behavior of the underlying dynamics within the teams are usually sidelined. Either for reasons of mathematical convenience bigger picture understanding, "teams" in literature typically modeled as if they were unitary actors, i.e., single individuals without unveiling the internal decision-making of the team members (see Kim et al. (2019)).
For instance, in the biology setting of weak selection model (Nagylaki, 1993; Chastain et al., 2014; Mehta et al., 2015) species are modeled compete as teams, while the crux of the matter the genes of each species are the actual players and their alleles are the actions in the survival game. Similarly, was the social-media collaboration of the Reddit retail trading crowd as team that touches off the last year's GameStop frenzy of short squeeze (Umar et al., 2021; Hasso et al., 2021) transforming the markets into a tug of war game against the team of Wall Street hedge funds.
Recently, these intrinsic details behind the competition among teams have attracted renewed interest in the Machine Learning community, motivated by the advent of multi-agent systems that are used for generative tasks or playing complex games like CTF (Jaderberg et al., 2019) or Starcraft (Vinyals et al., 2019). So as to win this kind of games, self-training AI systems have to develop both col- laborative attributes (coordination within each team) as well as contesting ones (competition across the teams). Moreover, following the complementary thread multi-agent generative adversarial network research, the creation of pool by efficient incumbent agents, either in generators (Arora et al., 2017; Hoang et al., 2017; 2018; Zhang et al., 2018; Tang, 2020), or discriminators (Hardy al., 2019; Albuquerque et al., 2019) has been tested providing significant statistical and computa-

---

Under review as a conference paper at ICLR 2022
tional benefits. In this direction, researchers strive to hamness the efficacy of distributed processing, utilizing shallower networks that can learn all the while more diverse datasets
In order to shed some light on this persistent strain of research, the main premise of the theoretical scaffolding developed in this paper is that
The " "unitary two-players" min-max approach misses the critical component of the collective strategy making within each competing team.
Our class of games. In this regard, we turn our attention to Two-Tean Zero-Sum games, proposed by Schulman & Vazirani (2019b), quite general class of min-max optimization problems that in- clude bilinear games as well as a wide range of non-convex non-concave games. In this class, the players fall in two teams of size k1, l2 and submit their own probabilistic strategy vector inedpne- dently, akin to a general normal form multi-player game. Following the econometric common value assumption of Marschak (1955), what makes a group of players team that in any outcome the players of each team receive an identical payoff. Thus, to build some intuition, it is easy to see that if perfect coordination existed within each team, the interaction between the teams is merely a zero-sum game between two "virtual" players. To streamline our presentation here, we defer the more precise description of our model to Section 2.
Challenges behind Two-Team Zero-Sum games. In the archetypical case of two players, i.e., (A1 f2 1), min-max strategies are typically thought of as the axiomatically correct predic- tions thanks to the seminal Von Neumann's 's minmax theorem (Von Neumann, 1928). Unfortu- nately, min-max optimization for case k > 1 is a much more tenuous affair: Schulman & Vazi- rani (2019b) preclude the existence of unique value by presenting a family of team games where min max * max min together with bounds about this duality gap. which quantifies exactly the ef- feet of exchanging the order of strategy commitment either between the teams or the players thereof.
If defining the correct figure of merit for Team games is rife with frustration, what even more demanding is understanding what kind of algorihms/dynamics are able to solve this problem when a
meaningful solution exists: Firstly, computing local Nash Equilibria (NE) in general non-convex non-concave games is PPAD-complete (Daskalakis et al., 2009; 2021). Thus, all well-celebrated first-order methods, like gradient descent-ascent (Lin et al., 2020; Daskalakis & Panageas, 2019), its optimistic (Popov, 1980; Daskalakis & Panageas, 2018: 8; Mertikopoulos 2019) and extra gradient variant (Korpelevich, 1976) would require an exponential number of steps in the parameters of the problem to find an appoximate NE under Nemirovsky- Yudin (Nemirovskij & Yudin, 1983) oracle optimization model. Secondly, even if a regret notion could be defined, no- regret methodology is guarranteed to attract only the set of coarse correlated equilibria (CCE) (Fudenberg, 1991; Hannan, 2016; Flokas et al., 2020; Giannou et al., 2021), weaker notion that may be exclusively supported on strictly dominated strategies, even for simple symmetric two-player games (See also Viossat & Zapechelnyuk (2013)).
al.,
Whilst the aforementioned intractability failures for the general case of non-convex non-concave min-max problems provides significant insights, they can not fortiori answer the fundamental question, restricted in the model of Two-Team Zero-Sum Games:
Can we compute Nash equilibria in Two-Team Zero-Sum Games and ultimately are there first-order methods that converge them under tangible guarantees?
Our results. To the best of our knowledge, the following contributions are the first-of-its-kind type of results for the case of Two-Team Zero-Sum games:
For the case of the computational complexity of approximate (possibly mixed) NE we establish a sweeping negative result proving that it is CLS-hard (Theorem 3)1,, i.e., is computationally harder than finding pure NE in a congestion game or finding approximate gradient descent fixed points. From an optimization perspective, we settle these questions with a resounding "no" for all the well-known discrete gradient flow variations. Specifically, we present simple family of two- team with two-players zero-sum games where Projected-GD.. GDAA Optimistic-GDa and Extra Gra- dient fail even to stabilize around a mixed NE, when they are initialized nearby (Theorem 3.5).
Indeed, from the training perspective, it's more computationally preferable to back- propagate through two equally sized neural networks with smaller capacity rather than through a giant single one that would be twice deep. 2020)
2

---

Under review as a conference paper at ICLR 2022
Additionally, for the category GDA in the non-degenerate team games with unique mixed NE, one could acquire an even stronger result for any high-dimensional configuration of actions and players. (Theorem 3.2)
In order to make some substantial headway under the burden of the above instability re- sults, we shift our attention to adaptive control generalizations of the celebrated Washout fil- teaditracitionally used for stabilizing the Dutch-roll motion of an aircraft during flight (Has- souneh et al., 2004; Grant & Reid, 1997). Inspired by this framework, we propose the modified KPV-GDA" which consists of a tandem combination of GDA together with stabilizing feedback introduces by Bazanella et al. (1997).
sttttek+1))= state + (GDA(state( + n (statel)) - stress(!) stress(b+l) (tress + () stress(k)
(KPV-GDA)
The main linchpin of KPV-GDA method the Simon's and Theil's (Simon, 1956; Theil, 1957) certainty equivalence principle, a widely used methodology in Control theory in developing ap- plied dynamic rational expectations models. According to this principle, the feedback law is split into two optimization steps whereby -tstep attracts quickly the stale the stress while P-step converges slowly to the fixed points of GDA. Compared with the plethora of the proposed dynamics for min-mas max problems, the crucial advantage of the afore-described technique that does not introduce any extra fixed points than GDA's ones. In Section 2.2, we provide some il- lustrative examples of KPV-GDA technique, while in Theorem 3.7 we prove the existence of such control feedback for our class of games.
Finally, in Section 4 we provide series of experiments in simple two-team zero-sum games showcasing both the messy behaviors of traditional methods like GDA,OGDA and the power of KPV-GDA method in these optimization environments. Additionally, we show that multi-agent GAN architectures achieve better performance than the single-agent ones, in terms of network capacity, when they are trained in synthetic or real-world datasets like CIFARIO.
PRELIMINARIES
2.1 DEFINITIONS
Our setting. Formally, a two-team game in normal form is defined as a tuple r= T(N, A, u) consisting of (i) finite set of players N, split into two teams A, B with RA and kB players cor- respondingly such that: N = NA U actions (or pure strategies) A; {a1,... (0.,.... an; J per player E N: (iii) each team's payoff func- tion UA, un A + I., where A = II, denotes the ensemble of all possible action profiles (QA,....,
{AI,... ARs B
(ii) a finite set of
.BB............................. a while the individual utility of a player is identical to her teammates, i.e., u4 = UAA & ú ug (i, E NA x W.B. In this general context, players could also adhere mixed strategies, i.e. probability distributions 8 (AA)) over the pure strategies &g Ag- Correspondingly, we define the product distributions x = 9 X ...... @ A y = 8B, 8 ..... X Beg as the teams' strategies. Collectively, we will write := IL X. = II A(A.). IEE V/- = IIEN,, A(A,) the space of mixed strategy profiles of teams A, B.
Similarly with the bilinear two-player games, the teams' utility functions can be expressed via the payoff-tensors A, B E RT with 7 II [Al and acquire the form?:
U A & uB BY
(2.1)
'The name "KPY-GDA" is an initialism from (K, V)-Vaded Gradient Descent Ascent method; Just like the tail section of an aircraft where the vanes flight control surfaces that control the unstable yaw, (K, control feedback aims to stabilize the unstable arrows of Gradient flow around mixed NE.
Figuratively, the latter form denotes what is known E, Enensthe Ii.... K...W................. If x,y have shapes (1,5) and (k, 1) that would he equivalent to u sinsum (") 1ikl, 2011, k1, A, x, y)
tensor contraction given: A
3

---

Under review as a conference paper at ICLR 2022
In terms of solutions, focus the per player Nash Equilibrium (NE), i.e, a state strategy profile s* = (x, = (5 AARA ), ($T ..... Bag )) such that
u,(s") 2 us 6",) for all E ((A,) and all i E E
(NE)
The state strategy profile 8* is called pure if every player of both teams chooses a single action; otherwise we say that it is mixed. Finally, a two-team game is called two-team zero-sum if u -u or equivalently B
Remark 2.1. A quite technical prerequisite for the rest of this work, we will assume that succinet representation of the utility tensors of the game is available or equivalently that a payoff oracle provides efficiently both the value of the utility function and its derivatives for a specific input, which is consistent with the vast majority of the applications that are described in the literature (von Stengel & Koller, 1997).
A first approach computing Nash equilibria in Two-Team Zero-Sum games. Given the existence of the duality-gap between the min max and max min, in lieu of the two-player zero-sum game, an equilibrium in our setting can not be computed via linear programming. For the goal of computing Nash equilibria in two-team zero-sum games, we have experimented with a selection of 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 it) Optimistic Gradient Descent-Ascent tii) Extra Gradient Method iv) Optimistic Multiplicative Weights Update Method We defer their precise definitions in Appendix B. The below remark will play a key role in the sequel.
Remark 2.2. Any fixed point of the aforementioned discrete-time dynamics on the utility function corresponds necessarily to the Nash equilibria of the game.
Hence, important testbed for the long-run behavior of GDA, OGDA, and EG methods is to exam- ine whether these methods stabilize around their fixed points, which effectively constitute the Nash equilibria of the game. In Section 3.2, show that in lack of pure Nash equilibria, all the above methods fail to stabilize on their fixed points even for simple class of (2, 2)-plyesss game, and as a consequence to the mixed Nash equilibria of the game.
The presence of these results showcases the need for a different approach that lies outside purely optimization- based ideas. Inspired by the applications of washout filters to stabilize highly sus- ceptible systems and their adaptive control generalizations, we design a new incarnation of GDA vaned by two matrices-control feedback. Surprisingly, in contrast with the aforementioned tradi- tional methods, our proposed technique accomplishes last-iterate stabilization on its fixed point, i.e., the mixed Nash equílibria of the team game.
(K, P)- GDA Method.
After concatenating the vectors of the minimizing and the maxi- write our method, for appropriate matrices K,
mizing agents (k) (x))
())((())) 2 (((++))= II z (k) + n ( F(((((())) + (z())( -0(0)
(2.2)
g(k+t)= 11 (k)) + P( - 8(4)}}
Intuitively, the added variable ((k) holds an estimate of the fixed point, and through the feedback r (2)) - (()) the vector z stabilizes around that estimate which slowly moves towards the real fixed point of the plain GDA dynamic. It is crucial note that additional fixed points are intro- duced to the system.
2.2 TWO ILL.STRATIVE EXAMPLES
Our first example supports a double role: Firstly, it exemplifies how our two-team min-max compe- tition can capture the formulation of multi-agent GANs architectures. Secondly, it hints also at an early separation between the optimization methods, since as we will see GDA will not converge to the Nash Equiibrium//round-nuu distribution.
We are using here the standard shorthand (#1, 8i. Bi...., (AAr) to highlight the strategy of a given player i Af versus the rest of players A {i)-
4

---

Under review as a conference paper at ICLR 2022
GDA
OGDA
EG
Proposed Method
2.
Go
Go
1.
D D.
71
1000
2000
1000
2000
1000
2000 0
1000
2000
Figure 1: Parameter training the configuration under different algorithms
2.2.1 LEARNING MIXTURE OF GAUSSIANS WITH MULTI-AGENT GANS
Consider the case of M, a mixture of gaussian distribution with two components, C1 ~ NN,, I) and ~2~~((MM I) and mixture weights I,, m2 to be positive such that का T2 1 and mi T2 # 2.
To learn the distribution above, we utilize an instance of Team-WGAN which there exists a generating team of agents Gp IR R, Gg IR" R", and discriminating team of agents Dv : IR" + R, Dw RR + R, all described by the following equations:
Generators: G₂(C) = 5 Go(z) = 2 z
(2.3)
Discriminators: Dv (v.y) (v.y),D((y) -, w.y?
The generating agent Gg maps random noise z ~ (O T) to samples while generating agent Gp(C), utilizing independent source of randomness Ç -O, 1), probabilistically controls the sign of the output of the generator Gg. The probability of ultimately generating sample y = z 0 equal to + while the probability of the sample being y
0 is equal to 1 (p ().
On the other end, there stands the discriminating team of Dv. Dw. Discriminators, D, (y) map any given sample y to 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
in their definitions.
We follow the formalism of the Wasserstein GAN to form the optimization objective:
Ey-reat Dv(y)+ + Dw
Gp(s) (Dv(Goly)) + Dw (Goly)))
min v.w 0.P
B.-wwonn,c--wo..
+ (1 (p-))(()) (D.(-Goly)) + Dw Dm(-Go(s)))
(2.4)
Equation equation 2.4 yields the simpler form:
max min R1 - Tz) μ 2pv + v + Σ w. we(n 07)
(2.5)
v.W P.P
is easy to check that Nash equilibria of Equation equation 2.4 must satisfy:
{
μ. 1=1- = =m
n. p=1- π22
Figure demonstrates both GDA's failure and OGDA, EG, and our KPV-GDA method's success to converge to the above Nash equilibria and simultaneously to discover the groud truth mixture.
5

---

Under review as a conference paper at ICLR 2022
2.2.2 MULTIPLAYER MATCHING PENNIES
Interestingly enough, there are non-trivial instances of two-team competition settings that even Op- timistic GDA and EG Method fail to converge. Such is the case for team version of the well-known game of matching pennies. The game can be shortly described as such: "coordinate with your team- mates to play a game of matching pennies against the opposing team, coordinate not and pay penulty". The penalty set to 2. For the interested reader, we defer to appendix C.2 the precise description of the game in a contracted tensor/table. Since every player has simply two actions, their probability vector can be represented by a single variable in [0. 1]. Considering the minimizing team its players T1, while the players of the maximizing team y yı, y2. The multiplayer of matching pennies is described by the utility function:
u(1 22, 1/1 V2) 21-2-1122111 1122111111111/11a
22// 2232 v1 0.5((11 +32) (2.6)
As we can see in Figures and 3, multiplayer matching pennies game consists an excellent bench- mark where all traditional gradient flow discretizations fail under perfect competition setting. Inter- estingly, we are not aware of a similar example in min-max literature and it has been our starting point for seeking new optimization techniques inspired by Control theory. Indeed, KPV-GDA varia- tion with (K, P) = (-1.1I, 0.3I) achieves to converge to the unique mixed Nash Equilibrium of the game. the following sections, we provide theorems that explained formally this long-rum gun behavior of the examined dynamics.
11,0,0)
HH
0.75
GDA DODA
DGDA
0.50
0.25
(1
40. 0,010
0
200
1000
1500
2000
2500
TT
HT/TH
Figure 2: Multiplayer matching pennies under different algorithms
Figure Projected Trajectory of Team A under different algorithms
OUR MAIN RESULTS
3.1 ON THE COMPLEXITY OF TWO-TEAM ZERO-SUP -UM GAMES
We start this section by showing that computing a Nash equilibrium two-team zero-sum games is computationally hard and thus getting polynomial-tmme algorithm that computes Nash equilib- rium is unlikely.
Theorem 3.1 (CLS-hard), Computing a Nash equilibrium two-team zero-sum games is CLS-hard.
The main idea of the proof of Theorem 3.1 relies reduction of approximating Nash equilibria in congestion games, which has been shown to be complete for the interesting class of CLS, which contains the problem of continuous optimization. For concision, defer the proof of the above theorem to the paper's supplement.
3.2 FIRST-ORDER METHODS FAIL TO STABILIZE
The negative computational complexity result we proved for two-team zero-sum games (Theorem 3.1) does not conclude the prospect of having algorithms (learning dynamics, first-order methods) that converge to Nash equilíbria and thus can approximate them well enough. Unfortunately, we can even prove negative results about convergence Nash equilibria in two-team zero-sum games of well-established methods broadly used classic two-player zero-sum games.
In this section, that GDA, OGDA, EG, and OMWU fail to stabilize to Nash equilibria. This result indicates how challenging and rich the setting of team zero-sum games can be and why provable guarantees about
going to construct family of two-team zero-sum games with the property

---

Under review as a conference paper at ICLR 2022
convergence have not been established yet. Before defining the family of two-team zero-sum games, we prove an important theorem which states that GDA does not stabilize around mixed Nash equi- libria. This fact is stepping stone in constructing the family of team-zero sum games later. We present the proof of all of the below statements in detail in the paper's appendix.
Wtakly-stable Nash equilibrium (Kleinberg et 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 her 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. Note that trivially pure Nash equilibria are weakly-stable. It has been shown that mixed Nash equilibria are not weakly-stable in generic games* (Kleinberg et al., 2009). We can show that Nash equilibria that are not weakly-stable Nash are actually unstable for GDA moreover, through standard dynamical systems machinery, that the set of initial conditions that converges to Nash equilibria that are not weakly-stable should be of measure zero. Formally, we prove that:
Theorem 3.2 (Non seakly- Nash are unstable). Consider a two-team zero-sun game with utility function of Team B (y vector) being Uxx y) and Team A (x vector) being being-U(Xx -U(x,y) y). More- over, assume that yx) is a Nash equilibrium of full support that is not weakly-stable. It follows that the set of initial conditions so that GDA converges to (x",y" yy) is of measure zero for step size n < m where L is the Lipschitz constant of QU.
3.3 GENERALIZED MATCHING PENNIES (GMP)
Inspired by Theorem 3.2, in this section construct family of team zero-sum games so that GDA, OGDA, 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 intuition is to construct family of games, each of which has only mixed Nash equilibria (that are 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 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 players. Inspired by the standard matching pennies game and the game defined in Schulman & Vazirani (2019a), we allow each agent i to have two strategies/actions that is S = {H, T} for both teams with 2$ possible strategy profiles. In case all the members of Team choose the same strategy say H or T then the Team "agrees" to play H or T (otherwise the Team "does not agree").
Thus, in the case both teams "agree", the payoff of each team is actually the payoff's for the two- player matching pennies. If one team "agrees" and the other does not, the team that "agrees" gets payoff w E (0, 1) and the other team gets penalty w. If both teams fail to "agree", both teams get payoff zero. Let x; with i E (1,2) be the probability that agent i of Team A chooses H and x4 the probability that she chooses T. We also denote x 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 1-2 ys the probability that she chooses T and y the probability vector.
The first fact about the game that we defined is that for w E (0, 1), there is only one Nash equilibrium (x", ,y), which is the uniform, i.c., xj = 2タ = y = . = 1/2 for all agents
Lemma 3.3 (GMP has a unique Nash). The Generalized Matching Pennies game exhibits a unique Nash equilibrium which is (x",y* = ((}, 1), ( 1)).
Remark 3.4. The fact that the game we defined has a unique Nash equilibrium that is in the interior of [0, 1]a 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 corollary due to Theorem 3.2. Please also note that if w = 1 then there are more Nash equilibria, in particular the (0, 0), 0), (0, 1), (1, 1) are also Nash equilibria (which are pure).
The following Theorem is the main (negative) result of this section.
Theorem 3.5 (GDA, OGDA, EG, and OMWU fail). Consider GMP game with E (0, 1). Assume that MADA < 4. MOGDA min(w, })- MEG < _ and Noowu min (t: +) (bound on the stepsize
Roughly speaking, games in which we add small Gaussian noise every payoff.
7

---

Under review as a conference paper at ICLR 2022
Proposed Method
0.6
GDA
0.4
OMWU
NE
0.2
1000
2000
3000
4000
5000
Figure GDA, OGDA, EG fail to converge Nash Equilibrium even average
for GDA, OGDA, EG, and OMWU methods respectively). holds that set of initial conditions so that GDA, OGDA, EG, OMWU converge (stabilize to any point) is of measure zero.
Remark 3.6 (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 Nash equilibria. Indeed we construct examples in which the average iterate of GDA, OGDA, and EG experimentally fail to stabilize to Nash equilibria. particular, we consider a slight modification of GMP; players and strategies are the same but the payoff matrix has changed and can be found below (table on the right):
HH
HT/TH
TT
HH
HT/TH
HT
TH
TT
HH HT/TH TT
1,-1
W. -W
-,,1
HH
2, -2
2,
WWWW
0,0
W.
HT/TH
1
0,0
1,1
1,-1
TT
-1,1
1, -1
21 7
Table 1: GMP configurations of Theorem 3.5 (left) and Remark 3.6 (right)
Figure illustrates that the average iterates of GDA, OGDA, and EG stabilize to points that are not Nash equilibria. Note that since our method (see next subsection) converges locally, the average iterate should converge locally to Nash equilibrium.
3.4 WASH-OUT FILTERS & ADAPTIVE CONTROL
The aforementioned results indicate that to answer the tantalizing question of finding NE in two- team zero-sum games, our machinery should be broadened outside the limits of textbook optimiza- tion arsenal. The mainstay of this effort and positive result is KPV-GDA method defined in (2.2), inspired by the adaptive control toolbox and washout filters. Our main statement shows that KPV-GDA stabilizes around any Nash equilibrium for appropriate choices of matrices K, P. The formal theorem is given below:
Theorem 3.7 (KPV-GDA stabilizes). Consider team zero-sum game so that the utility of Team B is (x, and hence the utility of Team A -U(x, v) and a Nash equilibrium (x".y) of the game. Moreover we assume
( Xxxx y²)
- xxx"U(x""
( Uxx"" y")
V2 Uxx" ,y") is invertible.
For any fixed step size 1) >> can always find matrices K, P so that KPV-GDA method defined in (2.2) converges locally to )*).
The latter statement concerns the existence of matrices K, P. Below, we provide a sufficient condi- tion under which simple parametrization of K, (provably) guarantees convergence.
8

---

Under review as a conference paper at ICLR 2022
Theorem 3.8. Consider two-team zero-sum game that the utility of Team B is U y) and hence the utility of Team A is yx) and a Nash equilibrium (x", of the game. Moreover let
(xX((")))) V (x,,))
V Uxx )
H
and E be the set of eigenvalues p of H with real part positive, that is E {H's eigenvalues Re(p) > 03. We assume that H. is invertible and moreover
Re(p)² +mm((p)
8 min PEE
max Re(p) a.
(3.1)
Re(p)
DEE
We set K I, p. There exist small enough step size 0 and scalar 0 and for any k E (-3, so that KPV-GDA method defined in (2.2) with chosen K, P converges locally to yx","").
4 EXPERIMENTS
In this section, we perform a series numerical experiments to validate our theoretical findings. Our experiment setting includes a 2-D Gaussian Mixture Model with 8 modes. Our architecture includes 8 "shallow" generators and discriminators with 2 layers of 2-16-2 ReLUs activations, compared with giant single-agent GAN with 4 layers of 2- 2-122-2256- 108-256-1024-2 activations. Interestingly, the giant one fails in a double sense; It demonstrates both mode-collapsing and mode-drop phenomena without stabilizing. On the other hand, our architecture with small number of neurons achieves fit the data well. We defer the discussion of the experiments with multi-generators muuli-ddisrrimintoo architectures for CIFAR-10 again the paper's 's supplement.
Iter 2000
Iter 3000
Iter 1000
Ocaenied data
Cousatol dui
1-
Cooeratod das
2-
2-
0-
0-
0-
2-
2-
2-
4-
4-
4-
(a) Each generator of MGAN (b) Mode Collapse of single-(c) Single-agent GAN can't dis- learns one mode of 8-GMM
agent GANs
criminate between modes
CONCLUSIONS AND OPEN PROBLEMS
In this paper, we have presented a number of negative results about the problem of finding a Nash equilibrium in team zero-sum games and moreover about the inability of commonly used methods for min-max optimization such as GDA, OGDA, and EG to stabilize. We also presented a method (called KPV-GDA) that manages to stabilize around Nash equilibria. Given these results, a number of interesting open questions emerge.
Open Questions. One question for future consideration is the global convergence and the rates of convergence of KPV-GDA method. We believe that the KPV-GDA converges globally for an appropriate choice matrices K, P. One other possible direction to find a systematic way to get the matrices K, P.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
In our submission folder, we provide all the necessary additional technical materials and complete proofs of the main draft's statements in the appendix section. We also uploaded the code of our experiments Catpa//Pyyoooo/Tennneeeee
REFERENCES
Isabela Albuquerque, João Monteiro, Thang Doan, Breandan Considine, Tiago Falk, and Ioannis Mitliagkas. Multi-objective training of generative adversarial networks with multiple discrimina- tors. In International Conference on Machine Learning, pp. 202-211, PMLR, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 214 223, 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In International Conference Machine Learning, pp. 224- 232. PMLR, 2017.
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 Theory Computing, Virtual Event, Italy, June 21-25, 2021, pp. 1426 1437. ACM, 2021.
Michael Bacharach. Interactive team reasoning: A contribution the theory of co-operation. Research in Economics, 53(2):117-177, 1999. ISSN 1090-9443, doi: https://doi.or//10 10. 1006/recc.1999.0188. URL https: //www//wwwww...... sciencedirect cwm/ http//ciinne/rrcccee p11//80009943999018888
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Computing the team-maxmin equilibrium in single-team aingle-adversary team games. Intelligenza Artificiale, 11(1):67-79, 2017a.
Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Team- equilibrium: ef- ficiency bounds and algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017b.
A. Bazanella, P. V. Kokotovic, and A. 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/ECC.1997 1997.708644.,
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-for fornssiveefommmo adversarial team games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. Algorithms, games, and evolution. Proceedings of the National Academy of Sciences, 111029);10200-1061) 2014.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances Neural Information Processing Systems, 31, 2018
Constantinos Daskalakis and Ioannis 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. In Proceedings of the twenty-second anmual ACM-SIAM symposium on Discrete Algorithms, pp. 790-804, SIAM, 2011.
10

---

Under review as a conference paper at ICLR 2022
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-23)) 200.. 2009.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Ishan Durugkar, lan Gemp, and Sridhar Mahadevan. Generative multi-adversarial networks. arXiv preprint ar 161 1.01673, 2016.
Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In Proceedings of the thirty-sixth annual ACM symposium Theory of computing, pp. 604-612, 2004.
John Fearnley, Paul W Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gra- dient descent: CLS = PPADOPLS. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp- 46-59, 2021.
Lampros Flokas, Emmanouil Vlatakis-Gkarageee and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. In NeurIPS'20 20: The 34th International Conference on Neural Information Processing Systems, 2020.
Thanasis Lianeas, Panayotis Mertikopoulos,
Lampros Flokas, Emmanouil- Vasiileis Uaarkkis-Karagkkomiii and Georgios Piliouras. Solving min-max optimization with hidden structure via gradient descent ascent. Advances in Neu- ral Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 2021, virtual, 2021.
Drew Fudenberg. Jean tirole game theory, 1991.
Angeliki Giannou, Emmanouil Vasileios Vlatakis GraakiioGaaaaa and Panayotis Mertikopoulos. Sur- vival of the strictest: Stable and unstable equilibria under regularized learning with partial in- formation. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Con- ference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 2147-2148. PMLR, 15-19 Aug 2021. URL giannou2la html.
Natalie Gold. Introduction: Teamwork in theory and practice. Teamwork, pp. 1-21. Springer, 2005.
Hans Gottinger. J. marschak and roy radner," economic theory of teams"(book review). Theory and Decision, 5(3):349, 1974.
Peter R Grant and Lloyd D Reid. Motion washout filter tuning: Rules and requirements. Journal of aircraft, 34(2):145-151, 1997.
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.
Tim Hasso, Daniel Müller, Matthias Pelster, and Sonja Warkulat. Who participated in the gamestop frenzy? evidence from brokerage accounts. Finance Research Letters, pp. 102140, 2021.
Munther A Hassouneh, Hsien-Chiam 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. IEFF, 2004.
Quan Hoang, Tu Dinh Nguyen, Trung Le, and Dinh Phung. Multi-generator generative adversarial nets. arXiv preprint 170.00000 2017.

---

Under review as a conference paper at ICLR 2022
Quan Hoang, Tu Dinh Nguyen, Trung Le, and Dinh Phung. Mgan: Training generative adversarial nets with multiple generators. International conference on learning representations, 2018.
Max Jaderberg, Wojeiech M Czamecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population-based reinforcement learning. Sci- ence, 364(6443))859-886) 2019.
Jeongbin Kim. Thomas R Palfrey, and Jeffrey R Zeidel. A theory of games played by teams of players. 2019.
R. Kleinberg, G. Piliouras, and É. Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. STOC, 2009.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Malecon, 12:747-756, 1976.
Jason D. Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael Jordan, and Ben- jamin Recht. First-order methods almost always avoid strict saddle points. Math. Program., 2019, doi: 10.1007/110007-0119-013744 URL /attps://doi.ooo/ 1007/s10107-019-0100
176(1-2):311-33) 2019,
Joel Z Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint arXiv:1702.03037, 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-coneav mini- max problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020.
Jakob Marschak. Elements for theory of teams. Management science, 1()):127-337, 1955.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 536-543, 2003.
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, Houssam Zenati, Bruno Lecouat, Shean- Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile, In /CLR/CC//AA 19-International Conference on Learning Representations, pp. 1-23, 2019.
Mohammad Sal Moslehian. Ky fan inequalities. CoRR, abs/1 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):450-465, 1992.
Georgios Piliouras and Leonard J Schulman. Learning dynamics and the co-evolution of competing sexual species. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94, pp. 59. Schloss Dagstuhl-LeibmiizZZeee fuer Informatik, 2018.
12

---

Under review as a conference paper at ICLR 2022
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematicall notes of the Academy of Sciences of the USSR, 28(5):845 848, 1980.
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-firs anmual ACM symposium on Theory of computing, pp. 513-522, 2009.
Leonard J. Schulman and Umesh V. Vazirani. The duality gap for two-team zero-sum games. Games doi: 10.1016fjgeeb.2211.0...0
Econ. Behav., 1 11::336-345, 2019a.
URL https:tttt/oo
org/10 6/ J geb. 2019 03 0011.
Leonard Schulman and Umesh V Vazirani. The duality gap for two-team zero-sum games. Games and Economic Behavior, 115:336-345, 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-494, IEEE, 2019.
Herbert A Simon. Dynamic programming under uncertainty with quadratic criterion function. Econometrica, Journal of the Econometric Society, pp. 74-81, 1956.
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-29977 2015.
Shichang Tang. Lessons learned from the training of gans on artificial datasets. IEEE Access, 8: 189044-155555 2020.
Henri Theil. A note certainty equivalence in dynamic planning. Econometrica: Journal of the Econometric Society, pp. 346-349, 1957.
Zaghum Umar, Mariya Gubareva, Imran Yousaf, and Shoaib Ali. A tale of company fundamentals
vs sentiment driven pricing: The case of gamestop. Journal of Behavioral and Experimental Finance, 30:100501, 2021.
Oriol Vinyals, Igor Babuschkin, Wojciech 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)3350-3555 2019.
Yannick Viossat and Andriy Zapechelnyuk. No-regret dynamics and fictitious play. Journal of
Economic Theory, 148(2):825-84)) 2013.
Emmanouil- Vlatakis- Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-deseentaascem for non-convex non- concave zero-sum games. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-BB 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. 10450-10461, 2019. URL
newrips hatppp.ccppppppe cctppppe///11////////epp httml
hash/6ch /aaaa////.ob11222222ee2eeeeeeee3
John Von Neumann. Zur theorie der gesellschaftsspiele Math, 100:295-3200 1928.
Bernhard von Stengel and Daphne Koller. Team-maxmin equilibria. Games and Economic Behavior, 21(1-2))309-3211 1997.
Hongyang Zhang, Susu Xu, Jiantao Jiao, Pengtao Xie, Ruslan Salakhutdinov, and Eric P Xing- Stackelberg gan: Towards provable minimax equilibrium via mellii-eenerator architectures. arXiv preprint arXiv: 180000 2018.
Youzhi Zhang and Bo An. Converging to team-maxmin equilibria 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- equilibria in zero-sume sum multiplayer extensive-form games, arXiv preprint XXX.x:2009..22222 2020.
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 FURTHER RELATED WORK
The properties of team games have given rise to vast corpus of literature which we cannot hope to review here; for an appetizer, we refer the reader to Kim et al. (2019); Gold (2005) and reference therein. On the other hand, the convergence of first-order methods to NE, like GDA, OGDA, or Extragradient in team games (even finite ones) is nowhere near as well understood.
A notable exception to this is the case of team-maxmin equilibria (TME), notion introduced by von Stengel & Koller (1997). In this category of two-team zero-sum games, a team of n 1--llayers plays defensively against single adversarial player. TMES provide crucial information about the robustness since they give the team players the highest payoff they employ uncoordinated strategies. Unfortunately, TMEs correspond to the solution of non non-lineat non-convex program. (Basilico et al., 2017b) provided heuristics with iterative LP and support enumeration methods with proved approximation guarantees. For the case of extensive et al. (2017a); Celli & Gatti (2018) introduced a relaxed notion of coordination device (TMECor). In TMECor solutions, the team of players shares their strategies ex- ante against the adversary. While TMECor shares some properties of NEs in zero-sum two-player games (e.g., exchangeability) the proposed algorithms by (Celli & Gatti, 2018) leverages tools like the Mixed-Integer Linear Program (MILP) that involves large number of integer variables. To tackle heuristically these hurdles, (Zhang et al., 2020; Zhang & An, 2020) had been proposed modified versions of incremental strategy generation (ISG) algorithm (See (McMahan et al., 2003)) for lizee games.
large-sized normal form games, Basilico equilibrium with
Describing the history and the literature surrounding multi-agent GANs would take us too far afield, so we do not attempt it. Scratching only the surface, we mention that: a) In MGAN (Hoang et al., 2018) and MAD-GAN (Li et al., 2019), we have mixture of generative models with asymptotically infinite capacity networks. b) In the seminal case of MIX+GAN (Arora et al., 2017), an extra regularization term is typically added to discourage the weights of mixture of generators being too far away from uniform. c) In Stackelberg GAN, (Zhang et al., 2018) 8) exploit the leader-followers relation of discriminator vs generators achieve smaller minimax gap and better Frechét metrics. For the case of of agents are used achieve higher quality images, while e) MD-GAN (Hardy et al., 2019) is designed to generalize over different datasets and multiple tasks that are spread on multiple workers.
d) In GMAN (Durugkar et al., 2016), an increased number
Interestingly, in the continuous regime, gradient flow has been recently studied under the perspec- tive of dynamical systems. In the setting of Hidden Games, two competitive non-convex operators join a two-player min-max game. Piliouras & Schulman (2018); V'atakis-Gkaragkee (2019), the authors exploit the bi-linear form of the hidden game to prove antithetical to conver- gence, like spurious fixed points, cycles, and generalized high-dimensional recurrence phenomena. Additionally, in the case of general convex-concave settings, Flokas et al. (2021) proved that local stability can be achieved around the von-Neumann equilibria while a global convergent result can be described for strictly convex hidden games. A crucial comparison of the hidden model with the team games as described in our setting is the capacity& & independence of the player's s choice.
et al.
While the main contribution of this work is to highlight the inherent difficulties that the above heuris- tic architectures are cursed, our theoretical findings in team competition hint also at new optimiza- tion schemes like KPV-GDA whose performance is illustrated in Section 4 with delicate network architectures that contain even multiple generators and discriminators simultancously.
A.2 DISCUSSION ABOUT DIFFERENT SOLUTION CONCEPTS
In this subsection, we would like to stress some differences between the different equilibrium notions ( (TMECor, TME, and per-player NE) explaining the game-theoree came-theoretic rationalism of our choice.
Initially, it is easy to see that TMECor similarly with the Coarse correlated equilibria can achieve better social welfare but as in the case of congestion games, found in literature, their price of anarchy
That is, the team members are allowed to discuss and agree tactics before the game starts, but they cannot communicate during the game.
14

---

Under review as a conference paper at ICLR 2022
can become significantly worse Roughgarden (2009). In order to give a better result, TMECor requests ana priori knowledge of the game. For example, as Zhang et al. (2020) mentioned: For example, in multiplayer poker games, team may play against an adversary player, but they cannot communicate and discuss their strategy during the game due to the rule.
However in many nowadays challenging AI models, the agents/players of each team do not neces- sarily have knowledge of the actual game. Thus, the team players can only decide in advance only about their own dynamics. Thus, the main conceptual reason that we focus on NE per player in com- parison with the aforementioned TME relaxations is to study the interplay between the individual and team incentives in competitive tasks. It is also a way of reasoning about games in which players do not necessarily need to know in which team they fall into in advance.
Problems of this kind are prevalent in modern ML applications like strategic conflict resolution Leibo et al. (2017), coordination between autonomous vehicles Cao et al. (2012), or collaboration of agents in defensive escort teams Sheikh et al. (2019). In this kind of games each agent is simultaneously working towards maximizing its own payoff (local reward) as well as the collective success of the team (global reward).
As it is stated again in Zhang et al. (2020), Celli and Gatti (2018) show that the "ex ante" coordi- nation can be modeled using a coordination device, assuming that the adversary does not observe any signal from the device. The team members agree a planned strategy (e.g., mixed strategy) in the planning phase, and then, just before the game starts, the coordination device randomly picks a pure joint strategy (from the planned strategy) for the team members to act upon.
Therefore, this TMECor interpretation would critically correspond to a high-level wootmetaplayer zero-sum game, where the metaplayer is the team as a whole entity with every individual player in perfect coordination with its teammates.
Finally, additional reason, the notion of "per player Nash equilibria" can be seen smoother figure of merit for the performance of a defensive team against an adversary. Notably, in the vast majority of the aforementioned literature, a single superpowerful adversary has been used. However, using a single-agent adversary can describe a universally fair model.By contrast, the notion of per player NE expresses the model hurdles of both simultaneous team intra-collaboration and inter- competition.
B
GAME DYNAMICS
The following algorithms are ubiquitous in the literature of min max optimization and have known variable success under different settings. Gradient descent-ascent (GDA) is the prototypical method upon which Optimistic Gradient Descent (OGDA), Extra Gradient (EG), and our proposed method K, P-vaned Gradient Dsseent-Ascent (KPV-GDA) are built. Optimistic Multiplicative Weights Up- date Method is the optimistic variant of the Multiplicative Weights Update Method.
B.1 GRADIENT DESCENT-ASCEN
x (K+1))
(k) x
17 ( (x(0)) .)((0))
IIx
(k+1)
Thys
Uj
(K)
V (x((A) y(()))
B.2 OPTIMISTIC GRADIENT DESCENT-ASCENT
(++1) = IIx,
((x(t-1), x (8) - 2 a. f(x(()) + V, 22 1), 1,00-11)))((1))) y((6-1))
vj (++1)
-Tyy
Uj + 2 us (x((1) ,y(0)) - 1/ us (x((1-11, y(R-11)] }
(K)
B.3 EXTRA GRADIENT METHOD
(1+ = 1Ix, (k) V, fx((t), yx()))
(k+1) = 11x, { (A) V. ((6+ (lg 2
(k+1) = =Ily; 10
(N)
+ 1 (x(()) (x(()),((1)) _(())]
(6+1) Tlis 1
(k)
+ + Dy (x(++)) , ((ttt)
My
15

---

Under review as a conference paper at ICLR 2022
B.4
OPTIMISTIC MULTIPLICATIVE WEIGHTS UPDATE METHOD
(k+1)
(K)
exp
2, y + 1) 1114-111)
(4)
exp
-21V ( ((0))))))))))))))))) (xcl yrck
(x/1
(x++)
(R)
exp
2n (xx(1) y
fj
fj
Eg (8)
exp
2n/ [(x(M) ((1) (xx( -y(k-11)
B.5 K, P-VANED GRADIENT DESCENT-ASCENT
(2(++))= ITz (z + n (=F + [)((2(1)) -
(y(((N)))
0 Il (0() + +n(((2(()) - 0(6))} }
z; (k) (or y) ) stand for the strategy vector of the i-th minimizing (or j-th maximizing) agent at time-step k. The step size is denoted 17. Operators IIx, Iy IIg are the projection operators the corresponding simplices. The projection operator important since the context of operation is that of constrained optimization and remaining inside the set of feasible solutions is not guaranteed at every step except for the case of the OMWU method.
Notations
C DERIVATION OF THE MIN-MAX OBJECTIVE IN EQUATION 2.5
By the definition of Variance, we get that Var [xa] =E (E[x;)) (B(n:))² More precisely for any NV,,, I), we get E[x]] nt: Additionally, after calculations, we can get that:
+ Bla Var 23 +
E E + 0.) = Var [24 + 0.] + (B [2] + 0.1)
E E + 0.) = Var [x]]
+ [B[z)] + B(0,1)*
E E. + #,) = Var |x|]
+ (0 + 9:)
E E + 0,) = 1 + 03
Moreover, it is easy to check that for mixture D(ui, o1 I, n22 021, mi, 72) of two multi- dimensional normal distributions (( 0i N a I) with corresponding weights mi, n2द
Var [mi] = πi + T + -ip. + T2p. (TIPL, + T2
Specifically for the case /41 = μ -12, this equivalent with:
Var(z:] = 1 + n - (TI/4 T2/4)²²
Hence:
Var[a:] + (TT144 - -2211)2 + 147
So we can apply the following manipulations in the objective (The notation [x]] stands for the vector that has entries the values of the vector x squared):
max min Ey-rent Dr(y)) (ow)+Dw(y)) v.w 0.P
E E.w (GrlS)- (Dv(-Golo) + Dw (Goly)))+
(1-Gp(()) (D.(G)())) + Dw (Go()))))
16

---

Under review as a conference paper at ICLR 2022
max min Ey Eywreat (v. + (w, [w.[ v.w
0.P
E, - (pp + ((v, (2 0)) + (w. 1(0 + 2()+++)))))+++++++
+ (1- ((v, + 0)) + (w, 1( - (0. - z1)) 11) =
max min By [V.,s)] + Bynreal [ww, [u?]]] w.w 0.P
-a...o..). [ () (1v, + 0) + (w,
kww110 1(0: + +2))11))
+ (1- ()) ((vi- + 0)) + (w., 10, + =z)
O.P (v, Ey-reel (5]) + ( Eyrreal [161])
max min v.w
p ((v,Bensro.n) (2 + 00) + +(W,IBewNioon)) [[0: + +z2))111 =;)R1})]
- (1 - 1) (: ( (v, BeNsironn [ - - - (2++0))) + ( (w, BownrOn [10, + 21) z))1))
(v, Tipe + 72( x2(--11) +((w + [111+
max min v.w O.
p ) + (w, [08 + +]]])) - (11 ((v, ((v,-0)
0) + +( (w. + 1)1>
max min ( - (mI- u 1-pv== v.w 0,P
0 + v + Σ Wi [n] - -02
C.I PROOF OF THEOREM 3.1
We will reduce the problem of finding a Nash equilibrium in congestion games to the problem of finding a Nash equilibrium in two-team zero-sum games. The result then will follow since comput- ing Nash equilibria in congestion games is -ard (Babichenko & Rubinstein (2021)).
As recent result (Fearnley et al., 2021) shows CLS is equal to the intersection to PLS and PPAD, two important classes of total problems. PPAD captures diverse problems in combinatorics and (non- Jcooperative game theory, like the e-approximation of a mixed Nash Equilibrium in graphical game or the computation of market equilibria. PLS, for "Polynomial Local Search", captures problems of finding a local minimum of an objective function f, in contexts where any candidate solution has local neighbourhood within which we can readily check for the existence of some other point having lower value of f. Many diverse local optimization problems have been shown complete for PLS, attesting to its importance. Examples include searching for a local optimum of the TSP according to the Lin- Ln-Kernighan heuristic (Papadimitrion, 1992), and finding pure Nash equilibria in many many-player congestion games (Fabrikant et al., 2004). The complexity class CL.S ("Continuous Local Search") was introduced by Daskalakis and Papadimitriou (Daskalakis & Papadimitriou, 2011) to classify various important problems that lie in both PPAD and PLS. CLS is seen strong candidate for capturing the complexity of some of those important problems, like the general versions of Banach's 's fixed point theorem, computation of KKT points, computation of gradient descent fixed points etc.
In our reduction, a congestion game is defined by the tuple (N; E; (S.) (c<)ee)) where N is the set of agents, E is a set of resources (also known edges or facilities), and each player p has a set S; of subsets of E. Each strategy s; E S, is a set of edges (a path). and c, is a cost (negative utility) function associated with facility e. For a strategy profile s (81, .2...., 8x), the cost of player i is given by (s))) = Eeco, ce (e)(())) where (s)s) is the number of players using e in s (the load of edge e). It a well-known result Rosenthal (1973) that congestion games exhibit a potential function (ss), that
(x)
((s)
ΣΣ
co(
BEE j=1
with the property that if any agent changes her strategy to s it holds that (1s/ :) ( = c((5), ca s.))
17

---

Under review as a conference paper at ICLR 2022
Reduction. Consider congestion game (N; E; (St):EN; (ce)eE with [N] players and potential function Q. We define a team zero-sum game as follows: Team A has n players. in which each agent chooses strategies from S,. Team B has n players, with each agent having only one possible choice (singleton set of actions) call it d, i.e., these are dummy players. If players from Team A choose strategy profile (Team B has only (s).. The utility members of Team B get is (g d) (s)).
choice) then they get utility uA
Let x (zi; ...; 2 and (d,...,d) d) be (possibly mixed) Nash equilibrium in the team zero-sum game we defined. We shall show that game and the reduction will be complete. Aiming for contradiction, suppose ( x;, not Nash equilibrium of the original congestion game. Then there exists an agent i that can deviate from strategy xi to 3. and decrease her expected cost. Hence we have that
.,,), is a Nash equilibrium of the original congestion
0 Exaxx [c((s) (a x [lc(s)]
Egax [(()] - xx, (Property of potential).
We conclude that Egaxx (s,, Eg xt. .) A d)] which a contradiction since (.;, 2nn) is Nash equilibrium for the team zero-sum game hence player deviates, her payoff (i.e., the payoff of her Team) should not increase.
-Eg-xx (())
(2 [s()
((())
C.2 MULTIPLAYER MATCHING PENNIES
Below, we present the exact definition of the (2x2) two-team of two-players matching pennies that diseuss in Sec
Team B
HH
HT TH
TT
HH
-1,1
11/2,1/2
1,-1
Team A
HT/TH TT
1/2, 1/2 -1
0,0 - 1/2
1/2,-1/2
-1,1
C.3 PROOF OF THEOREM 3.2
Since (x",y*) is not weakly-stable, there exist players i,j from the same team (say without loss of generality) and strategies k, 1' so that if i is forced to play k, then j's best response is I and that gives larger payoff than another strategy l' in her support. Formally holds that (by multi-lineame of U))
PU(x'
PU(x",y") (payoff if dyn Oyadyy
(payoff if i,j choose 1,
choose k,))) (C.1)
and also aU(x" 0zgz
(x(x"")") (*). We shall show that Ux""(x",")) has strictly positive By,1
eigenvalue tangent in the product of simplices (note that if we were working with A, we would show that V2 U2"U(x", (x",y*) has a strictly negative eigenvalue). Consider vector of size Σ, | (where JSS| is the cardinality of the strategy space of agent i in Team B) which has at coordinates (i, k), (i,1), -1 at coordinate (j, l') and from which subtract yf: denote by the resulting vector. We shall show that v 22 UOx' y")v 0.
18

---

Under review as a conference paper at ICLR 2022
By multilinearity of U it follows that
8 By 0 (**) for all agents and strategies s' and the
same is true for I variables (team A). We conclude that
2 yy Uxx y'v== ("'x""y") 8U((", ,y")
(OU(("
8U(x",''
Σ Viie
Oyii
dyjo
#ES:
(U(x")'))
OU(xx'")
(X())"y") (U(x"(y")
Oyn
Oyn
Oyj
dyf
OUx('' ,")
(C.1)
0.
dynt
Therefore U y*) has positive eigenvalue and as result
R ( - V22 Uxx',
(C.2)
0
Ux"
must have a positive and negative eigenvalue (since the trace zero).
We consider the Jacobian of the GDA dynamics at (x",y"). The corresponding matrix is the fol- lowing:
JGDA - II ( - -xx (xx" (gyU(x(,)"))
-V,u(x"; ,y'
(C.3)
We will show that JODA has an eigenvalue (possible complex) with an absolute value greater than one. It suffices to show that JGDA I has an eigenvalue with positive real part (because then JEDA would have an eigenvalue with real part greater than I and hence magnitude greater than one). Due to (**), we get that JCDA I has trace zero. reach contradiction suppose that no eigenvalue of JGDA - I has positive real part, then all eigenvalues of JGDA I should be imaginary zero. But an imaginary eigenvalue (that is not zero) also results in an eigenvalue with magnitude greater than one for JODA, therefore all eigenvalues of JEDA I should be zero. We Ky Fan inequalities which states that the sequence (in decreasing order) of the eigenvalues of (H + H majorizes the real 2
part of the sequence of the eigenvalues of H (see Moslehian (201 1), page 4) for any matrix H. We choose H = ア (JGDA - I). Since R has both a negative and a positive eigenvalue, we get that H has an eigenvalue with negative real part. The claim follows since H has trace zero, thus it should have an eigenvalue with positive real part as well.
We conclude that JGDA has an eigenvalue with an absolute value greater than one. Using Theorem 2.2 in Daskalakis Panageas (2018), it occurs that the set of initial conditions so that GDA converge to (x", yy" is of measure zero (for the particular choice of the step size).
D PROOF OF LEMMA 3.3
Firstly, we start with the min-max formulation of GMP game:
min max -21 (1 z1)(1 z2) v1)(1 (1- y2) - 21 v1)(1 y22+
x ye(0.1]²
+ (1 x1 x2 22)2132222 + w 21 (1 21)(1 22)) (V192 + (1 (1- - -22)
- w (1 9192 (1 - )1 - 122) (x) + (1 - =1)(1 - x2))
or after simplification, it is equivalent with
min max (w x x= ye/o,11
(x1 + x2) v2) 2wr x22 + 2w01 (D.1)
Remark D.I. Please note that the objective in the min-max is multi-linear and the degree of each variable in every summand is most one (total degree 2). Moreover note that due to the non convexity of the function above, the max-min is not equal to the min-max.
Let (xf .r. vf. v2) be Nash equilibrium. Assuming af, xt, vi V2 (0,1) from (D.1) and first- order conditions we get the system of cquations
1. w +1 1 vî v/ 2wxr 0,
19

---

Under review as a conference paper at ICLR 2022
2. w +1 vi y/ 2wz1 0,
3. w oं z + 2w7y2 = 0,
4. 1 `ं 2 + 2wysi
Combining the first two equations, we have wi = x and combining the last two it follows yi 1/2
Dividing equation one by w and subtracting three, it follows that 2 + -2wy" = 0. Hence conclude that yi
As result 3/ and substituting in first equation 2 = 2
Assume now that v O and 2.z, vi, 1/2 E (0, Following the same idea, now only
equations 2, 4 hold and instead of the first we have the constraint w+1-31 - 2waz 2
I- 0. From 3, 4 we conclude that yf = 3/2 and using 2 it holds that yi = = 2 Using
3 follows that because x2 [0, 1)..
222 + w(w + 1) = 0. Thus x. = 1 + w > 1 (this is not possible
Consider the that 2j 1 and 22 vi V2 (0. 1). Only equations 2, 3, 4 hold and
instead of the first we have the constraint w + yi 32 2wxz S 0. From 3, 4 we conclude that vî 3/2 and using 2 it holds that yi y/2 - Using 3 follows that -w 22 + w(1 w) O. Thus x5 -w²
(this not possible because 22 E [0, I). By symmetry the same happens when 25 = 0 or 2. and xi, vi. 3/2 E (0, 1).
Case z z and yi. ./5 (0, 1). Using 3, 4 we get y/ y2
w-1 0 (this is not 2n
possible).
Case zj = 2 and vi. v6 E (0, 1). Using 3, 4 we get yf 32
w+1 > 1 (this is not 2
possible).
Case áं = 0 and 2 = and vi v2 E (0, 1). Using 3, 4 we get vi = 5/ = Moreover
one becomes 2wrr 2 0 and two w 2war I 0, that is x 2 2 and x S
(contradiction). The case x and z = 0 and yf 32 E (0, 1) is symmetric.
Similarly consider the where the team plays pure and -j. (0, 1). One can also check that all possible pure strategy profies are not Nash equilibria.
E PROOF OF THEOREM 3.5
We split the proof in parts. Before start the proof, note that the Hessian of U (E.4) has infinity norm less than 4 (since w E (0, 1)), so has gradient Lipschitz with < 4. Thus for the rest of the proof for GDA, we choose 7JGGAA <
GDA. For GDA the proof will be straightforward. We will show that (Ii, vf, v/) is weakly Nash equilibrium. Then the claim about GDA will follow because of Lemma 3.3, Theorem, 3.2 and Remark 2.2.
Assume that player 2j fixes his strategy to .1 = O. and yı, keep their strategy (3) 1). We shall show that 22 is not indifferent in his support and would like to change his mixed strategy x2 7 to pure. When 3j = 0 and
y/2 Y/2 the payoff of Team A (æ variables) becomes -wzz + 2
Since (0, 1), 22 prefers play x2 (instead of & she had). We conclude that ( 3: 2: ) is not a weakly-stable Nash equilibrium.
OGDA. The Jacobian of the update rule of OGDA dynamics (use the same machinery of Section Daskalakis & Panageas (2018)) is the following:
I 21OODD V2 21JOGDA 2 yx I
2TOODA 2MOGDA I
V2
Xy
U
MOUDA
V2U U 2
JUGDA
V2 2 vy
JOGDA
vy
U
JJOGDA 0
yx
"JGGD
U
(E.1)
0 I
O 0
0
20

---

Under review as a conference paper at ICLR 2022
where U is the payoff of Team B (max) and -U is the payoff of team A. Substituting for MPG payoff at Nash equilibrium, we have
V
-2
2w
2w
V
-1
2 0
2w
0
The corresponding Jacobian matrix becomes:
4w
2
2
228
-1
4w
0
2
2
2w
0
1111011
I
0
0
2
0
4w
22
0
1
0
0
2
4w
0
29000
2w
JOGDA
+ TJUDDA
1000
10:00
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
(E.2)
It turns out that matrix (E.2) has characteristic polynomial (help of Mathematica)
क (A) = (4(1 + nOODA (1 - 22)² + (A - 1) AWTJOAA X(1 -3X + 2X²))
(E.3)
((A 1)A + 2wmoODA (2A 1))²
A root of T(A) is 1 +1+ 4NOGDAJ + 4UMoGDA + 1 16TOODA + 32jWn + 16w 16W2TOGOA TOGDA
which is in absolute value greater than one for 0 < TJGGDA I w is also easy to see the Hessian of U, that is:
0
2w
-
DZ
V2
V2u
yxU
D
V2
U
U
Xy
2w
-1
0
-
2w
(E.4)
2w
0
invertible for w (0, 1) (this true as the eigenvalues are -2w, 2w, -2 12/1+u0 201 wa, non of which is zero). From Theorem 3.2 in Daskalakis & Panageas (2018) follows that the initial conditions so that OGDA converges the Nash equilibrium is of measure zero for step size JJGDA < 1 < (where L is the Lipschitz constant of VU). We choose JOGDA I min( g w) and 2T.
the claim follows.
EG. The Jacobian of EG dynamics computed at the Nash equilibrium (fixed point) is given below (made use of chain rule):
JBG I++EE (
- (xU((")))))
V2 U2x "x"U(""""")
)
-VaU ,"
-22 y-))
+
V2 Uxet y²) (x",,")
(E.5)
We substitute with the values and we get
0
2w
1
1
4w -2
-2
Aw
4w
2w
1
1
-2
4w2 2
4w
4w
JEG I++]EG
+1B
-1 -1
0
2w
4w
Aw
22
4w2
2
-1
2w
0
Aw
- 4w
-2
-2 + 4w
(E.6)
The eigenvalues of JEG are 1 + 2w + 4mmow ) + MEG
2w + 4VJEG
1 - MBG
-4neE + 2w + 4nTow 2/- 8mgaw - 16 and
1 + meG
(-41JG + 2w + 4ma 2 + +2 /-11- -1 8MEG - 16 2
If -4-44 + 2w + 41jGww2 0
then JEG will have an eigenvalue with absolute value greater than one. A sufficient condition for that MEG Σ 2. Finally, for the same choice of stepsizes we have that JBG is invertible for all (x, y), hence the EG dynamics is a local diffeomorphism. From Theorem in arxiv version of Lee et al. (2019) the claim for EG method follows.
OMWU, The Jacobian of the update rule of OMWU dynamics (use the same machinery of Section 3 in Daskalakis & Panageas (2019)) is the following:
21

---

Under review as a conference paper at ICLR 2022
MR
1
17
r7
7
17
1
Jomwu
77
17
(E.7)
0
1
0
0
0
0
10000
0
10000
0
1
0
0
0
1
It turns out that matrix (E.7) has characteristic polynomial (help of Mathematica)
((a) 16 ((4 + ((++w))(( 2A)² + 4(1 - 4 4w7A(1 - 31 + 22²))
(E.8)
(2 - +) w - - 1))²
One root of the polynomial x (A) above is 1 [1 + 2nj + Mj + / 4n22 + 41fwjj + w?) As in the analysis of OGDA, it turns out that for 0 < 1 < the aforementioned root has absolute value greater than one.
Therefore we conclude that the Nash equilibrium where each agent plays (5 2)22) is repelling (and thus the fact that the set of initial conditions so that OMWU converges to that particular fixed point is of measure zero is derived from standard arguments from Lee et al. (2019). To conclude the proof we need to exclude that OMWU will stabilize in other fixed points. Note that OMWU can stabilize to points that are not Nash equilibria (e.g., all pure strategy profiles such stabilization, the trick is that if OMWU stabilizes to a point, it should be (approximate coarse correlated equilibrium where the approximation depends of the pure strategy profiles a 2/2- approximate coarse correlated equilibrium, so OMWU does not stabilize. Hence if we choose 0 < 17 < w/2, OMWU does not stabilize.
fixed points). To exclude
the size of the stepsize). However, none
F PROOF OF THEOREM 3.8
We first compute the Jacobian of KPV-GDA dynamics (2.2) where we have eliminated one variable per agent (to avoid using the projection operator). The Jacobian has the following form:
Ux', V2 U(""x")
"2U Ux",,)))))
II
k
JKPV-GDA =I+n 77
(F.1)
P.
p
suffices to show that the spectral radius of JKPV.GDA is less than one for step size small enough. We first show the claim below
Claim F.. Let J = I HM where I is the identity matrix. Suppose that M has all of its eigenvalues with a real part that is negative. Then, there exists an interval (0, n0) so that if n E (0,10) then has all of its eigenvalues with an absolute value less than one.
Proof. Let a, + b..5 be an eigenvalue of M such that a, < 0. Assume that 17 <
20
then the
of +
corresponding eigenvalue of + +ta + by f), the magnitude of which (1 + na, + of 2
1+ 2na; + 17 (a² + +66 < since -2a; > na + 63) (by assumption). Hence can choose 770 to 0.
be min; of -2
Using Claim F.1, we conclude that as long as the matrix M below has eigenvalues with real part negative then (x","" "y"")
) is attracting:
M = k.I (
-V (x) 22
)
-k-
U(",
(F2)
P.I
-p.1
22

---

eigenvalue of Under review as a conference paper at ICLR 2022
By setting M11, M12, M21, M22 as the corresponding block matrices we compute the characteristic polynomial of M. holds
det(M- - A1) det ([
M1
M1
((
Mi -
XI
KI
1)
M21
M22
A1 = det
pl
p
AI
(FF3)
([ M
- Al
kp
-kI
-1-M0 AI 1)
det
p+d
(F.4)
0
-pl
kp
)1) det (-(p +())).
det
M11
(F.5
p+
det(M - AI) has roots at X = -p and when
det MM (x+ kp
p p+ +
)+)x))= =0 0.
Therefore, if M has all eigenvalues with real part negative, we must have p > 0. Let p be an -V Xxx"(xx,""
V2 Xx (x'xxx"'"
vy UXx" yy)) ) must hold that
V2 ((".
kp
A +
k =
(Ri)
p+d
We need to investigate under what assumptions À will have real part negative. We expand (F.6) and we get
A + A(p - k p) pp =
(F.7)
We solve Equation (F.7) and get
A12 P k
V(p (p-pp - k p)2 + 4pp
(F.8)
2
< 0. We consider the following cases: We provide sufficient conditions so that Re(21.2)
p is real and negative. In this case observe that for p = O we have that 21.2 = k + P and 0. Note that for it < O, the first eigenvalue has real part negative and the second eigenvalue
-h_p 0. Therefore the λ1 as a function of is strictly decreasing at zero. We conclude that for p sufficiently small and positive, both eigenvalues of M1 will be real and negative. Hence if an eigenvalue of H is real and negative then for p sufficiently small positive and k < both eigenvalues of M will be negative.
zero. We compute the first derivative at p 0 and this gives 1 (-1+ -ktp
[K+
p is complex with [lm(p) * O. In this case observe that for p 0 we have that A1,2 k p and O. If we choose min(0. -pe(p)) > k. then the first eigenvalue will have real part negative. Now using the same idea for the first case, compute the first derivative of the real part of X as a function of and we get
2²- Re(p)² - lm(p) 1 (1 (k Re(p))² Im (p)²
2
The expression above is negative as long as - Im()) is trivially satisfied when Re(p) since is chosen be negative. Assume Re(p) (if it is zero then the above is trivially true since the imaginary part is non-zero). It occurs that the inequality above true when >
< O. The equation
l0 Re(p)
Since i is chosen to be smaller than
min (0, Re())), it suffices to show that
lpl
Re((p)
is satisfied by assumptions.
Re(p)
The above true as long as Im(p) * 0. Let E the set of eigenvalues p of H with real part positive (and non-zero imaginary part by assumption). There exists a choice for 17, k, in which n, > 0 and sufficiently small and is negative and chosen to
lp
min PEE Re(p)
k
max Re(p). E
23

---

Under review as a conference paper at ICLR 2022
G CIFAR-10
CIFAR-10 is a well-established testbed for various GAN architectures. contains 10 balanced classes of images of different objects.
Just to further illustrate the merits of multi-agent GANs, we offer a selection of images generated by WGAN-GP Arjovsky al. (2017) and the MGAN Hoang et al. (2017).
In the pictures provided by the WGAN-GP we see that across iterations, the generated samples tend cover only certain classes of the dataset while it takes longer for the samples to become realistic.
On the other hand, the MGAN architecture from an early stage provides with diverse samples that tend to be more realistic from early on.
Figure 6: MGAN after 300 iterations
24

---

Under review as a conference paper at ICLR 2022
Figure 7: WGAN after 10000 iterations
Figure 8: WGAN after 15000 iterations
25

---

Under review as a conference paper at ICLR 2022
Figure 9; WGAN after 25000 iterations
26


Reviews:
[{"review_id": "k37jmhlE77t", "reviewer": "Reviewer_89w7", "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": "I have read the authors answer' and the other reviews. I am satisfied with their answers and do not have any concern other than the lack of clarity at some points. I am thus still in favour of its acceptance.\n-----------------------------------------\nI globally find this work very interesting, well writtend and I think the problem of two-team zero-sum games deserves careful considerations. My main concern is about the comparison with related work, which seems weird/incomplete. When reading the related paper from Daskalakis and Panageas for example, they already claim that GDA and OGDA may not converge to NE in zero sum-games (in last iterate). A main part of this work is a similar claim in two-team zero-sum games (Thm 3.5), but it trivially holds if it is already the case in classical zero-sum games. As a consequence, I think the better should better focus on comparing to average iterates of these algorithms, that are known to converge to equilibria, or to methods that are known to converge in last iterate, such as OMWU for example. The case of average iterates is only mentioned in Figure 4 and Remark 3.6, but having a longer discussion (+ a theoretical result) on this would be great in my opinion. For example, Figure 2 makes less sense as soon as we are considering average iterates.\n\nThe other main \"weakness\" of this paper is the fact that Theorem 3.7 only holds under specific choices of the matrices K and P, that depend on the problem parameters. This is mentioned by the authors in the conclusion, and I agree with them that this can be left as future work.\n\nMinor comments:\n- p.2: \"is computationally harder of finding pure NE in a congestion game\". Isn't it a typo? \"than\" instead of \"of\"?\n- typos:\n           p.3 \"introduces\" -> \"introduced\"\n                 \"their\" -> \"they are\"\n           p.5 \"captures\" -> \"capture\"\n           p.6 \"non-trivial\", don't you mean \"trivial\"?\n           p.9: \"small number of neurons achieves to\", the end of the sentence is missing\n\n- could you please explain the meaning of equation (2.4) with words?\n- the figures are lacking legends and are thus hard to interpret for some of them\n- Theorem 3.1: I think it would be nice to define CLS hard before\n- Theorem 3.7: what is exactly $\\nabla_{x,x}$?", "summary_of_the_paper": "This work considers two-team zero-sum games where two teams with opposite objectives are facing each other. While the literature is quite extensive on learning in zero-sum games, very little is known for two-team zero sum-games. This paper first shows that this problem is much harder than classical zero-sum games by showing that the computation of a NE is CLS hard. Besides showing the failure of classical optimization methods for zero-sum games, the authors propose an optimisation algorithm better suited to this setting, which converges locally to a NE for carefully tuned hyperparameters.", "summary_of_the_review": "This paper is overall interesting and significant for the problem of two team zero sum games. My main concern is how it relates to previous works and I hope the authors could clarify this point.", "strength_and_weaknesses": "", "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": {}}, {"review_id": "IYoZgi6cDN5", "reviewer": "Reviewer_FpwP", "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": "The claims in this paper are supported by theoretical and experimental results.\n\nHowever, my concerns are:\n\nThe solution concept for the studied two-team zero-sum game is Nash equilibrium, and this two-team zero-sum game is an N-player game. It is well-known that computing a Nash equilibrium in N-player games is PPAD-complete (Daskalakis et al., 2009) (i.e.., it is unlikely to have a polynomial-time algorithm for computing a Nash equilibrium), and this paper shows that finding a Nash equilibrium in two-team zero-sum games is CLS-hard (i.e., it is unlikely to have a polynomial-time algorithm for computing a Nash equilibrium). \n\nGradient-based algorithms have been used to compute a Nash equilibrium in N-player games (Mckelvey, 1988; Mckelvey et al., 2014; Gemp et al., 2021), which cannot guarantee the convergence in general but will converge to a Nash equilibrium with special settings. That is the similar result presented in this paper.\n\nTherefore, this paper cannot make us understand two-team zero-sum games better.\n\n\n \nMcKelvey, R.D., 1998. A Liapunov function for Nash equilibria.\\\nMcKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. (2014). Gambit: Software Tools for Game Theory, Version 16.0.1. http://www.gambit-project.org. \\\nGemp, I., Savani, R., Lanctot, M., Bachrach, Y., Anthony, T., Everett, R., Tacchetti, A., Eccles, T. and Kramár, J., 2021. Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent. arXiv preprint arXiv:2106.01285.\n\n\nThe presentation can be improved:\n1.\tIt will be better to explain the given equations, e.g., the gradient formulation in Section 2. By the way, what is k+1/2 in Extra Gradient Method? \n2.\tHow to obtain Eq.(2.5) from Eq.(2.4)? What is \\mu in Eq.(2.5)?\n3.\tWhat is “measure zero” in Theorem 3.2?\n4.\tThe number in figures is unclear.\n5.\tNeed to explain how the experimental results in Section 4 validate the theoretical findings (or which finding).\n\n\nMinor: \\\nThere are many grammar issues:\\\nIn the abstract: “Moreover In ”\\\nIn Section 1: “Firstly, computing local Nash Equilibria (NE) in general non-convex non-concave games **are** PPAD-complete”, \"MD-GAN (Hardy et al., 2019) **are**\"\\\nIn Section 3.2: “we prove an important **Theorem** ”\\\nIn Section 3.3: “**course**-correlated equilibria (CCE)”\\\nIn Section 4: “On the other hand our architecture with a small number of neurons achieves to **We \ndefer an execution** of multi-generators multi-discriminators architectures for CIFAR-10 **again to** the \npaper’s supplement. ”\n\nAbout the related work on TME, the following two latest papers should be discussed:\\\nZhang, Y., An, B. and Černý, J., 2021, May. Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5813-5821).\\\nFarina, G., Celli, A., Gatti, N. and Sandholm, T., 2021, July. Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results. In International Conference on Machine Learning (pp. 3164-3173). PMLR.\n", "summary_of_the_paper": "This paper shows that finding a Nash equilibrium in team zero-sum games is CLS-hard (i.e., it is unlikely to have a polynomial-time algorithm for computing a Nash equilibrium).  They show that the commonly used gradient-based methods cannot converge to a Nash equilibrium and then propose a gradient-based method with special conditions, which manages to stabilize around Nash equilibria.", "summary_of_the_review": "This paper cannot make us understand two-team zero-sum games better.\n\n***After the discussion:***\nIt seems that the authors have misunderstood the relation between different solution concepts.\n\nThe statement “the notion of\"per player Nash equilibria\" can be seen as a smoother figure of merit for the performance of a defensive team against an adversary” is not correct because a per-player Nash equilibrium may not be a team maxmin equilibrium (TME). Similar to TME, a two-team maximin equilibrium is still a per-player Nash equilibrium, but a per-player Nash equilibrium may not be a two-team maximin equilibrium. This paper focuses on min-max optimization in team zero-sum games, but it only achieves a per-player Nash equilibrium. I think this is inappropriate.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "GCSnjbVwoT", "reviewer": "Reviewer_iJde", "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": "Strengths:\n1. The setting of two-team games is important, even the zero-sum version has many applications.\n2. The techniques used in the paper are well-motivated and, as far as I checked, are correct.\n\nWeaknesses:\n1. The detailed proofs are relatively simple. Although not trivial, most conclusions are not suprising. The reduction for CLS-hardness is somewhat straightforward. The locally convergence of the proposed KPV-GDA is proved by showing the existance of suitable K and P but no construction is provided.\n2. There are several issues related to the presentation. The general organization is fine but there are many typos and misused capital chatractors. The most important one is the ambiguity in Section 4 (last two sentences). Basically, I cannot understand the settings and the results provided in the experiments, although this does not influence the theoretical parts.\n3. One minor concern about the illustraive exmample on multi-agent GANs: The Nash equilibrium in this paper is defined in the sense of per player, i.e. each individual player cannot improve itself by unilaterally changing its strategy. However, it seems MGANs should in fact care about the equilibrium where each team cannot improve itself by unilaterally changing all its team members' strategies (still restricted in the space of Cartesian product of simplices). The later, just called per team NE as I have not the official name, is defined similarly as the team max-min equilibrium except both teams can have multiple players. Each per team NE, although not necessarily exists, must be a per player NE, but not vise versa.", "summary_of_the_paper": "This paper studies the equilibrium compution in two-team zero-sum games. Finding the per player Nash is proved to be CLS-hard, and many popular gradient-based algorithms are proved to be not stable. A vaned gradient descent ascent algorithm is proposed to address the instability, shown to locally converge.", "summary_of_the_review": "I think this paper is blow the bar of acceptance. Currently I am negative on it due the weaknesses I mentioned, but may change to be positive if those issues can be addressed.", "strength_and_weaknesses": "", "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": "Bw3pgEOmlCP", "reviewer": "Reviewer_rW5j", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Overall, I am a bit conflicted for this paper. I appreciate the CLS-hardness result, and like the idea of using control theory to stabilize the dynamics of GDA. At the same time, I think the paper is lacking in many aspects:\n\n#1. First of all, I was surprised to see no mention of the dichotomy between team maxmin equilibrium [3] (which to my understanding is what the authors are focusing on), versus its convexification TMECor [1][2] until the appendix. TMECor allows for correlated strategies to be used within the team. As independent strategies are a special case of correlated strategies, TMECor always allows for higher social welfare compared to TME against the same opponent. Also, the use of correlation is not an obstacle, as long as the team members can agree on a common shared signal to use to seed the same random number generator (for example, the team member having access to the current time would often be good enough).\n\nBut above all, beyond higher welfare and limited additional assumptions, TMECor is a convex concave problem. So, I think that TME makes for a pretty non compelling solution concept compared to TMECor. Showing hardness of TME is definitely interesting, but I believe that a robust discussion about TMECor and its benefits should be present in the paper. Realistically, it's hard for me to imagine a practical case where I'd rather use TME than TMECor.\n\n#2. The paper is a bit hard to read. I've numbered here a few questions that would help clarify a few of the obscure points in the rebuttal:\n\na) It was not immediately clear to me what \"converge *locally* to a point\" means\n\nb) Is KPV-GDA defined in the introduction the same as GDA-KPV mentioned in Theorem 3.7?\n\nc) In the conclusions you mention that your stabilized algorithm \"manages to stabilize *around* Nash equilibria\". What does around mean here? In Theorem 3.7 you talk about \"local convergence\" to a Nash equilibrium. So, it that the same thing?\n\nd) What can be said about the matrices K and P in Theorem 3.7? Does it mean that the theorem is purely an existential result? Or is there an algorithm to compute the required matrices?\n\n#3. I think the paper would benefit from polishing the language. That goes beyond typos: I think the overall language of the paper needs to be made more precise, as it often came off to me as vague and handwavy. For example, beyond all examples mentioned above in point 2.:\n- In the abstract, you write \"We present a family of team games whose induced utility is non-multilinear with non-attracting per-se mixed Nash equilibria\". What does \"per-se\" bind to here? The term is only used once, and it was not clear to me if it was a technical term I was not familiar with (a \"per-se Nash equilibrium\"), or if it instead referred to \"per-se not-attracting\", which again was not clear. Is the point attracting, or not attracting, or something else that needs to be explained? Also, if \"per-se\" referred to the Latin expression, I believe it does not need a hyphen.\n- In the abstract again, you write \".. is not possible using .. (GDA), its optimistic variant and extra gradient\". I think it would have been clearer to say \"its extragradient variant\".\n- The paper is inconsistent between \"two-player zero-sum\" and \"two player zero-sum\".\n- In the introduction, you talk about a certain min-max approach missing \"the critical component of the collective strategy making\". What is the critical component? I wish you had been way more specific.\n- Introduction: \"computing local Nash Equilibrium .. are\" -> is\n- Introduction: \"is computationally harder of finding\" -> than\n- Introduction: \"From optimization perspective\" -> \"From an\"\n- I encourage the authors to improve the figures, which are hard to read due to the fonts (very low contrast, the text looks pale instead of black) and font sizes used.\n- Section 3.4: \"our machiner\" -> \"machinery\"\n- Experiments: \"Iter 3000\" refers to data generated by 3000 episodes worth of training? It would be great to dive a more complete description as to how the experiments were run in the Experimental section of the paper.\n\n\n[1] Basilico et al. \"Team–Maxmin Equilibrium: Efficiency Bounds and Algorithms\"\n\n[2] Celli & Gatti \"Computational Results for Extensive-Form Adversarial Team Games\". \n\n[3] von Stengel & Koller \"Team maxmin equilibria\".", "summary_of_the_paper": "The main contributions of the paper are as follows. First, the authors show show that the computation of Nash equilibrium in two-team zero-sum game is CLS-hard. As a result, GDA and its variants (including optimistic GDA and extragradient) cannot---in general---be used to converge to the Nash equilibrium. Then, the authors propose a \"stabilized\" version of GDA (called KPV-GDA) obtained through certain stabilization techniques in control theory. ", "summary_of_the_review": "I appreciated the theoretical results of the paper, though I believe more needs to be done to justify the model. I also think the writing could be significantly improved. Overall, I am somewhat on the fence. I welcome a thorough discussion with the authors. ", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: In this paper, the authors study "team-zero sum games", where two teams are facing each other with opposite objective. 

The main result is that the complexity of finding equilibrium is CLS, hence probably not polynomial. This result is obtained via a reduction to some congestion games.

Three reviewers gave a mild positive score (6) while the fourth one had more concerns. I tend to agree with the first three reviewers, with a  a personal opinion around 5-6. The paper is interesting, but could benefit from polishing here and there (I acknowledge that the related work section is more precise after discussion). 

This said, I also kind of agree with the last reviewer in the sense that the result of this paper is a bit narrow (also not really surprising, but we cannot always have breathtaking results), and I am also not sure that most of the ICLR community will be interested by this kind of result. This is not really a criticism, but this paper is really borderline, and this is what makes it fall into the rejection pile.

For instance, I think this paper would be more suited to some other conferences, more concerned about games and computations for instance (or even a journal).
Decision: Reject