Year: 2021

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 into two teams with payoffs equal within the same team and of opposite sign across the opponent team. Unlike the textbook twoplayer zero-sum games, finding a Nash equilibrium in our class can be shown to be 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 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 structures like multi-agent generative adversarial networks.

text: 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 into two teams with payoffs equal within the same team and of opposite sign across the opponent team. Unlike the textbook twoplayer zero-sum games, finding a Nash equilibrium in our class can be shown to be 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 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 structures like multi-agent generative adversarial networks.

heading: 1 INTRODUCTION
text: 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 or bigger picture understanding, “teams” in literature are 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 to compete as teams, while at 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, it was the social-media collaboration of the Reddit retail trading crowd as a 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 collaborative attributes (coordination within each team) as well as contesting ones (competition across the teams). Moreover, following the complementary thread of multi-agent generative adversarial network research, the creation of a 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 et al., 2019; Albuquerque et al., 2019) has been tested providing significant statistical and computa-
tional benefits. In this direction, researchers strive to harness the efficacy of distributed processing, utilizing shallower networks that can learn all the while more diverse datasets 1.
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-Team Zero-Sum games, proposed by Schulman & Vazirani (2019b), a quite general class of min-max optimization problems that include 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, k2 and submit their own probabilistic strategy vector independently, akin to a general normal form multi-player game. Following the econometric common value assumption of Marschak (1955), what makes a group of players a team is 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., (k1 = k2 = 1), min-max strategies are typically thought of as the axiomatically correct predictions thanks to the seminal Von Neumann’s minmax theorem (Von Neumann, 1928). Unfortunately, min-max optimization for case k > 1 is a much more tenuous affair: Schulman & Vazirani (2019b) preclude the existence of unique value by presenting a family of team games where min max 6= max min together with bounds about this duality gap, which quantifies exactly the effect 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 is even more demanding is understanding what kind of algorithms/dynamics are able to solve this problem when a game-theoretically 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; Mertikopoulos et al., 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, noregret methodology is guarranteed to attract only to the set of coarse correlated equilibria (CCE) (Fudenberg, 1991; Hannan, 2016; Flokas et al., 2020; Giannou et al., 2021), a weaker notion that may be exclusively supported on strictly dominated strategies, even for simple symmetric two-player games (See also Viossat & Zapechelnyuk (2013)).
Whilst the aforementioned intractability failures for the general case of non-convex non-concave min-max problems provides significant insights, they can not a 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 to 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 a simple family of twoteam with two-players zero-sum games where Projected-GDA, Optimistic-GDA, and Extra Gradient fail even to stabilize around a mixed NE, when they are initialized nearby (Theorem 3.5).
1Indeed, 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 as deep.(Tang, 2020)
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 results, we shift our attention to adaptive control generalizations of the celebrated Washout filters–traditionally used for stabilizing the Dutch-roll motion of an aircraft during a flight (Hassouneh et al., 2004; Grant & Reid, 1997). Inspired by this framework, we propose the modified KPV-GDA2 which consists of a tandem combination of GDA together with a stabilizing feedback introduces by Bazanella et al. (1997).
{ state(k+1) = state(k) + ηGDA(state(k+1)) + ηK(state(k) − stress(k)) stress(k+1) = stress(k) + ηP (state(k) − stress(k)) (KPV-GDA)
The main linchpin of KPV-GDA method is the Simon’s and Theil’s (Simon, 1956; Theil, 1957) certainty equivalence principle, a widely used methodology in Control theory in developing applied dynamic rational expectations models. According to this principle, the feedback law is split into two optimization steps whereby K−step attracts quickly the state to the stress while P−step converges slowly to the fixed points of GDA. Compared with the plethora of the proposed dynamics for min-max problems, the crucial advantage of the afore-described technique is that does not introduce any extra fixed points than GDA’s ones. In Section 2.2, we provide some illustrative 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 a 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 CIFAR10.

heading: 2 PRELIMINARIES

heading: 2.1 DEFINITIONS
text: Our setting. Formally, a two-team game in normal form is defined as a tuple Γ = Γ(N ,A, u) consisting of (i) a finite set of players N , split into two teams A,B with kA and kB players correspondingly such that: N = NA ∪ NB = {A1, · · · , AkA , B1, · · · , BkB}; (ii) a finite set of actions (or pure strategies) Ai = {α1, . . . , αni} per player i ∈ N ; (iii) each team’s payoff function uA, uB : A → R, where A := ∏ iAi denotes the ensemble of all possible action profiles α = (αA1 , . . . , αAkA , αB1 , . . . , αBkB ) while the individual utility of a player is identical to her teammates, i.e., ui = uA & uj = uB ∀(i, j) ∈ NA×NB . In this general context, players could also adhere mixed strategies, i.e, probability distributions sk ∈ ∆(Ak) over the pure strategies αk ∈ Ak. Correspondingly, we define the product distributions x = sA1 ⊗ · · · ⊗ sAkA , y = sB1 ⊗ · · · ⊗ sBkB as the teams’ strategies. Collectively, we will write X := ∏ i∈NA Xi = ∏ i∈NA ∆(Ai),Y :=∏
i∈NA Yi = ∏ i∈NB ∆(Ai) 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 ∈ Rτ with τ = ∏ i∈N |Ai| and acquire the form3:
uA = Ayx & uB = B y x (2.1)
2The name “KPV-GDA” is an initialism from (K,P )-Vaned Gradient Descent Ascent method; Just like the tail section of an aircraft where the vanes are flight control surfaces that control the unstable yaw, (K,P ) control feedback aims to stabilize the unstable arrows of Gradient flow around a mixed NE. 3Figuratively, the latter form denotes what is known as a tensor contraction given: Ayx =∑ i,...,j,k...,l xi,...,jAi,...,j,k...,lyk...,l If x,y have shapes (i, j) and (k, l) that would be equivalent to u = einsum(’ijkl,ij,kl’, A, x, y)
In terms of solutions, we focus on the per player Nash Equilibrium (NE), i.e., a state strategy profile s∗ = (x,y) = ( (s∗A1 , . . . , s ∗ AkA ), (s∗B1 , . . . , s ∗ BkB ) ) such that
ui(s ∗) ≥ ui(si; s∗−i)4 for all si ∈ ∆(Ai) and all i ∈ N (NE)
The state strategy profile s∗ 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 uA = −uB or equivalently A + B = O. Remark 2.1. A quite technical prerequisite for the rest of this work, we will assume that a succinct 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 on 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 zerosum case. Namely, we analyze the following methods: i) Gradient Descent-Ascent ii) Optimistic Gradient Descent-Ascent iii) 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, an important testbed for the long-run behavior of GDA, OGDA, and EG methods is to examine whether these methods stabilize around their fixed points, which effectively constitute the Nash equilibria of the game. In Section 3.2, we show that in lack of pure Nash equilibria, all the above methods fail to stabilize on their fixed points even for a simple class of (2, 2)-players 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 susceptible 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 traditional methods, our proposed technique accomplishes last-iterate stabilization on its fixed point, i.e., the mixed Nash equilibria of the team game.
(K,P )-Vaned GDA Method. After concatenating the vectors of the minimizing and the maximizing agents z(k) = (x(k),y(k)) we can write our method, for appropriate matrices K,P :z (k+1) = ΠZ { z(k) + η (−∇xf(z(k)) ∇yf(z(k)) ) + ηK(z(k) − θ(k)) } θ(k+1) = ΠZ { θ(k) + ηP (z(k) − θ(k))
} (2.2) Intuitively, the added variable θ(k) holds an estimate of the fixed point, and through the feedback ηK(z(k) − θ(k)) the vector z stabilizes around that estimate which slowly moves towards the real fixed point of the plain GDA dynamic. It is crucial to note that no additional fixed points are introduced to the system.

heading: 2.2 TWO ILLUSTRATIVE EXAMPLES
text: Our first example supports a double role: Firstly, it exemplifies how our two-team min-max competition 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 Equilibrium/ground-truth distribution.
4We are using here the standard shorthand (s1, . . . , si, . . . , s|N|) to highlight the strategy of a given player i ∈ N versus the rest of players N \ {i}.

heading: 2.2.1 LEARNING A MIXTURE OF GAUSSIANS WITH MULTI-AGENT GANS
text: Consider the case ofM, a mixture of gaussian distribution with two components,C1 ∼ N (µ, I) and C2 ∼ N (−µ, I) and mixture weights π1, π2 to be positive such that π1 + π2 = 1 and π1, π2 6= 12 . To learn the distribution above, we utilize an instance of a Team-WGAN in which there exists a generating team of agents Gp : R → R, Gθ : Rn → Rn, and a discriminating team of agents Dv : Rn → R, Dw : Rn → R, all described by the following equations:
Generators: Gp(ζ) = p+ ζ , Gθ(z) = z + θ Discriminators:Dv(y) = 〈v,y〉 , Dw(y) = ∑ i wiy 2 i
(2.3)
The generating agentGθ maps random noise z ∼ N (0, I) to samples while generating agentGp(ζ), utilizing an independent source of randomness ζ ∼ N (0, 1), probabilistically controls the sign of the output of the generatorGθ. The probability of ultimately generating a sample y = z+θ is equal to ζ + p, while the probability of the sample being y = −z− θ is equal to 1− (p+ ζ). On the other end, there stands the discriminating team of Dv, Dw. Discriminators, Dv(y), Dw(y) map any given sample y to a 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 as seen in their definitions.
We follow the formalism of the Wasserstein GAN to form the optimization objective:
max v,w min θ,p 
Ey∼real [ Dv(y) +Dw(y) ] −
Ez∼N (0,I),ζ∼N (0,1)  
Gp(ζ) · ( Dv ( Gθ(y) ) +Dw ( Gθ(y) )) +(
1−Gp(ζ) ) · ( Dv ( −Gθ(y) ) +Dw ( −Gθ(y) ))    (2.4)
Equation equation 2.4 yields the simpler form:
max v,w min θ,p (π1 − π2)vTµ− 2pvTθ + vTθ + n∑ i wi(µ 2 i − θ2i ) (2.5)
It is easy to check that Nash equilibria of Equation equation 2.4 must satisfy:{ θ = −µ, p = 1− π2 = π1 θ = −µ, p = 1− π1 = π2. } Figure 1 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.

heading: 2.2.2 MULTIPLAYER MATCHING PENNIES
text: Interestingly enough, there are non-trivial instances of two-team competition settings that even Optimistic GDA and EG Method fail to converge. Such is the case for a team version of the well-known game of matching pennies. The game can be shortly described as such: “coordinate with your teammates to play a game of matching pennies against the opposing team, coordinate not and pay a penalty”. The penalty is set to 12 . 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 x its players are x1, x2, while the players of the maximizing team y are y1, y2. The multiplayer of matching pennies is described by the utility function:
u(x1, x2, y1, y2) = −x1x2−x1y1−x1y2+1.5(x1+x2)−x2y1−x2y2+y1y2+0.5(y1+y2)−1 (2.6)
As we can see in Figures 2 and 3, multiplayer matching pennies game consists an excellent benchmark where all traditional gradient flow discretizations fail under perfect competition setting. Interestingly, 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 variation with (K,P ) = (−1.1I, 0.3I) achieves to converge to the unique mixed Nash Equilibrium of the game. In the following sections, we provide theorems that explained formally this long-run behavior of the examined dynamics.
Figure 2: Multiplayer matching pennies under different algorithms
Figure 3: Projected Trajectory of Team A under different algorithms

heading: 3 OUR MAIN RESULTS

heading: 3.1 ON THE COMPLEXITY OF TWO-TEAM ZERO-SUM GAMES
text: We start this section by showing that computing a Nash equilibrium in two-team zero-sum games is computationally hard and thus getting a polynomial-time algorithm that computes a Nash equilibrium is unlikely. Theorem 3.1 (CLS-hard). Computing a Nash equilibrium in two-team zero-sum games is CLS-hard.
The main idea of the proof of Theorem 3.1 relies on a 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, we defer the proof of the above theorem to the paper’s supplement.

heading: 3.2 FIRST-ORDER METHODS FAIL TO STABILIZE
text: 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 equilibria and thus can approximate them well enough. Unfortunately, we can even prove negative results about convergence to Nash equilibria in two-team zero-sum games of well-established methods broadly used in classic two-player zero-sum games.
In this section, we are going to construct a family of two-team zero-sum games with the property 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
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 equilibria. This fact is a 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.
Weakly-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 games5 (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 weakly-stable Nash are unstable). Consider a two-team zero-sum game with utility function of Team B (y vector) being U(x,y) and Team A (x vector) being −U(x,y). Moreover, assume that (x∗,y∗) is a Nash equilibrium of full support that is not weakly-stable. It follows that the set of initial conditions so that GDA converges to (x∗,y∗) is of measure zero for step size η < 1L where L is the Lipschitz constant of∇U .

heading: 3.3 GENERALIZED MATCHING PENNIES (GMP)
text: Inspired by Theorem 3.2, in this section we construct a 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 a 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 n = 2 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 24 possible strategy profiles. In case all the members of a Team choose the same strategy say H or T then the Team “agrees” to play H or T (otherwise the Team “does not agree”).
Thus, in the case both teams “agree”, the payoff of each team is actually the payoffs for the twoplayer matching pennies. If one team “agrees” and the other does not, the team that “agrees” gets payoff ω ∈ (0, 1) and the other team gets penalty ω. If both teams fail to “agree”, both teams get payoff zero. Let xi with i ∈ {1, 2} be the probability that agent i of Team A chooses H and 1 − xi the probability that she chooses T . We also denote x the vector of probabilities for Team A. Similarly, we denote yi for i ∈ {1, 2} be the probability that agent i of Team B chooses H and 1− yi the probability that she chooses T and y the probability vector. The first fact about the game that we defined is that for ω ∈ (0, 1), there is only one Nash equilibrium (x∗,y∗), which is the uniform, i.e., x∗1 = x ∗ 2 = y ∗ 1 = y ∗ 2 = 1 2 for all agents i. Lemma 3.3 (GMP has a unique Nash). The Generalized Matching Pennies game exhibits a unique Nash equilibrium which is (x∗,y∗) = (( 12 , 1 2 ), ( 1 2 , 1 2 )).
Remark 3.4. The fact that the game we defined has a unique Nash equilibrium that is in the interior of [0, 1]4 is really crucial for our negative convergence results later in the section as we will show that it is not weakly-stable Nash equilibrium and the negative result about GDA will be a corollary due to Theorem 3.2. Please also note that if ω = 1 then there are more Nash equilibria, in particular the (0,0), (1,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 ω ∈ (0, 1). Assume that ηGDA < 14 , ηOGDA < min(ω, 1 8 ), ηEG < ω 2 , and ηOMWU < min ( 1 4 , ω 2 ) (bound on the stepsize
5Roughly speaking, games in which we add small Gaussian noise on every payoff.
for GDA, OGDA, EG, and OMWU methods respectively). It holds that the 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 be Nash equilibria. Indeed we can construct examples in which the average iterate of GDA, OGDA, and EG experimentally fail to stabilize to Nash equilibria. In 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):
Figure 4 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 a Nash equilibrium.

heading: 3.4 WASH-OUT FILTERS & ADAPTIVE CONTROL
text: The aforementioned results indicate that to answer the tantalizing question of finding NE in twoteam zero-sum games, our machinery should be broadened outside the limits of textbook optimization arsenal. The mainstay of this effort and our 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 a team zero-sum game so that the utility of Team B is U(x,y) and hence the utility of Team A is −U(x,y) and a Nash equilibrium (x∗,y∗) of the game. Moreover we assume(
−∇2xxU(x∗,y∗) −∇2xyU(x∗,y∗) ∇2yxU(x∗,y∗) ∇2yyU(x∗,y∗)
) is invertible.
For any fixed step size η > 0, we can always find matrices K,P so that KPV-GDA method defined in (2.2) converges locally to (x∗,y∗).
The latter statement concerns the existence of matrices K,P . Below, we provide a sufficient condition under which a simple parametrization of K,P (provably) guarantees convergence.
Theorem 3.8. Consider a two-team zero-sum game so that the utility of Team B is U(x,y) and hence the utility of Team A is −U(x,y) and a Nash equilibrium (x∗,y∗) of the game. Moreover let
H := ( −∇2xxU(x∗,y∗) −∇2xyU(x∗,y∗) ∇2yxU(x∗,y∗) ∇2yyU(x∗,y∗) ) .
and E be the set of eigenvalues ρ of H with real part positive, that is E = {H ′s eigenvalues ρ : Re(ρ) > 0}. We assume that H is invertible and moreover
β = min ρ∈E
Re(ρ)2 + Im(ρ)2
Re(ρ) > max ρ∈E Re(ρ) = α. (3.1)
We set K = k · I, P = p · I. There exist small enough step size η > 0 and scalar p > 0 and for any k ∈ (−β,−α) so that KPV-GDA method defined in (2.2) with chosen K,P converges locally to (x∗,y∗).

heading: 4 EXPERIMENTS
text: In this section, we perform a series of 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 a giant single-agent GAN with 4 layers of 2-128-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 a small number of neurons achieves to fit the data well. We defer the discussion of the experiments with multi-generators multi-discriminator architectures for CIFAR-10 again to the paper’s supplement.
(a) Each generator of MGAN learns one mode of 8-GMM (b) Mode Collapse of singleagent GANs (c) Single-agent GAN can’t discriminate between the modes

heading: 5 CONCLUSIONS AND OPEN PROBLEMS
text: 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 of matrices K,P . One other possible direction is to find a systematic way to get the matrices K,P.
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 (Python/PyTorch/Tensorflow).

heading: A APPENDIX
text: A.1 FURTHER RELATED WORK
The properties of team games have given rise to a 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), a notion introduced by von Stengel & Koller (1997). In this category of two-team zero-sum games, a team of n−players plays defensively against a 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 a non–linear 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 or large-sized normal form games, Basilico et al. (2017a); Celli & Gatti (2018) introduced a relaxed notion of team-maxmin equilibrium with coordination device (TMECor). In TMECor solutions, the team of players shares their strategies exante6 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 a large number of integer variables. To tackle heuristically these hurdles, it (Zhang et al., 2020; Zhang & An, 2020) had been proposed modified versions of incremental strategy generation (ISG) algorithm (See (McMahan et al., 2003)) for large-sized games.
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 a 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 a mixture of generators being too far away from uniform. c) In Stackelberg GAN, (Zhang et al., 2018) exploit the leader-followers relation of discriminator vs generators to achieve smaller minimax gap and better Frechét metrics. For the case of multiple-discriminators: d) In GMAN (Durugkar et al., 2016), an increased number of agents are used to 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.
Interestingly, in the continuous regime, gradient flow has been recently studied under the perspective of dynamical systems. In the setting of Hidden Games, two competitive non-convex operators join in a two-player min-max game. In Piliouras & Schulman (2018); Vlatakis-Gkaragkounis et al. (2019), the authors exploit the bi-linear form of the hidden game to prove antithetical to convergence, 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 choice.
While the main contribution of this work is to highlight the inherent difficulties that the above heuristic architectures are cursed, our theoretical findings in team competition hint also at new optimization schemes like KPV-GDA whose performance is illustrated in Section 4 with delicate network architectures that contain even multiple generators and discriminators simultaneously.
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-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
6That is, the team members are allowed to discuss and agree on tactics before the game starts, but they cannot communicate during the game.
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, a 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 necessarily 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 comparison 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” coordination can be modeled using a coordination device, assuming that the adversary does not observe any signal from the device. The team members agree on a planned strategy (e.g., a 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 two-metaplayer zero-sum game, where the metaplayer is the team as a whole entity with every individual player in perfect coordination with its teammates.
Finally, an additional reason, 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. 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 intercompetition.

heading: B GAME DYNAMICS
text: 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 Descent-Ascent (KPV-GDA) are built. Optimistic Multiplicative Weights Update Method is the optimistic variant of the Multiplicative Weights Update Method.
B.1 GRADIENT DESCENT-ASCENTx (k+1) i = ΠXi { x (k) i − η∇xif(x(k),y(k)) } y (k+1) j = ΠYj { y (k) j + η∇yjf(x(k),y(k))
} B.2 OPTIMISTIC GRADIENT DESCENT-ASCENTx (k+1) i = ΠXi { x (k) i − 2η∇xif(x(k),y(k)) + η∇xif(x(k−1),y(k−1)) } y (k+1) j = ΠYj { y (k) j + 2η∇yjf(x(k),y(k))− η∇yjf(x(k−1),y(k−1))
} B.3 EXTRA GRADIENT METHODx (k+ 12 ) i = ΠXi { x (k) i − η∇xif(x(k),y(k)) } , x (k+1) i = ΠXi { x (k) i − η∇xif(x(k+ 1 2 ),y(k+ 1 2 )) }
y (k+ 12 ) j = ΠYj { y (k) j + η∇yjf(x(k),y(k)) } , y (k+1) j = ΠYj { y (k) j + η∇yjf(x(k+ 1 2 ),y(k+ 1 2 )) }
B.4 OPTIMISTIC MULTIPLICATIVE WEIGHTS UPDATE METHOD x (k+1) i = x (k) i exp ( −2η∇xif(x (k),y(k))+η∇xif(x (k−1),y(k−1)) ) ∑ j x (k) j exp ( −2η∇xif(x(k),y(k))+η∇xif(x(k−1),y(k−1) ) y (k+1) j = y (k) j exp ( 2η∇yj f(x (k),y(k))−η∇yj f(x (k−1),y(k−1)) ) ∑
j y (k) j exp ( 2η∇yj f(x(k),y(k))−η∇yj f(x(k−1),y(k−1)) ) B.5 K,P -VANED GRADIENT DESCENT-ASCENTz (k+1) = ΠZ { z(k) + η (−∇xf(z(k)) ∇yf(z(k)) ) + ηK(z(k) − θ(k)) } θ(k+1) = ΠZ { θ(k) + ηP (z(k) − θ(k))
} Notations x(k)i ( or y (k) j ) stand for the strategy vector of the i-th minimizing (or j-th maximizing)
agent at time-step k. The step size is denoted as η. Operators ΠXi ,ΠYj ,ΠZ are the projection operators to the corresponding simplices. The projection operator is 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.

heading: C DERIVATION OF THE MIN-MAX OBJECTIVE IN EQUATION 2.5
text: By the definition of Variance, we get that : Var [ xi ] = E[x2i ] − ( E[xi] )2 ⇔ E[x2i ] = Var[xi] +( E[xi] )2 . More precisely for any x ∼ N (µ, I), we get E[x2i ] = 1 + µ2i .
Additionally, after calculations, we can get that:
Ez∼N (0,I)[(zi + θi)2] = Var [ zi + θi ] + ( E[zi + θi] )2 θi const.=====⇒ Ez∼N (0,I)[(zi + θi)2] = Var [ zi ] + ( E[zi] + E[θi]
)2 ⇒ Ez∼N (0,I)[(zi + θi)2] = Var [ zi ] + ( 0 + θi
)2 ⇒ Ez∼N (0,I)[(zi + θi)2] = 1 + θ2i
Moreover, it is easy to check that for a mixture D(µ1, σ1I, µ2, σ2I, π1, π2) of two multidimensional normal distributions N (µ1, σ1I),N (µ1, σ1I) with corresponding weights π1, π2:
Varx∼D[xi] = π1σ 2 1 + π2σ 2 2 + π1µ 2 1,i + π2µ 2 2,i − (π1µ1,i + π2µ2,i)2
Specifically for the case of µ1 = µ = −µ2, this equivalent with:
Var[xi] = 1 + µ 2 i − (π1µi − π2µi)2
Hence:
E[x2i ] = Var[xi] + (π1µi − π2µi)2 = 1 + µ2i
So we can apply the following manipulations in the objective (The notation [x2i ] stands for the vector that has as entries the values of the vector x squared):
max v,w min θ,p
Ey∼real [ Dv(y) +Dw(y) ] −
−Ez∼N (0,I),ζ∼N (0,1) [ Gp(ζ) · ( Dv ( −Gθ(y) ) +Dw ( Gθ(y) )) +
+ ( 1−Gp(ζ) ) · ( Dv ( Gθ(y) ) +Dw ( Gθ(y) ))] =
max v,w min θ,p
Ey∼real [ 〈v,y〉+ 〈w, [y2i ]〉 ] −
−Ez∼N (0,I),ζ∼N (0,1) [ (p+ ζ) · ( 〈v,−(z + θ)〉+ 〈w, [(θi + zi)2]〉 ) +
+ ( 1− (p+ ζ) ) · ( 〈v,−(z + θ)〉+ 〈w, [ ( − (θi + zi) )2 ]〉 )] =
max v,w min θ,p
Ey∼real [ 〈v,y〉 ] + Ey∼real [ 〈w, [y2i ]〉 ] −
−Ez∼N (0,I),ζ∼N (0,1) [ (p+ ζ) · ( 〈v, z + θ〉+ 〈w, [(θi + zi)2]〉 ) +
+ ( 1− (p+ ζ) ) · ( 〈v,−(z + θ)〉+ 〈w, [(θi + zi)2]〉 )] =
max v,w min θ,p
〈 v,Ey∼real [ y ]〉 + 〈 w,Ey∼real [ [y2i ] ]〉 −
−p · (〈 v,Ez∼N (0,I) [ (z + θ) ]〉 + 〈 w,Ez∼N (0,I) [ [(θi + zi) 2] ]〉) −
− ( 1− p )( · 〈 v,Ez∼N (0,I) [ − (z + θ) ]〉 + 〈 w,Ez∼N (0,I) [ [(θi + zi) 2] ]〉) =
max v,w min θ,p
〈 v, ( π1µ+ π2(−µ) )〉 + 〈 w, [1 + µ2i ] 〉 −
−p · (〈 v,θ 〉 + 〈 w, [(θ2i + 1)] ]〉) − ( 1− p ) · (〈 v,−θ 〉 + 〈 w, [(θ2i + 1)] 〉 =
max v,w min θ,p (π1 − π2)vTµ− 2pvTθ + vTθ + ∑ i wi(µ 2 i − θ2i )
C.1 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 computing Nash equilibria in congestion games is CLS-hard (Babichenko & Rubinstein (2021)).
As a 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)cooperative game theory, like the ε-approximation of a mixed Nash Equilibrium in a 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 x has a local neighbourhood within which we can readily check for the existence of some other point having a 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-Kernighan heuristic (Papadimitriou, 1992), and finding pure Nash equilibria in many-player congestion games (Fabrikant et al., 2004). The complexity class CLS (“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 as a strong candidate for capturing the complexity of some of those important problems, like the general versions of Banach’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; (Si)i∈N ; (ce)e∈E) where N is the set of agents, E is a set of resources (also known as edges or facilities), and each player i has a set Si of subsets of E. Each strategy si ∈ Si is a set of edges (a path), and ce is a cost (negative utility) function associated with facility e. For a strategy profile s = (s1, s2, . . . , sN ), the cost of player i is given by ci(s) = ∑ e∈si ce(`e(s)), where `e(s) is the number of players using e in s (the load of edge e). It is a well-known result Rosenthal (1973) that congestion games exhibit a potential function Φ(s), that
Φ(s) = ∑ e∈E `e(s)∑ j=1 ce(j)
with the property that if any agent i changes her strategy to s′i it holds that Φ(s′i, s−i)− Φ(si, s−i) = ci(s′i, s−i)− ci(si, s−i).
Reduction. Consider a congestion game (N ;E; (Si)i∈N ; (ce)e∈E) with n = |N | players and potential function Φ. We define a team zero-sum game as follows: Team A has n players, in which each agent i chooses strategies from Si. Team B has n players, with each agent j 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 s (Team B has only one choice) then they get utility uA(s, d) = −Φ(s). The utility members of Team B get is uB(s, d) = Φ(s). Let x∗ ≡ (x∗1, ..., x∗n) and (d, ..., d) be a (possibly mixed) Nash equilibrium in the team zero-sum game we defined. We shall show that (x∗1, ..., x ∗ n) is a Nash equilibrium of the original congestion game and the reduction will be complete. Aiming for contradiction, suppose (x∗1, ..., x ∗ n) is not a Nash equilibrium of the original congestion game. Then there exists an agent i that can deviate from strategy x∗i to x̃i and decrease her expected cost. Hence we have that
0 < Es∼x∗ [ci(s)]− Es∼(x̃∗i ,x∗−i)[ci(s)] = Es∼x∗ [Φ(s)]− Es∼(x̃∗i ,x∗−i)[Φ(s)] (Property of potential).
We conclude that Es∼x∗ [uA(s, d)] = −Es∼x∗ [Φ(s)] < −Es∼(x̃∗i ,x∗−i)[Φ(s)] = Es∼(x̃∗i ,x∗−i)[uA(s, d)] which is a contradiction since (x ∗ 1, ..., x ∗ n) is a Nash equilibrium for the team zero-sum game hence if player i deviates, her payoff (i.e., the payoff of her Team) should not increase.
C.2 MULTIPLAYER MATCHING PENNIES
Below, we present the exact definition of the (2x2) two-team of two-players matching pennies that we discuss in Sec
Team B HH HT/TH TT
Team A HH −1, 1 −1/2, 1/2 1,−1
HT/TH 1/2,−1/2 0, 0 1/2,−1/2 TT 1,−1 −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 B without loss of generality) and strategies k, l, l′ so that if i is forced to play k, then j’s best response is l and that gives larger payoff than another strategy l′ in her support. Formally it holds that (by multi-linearity of U )
(payoff if i, j choose k, l) ∂2U(x∗,y∗) ∂yik∂yjl > ∂2U(x∗,y∗) ∂yik∂yjl′ (payoff if i, j choose k, l′), (C.1)
and also ∂U(x ∗,y∗)
∂yjl = ∂U(x ∗,y∗) ∂yjl′ (*). We shall show that ∇2yyU(x∗,y∗) has a strictly positive eigenvalue tangent in the product of simplices (note that if we were working with A, we would show that ∇2xxU(x∗,y∗) has a strictly negative eigenvalue). Consider a vector of size ∑ i |Si|, (where |Si| is the cardinality of the strategy space of agent i in Team B) which has 1 at coordinates (i, k), (j, l), −1 at coordinate (j, l′) and from which we subtract y∗i ; we denote by v the resulting vector. We shall show that v>∇2xxU(x∗,y∗)v < 0.
By multilinearity of U it follows that ∂ 2U ∂yjs∂yjs′ = 0 (**) for all agents j and strategies s, s′ and the same is true for x variables (team A). We conclude that
1 2 v>∇2yyU(x∗,y∗)v =
∂2U(x∗,y∗)
∂yik∂yjl − ∂
2U(x∗,y∗) ∂yik∂yjl′ − ∑ s∈Si y∗is ( ∂2U(x∗,y∗) ∂yis∂yjl − ∂ 2U(x∗,y∗) ∂yis∂yjl′ )
= ∂2U(x∗,y∗)
∂yik∂yjl − ∂
2U(x∗,y∗) ∂yik∂yjl′ − ( ∂U(x∗,y∗) ∂yjl − ∂U(x ∗,y∗) ∂yjl′ ) (∗) = ∂2U(x∗,y∗)
∂yik∂yjl − ∂
2U(x∗,y∗)
∂yik∂yjl′
(C.1) > 0.
Therefore∇2yyU(x∗,y∗) has a positive eigenvalue and as a result
R :=
( −∇2xxU(x∗,y∗) 0
0 ∇2yyU(x∗,y∗)
) (C.2)
must have a positive and a negative eigenvalue (since the trace is zero).
We consider the Jacobian of the GDA dynamics at (x∗,y∗). The corresponding matrix is the following:
JGDA = I + η ( −∇2xxU(x∗,y∗) −∇2xyU(x∗,y∗) ∇2yxU(x∗,y∗) ∇2yyU(x∗,y∗) ) , (C.3)
We will show that JGDA 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 JGDA would have an eigenvalue with real part greater than 1 and hence magnitude greater than one). Due to (**), we get that JGDA − I has trace zero. To reach contradiction suppose that no eigenvalue of JGDA− I has positive real part, then all eigenvalues of JGDA− I should be imaginary or zero. But an imaginary eigenvalue (that is not zero) also results in an eigenvalue with magnitude greater than one for JGDA, therefore all eigenvalues of JGDA − I should be zero. We use Ky Fan inequalities which states that the sequence (in decreasing order) of the eigenvalues of 12 (H + H
>) majorizes the real part of the sequence of the eigenvalues of H (see Moslehian (2011), page 4) for any matrix H . We choose H = 1η · (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∗,y∗) is of measure zero (for the particular choice of the step size).

heading: D PROOF OF LEMMA 3.3
text: Firstly, we start with the min-max formulation of GMP game:
min x∈[0,1]2 max y∈[0,1]2
−x1x2y1y2 − (1− x1)(1− x2)(1− y1)(1− y2) + x1x2(1− y1)(1− y2)+
+ (1− x1)(1− x2)y1y2 + ω (1− x1x2 − (1− x1)(1− x2)) (y1y2 + (1− y1)(1− y2))− − ω (1− y1y2 − (1− y1)(1− y2)) (x1x2 + (1− x1)(1− x2))
or after simplification, it is equivalent with
min x∈[0,1]2 max y∈[0,1]2
(ω+1)(x1+x2)+(1−ω)(y1+y2)−(x1+x2)(y1+y2)−2ωx1x2+2ωy1y2. (D.1)
Remark D.1. Please note that the objective in the min-max is multi-linear and the degree of each variable in every summand is at most one (total degree is 2). Moreover note that due to the non convexity-concavity of the function above, the max-min is not equal to the min-max.
Let (x∗1, x ∗ 2, y ∗ 1 , y ∗ 2) be a Nash equilibrium. Assuming x ∗ 1, x ∗ 2, y ∗ 1 , y ∗ 2 ∈ (0, 1) from (D.1) and firstorder conditions we get the system of equations
1. ω + 1− y∗1 − y∗2 − 2ωx∗2 = 0,
2. ω + 1− y∗1 − y∗2 − 2ωx∗1 = 0,
3. 1− ω − x∗1 − x∗2 + 2ωy∗2 = 0,
4. 1− ω − x∗1 − x∗2 + 2ωy∗1 = 0.
Combining the first two equations, we have x∗1 = x ∗ 2 and combining the last two it follows y ∗ 1 = y ∗ 2 . Dividing equation one by ω and subtracting three, it follows that 1ω − 2 y∗1 ω + ω − 2ωy ∗ 1 = 0. Hence we conclude that y∗1 = 1 2 . As a result y ∗ 2 = 1 2 and substituting in first equation x ∗ 1 = x ∗ 2 = 1 2 .
• Assume now that x∗1 = 0 and x ∗ 2, y ∗ 1 , y ∗ 2 ∈ (0, 1). Following the same idea, now only
equations 2, 3, 4 hold and instead of the first we have the constraint ω+1−y∗1−y∗2−2ωx∗2 ≥ 0. From 3, 4 we conclude that y∗1 = y ∗ 2 and using 2 it holds that y ∗ 1 = y ∗ 2 = 1+ω 2 . Using 3 follows that 1 − ω − x∗2 + ω(ω + 1) = 0. Thus x∗2 = 1 + ω2 > 1 (this is not possible because x∗2 ∈ [0, 1]).
• Consider the case that x∗1 = 1 and x ∗ 2, y ∗ 1 , y ∗ 2 ∈ (0, 1). Only equations 2, 3, 4 hold and
instead of the first we have the constraint ω + 1 − y∗1 − y∗2 − 2ωx∗2 ≤ 0. From 3, 4 we conclude that y∗1 = y ∗ 2 and using 2 it holds that y ∗ 1 = y ∗ 2 = 1−ω 2 . Using 3 follows that −ω − x∗2 + ω(1− ω) = 0. Thus x∗2 = −ω2 < 0 (this is not possible because x∗2 ∈ [0, 1]). By symmetry the same happens when x∗2 = 0 or x ∗ 2 = 1 and x ∗ 1, y ∗ 1 , y ∗ 2 ∈ (0, 1).
• Case x∗1 = x ∗ 2 = 0 and y ∗ 1 , y ∗ 2 ∈ (0, 1). Using 3, 4 we get y∗1 = y∗2 = ω−12ω < 0 (this is not
possible).
• Case x∗1 = x ∗ 2 = 1 and y ∗ 1 , y ∗ 2 ∈ (0, 1). Using 3, 4 we get y∗1 = y∗2 = ω+12ω > 1 (this is not
possible).
• Case x∗1 = 0 and x ∗ 2 = 1 and y ∗ 1 , y ∗ 2 ∈ (0, 1). Using 3, 4 we get y∗1 = y∗2 = 12 . Moreover
one becomes ω − 2ωx∗2 ≥ 0 and two ω − 2ωx∗1 ≤ 0, that is x∗1 ≥ 12 and x ∗ 2 ≤ 12 (contradiction). The case x∗1 = 1 and x ∗ 2 = 0 and y ∗ 1 , y ∗ 2 ∈ (0, 1) is symmetric.
Similarly one can consider the case where the y team plays pure and x∗1, x ∗ 2 ∈ (0, 1). One can also check that all possible pure strategy profiles are not Nash equilibria.

heading: E PROOF OF THEOREM 3.5
text: We split the proof in 3 parts. Before we start the proof, note that the Hessian of U (E.4) has infinity norm less than 4 (since ω ∈ (0, 1)), so U has gradient Lipschitz with L ≤ 4. Thus for the rest of the proof for GDA, we choose ηOGDA < 14 .
GDA. For GDA the proof will be straightforward. We will show that (x∗1, x∗2, y∗1 , y∗2) is a 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 x1 fixes his strategy to x1 = 0. and y1, y2 keep their strategy ( 12 , 1 2 ). We shall show that x2 is not indifferent in his support and would like to change his mixed strategy x2 = 12 to pure. When x1 = 0 and y1 = y2 = 12 the payoff of Team A (x variables) becomes −ωx2 − 1 + ω 2 . Since ω ∈ (0, 1), x2 prefers to play x2 = 0 (instead of 12 she had). We conclude that ( 1 2 , 1 2 , 1 2 , 1 2 ) is not a weakly-stable Nash equilibrium.
OGDA. The Jacobian of the update rule of OGDA dynamics (use the same machinery of Section 3 in Daskalakis & Panageas (2018)) is the following:
JOGDA =  I− 2ηOGDA∇ 2 xxU −2ηOGDA∇2xyU ηOGDA∇2xxU ηOGDA∇2xyU
2ηOGDA∇2yxU I + 2ηOGDA∇2yyU −ηOGDA∇2yxU −ηOGDA∇2yyU I 0 0 0 0 I 0 0
 , (E.1)
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
∇2xxU = ( 0 −2ω −2ω 0 ) ,∇2yyU = ( 0 2ω 2ω 0 ) ,∇2xyU = ( −1 −1 −1 −1 ) .
The corresponding Jacobian matrix becomes:
JOGDA =  I 0 0 00 I 0 0I 0 0 0 0 I 0 0 + ηOGDA  0 4ω 2 2 0 −2ω −1 −1 4ω 0 2 2 −2ω 0 −1 −1 −2 −2 0 4ω 1 1 0 −2ω −2 −2 4ω 0 1 1 −2ω 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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)
π(λ) = (4(1 + ω2)η2OGDA(1− 2λ)2 + (λ− 1)2λ2 − 4ωηOGDAλ(1− 3λ+ 2λ2)) ·((λ− 1)λ+ 2ωηOGDA(2λ− 1))2.
(E.3)
A root of π(λ) is 12 ( 1 + 4ηOGDAj + 4ωηOGDA + √ 1− 16η2OGDA + 32jωη2OGDA + 16ω2η2OGDA ) , which is in absolute value greater than one for 0 < ηOGDA ≤ ω It is also easy to see the Hessian of U , that is: (
∇2xxU ∇2xyU ∇2yxU ∇2yyU
) =  0 −2ω −1 −1−2ω 0 −1 −1−1 −1 0 2ω −1 −1 2ω 0  (E.4) is invertible for ω ∈ (0, 1) (this is true as the eigenvalues are −2ω, 2ω,−2 √ 1 + ω2, 2 √ 1 + ω2, non of which is zero). From Theorem 3.2 in Daskalakis & Panageas (2018) follows that the initial conditions so that OGDA converges to the Nash equilibrium is of measure zero for step size ηOGDA < 1 2L ≤ 1 8 (where L is the Lipschitz constant of ∇U ). We choose ηOGDA ≤ min( 1 8 , ω) and the claim follows.
EG. The Jacobian of EG dynamics computed at the Nash equilibrium (fixed point) is given below (made use of chain rule):
JEG = I+ηEG ( −∇2xxU(x∗,y∗) −∇2xyU(x∗,y∗) ∇2yxU(x∗,y∗) ∇2yyU(x∗,y∗) ) +η2EG ( −∇2xxU(x∗,y∗) −∇2xyU(x∗,y∗) ∇2yxU(x∗,y∗) ∇2yyU(x∗,y∗) )2 . (E.5) We substitute with the values and we get
JEG = I+ηEG  0 2ω 1 12ω 0 1 1−1 −1 0 2ω −1 −1 2ω 0 +η2EG  4ω 2 − 2 −2 4ω 4ω −2 4ω2 − 2 4ω 4ω −4ω −4ω −2 + 4ω2 −2 −4ω −4ω −2 −2 + 4ω2  . (E.6) The eigenvalues of JEG are 1 + ηEG(−2ω + 4ηEGω2), 1 + ηEG(−2ω + 4ηEGω2), 1 + ηEG ( −4ηEG + 2ω + 4ηEGω2 − 2 √ −1− 8ηEGω − 16η2EGω2 ) , and
1 + ηEG ( −4ηEG + 2ω + 4ηEGω2 + 2 √ −1− 8ηEGω − 16η2EGω2 ) . If −4ηEG + 2ω + 4ηEGω2 > 0 then JEG will have an eigenvalue with absolute value greater than one. A sufficient condition for that is ηEG ≤ ω2 . Finally, for the same choice of stepsizes we have that JEG is invertible for all (x,y), hence the EG dynamics is a local diffeomorphism. From Theorem 2 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:
JOMWU =  1 ηω η η 0 −ηω2 − η 2 − η 2 ηω 1 η η −ηω2 0 − η 2 − η 2 −η −η 1 ηω η2 η 2 0 − ηω 2 −η −η ηω 1 η2 η 2 − ηω 2 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
 . (E.7)
It turns out that matrix (E.7) has characteristic polynomial (help of Mathematica)
π(λ) = 1
16
( (4 + ω2)η2(1− 2λ)2 + 4(λ− 1)2λ2 − 4ωηλ(1− 3λ+ 2λ2) ) ·
(2(λ− 1)λ+ ωη(2λ− 1))2 . (E.8)
One root of the polynomial π(λ) above is 12 (1 + 2ηj + ηω + √
1− 4η2 + 4η2ωj + η2ω2). As in the analysis of OGDA, it turns out that for 0 < η < ω the aforementioned root has absolute value greater than one.
Therefore we conclude that the Nash equilibrium where each agent plays ( 12 , 1 2 ) 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 are fixed points). To exclude such stabilization, the trick is that if OMWU stabilizes to a point, it should be (approximate coarse correlated equilibrium where the approximation depends on the size of the stepsize). However, none of the pure strategy profiles is a ω/2- approximate coarse correlated equilibrium, so OMWU does not stabilize. Hence if we choose 0 < η < ω/2, OMWU does not stabilize.

heading: F PROOF OF THEOREM 3.8
text: 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:
JKPV-GDA = I + η  k · I + ( −∇2xxU(x∗,y∗) −∇2yxU(x∗,y∗)∇2xyU(x∗,y∗) ∇2yyU(x∗,y∗) ) −k · I
p · I −p · I  . (F.1) It 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.1. Let J = I+ηM where I is the identity matrix. Suppose thatM has all of its eigenvalues with a real part that is negative. Then, there exists an interval (0, η0) so that if η ∈ (0, η0) then J has all of its eigenvalues with an absolute value less than one.
Proof. Let ai + bi · j be an eigenvalue of M such that ai < 0. Assume that η < − 2aia2i+b2i , then the corresponding eigenvalue of J is 1 + η(ai + bi · j), the magnitude of which is (1 + ηai)2 + η2b2i = 1 + 2ηai + η 2(a2i + b 2 i ) < 1 since −2ai > η(a2i + b2i ) (by assumption). Hence we can choose η0 to be mini −2aia2i+b2i > 0.
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 + ( −∇2xxU(x∗,y∗) −∇2yxU(x∗,y∗)∇2xyU(x∗,y∗) ∇2yyU(x∗,y∗) ) −k · I
p · I −p · I
 . (F.2)
By setting M11,M12,M21,M22 as the corresponding block matrices we compute the characteristic polynomial of M . It holds
det(M − λI) = det ([
M11 M12 M21 M22
] − λI ) = det ([ M11 − λI −kI
pI −pI− λI
]) = (F.3)
= det
([ M11 − λI− kpp+λ I −kI
0 −pI− λI
]) = (F.4)
= det ( M11 − ( λ+ kp
p+ λ
) I ) det (−(p+ λ)I) . (F.5)
det(M − λI) has roots at λ = −p and when
det ( M11 − ( λ+ kp
p+ λ
) I ) = 0.
Therefore, if M has all eigenvalues with real part negative, we must have p > 0. Let ρ be an eigenvalue of ( −∇2xxU(x∗,y∗) −∇2yxU(x∗,y∗) ∇2xyU(x∗,y∗) ∇2yyU(x∗,y∗) ) . It must hold that
λ+ kp
p+ λ − k = ρ. (F.6)
We need to investigate under what assumptions λ will have real part negative. We expand (F.6) and we get λ2 + λ(p− k − ρ)− ρp = 0. (F.7) We solve Equation (F.7) and we get
λ1,2 = −p+ k + ρ± √ (p− k − ρ)2 + 4ρp 2 . (F.8)
We provide sufficient conditions so that Re(λ1,2) < 0. We consider the following cases:
• ρ is real and negative. In this case observe that for p = 0 we have that λ1,2 = k + ρ and 0. Note that for k < 0, the first eigenvalue has real part negative and the second eigenvalue is zero. We compute the first derivative at p = 0 and this gives 12 ( −1 + −k+ρ|k+ρ| ) = ρ−k−ρ <
0. Therefore the λ1,2 as a function of p is strictly decreasing at zero. We conclude that for p sufficiently small and positive, both eigenvalues of M will be real and negative. Hence if an eigenvalue of H is real and negative then for p sufficiently small positive and k < 0 both eigenvalues of M will be negative.
• ρ is complex with |Im(ρ)| 6= 0. In this case observe that for p = 0 we have that λ1,2 = k+ρ and 0. If we choose min(0,−Re(ρ)) > k, then the first eigenvalue will have real part negative. Now using the same idea as for the first case, we compute the first derivative of the real part of λ1,2 as a function of p and we get
1
2
( −1± k 2 − Re(ρ)2 − Im(ρ)2
(k + Re(ρ))2 + Im(ρ)2
) .
The expression above is negative as long as−Re(ρ)2−Im(ρ)2−kRe(ρ) < 0. The equation is trivially satisfied when Re(ρ) < 0 since k is chosen to be negative. Assume Re(ρ) > 0 (if it is zero then the above is trivially true since the imaginary part is non-zero). It occurs that the inequality above is true when k > − |ρ| 2
Re(ρ) . Since k is chosen to be smaller than min(0,−Re(ρ)), it suffices to show that
−Re(ρ)) > − |ρ| 2
Re(ρ) is satisfied by our assumptions.
The above is true as long as Im(ρ) 6= 0. Let E be the set of eigenvalues ρ of H with real part positive (and non-zero imaginary part by assumption). There exists a choice for η, k, p, in which η, p > 0 and sufficiently small and k is negative and chosen to be
min ρ∈E
|ρ|2
Re(ρ) > −k > max ρ∈E Re(ρ).

heading: G CIFAR-10
text: CIFAR-10 is a well-established testbed for various GAN architectures. It 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 et 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 to 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.

Review summaries:
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. 

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.

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.