Towards convergence to Nash equilibria in two-team zero-sum games

Problem setting

• Two-team zero-sum games model independently randomized agents sharing utilities within teams and opposing the other team.The framework includes bilinear and broad nonconvex-nonconcave games, including adversarial potential games.Source: §1 · p. 2

Motivation

• Nash equilibrium remains relevant when coordination is unavailable, unreliable, or inappropriate, despite TMECor often yielding higher team utility.The paper emphasizes that no single solution concept fits every two-team setting.Source: §1 · p. 2

Computational complexity

• Computing an approximate, possibly mixed, Nash equilibrium in two-team zero-sum games is CLS-hard.This is stated as Theorem 3.1 and is harder than finding pure Nash equilibria in congestion games or approximate fixed points of gradient descent.Source: §1 · p. 3

Online learning

• Projected GDA, OGDA, OMWU, and extra gradient fail to converge locally to mixed Nash equilibria in a simple family of two-team zero-sum games.The paper presents this family as the first known example where all four methods provably fail simultaneously.Source: §1 · p. 3

Proposed method

• The proposed control-inspired first-order method modifies GDA with stabilizing feedback while preserving decentralization.Its feedback is designed to stabilize unstable fixed points without prior knowledge of their positions or introducing new fixed points.Source: §1 · p. 3

Experiments

• Experiments report that multi-GAN architectures outperform single-agent architectures relative to network capacity on synthetic and CIFAR10 datasets.These experiments are conducted in simple two-team zero-sum GANs.Source: §1 · p. 3

2 Preliminaries

• A two-team zero-sum game has independently mixed-strategy players whose teammates share utility and whose opposing team has the negative utility.The game assumes succinct representation and polynomial-time utility evaluation for mixed strategy profiles.Source: §2 · p. 4
• The paper analyzes GDA, OGDA, extra gradient, and OMWU as candidate decentralized methods for computing Nash equilibria.Their precise definitions are deferred to the appendix.Source: §2 · p. 4
• For GDA, OGDA, and extra gradient, fixed points correspond to Nash equilibria, making stabilization around fixed points a convergence test.The statement excludes OMWU from the fixed-point correspondence in Fact 2.1.Source: §2 · p. 4
• In the absence of pure equilibria, all four examined methods fail to stabilize at fixed points even in a two-player-per-team game, so they fail to converge to its mixed equilibrium.This provides the dynamical-systems motivation for seeking a different method.Source: §2 · p. 4
• The proposed vaned GDA adds a two-matrix feedback loop that achieves asymptotic last-iterate convergence to the mixed Nash equilibrium under suitable conditions.The auxiliary variable estimates the fixed point while feedback stabilizes the iterate around that estimate.Source: §2 · pp. 4–5

2.1.1 Learning a mixture of gaussians with multi-agent GAN’s

• A multi-agent GAN example represents generators and discriminators as competing teams, with the generator sampling a Gaussian mixture and discriminators scoring realness.The generator’s independent randomness controls mixture-component selection, while another generator shifts samples.Source: §2.1 · p. 5, §2.1.1 · p. 5
• The Gaussian-mixture example reports that GDA fails, whereas OGDA, extra gradient, and KPV-GDA converge to the Nash equilibria and recover the ground-truth mixture.The equilibrium conditions are given in terms of θ and p relative to the mixture parameters.Source: §2.1.1 · p. 5

2.1.2 Multiplayer Matching Pennies

• Generalized multiplayer matching pennies benchmarks the methods by rewarding team coordination, penalizing unilateral coordination mismatches, and giving zero payoff when neither team coordinates.The game is presented as a nontrivial setting where even OGDA and extra gradient fail to converge.Source: §2.1.2 · pp. 5–6

3.1 On the hardness of computing NE in two-team zero-sum games

• Computing a Nash equilibrium in a succinctly represented two-team zero-sum game is CLS-hard.The proof reduces from approximating Nash equilibria in congestion games.Source: §3.1 · p. 6

3.2 Failure of common online, first-order methods

• GDA, OGDA, OMWU, and EG can fail to converge locally or asymptotically to mixed Nash equilibria in a constructed family of two-team games.For non-weakly-stable full-support equilibria, GDA converges only from a Lebesgue-measure-zero set of initial conditions under the stated stepsize condition.Source: §3.2 · p. 7, §3.3 · p. 7

3.3 Generalized Matching Pennies (GMP)

• The Generalized Matching Pennies benchmark uses two teams of two players whose agreement or disagreement determines matching-pennies payoffs, penalties, or zero payoff.The game is nonconvex-nonconcave due to multilinearity and satisfies none of the listed monotonicity, cocoercivity, zero-duality-gap, or unconstrained-space properties.Source: §3.3 · pp. 7–8, Properties of GMP · p. 8

Properties of GMP.

• The Generalized Matching Pennies game has a unique Nash equilibrium, which is interior and assigns each agent probability 1/2 to each action in the stated game.The passage identifies this equilibrium as not weakly stable and says its interiority is crucial for later negative convergence results.Source: Properties of GMP · p. 8
• Average iterates of GDA, OGDA, OMWU, and EG can stabilize at points that are not Nash equilibria, so averaging does not repair the benchmark’s failure.The reported figure concerns average-iterate behavior rather than only last iterates.Source: Properties of GMP · p. 8, Figure 3 · p. 9

3.4 Our proposed method

• KPV-GDA uses control-inspired matrix parameters and can converge locally to a Nash equilibrium under suitable conditions.An existential result allows matrix choices for any fixed stepsize, while a scalar identity parametrization yields convergence for sufficiently small stepsize and suitable k and p.Source: §3.4 · pp. 8–9
• The general matrix-existence guarantee is limited because selecting K and P may require knowledge of the Nash equilibrium and need not produce an uncoupled practical dynamic.The paper therefore follows it with sufficient conditions for a simpler parametrization.Source: §3.4 · p. 9

• Multi-agent architectures attain better-quality solutions because their expressivity differs from single-agent architectures, not because theoretical hardness disappears.The paper distinguishes convergence rates from non-convergence and attributes the observed advantage to attainable solution quality.Source: §4 · p. 10
• Figure 4 contrasts generators learning separate Gaussian modes with single-agent mode collapse and failure to discriminate between modes.Source: Figure 4 · p. 10

5 Conclusions and Open Problems

• The paper concludes that GDA, OGDA, OMWU, and EG fail to converge to Nash equilibria in both average and last iterates, while KPV-GDA stabilizes around Nash equilibria.Source: §5 · p. 10

A Further related work

• Convergence properties of online-learning and first-order methods in team games remain poorly understood.Source: A Further related work · p. 16
• Team-maxmin equilibria provide robustness through uncoordinated strategies but are NP-hard to compute, limiting online-learning and first-order approaches.Source: A Further related work · p. 16
• TMECor algorithms for large games use MILP formulations with many integer variables or heuristic incremental strategy generation.Source: A Further related work · p. 16
• Multi-GAN variants use mixtures, regularization, leader-following, multiple agents, or distributed workers to improve quality, generalization, or task coverage.Source: A Further related work · p. 16

A.1 Discussion about different solution concepts

• TMECor can improve social welfare but requires prior game knowledge, whereas Nash equilibrium applies when teammates may lack game knowledge or cannot coordinate beforehand.Source: §A.1 · p. 16
• Nash equilibrium is therefore presented as a solution concept requiring thorough investigation in two-team zero-sum games.Source: §A.1 · p. 17

A.2 Adversarial potential games.

• The adversarial potential setting represents each player’s cost or utility as a shared potential plus a term independent of that player’s own strategy.Source: §A.2 · p. 17
• An ε-approximate Nash equilibrium in the constructed two-team zero-sum game Γ(n, m, Φ) is also an ε-approximate Nash equilibrium of the original adversarial potential game.Source: §A.2 · p. 17

B Game Dynamics

• GDA is the prototypical min-max method underlying OGDA, EG, and KPV-GDA, while OMWU is the optimistic variant of MWU.Source: B Game Dynamics · p. 17

B.5 K, P-vaned Gradient Descent-Ascent

• KPV-GDA uses projection operators to keep iterates within feasible strategy simplices, unlike OMWU where feasibility is guaranteed by the update structure.Source: §B.5 · p. 18

C Properties of GMP

• The extra-gradient convergence conditions are not satisfied for GMP.Source: C Properties of GMP · p. 18

C.1 Lack of favorable properties

• GMP violates the Minty variational inequality, and weak-MVI violations are numerically verified for ω = 1/2 across tested ρ values.Source: §C.1 · p. 19
• Known techniques cannot tackle Nash-equilibrium computation in GMP because the relevant favorable variational-inequality properties fail.Source: §C.1 · p. 19
• Cocoercivity does not hold in GMP because it is stronger than the already-unsatisfied MVI condition.Source: §C.1 · p. 19
• GMP is not strictly hidden convex-concave, so continuous-time global-convergence results for that class do not apply.Source: §C.1 · p. 19

C.2 GMP satisfies the sufficient conditions of Theorem 3.5

• The generalized matching pennies game satisfies the sufficient conditions of Theorem 3.5 through its eigenvalue structure.The eigenvalues with positive real part are E = {2ω − 2i, 2ω + 2i}.Source: §C.2 · p. 19
• For ω = 1/2, convergence occurs when k ∈ (−5, −1).Source: §C.2 · p. 19

D.1 Derivation of the min-max objective in equation 3

• The objective is presented for a mixture of two multidimensional normal distributions with parameters µ1, σ1I, µ2, σ2I and weights π1, π2, including the symmetric case µ1 = µ = −µ2.Source: §D.1 · p. 19

E.1 Proof of Theorem 3.1

• Computing Nash equilibria in two-team zero-sum games is CLS-hard via a reduction from congestion-game Nash equilibrium computation.The reduction uses the CLS-hardness of congestion games and maps a congestion-game potential Φ to team utilities uA(s,d) = −Φ(s) and uB(s,d) = Φ(s).Source: §E.1 · pp. 20–21
• The appendix situates CLS among PPAD and PLS and relates it to continuous local-search problems such as KKT points and gradient-descent fixed points.Source: §E.1 · pp. 20–21
• The reduction uses dummy players on one team, while the other team’s strategies coincide with the congestion game’s agent strategies.Succinct representation and the polynomial expectation property are assumed for both games.Source: §E.1 · p. 21

E.2 Multiplayer Matching Pennies

• The benchmark includes a 2×2 two-team, two-player multiplayer matching-pennies game.Source: §E.2 · p. 21

E.3 Proof of Theorem 3.2

• At the benchmark equilibrium, the relevant team Hessians have positive and negative eigenvalues because their traces are zero.The proof constructs tangent directions showing opposite curvature for the two teams.Source: §E.3 · p. 22
• GDA has an eigenvalue with absolute value greater than one, so convergence to the Nash equilibrium occurs only from a measure-zero set of initial conditions.The argument uses the Jacobian at the equilibrium, trace properties, and eigenvalue inequalities.Source: §E.3 · pp. 22–23

E.4 Proof of Lemma 3.1

• Boundary cases are ruled out because the equilibrium equations imply probabilities outside [0, 1] or contradictory inequalities.Source: §E.4 · p. 23
• The generalized matching-pennies game has an interior equilibrium with x*_1 = x*_2 and y*_1 = y*_2, while all pure strategy profiles are excluded as Nash equilibria.Source: §E.4 · p. 23

E.5 Proof of Theorem 3.3

• GDA, OGDA, OMWU, and EG fail to converge locally to the benchmark Nash equilibrium under the stated step-size conditions.For GDA, the equilibrium is not weakly stable; OGDA and EG have expanding Jacobian eigenvalues; OMWU’s equilibrium is repelling and pure fixed points are excluded from stabilization.Source: §E.5 · pp. 24–26
• For EG, a sufficient condition for an eigenvalue to have absolute value greater than one is ηEG ≤ ω/2.Source: §E.5 · p. 25

E.6 Proof of Theorem 3.4

• KPV-GDA adds control feedback to the local GDA linearization, exploiting stabilizability of the pair (JGDA, I).The construction uses matrix transformations and a controllability argument based on the PBH test.Source: §E.6 · p. 26
• The stabilization construction requires JGDA + K to be stable with eigenvalues away from 1, while a suitable perturbation matrix controls the remaining term.Source: §E.6 · p. 27

E.7 Proof of Theorem 3.5

• KPV-GDA is locally attracting when the constructed matrix M has all eigenvalues with negative real parts, with sufficiently small step size.The discrete-time claim follows from the fact that J = I + ηM has spectral radius below one for sufficiently small η.Source: §E.7 · p. 28
• Sufficient parameter conditions are derived separately for real negative and complex eigenvalues of the underlying matrix H.Source: §E.7 · p. 29

F Experiments

• MGAN’s eight shallow generator-discriminator pairs fit the eight-mode Gaussian mixture, whereas a larger single-agent GAN exhibits both mode collapse and mode drop without stabilizing.The MGAN uses 2-layer 2-16-2 ReLU networks, while the single-agent GAN uses 4-layer 2-128-256-1024-2 networks.Source: F Experiments · p. 30
• The demonstrated iterations mark approximate convergence, with no observed changes afterward.Source: F Experiments · p. 30
• Figure 5 contrasts mode specialization across MGAN generators with mode collapse and failed mode discrimination in a single-agent GAN.Source: Figure 5 · p. 30

F.1 MGAN vs. WGAN

• MGAN produces diverse, more realistic CIFAR-10 samples from an early stage, while WGAN-GP initially covers only certain classes and takes longer to become realistic.Source: §F.1 · p. 30
• The WGAN-GP snapshots at 10,000, 15,000, and 25,000 iterations document its progression across training.Source: Figure 7 · p. 32, Figure 8 · p. 32, Figure 9 · p. 33

G Empirical performance of the proposed method

• The Nash equilibrium gap vanishes for virtually all of 500 random two-team games with two strategies per player under fixed parameters η = 0.05, k = −1.2, p = 0.02.The authors state that this suggests Theorem 3.5’s conditions are sufficient but not necessary.Source: G Empirical performance of the… · p. 34, Figure 10 · p. 34
• The Nash equilibrium gap is defined as the sum of each player’s best-response advantage over the strategy they play.Source: G Empirical performance of the… · p. 34
• Most random 2-vs.-2 two-team games with three strategies per player converge to a 0 NE-gap using fixed parameters η = 0.05, k = −1.05, p = 0.005.Source: G Empirical performance of the… · p. 34, Figure 11 · p. 35, Figure 12 · p. 35
• For 500 random two-player zero-sum games with five strategies per player, the method converges for virtually all games without tuning parameters separately for each game.Source: G Empirical performance of the… · p. 34