# GENERALIZED NATURAL GRADIENT FLOWS IN HIDDEN CONVEX-CONCAVE GAMES AND GANS

**Andjela Mladenovic** _[∗]_ **Iosif Sakos** **Gauthier Gidel[†]** **Georgios Piliouras**
Univ. of Montr´eal & Mila SUTD Univ. of Montr´eal & Mila SUTD

ABSTRACT

Game-theoretic formulations in machine learning have recently risen in prominence, whereby entire modeling paradigms are best captured as zero-sum games.
Despite their popularity, however, their dynamics are still poorly understood. This
lack of theory is often substantiated with painful empirical observations of volatile
training dynamics and even divergence. Such results highlight the need to develop
an appropriate theory with convergence guarantees that are powerful enough to inform practice. This paper studies the generalized Gradient Descent-Ascent (GDA)
flow in a large class of non-convex non-concave Zero-Sum games dubbed Hidden Convex-Concave games, a class of games that includes GANs. We focus on
two specific geometries: a novel geometry induced by the hidden convex-concave
structure that we call the hidden mapping geometry and the Fisher information
geometry. For the hidden mapping geometry, we prove global convergence under
mild assumptions. In the case of Fisher information geometry, we provide a complete picture of the dynamics in an interesting special setting of team competition
via invariant function analysis.

1 INTRODUCTION

Min-max optimization has found extensive applications in modern Machine Learning (ML) and
Deep Learning. Popular application settings include Generative Adversarial Networks (GANs)
(Goodfellow et al., 2014), adversarial training (Madry et al., 2018), and multi-agent reinforcement
learning (Silver et al., 2017). In all of these cases, a pair of networks is typically trained towards
finding an approximate equilibrium of a highly non-convex non-concave problem. However, such
settings go beyond classical and well-known results in game theory for which equilibria only exist
in more restrictive settings, i.e., convex-concave games (Sion et al., 1958). Unfortunately, there is
no parallel guarantee if the payoff is not convex-concave, and all these applications are indeed based
upon non-convex non-concave games. Even worse, many negative results occur when dealing with
such payoffs: global or local minimax may not exist (Jin et al., 2020), and even if they exist, there is,
in general, no “reasonable algorithm”[1] that can globally converge to any meaningful notion of local
optimum (Letcher, 2021; Hsieh et al., 2020). To overcome these negative results, we analyze a specific class of non-convex non-concave games called Hidden Convex-Concave (HCC) games (Flokas
et al., 2020; Gidel et al., 2021; Flokas et al., 2021) that include many Machine Learning applications
such as GANs (Goodfellow et al., 2014), Adversarial Example Games (AEG) (Bose et al., 2020), or
Minimax Estimation of Conditional Moment (Dikkala et al., 2020).

**Our contributions. In the setting of HCC games, our analysis tackles unique challenges not occur-**
ring in the standard convex-concave games setting. We propose a new type of dynamics, dubbed
_Natural Hidden Gradient dynamics (NHG), and we prove its convergence to stationary points of the_
HCC game. Critically, our convergence results are global, i.e., we do not make any assumptions
about initial conditions, e.g., that the initial points belong to some local neighborhood. This novel
algorithm is inspired by the generalization of gradient flows in different Banach spaces than the standard Euclidean one. Arguably, the most well-known non-Euclidean gradient is the natural gradient

_∗Emails of contact:{andjela.mladenovic,gidelgau}@mila.quebec,_
iosif sakos@mymail.sutd.edu.sg, georgios@sutd.edu.sg
_†Canada CIFAR AI Chair_
1see (Letcher, 2021, Definition 5) for a definition of “reasonable algorithm”


-----

flow induced by the Fisher information matrix, which enjoys deep connections to the Replicator
Dynamics (RD). Thus, a natural second question emerges: Can we have similar convergence guarantees for RD? In that regard, we provide a complete picture of the resulting dynamics in a setting of
team competition via invariant function analysis. Specifically, we reduce the flow of the dynamics to
a competition between two generalized gradients, one for each team. We show that the behavior of
the dynamics in this setting is constrained by a maximal number of invariant functions, which, combined with the actual geometry of the available strategies, shows that the system can either converge
or cycle. These two results showcase, both, the importance of adapting the “algorithmic geometry”
to the application and the data at hand, as well as the unexplored effects of feasibility constraints on
the complexity of well-known game dynamics.

2 RELATED WORK

Despite the popularity of deep learning applications involving non-convex non-concave games, our
understanding of their optimization dynamics and the nature of their solution concepts are still preliminary. However, this space has already witnessed a few important early works that focus on
identifying new solution concepts. These solution concepts—which are also broadly applicable in
general min-max games—include (local/differential) Nash equilibria (Adolphs et al., 2019; Mazumdar & Ratliff, 2019), (local/differential) Stackelberg equilibria (Fiez et al., 2020; Wang et al., 2020),
local minmax (Daskalakis & Panageas, 2018), local robust points (Zhang et al., 2020), and approximate minimax theorems (Jin et al., 2020; Gidel et al., 2021). Numerous solutions concepts such as
cycles (Vlatakis-Gkaragkounis et al., 2019), chaotic behavior (Cheung & Piliouras, 2019; Cheung &
Tao, 2021), and computational issues (Daskalakis et al., 2021) indicate that solving min-max games,
in general, might involve challenging and complex behavior.

Many algorithms have been proposed to solve restricted classes of non-convex non-concave games
such as Polyak-Łojasiewicz games (Nouiehed et al., 2019; Yang et al., 2020), nonconvex-concave
games (Lin et al., 2020; Ostrovskii et al., 2021; Yang et al., 2020; Kong & Monteiro, 2021), as well as
classes of games inspired by variational inequalities (Mertikopoulos et al., 2019; Diakonikolas et al.,
2021; Lee & Kim, 2021). However, even though they are significant advances in the understanding
of non-convex non-concave game dynamics, such classes of games may not encompass games where
the players are parameterized neural networks such as GANs.

While convergence in GANs has been a topic of exploration (Kodali et al., 2017; Heusel et al.,
2017; Mescheder et al., 2018; Gemp & Mahadevan, 2018; Li et al., 2018; Hsieh et al., 2019; Cao &
Guo, 2020), its hidden convex-concave structure has not been exploited before, and there were no
theoretical global convergence guarantees in a general setting up to this date. In particular, Hsieh
et al. (2019) use a lifting trick and proceed in solving a relaxation of the problem in the distribution
space, while in our work we work entirely in the parameter space. With this respect, we consider
Flokas et al. (2021), and Gemp & Mahadevan (2018) as the closest related works. On the one hand,
in Gemp & Mahadevan (2018), the authors propose crossing-the-curl, a second-order technique, and
provide global convergence guarantees for the Wasserstein Linear Quadratic GAN (W-LQGAN).
While the W-LQGANs is a class of non-convex non-concave GANs it remains far from the GAN
formulation used in practice where the discriminator and the generator are neural networks. On
the other hand, the idea of Hidden Convex-Concave (HCC) games was first proposed by Flokas
et al. (2021) and Gidel et al. (2021). While Flokas et al. (2021) study the Gradient Descent-Ascent
(GDA) dynamics in the HCC setting, their work relies on hard-to-verify safety conditions. Our
global convergence results without hard-to-test assumptions on initialization are first of their kind,
to the best of knowledge.

3 PRELIMINARIES

Many game-theoretic applications in machine learning often involve a specific structure where the
models’ payoff is a convex-concave function (e.g., minimizing Jensen-Shannon-Divergence when
training GANs). To model this specific structure, we propose the following definition of Hidden
_Convex-Concave (HCC) games where intuitively, the game’s payoff is a convex-concave function_
whose actions are parametrized by non-convex mappings.


-----

**Definition 1 (Hidden Convex-Concave game). A Hidden Convex-Concave game comprises a collec-**
_tion of payoff (Lx,x′_ )x,x′∈Rd _, a distribution p, and two parametrized mappings, F : R[M]_ _×R[d]_ _→_ R,
_and G : R[N]_ _× R[d][′]_ _→_ R, such that the minimax game of interest is

**_θminR[M][ max]φ_** R[N][ Ψ] [(][θ][,][ φ][)] _where_ _Ψ_ (θ, φ) = L(Fθ, Gφ) := E(x,x′)∼p[Lx,x′ (Fθ(x), Gφ(x[′]))] . (1)
_∈_ _∈_

In this setting, while we do not expect Ψ (θ, φ) to be convex-concave, we assume the function L :
F×G → R to be convex-concave where F and G are, respectively, convex subsets of {F : R[d] _→_ R}
and {G : R[p] _→_ R}.[2] We extended Flokas et al. (2021)’s definition to now be able to include most
minimax machine learning applications such as GANs or AEG.

**Example 1 (Hidden Matching Pennies (HMP) games). Let us consider p, q ∈** [0, 1] the probabilities
_of picking HEADS for the first and the second player, respectively, in a Matching Pennies game with_
_payoff matrix A ∈_ R[2][×][2], where Ai,j = 1 if i = j; −1, otherwise. Then the payoff of this game is
_defined via_

_Lx,x′_ (p, q) := (1 2p)(1 2q) _if (p, q)_ [0, 1][2] _and_ 0 otherwise . (2)
_−_ _−_ _∈_

_Now, let us consider any mappings F : R[M]_ _×R[d]_ _→_ [0, 1] and G : R[N] _×R[d]_ _→_ [0, 1], such that their
_output does not depend on the d-dimensional input, i.e., Fθ(x) = f_ (θ), and Gφ(x) = g(φ), **_x_**
_∀_ _∈_
R[d]. The payoff Ψ (θ, φ) = L(Fθ, Gφ) := E[Lx,x′ (Fθ(x), Gφ(x[′]))] = (1 2f (θ))(1 2g(φ))
_−_ _−_
_defines a HCC game._

In this example, the two agents play the typical bilinear game of Matching Pennies. However, they
do not act on it directly (i.e., choose randomized actions to apply, e.g., the probability of playing
HEADS). Instead, they choose the input parameters θ, and φ, which are fed into functions f, and g,
respectively, whose outputs define the probability of playing HEADS for each agent.

**Example 2 (GANs). A Generative Adversarial Network (GAN) is a minimax game where the first**
_player, i.e., the generator, aims at learning a distribution pθ similar to a reference data distribution_
_pdata. In practice, the reference data distribution is taken to be the empirical data distribution._
_Conversely, the second player, usually called the discriminator or critic, Dφ, tries to distinguish the_
_distributions of pθ and pdata. The payoff, Ψ_ _, of this game is defined as:_

_Ψ_ (θ, φ) = Ex _pdata_ [log Dφ(x)] + Ex _pθ_ [log(1 _Dφ(x))] ._ (3)
_∼_ _∼_ _−_

_Assuming that pdata and pθ have a density with respect to Lebesgue measure,[3]_ _and that the_
_support of pθ is included in the support of pdata, we can consider the distribution p such_
_that p(x, x[′]) = pdata(x) if x = x[′], and 0 otherwise, and set Lx,x′_ (p[′], D) := log D +
_p[′]_

_pdata(x[′])_ [log(1][ −] _[D][)][. Thus][ L][x][,][x][′][ is][ convex-concave][ for any][ x][,][ x][′][ ∈]_ [R][d][. We have that][ Ψ] [(][θ][,][ φ][) =]
E(x,x′)∼p[Lx,x′ (pθ(x), Dφ(x[′]))], which is a HCC game.

A GAN formulates the generative modeling task as finding a Nash equilibrium of a minimax game.
The generator of a GAN is defined as a function that aims to produce realistic data samples by
transforming samples drawn from a fixed noise distribution, e.g., (0, Id). Here, we notice that the
_N_
GAN payoff is convex (actually linear) as a function of the density of the generated distribution. An
alternative formulation of a GAN is a Wasserstein GAN (WGAN) (Arjovsky et al., 2017). It turns
out that this GAN is also a HCC game.

**Example 3 (WGANs). A Wasserstein GAN is a constrained minimax game, where the second player**
_Dφ is a 1-Lipchitz function and where the payoff is_

_Ψ_ (θ, φ) = Ex _pdata[Dφ(x)]_ Ex _pθ_ [Dφ(x)] . (4)
_∼_ _−_ _∼_

_Similarly, as in Example 2, the WGAN payoff can be shown to be a HCC game._

As the last class of examples of HCC games, we present the Adversarial Example Games
_(AEG) (Bose et al., 2020)._

2One can always assume F and G to be convex sets by considering their convex hulls.
3We make this assumption for simplicity. We can consider Radon–Nikodym derivatives for the general case.


-----

**Example 4 (AEG). An Adversarial Example Game is a minimax game between a generator Gθ and**
_a classifier f_ _. Given samples (x, y) ∼_ _pdata, the generator Gθ aims at finding adversarial examples_
**_x[′]_** _such that_ **_x_** **_x[′]_** _ϵ and that x[′]_ _is not classified as y by f_ _, thus generating a distribution_
_∥_ _−_ _∥∞_ _≤_
_pθ. Overall, the payoff of this game is_

_Ψ_ (θ, φ) = −E(x′,y)∼pθ [ℓ(fφ(x[′]), y)] for (x[′], y) ∼ _pθ ⇐⇒_ **_x[′]_** = Gθ(x), (x, y) ∼ _pdata,_ (5)

_and where ℓ_ _is the cross-entropy loss and Gθ is such that ∥x −_ _Gθ(x)∥≤_ _ϵ, ∀x. By using a similar_
_construction as in Example 2, we can show that (5) is a HCC game with respect to pθ and fφ._

In this work, we make the assumption that the minimax problem induced by L admits a solution:
**Assumption 1. The HCC game defined by (1) admits a Nash equilibrium, (F** _[∗], G[∗]), i.e.,_

min (6)
_F ∈F_ [max]G∈G _[L][(][F, G][) = max]G∈G_ [min]F ∈F _[L][(][F, G][) =][ L][(][F][ ∗][, G][∗][)][ .]_

Such an assumption is relatively mild since it holds when the set F is compact (by definition, it is
convex) (Sion et al., 1958). Note that this solution may not be achievable, i.e., we do not assume
that there exists θ[∗] and φ[∗] such that (Fθ∗ _, Gφ∗_ ) = (F _[∗], G[∗]). Such sufficient conditions for the_
existence of a Nash equilibrium of L : F _×_ G → R are discussed in detail in Gidel et al. (2021, Prop.
1), e.g., Assumption 1 holds if the parameters θ and φ are bounded. From a high-level perspective,
this assumption is analogous to the existence of a global solution non-convex optimization. We use
(F _[∗], G[∗]) as a target to build a Lyapunov function of the natural hidden gradient flow._

3.1 NATURAL GRADIENT FLOW

In this section, we present the notion of a natural gradient flow (Amari, 1985; 1998). Let us consider
will refer to asa function f : S metric tensors → R and a class of symmetric positive definite matrices. The natural gradient flow is the flow given by the steepest descent (Pθ)θ∈S ≻ 0 that we
direction (Ollivier et al., 2017) with respect to the geometry induced by the matrices Pθ,
**_θ˙ = −Pθ[−][1][∇][f]_** [(][θ][)][ .] (7)

When Pθ = I, we consider the canonical Euclidean geometry and recover the standard gradient
flow. One celebrated example of a natural gradient in machine learning is the natural gradient
induced by the Fisher information matrix (Amari, 1998; Martens, 2020).
**Example 5 (The natural gradient flow of the Fisher information matrix). Let us consider P** (X) the
_space of probability distributions on a set X ⊆_ R with the metric induced by the Kullback–Leibler
_(KL) divergence. Then the natural gradient flow of the Fisher information matrix is given by_
**_θ˙ = −Fθ[−][1][∇][f]_** [(][θ][)] _where_ **_Fθ := −Ex∼pθ_** [∇θ[2] [log][ p][θ][(][x][)]][, p][θ] _[∈]_ _[P]_ [(][X][)][ .] (8)

_Moreover, if n := |X| = dim S is finite, and if pθ = θ, the flow (8) is the natural gradient flow of_
_the Shahshahani metric (Shahshahani, 1979) induced by the metric tensors_

**_Sθ := diag(_** _θ[1]1_ _[, . . .,][ 1]θn_ [)][ .] (9)


Recently, alternative natural gradient formulations have been developed using the Wasserstein distance (Li & Mont´ufar, 2018; Arbel et al., 2020).

3.2 CONNECTIONS BETWEEN REPLICATOR DYNAMICS AND GRADIENT FLOWS

The Replicator Dynamics (RD) are standard dynamics used in Evolutionary Game Theory and learning in games. It is, arguably, the most widely used model of evolutionary selection with multiple
applications in economics, biology, and other fields. Interestingly, RD enjoys a close connection
to gradient flows (see Sigmund (1984); Hofbauer et al. (1998); Harper (2009); Mertikopoulos &
Sandholm (2018)). Specifically, in the case of a symmetric and linear fitness landscape, the gradient induced by the Shahshahani metric of the mean fitness is a special case of RD. Such a landscape can be formally represented by a Potential game. A Potential game is a n-player game
**G = (n, S := [m1] × . . . × [mn], u : S →** R[n]), with payoff function u, characterized by the
existence of a potential function Φ : S → R that satisfies

Φ(si, s _i)_ Φ(s[′]i[,][ s][−][i][) =][ u][i][(][s][i][, s][−][i][)][ −] _[u][i][(][s][′]i[, s][−][i][)]_ _i_ [n] . (10)
_−_ _−_ _∀_ _∈_


-----

The connection between potential games and the gradient flows induced by the Shahshahani metric
can be formalized with a generalization of Hofbauer et al. (1998)’s lemma.
**Proposition 1. The Replicator Dynamics of a potential game G with potential function Φ is an**
_(extended) Shahshahani gradient in int(∆m1_ _. . ._ ∆mn ) having potential Ψ(θ) := Esi **_θi_** [Φ(s)].
_×_ _×_ _i_ _∼[n]_
_∈_

It follows that, for potential games, RD is a gradient flow with respect to a very specific geometry.
In the next section, we consider a geometry induced by the HCC structure, and which we leverage
to obtain a new natural gradient flow that we call Natural Hidden Gradient flow (NGH).

3.3 THE NATURAL HIDDEN GRADIENT FLOW FOR HCC GAMES

In HCC games, we assume Ψ (θ, φ) = L(Fθ, Gφ) (see Definition 1), and, therefore, since the
entities that characterize a solution to the minimax problem are the mappings Fθ and Gφ instead of
their parametrizations, θ and φ, respectively, a natural geometry for consideration is the one defined
by the L[2] distance in the space of F × G. Formally, let θ and θ[′] be two parameterizations for F
(similarly, for G). The L[2] distance between the mappings are:

_∥Fθ′ −_ _Fθ∥[2]_ := Ex∼px (Fθ′ (x) − _Fθ(x))[2]_ and _∥Gφ −_ _Gφ′_ _∥[2]_ := Ex∼px′ (Gφ′ (x[′]) − _Gφ(x[′]))[2]._

where px and px′ are the marginal of px,x′ . We can then derive the metric tensors of this geometry.
**Proposition 2 (Metric tensors of the model space). Under mild regularity assumptions, we have**
_that, for any θ ∈_ R[M] _,_

_Fθ+δθ_ _Fθ_ = _δθ, Aθδθ_ + o( _δθ_ ) _where_ **_Aθ := Ex_** _px_ [ **_θFθ(x)_** **_θFθ(x)[⊺]] . (11)_**
_∥_ _−_ _∥[2]_ _⟨_ _⟩_ _∥_ _∥[2]_ _∼_ _∇_ _∇_

Consequently, Aθ defines a metric on the parameter space in which the “distance” between two
values, θ, and θ[′], corresponds to the L[2] distance between Fθ and Fθ′ . We can, thus, construct the
corresponding natural gradient flow.
**Proposition 3 (Natural Hidden Gradient dynamics). The flow induced by the geometry (11) is**

**_θ˙ = −A[†]θ[E][(][x][,][x][′][)][∼][p][[][∇][θ][L][x][,][x][′]_** [(][F][θ][(][x][)][, G][φ][(][x][′][))]] (D1)
**_φ˙_** = Bφ[†] [E][(][x][,][x][′][)][∼][p][[][∇][φ][L][x][,][x][′] [(][F][θ][(][x][)][, G][φ][(][x][′][))]]

_where Aθ := Ex∼px_ [∇θFθ(x)∇θFθ(x)[⊺]] and Bφ := Ex′∼px′ [∇φGφ(x)∇φGφ(x)[⊺]] and C _[†]_
_denotes the pseudo-inverse of a matrix C._

4 CONVERGENCE OF THE NATURAL HIDDEN GRADIENT FLOW

In this section, we propose a new type of dynamics, dubbed Natural Hidden Gradient dynamics
_(NHG), and in the following two theorems, we prove their convergence in HCC games and GANs._
At the heart of our analysis lies the construction of a proper Lyapunov function that measures the
distance from the game’s equilibrium point. By proving that the Lyapunov function is proper, i.e.,
monotonic, we will prove our proposed dynamics are approaching a Nash Equilibrium.

4.1 WARM-UP: A SINGLE DATAPOINT

In this section, as a warm-up, we will consider the single datapoint case. In this case, (1) is,

_Ψ_ (θ, φ) = L(Fθ(x), Gφ(x[′])) (12)

where L : R × R → R is convex-concave (see Example 1). In this case, since the mapping Fθ and
_Gφ are evaluated at a single point, one can simplify the notation and consider Fθ(x) = f_ (θ) and
_Gφ(x[′]) = g(φ) where f : R[M]_ _→_ R and g : R[N] _→_ R are real-valued mappings that do not depend
on an input x or x[′]. This situation is already non-trivial since, as illustrated in Example 1, it can
correspond to a non-convex non-concave parametrization of the Matching Pennies game. In order
to solve this game we consider the Natural gradient of the metric defined in Proposition 2.
**Proposition 4. In the uni-dimensional case, the Natural Hidden Gradient flow D1 takes the form of**

**_θ˙ = −_** _[∇][θ]∥∇[L][(][f]θ_ _f[(][θ](θ[)][,g])∥[(][2][φ][))]_ _and_ **_φ˙_** = _[∇][φ]∥∇[L][(]φ[f]g[(][θ](φ[)][,g])∥[(][2][φ][))]_ _._ (D2)


-----

Using Proposition 4, it is relatively straightforward to show that the distance to the optimum is a
Lyapunov function for the Natural Hidden Gradient flow.
**Theorem 1. Let Ψ be the payoff of an HCC game (12) and consider the dynamics (D2). Then,**

_V (θ, φ) :=_ [1]2 [(][f] [(][θ][)][ −] _[f][ ∗][)][2][ +][ 1]2_ [(][g][(][φ][)][ −] _[g][∗][)][2]_ (13)

_is a Lyapunov function, i.e., it is positive, non-increasing, and null if and only if it evaluated at a_
_game solution. Moreover, if L is strictly convex-concave, we have that V is decreasing and that any_
_limit point (θ, φ) satisfies_ **_θL(f_** (θ), g(φ)) = **_φL(f_** (θ), g(φ)) = 0.
_∇_ _∇_

In order to see this, one can compute the time derivative of V . After some elementary computations,
it follows _V[˙] (θ, φ) = −(f_ (θ) − _f_ _[∗])_ _[∂L][(][f,g]∂f[(][φ][))]_ _f_ =f (θ) [+ (][g][(][φ][)][ −] _[g][∗][)][ ∂L][(][f]∂g[(][θ][)][,g][)]_ _g=g(φ)[, and, thus,]_

by the convex-concavity of L, we have that _V[˙] ≤_ 0. However, generalizing this theorem to HCC
games with non-constant mappings (with respect to x) is non-trivial since we drastically used the
simplicity of the mappings (Proposition 4) to simplify the expression of the flow. In the next section,
we propose to extend our convergence analysis to finite sum HCC games.

4.2 THE GENERAL FINITE SUM CASE

In this section, we consider a finite-sum version of the HCC games as they appear in Definition 1.
In this case, the payoff is defined as

_Ψ_ (θ, φ) := _nm1_ _Li,j(Fθ(xi), Gφ(x[′]j[)) =:][ L][((][F][θ][(][x][i][))]i∈[m][,][ (][G][φ][(][x][′]j[))]j∈[n][)][,]_ (14)

(i,j)∈X[m]×[b]

where the function L : R[m] R[n] R is assumed to be convex-concave. We note Li,j := Lxi,x[′]j
_×_ _→_
for compactness. Let us recall that we assumed the existence of a Nash equilibrium (F _[∗], G[∗]) for the_
minimax problem (Assumption 1). In this situation, the Natural gradient defined in Proposition 3
has the following form:

**_θ˙ =_** _nmθ_ **_θLi,j(Fθ(xi), Gφ(x[′]j[))][,][ ˙]φ =_** _nmBφ[†]_ **_φLi,j(Fθ(xi), Gφ(x[′]j[))][,]_** (D3)
_−_ _[A][†]_ _∇_ _∇_

(i,j)∈X[m]×[n] (i,j)∈X[m]×[n]

where Aθ := _m[1]_ _mi=1_ _n_ _nj=1_ _j[)][∇][φ][G][φ][(][x][′]j[)][⊺][.]_

_[∇][θ][F][θ][(][x][i][)][∇][θ][F][θ][(][x][i][)][⊺]_ [and][ B][φ][ :=][ 1] _[∇][φ][G][φ][(][x][′]_

We will generalize the Lyapunov function considered in the uni-dimensional case (P P 13). The idea is
to consider the L[2] distance between (Fθ(xi), Gφ(x[′]j[))][i,j][ and][ (][F][ ∗][(][x][i][)][, G][∗][(][x][′]j[))][i,j][ as our Lyapunov]
function V . However, in order to prove our result, we will need the following technical assumption.
**Assumption 2. For any θ** _∈_ R[M] _and φ_ _∈_ R[N] _, we have that the families of vectors_
( **_θFθ(xi))i_** [m] and ( **_φGφ(x[′]j[))][j][∈][[][n][]]_** _[are linearly independent.]_
_∇_ _∈_ _∇_

When the models are overparametrized, e.g., M > m and N > n, this assumption is relatively mild
since it can be insured by a small perturbation of the considered vectors. In practice, it suggests
regularizing the matrices Aθ and Bφ by adding ϵ · Id which is a standard way to stabilize methods
requiring matrix inversions.
**Theorem 2. Let Ψ be the payoff of a finite-sum HCC game given by (14) and consider the game**
_dynamics in (D3). Under Assumption 1, Assumption 2, we have that the quantity_


_V (θ, φ) := [1]_

2n


_n_

(Fθ(xi) _F_ (xi))[2] + [1]
_−_ _[∗]_ 2m
_i=1_

X


(Gφ(x[′]j[)][ −] _[G][∗][(][x][′]j[))][2]_ (15)
_j=1_

X


_is a Lyapunov function, i.e., is positive, non-increasing and null if and only if evaluated at a game_
_solution. Moreover, if L is strictly convex-concave, V is decreasing as long as (θ, φ) ̸= (θ[∗], φ[∗])_
_and if L is a µ-strongly convex-concave function we have that V is decreasing exponentially as_
_V (θ, φ) = V (θ0, φ0) exp(_ _µt)._
_−_

We showed that, in the overparametrized regime, if we assume not to encounter any singular matrices
_Aθ and Bφ along the trajectory, then, preconditioning low dimensional gradient of θ and φ can_
behave like doing gradient update on F and G to leverage the hidden-convex-cave structure of


-----

the the payoff. We do not know how to recover the gradients updates on F and G in the nonoverparametrized regime. It is a great open question that we consider outside of the scope of this
paper as we focus on understanding convergence in minimax games for deep learning models (that
are over-parametrized). The proofs of Theorem 1 and Theorem 2 are in §A.3.

Regarding the practicability of the method described in (D3), efficient approximations of preconditioning, such as the K-FAC algorithm, were proposed (Martens, 2020; Li & Mont´ufar, 2018) and
used to train large models on Imagenet and CIFAR (Martens et al., 2021; Arbel et al., 2020).

5 CHARACTERIZATIONS OF REPLICATOR DYNAMICS IN HCC GAMES

In this section, we consider a specific instance of HMP games (cf. Example 1), dubbed 2-Team HMP
_games or the XOR-XOR games. Although the possibility of cycling orbits for RD in such games was_
established before (Piliouras & Schulman, 2018), in this section, we show stronger results. Specifically, as we prove in subsection 5.2, by enforcing restrictions to the game’s parameters, it is possible
to affect the game’s outcome, e.g., we may deviate from the well-known cyclic behavior in the unrestricted setting, and moreover, enforce divergence away from the game’s original equilibrium and
convergence to novel fixed points. We completely characterize the geometry of possible limit cycles
in such a restricted setting by exploiting intuitions developed via the connection between RD and the
Shahshahani information geometry. Specifically, we show the dynamics are controlled by invariant
functions, which correspond to weighted sums of the cross-entropy of the current mixed strategies
of opposing members relative to the uniform, equilibrium strategies (19). For the complete proofs
of this section, we refer the interested reader to §A.4.

5.1 2-TEAM HIDDEN MATCHING PENNIES GAMES

We introduce the 2-Team HMP game, G = (n := n1 + n2, S := {0, 1}[n], u : S → R[n]), between
_n1 + n2 members divided into two teams. The first team, team 1, consists of n1 members, while_
the second team, team 2, consists of n2 members. The payoff function u for a strategy profile
**_s := (s1, s2) ∈_** S is given by

_uk,i(s) :=_ [(][−][1)]nk[k][−][1] (1 2 **1XOR(s1)=XOR(s2)), k** [2], i [nk] . (16)

_−_ _·_ _∈_ _∈_

(whereθ, 1 − XOR(θ), θs := (k) = 1θk) ifk∈ |{[2]s ∈k,i |[0 s, 1]k,i[n] = 1, the expected payoff of the}| is odd, and 0, otherwise. Given a mixed-strategy profile, i-th member of team k is given by

_Ψk,i(θ) := Esk,ik∈∼[2]Ber(, i∈[θnk,ik])[uk,i(s)] =_ [(][−][1)]nk[k][−][1] (1 − 2f (θ1))(1 − 2g(θ2)) (17)

where f (θ1) := Es1 Ber(θ1)[XOR(s1)] and g(θ2) := Es2 Ber(θ2)[XOR(s2)]. Notice that, since
_∼_ _∼_
each member of a given team aims at maximizing the same payoff, G is a Hidden Matching Pennies
game (Example 1) with hidden mappings f (θ1), and g(θ2),

_n1_


_Ψ1,i(θ) = (1_ 2f (θ1))(1 2g(θ2)) . (18)
_−_ _−_
_i=1_

X


min
**_θ2_** [max]θ1 _[Ψ]_ [(][θ][1][,][ θ][2][) :=]


It is not difficult to prove that the RD exhibit cyclic behavior in this setting. The following theorem
provides a fine-grained characterization of the dynamics of the HCC game (18) where we show that
the trajectories lie on the intersection of level sets of invariant functions.
**Theorem 3. Consider the Replicator Dynamics of G. Given any interior initial condition, the**
_resulting orbit is a cycle that satisfies the following n1 + n2 −_ 1 independent invariant functions:


_nk[log(θk,ik_ ) + log(1 _θk,ik_ )], ik [nk], k [2] . (19)
_k=1_ _−_ _∈_ _∈_

X


_Vi1,i2_ (θ) =


5.2 REPLICATOR DYNAMICS OF HIDDEN MATCHING PENNIES IN A RESTRICTED SETTING

Next, we introduce restrictions in the range of each member’s strategies in G such that θk,i ∈ Sk,i :=

[αk,i, βk,i] ⊆ [0, 1], ∀k ∈ [2], i ∈ [nk]. These restrictions reflect in RD as halts, i.e., **_θ[˙]k,i = 0, every_**


-----

time the strategy of the i-th member of the k-th team exceeds those bounds. To ease our notation, we
letis an allowed mixed strategy, and, to simplify this part of the analysis, we also make the following Sk := {i ∈ [nk] | [1]2 _[∈]_ [S][k,i][}][, k][ ∈] [[2]][ denote all the members of the][ k][-th team for which][ (][ 1]2 _[,][ 1]2_ [)]

mild assumption on the initialization of the dynamics:

**Assumption 3. For all k ∈** [2] and i ∈ [nk], θk,i(0) ∈ Sk,i ⊂ (0, 1).


A significant observation is that for any mixed-strategy profile (θ, 1 **_θ), θ := (θ1, θ2)_** [0, 1][n],
_−_ _∈_
if there exists someit is not difficult to see that these are the only interior equilibrium points of ik ∈ [nk], ∀k ∈ [2] such that θik = [1]2 [, then][ θ][ is an equilibrium point; in fact,] G, which implies that

an interior equilibrium point is reachable if and only ifprove that if the Nash Equilibrium of the unrestricted case is not reachable by both teams due to the Sk ̸= ∅, ∀k ∈ [2]. In our first result, we
constraints, then the dynamics converges to a point which only depends on those restrictions.

**Theorem 4. Under Assumption 3, if Sk = ∅, ∀k ∈** [2], the restricted RD of G converge to


_θ1[∗],i_ [=] _α1,i,_ _if β1,i <_ [1]2 _i_ [n1] _θ1[∗],i_ [=] _β1,i,_ _if β1,i <_ 2[1] _i_ [n1]

_β1,i,_ _otherwise_ _∈_ _α1,i,_ _otherwise_ _∈_

 _or_ 

_θ2[∗],i_ [=] _β2,i,_ _if β2,i <_ [1]2 _i_ [n2] _θ2[∗],i_ [=] _α2,i,_ _if β2,i <_ [1]2 _i_ [n2]

_α2,i,_ _otherwise_ _∈_ _β2,i,_ _otherwise_ _∈_

 

_if |S| is even_ _if |S| is odd_

_where| S := {(k, i) | k ∈{z[2], i ∈_ [nk], αk,i} > [1]2 _[}][.]_ | {z }


(20)


The key idea behind this result is that at any given time t 0, the direction of a strategy θk,i(t) only
_≥_
depends on whether |S|, the total number of members who can access the uniform strategy, is odd or
even. Thus, we can decouple the evolution of the dynamics of each of the members and analyze its
behavior separately. If an equilibrium point of the unrestricted setting is reachable by both teams,
i.e.,depend on the number of members who have access to the uniform strategy, Sk ̸= ∅, ∀k ∈ [2], then the dynamics converge to an invariant set whose degrees of freedom ( 2[1] _[,][ 1]2_ [)][.]

_invariant set defined by theTheorem 5.[2], where Vi Under1,i2_ (θ) is given as in Assumption 3 |S1|+ (|, ifS192|− S). _k1 ̸= independent invariant functions, ∅, ∀k ∈_ [2], then the restricted RD of Vi1,i2 (θ G), i converge to ank ∈ Sk, ∀k ∈

One can prove this result by partitioning the time based on the set of members that have halted. The
analysis of Vi1,i2 (θ) in each time-partition is almost trivial, and the result follows by a continuity
of the game. Notably, we show that if no equilibrium point is feasible, the RD converge to a pointargument on Vi1,i2 (θ). These results depict how the behavior of RD depends on the parameter space
described entirely by the strategy space restrictions. On the other hand, if an equilibrium point is
feasible, we prove the existence of a maximal number of invariant functions, with close connections
to the KL divergence. The latter does not merely show that the RD cycle in this setting, but that they
actually converge to an invariant set with specific degrees of freedom, and which we characterize.
For parameterizations that visualize the behavior of RD in such restricted settings, see §B.1.

6 EXPERIMENTAL RESULTS

**Toy multi-dimensional case. As a first experiment, we consider the HCC objective**

_Ψ_ (θ, φ) = L(Fθ, Gφ) := Fθ[⊺][M] _[G][φ][ +][ λ]2_ [(][∥][F][θ][ −] **[1]3** _[∥][2][ −∥][G][φ][ −]_ **[1]3** _[∥][2][)][,]_

where M is the payoff matrix of the Rock-Paper-Scissors game (see e.g. Gidel et al. (2021)). We
note Fθ(xi) = [Fθ]i, i ∈ [3], and **[1]3** [, i.e., the uniform distribution, is the game’s equilibrium. The]

mappings F and G are 2-layer MLP with 130 parameters and GELU non-linearities (Hendrycks &
Gimpel, 2016). In Figure 1, we depict a comparison between the performance of GDA and NHG
dynamics on the task of solving minθ maxφ Ψ (θ, φ). We remark, the NHG dynamics converges
smoothly (Figure 1 (Right)), compared to GDA (Figure 1 (Center)), which fail to converge. The
value of the Lyapunov function of the game described is depicted in (Figure 1 (Left)).

**GANs. For our second experiment, we implement the NHG dynamics to train a GAN. We consider**
a synthetic experiment to learn a sine wave sampled uniformly from 0 to π with 1024 observations.


-----

p p
q q

10[−1] Solution 0.40.5 Solution 0.250.300.35

0.3 0.20

10[−2] 0.2 0.100.15

0.1 0.05

Lyapunov value 10[−3] Natural Gradient 0.250.300.0 0.30.00

0 Standard Gradient500 1000 1500 2000 0.0 0.1 0.2 0.3 0.4 0.000.050.100.150.20 0.0 0.1 0.2 0.3 0.00.10.2

Number of Iterations


Figure 1: A comparison of GDA (Center) and NHG dynamics (Right) in the task of solving
minθ maxφ Ψ (θ, φ) where p = f (θ), and q = g(φ). In NHG, the Lyapunov function (Left) is
monotonically decreasing, as opposed to GDA.


Regarding the GAN, we consider a Flow-GAN architecture where our generator, G, is a Real NVP
consisting of 8 coupling layers (Dinh et al., 2017; 2014), and the discriminator is a 4-layer MLP
with 256-128-64-1 output features. We adapt K-FAC (Martens & Grosse, 2015) as an approximator
to compute NHG, with a learning rate of 10[−][4], selected using the standard parameter optimizer
package Optuna (Akiba et al., 2019). We used gradient clipping with gradient clip to a maximum
norm of 1 on, both the discriminator and the generator, to stabilize the optimization.

As observed in (Figure 2 (Center)), by iteration 200, the GAN optimized using K-FAC learns the
true sinusoid almost perfectly and converges to a better Wasserstein-1 score than the conventional
GDA (Figure 2 (Right)). The experiments reveal that our approach provides good performance and
convergence guarantees. However, we observe instabilities during training, and lack of convergence
in certain instances, which stay in line with the empirical observations regarding the difficulty of
GAN training, and the instability of matrix inversions close to singularities. We remark that this experiment goes slightly beyond the theoretical results: while in theory, we assume a natural gradient
flow on a “full-batch”, our experiments are based on discrete stochastic updates, and an approximation of the pseudo-inverses of the matrices (see (D1)) using K-FAC. Thus, this experiment acts as a
proof-of-concept rather than a large-scale comparison between NHG and GDA. The details of both
experiments can be found within the source-code files included with this work.

1.000.75 1.0 3.0 Natural GradientStandard Gradient

0.50 0.5 2.5

0.25 2.0

0.00 0.0

1.5

0.25

0.50 0.5 Wasserstein-11.0

0.75 0.5

1.00 1.0 0.0

0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 25 50Number of Iterations75 100 125 150 175 200


Figure 2: A plot of the real sinusoid sampled on the interval from 0 to 2π (Left). GAN generated
samples for NHG dynamics (Center). The performance of GDA vs. NHG dynamics on GANs as
measured by Wasserstein-1 distance (Right).


7 DISCUSSION

We proposed a novel version of Gradient Descent Ascent dynamics in Hidden Convex-Concave
games, a subset of non-convex non-concave games. In this class of games, which includes GANs, the
utility is convex-concave in the function space. Still, training happens in the parameter space, where
the mappings between the input and output are non-convex non-concave functions. We explored
the dynamics of gradient flows induced by different Banach spaces (e.g., the Fischer information
geometry) that led to the discovery of Lyapunov functions suited to these geometries. Our analysis
of the convergence of our proposed type of dynamics, Natural Hidden Gradient (NHG) dynamics,
uses ideas from Game Theory and Dynamical Systems. We proved global convergence guarantees
for NHG in HCC games to local stationary points via Lyapunov function analysis in the finite-sum
case. To the best of our knowledge, such a non-local convergence result in HCC games and GANlike settings, is one of the first of its kind. We also show promising experimental results on practical
GANs using NHG and standard gradient approximation techniques such as KFAC. We are aware that
the current formulation of NHG may be challenging to scale up to large neural networks because
of the tensor pseudo-inversion step that is part of the dynamics. Investigating experimentally novel
versions of Gradient Descent Ascent dynamics with a richer set of experiments and developing
techniques to scale our results for larger neural networks is a natural direction for our future work.


-----

STATEMENT OF REPRODUCIBILITY

We made sure to provide sufficient details to ensure the reproducibility of our results. The complete
proofs of the theoretical results can be found in §A, and all the assumptions have been stated and
are referenced in each statement. We provide details regarding the experimental results, such as
code language, required libraries, and parametrization to execute and reproduce the experiments in
section 6 and §B. We also include the source code files and the necessary input files in the supplementary material that accompanies this work.

ACKNOWLEDGEMENTS

The authors would like to acknowledge Joey Bose for his help on the GANs experiments.

This research/project is supported in part by the National Research Foundation, Singapore under
its AI Singapore Program (AISG Award No: AISG2-RP-2020-016), NRF 2018 Fellowship NRFNRFF2018-07, NRF2019-NRF-ANR095 ALIAS grant, grant PIE-SGP-AI-2020-01, AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research
(A*STAR) and Provost’s Chair Professorship grant RGEPPV2101. This work is supported by the
Canada CIFAR AI Chair Program and an IVADO grant.

REFERENCES

Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point
optimization: A curvature exploitation approach. In The 22nd International Conference on Arti_ficial Intelligence and Statistics. PMLR, 2019._

Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna:
A next-generation hyperparameter optimization framework. In Proceedings of the 25rd ACM
_SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019._

Shun-ichi Amari. Differential-geometrical methods in statistics. Lecture Notes on Statistics, 28,
1985.

Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2), 1998.

M Arbel, A Gretton, W Li, and G Montufar. Kernelized wasserstein natural gradient. In Interna_tional Conference on Learning Representations, 2020._

Martin Arjovsky, Soumith Chintala, and L´eon Bottou. Wasserstein generative adversarial networks.
In International conference on machine learning. PMLR, 2017.

Avishek Joey Bose, Gauthier Gidel, Hugo Berrard, Andre Cianflone, Pascal Vincent, Simon
Lacoste-Julien, and William L Hamilton. Adversarial example games. In NeurIPS, 2020.

Haoyang Cao and Xin Guo. Approximation and convergence of GANs training: an SDE approach.
_arXiv preprint arXiv:2006.02047, 2020._

Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization:
Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning
_Theory. PMLR, 2019._

Yun Kuen Cheung and Yixin Tao. Chaos of learning beyond zero-sum and coordination via game
decompositions. In ICLR, 2021.

Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in
min-max optimization. In NeurIPS, 2018.

Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained
min-max optimization. STOC, 2021.

Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured
nonconvex-nonconcave min-max optimization. In ICML, 2021.


-----

Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of conditional moment models. In NeurIPS, 2020.

Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components estimation. arXiv preprint arXiv:1410.8516, 2014.

Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real NVP. In
_ICLR, 2017._

Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg
games: Equilibria characterization, convergence analysis, and empirical study. In International
_Conference on Machine Learning. PMLR, 2020._

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Georgios Piliouras. Poincar´e
recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave
zero-sum games. In NeurIPS, 2020.

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Georgios Piliouras. Solving
min-max optimization with hidden structure via gradient descent ascent. In NeurIPS, 2021.

Ian Gemp and Sridhar Mahadevan. Global convergence to the equilibrium of GANs using variational
inequalities. arXiv preprint arXiv:1808.01531, 2018.

Gauthier Gidel, David Balduzzi, Wojciech Marian Czarnecki, Marta Garnelo, and Yoram Bachrach.
Minimax theorem for latent games or: How i learned to stop worrying about mixed-nash and love
neural nets. AISTATS, 2021.

I Goodfellow, J Pouget-Abadie, M Mirza, B Xu, D Warde-Farley, S Ozair, A Courville, and Y Bengio. Generative adversarial nets. In NeurIPS, 2014.

Marc Harper. Information geometry and evolutionary game theory. CoRR, abs/0911.1383, 2009.
[URL http://arxiv.org/abs/0911.1383.](http://arxiv.org/abs/0911.1383)

Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs). _arXiv preprint_
_arXiv:1606.08415, 2016._

Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.
GANs trained by a two time-scale update rule converge to a local nash equilibrium. NeurIPS, 30,
2017.

Josef Hofbauer, Karl Sigmund, et al. Evolutionary games and population dynamics. Cambridge
university press, 1998.

Ya-Ping Hsieh, Chen Liu, and Volkan Cevher. Finding mixed Nash equilibria of generative adversarial networks. In ICML, 2019.

Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization
algorithms: convergence to spurious non-critical sets. CoRR, 2020.

Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconcave
minimax optimization? In International Conference on Machine Learning. PMLR, 2020.

Naveen Kodali, Jacob Abernethy, James Hays, and Zsolt Kira. On convergence and stability of
GANs. arXiv preprint arXiv:1705.07215, 2017.

Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving
nonconvex-concave min-max problems. SIAM Journal on Optimization, 2021.

Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvexnonconcave minimax problems. In NeurIPS, 2021.

Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. In ICLR,
2021.


-----

Jerry Li, Aleksander Madry, John Peebles, and Ludwig Schmidt. On the limitations of first-order
approximation in gan dynamics. In International Conference on Machine Learning. PMLR, 2018.

Wuchen Li and Guido Mont´ufar. Natural gradient via optimal transport. Information Geometry, 1
(2):181–214, 2018.

Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICML, 2020.

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.
Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.

James Martens. New insights and perspectives on the natural gradient method. Journal of Machine
_Learning Research, 2020._

James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate
curvature. In International conference on machine learning, 2015.

James Martens, Andy Ballard, Guillaume Desjardins, Grzegorz Swirszcz, Valentin Dalibard, Jascha
Sohl-Dickstein, and Samuel S Schoenholz. Rapid training of deep neural networks without skip
connections or normalization layers using deep kernel shaping. arXiv preprint arXiv:2110.01765,
2021.

Eric Mazumdar and Lillian J Ratliff. Local nash equilibria are isolated, strict local nash equilibria in
‘almost all’zero-sum continuous games. In 2019 IEEE 58th Conference on Decision and Control
_(CDC). IEEE, 2019._

Panayotis Mertikopoulos and William H Sandholm. Riemannian game dynamics. Journal of Eco_nomic Theory, 2018._

Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going
the extra(-gradient) mile. In ICLR, 2019.

Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do
actually converge? In International conference on machine learning. PMLR, 2018.

Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving
a class of non-convex min-max games using iterative first order methods. NeurIPS, 2019.

Yann Ollivier, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. Information-geometric optimization algorithms: A unifying picture via invariance principles. Journal of Machine Learning
_Research, 18(18), 2017._

Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash
equilibria in nonconvex-concave smooth min-max problems. SIAM Journal on Optimization,
2021.

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).
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

Siavash Shahshahani. A new mathematical framework for the study of linkage and selection. American Mathematical Soc., 1979.

Karl Sigmund. The maximum principle for replicator equations. Iiasa working paper, IIASA,
Laxenburg, Austria, 1984.

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez,
Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go
without human knowledge. nature, 550(7676), 2017.

Maurice Sion et al. On general minimax theorems. Pacific Journal of mathematics, 8(1), 1958.


-----

Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Poincar´e
recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave
zero-sum games. In NeurIPS 32: Annual Conference on Neural Information Processing Systems
_2019, 2019._

Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A
follow-the-ridge approach. In International Conference on Learning Representations, 2020.

Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for a class
of nonconvex-nonconcave minimax problems. In NeurIPS, 2020.

Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and stability in non-convex smooth
games. arXiv preprint arXiv:2002.11875, 2020.

A OMITTED PROOFS

A.1 OMITTED PROOFS OF SECTION 3.1

**Proposition A.1. Let us consider P** (X) the space of probability distributions on a set X ⊆ R with
_the metric induced by the Kullback–Leibler (KL) divergence. If n := |X| = dim S, and pθ := θ ∈_
_P_ (X), then the natural gradient flow of the Fisher information matrix in (8) is the natural gradient
_flow of the Shahshahani metric induced by the metric tensors in (9)._

_Proof. All we need to show is that Fθ = Sθ, ∀θ ∈_ S. Simply, note that ∀i, j ∈ [n]:

_∂2 log pθ(x)_ _∂[2]_ log pθ(x)

(Fθ)i,j = Ex _pθ_ = _pθ(x)_
_−_ _∼_ _∂θi∂θj_ _−_ _∂θi∂θj_

  _xX∈X_

_∂[2]_ log θx _δx,iδx,j_

= _θx =_ = _[δ][i,j]_ = (Sθ)i,j .
_−_ _∂θi∂θj_ _θx_ _θi_

_xX∈X_ _xX∈X_


A.2 OMITTED PROOFS OF SECTION 3.2

Let G = (n, S := [m1] × . . . × [mn], u : S → R[n]) be a n-player (exact) potential game with payoff
functionfollowing proposition.of G. We are going to consider the RD of u and potential Φ : S → R, and let G M in := ∆ int Mm = int ∆1 × . . . ×m ∆1 ×m . . .n be the mixed-strategy space × int ∆mn as given in the
**Proposition A.2. The Replicator Dynamics of G in int M are given by the following dynamical**
_system of equations:_


_∂Ψ(θ)_

Ψ(θ) (D4)
_∂θi,j_ _−_

 


_θ˙i,j := θi,j(Esk_ **_θk_** [ui(sj, s _i)]_ Esk **_θk_** [ui(s)]) = θi,j
_k∈∼[n]_ _−_ _−_ _k∈∼[n]_


_where Ψ(θ) := Esi_ **_θi_** [Φ(s)] is the the expected potential function of the game.
_i∈∼[n]_

_Proof. First note that_


_∂Ψ(θ)_

_∂θi,j_


_θk,sk_ Φ(s) _[∂θ]∂θ[i,s]i,j[i]_
_kY≠_ _i_


_θk,sk_ Φ(s)δj,si
_kY≠_ _i_


_θk,sk_ Φ(j, s _i) = Esi_ **_θi_** [Φ(j, s _i)] ._
_−_ _i_ _∼[n]_ _−_
_k=i_ _∈_

Y̸


**_s−i_**


-----

From which follows that

_θ˙i,j = θi,j(Esk_ **_θk_** [ui(j, s _i)_ _ui(s)]) = θi,j(Esk_ **_θk_** [Φ(j, s _i)_ Φ(s)])
_k∈∼[n]_ _−_ _−_ _k∈∼[n]_ _−_ _−_

_∂Ψ(θ)_

= θi,j Ψ(θ) _._

_∂θi,j_ _−_

 


Next, let us consider a point θ ∈ int M, and note that the following proposition holds:
**Proposition A.3.is** _For any θ ∈_ int M = int ∆m1 × . . . × int ∆mn _, the tangent plane of int M at θ_


Tθ(int M) = {µ ∈ R[m][1] _× . . . × R[m][n]_ _|_


_µi,j = 0} ._ (21)


_Proof. We first note that int M is an open-subset of the surface D := {µ ∈_ R[m][1] _× . . . × R[m][n]_ _|_
_Ui(µ) = 1}, where Ui(µ) =_ _j_ _[µ][i,j][ = 1][; hence,][ T][θ][(int][ M][) = T][θ][ D][, up to isomorphism. Let]_

**_r(t) be a smooth curve in D with r(0) = θ. Then, by definition, Ui(r(t)) = 1 for all i, and, by_**
differentiating with respect to t, we have[P]

_Ui(r(t))_ _[d]_
_∇_ _·_ _dt_ **_[r][(][t][) =][ d]dt_** _[U][i][(][r][(][t][)) =][ d]dt_ [1 = 0][ .]


However, _dt[d]_ **_[r][(][t][)][ is tangent to][ D][ for all][ t][; hence,][ d]dt_** **_[r][(][t][)]_**

_t=0_

_∇Ui(θ) is normal to Tθ D for all i, and,thus, we have_ _[∈]_ [T][θ][ D][. It follows that][ ∇][U][i][(][r][(0)) =]


Tθ D ⊆{µ ∈ R[m][1] _× . . . × R[m][n]_ _| ⟨∇Ui(θ), µ⟩_ = 0} = {µ ∈ R[m][1] _× . . . × R[m][n]_ _|_


_µi,j = 0} ._


Finally, notice that dim{µ ∈ R[m][1] _× . . . × R[m][n]_ _|_ _j_ _[µ][i,j][ = 0][}][ = dim][ D][, which implies the]_

proposition.

[P]

**Proposition 1. The Replicator Dynamics of a potential game G with potential function Φ is an**
_(extended) Shahshahani gradient in int(∆m1_ _. . ._ ∆mn ) having potential Ψ(θ) := Esi **_θi_** [Φ(s)].
_×_ _×_ _i_ _∼[n]_
_∈_

_Proof. Let θ ∈_ int M := int ∆m1 × . . . × int ∆mn . Then for every ξ ∈ Tθ(int M) we have:

1 _∂Ψ(θ)_ _∂Ψ(θ)_
**_θ, ξ_** **_θ =_** _θ˙i,jξi,j =_ Ψ(θ) _ξi,j =_ _ξi,j_ Ψ(θ) _ξi,j_
_⟨_ [˙] _⟩_ _θi,j_ _∂θi,j_ _−_ _∂θi,j_ _−_



X X [] X X

_∂Ψ(θ)_
= _ξi,j =_ Ψ(θ) **_ξ ._**

_∂θi,j_ _∇_ _·_

X


Hence, by definition, we have that ∇Ψ(θ) = θ[˙], where the Del operator is defined with respect to
the Shahshahani metric, which implies the lemma.

Now, let us consider a different class of games, which we define as 2-Team Zero-Sum games.


-----

**Definition 2. A 2-Team Zero-Sum game, G = (m := m1+m2, S := [n1]×. . .×[nm], u : S →** R[m]),
_is a game between m players with strategy-space S whose utility function, u, satisfies the following:_


_−_ _mm[1]112_ [Φ(][Φ(][s][s][)][)][,][,] _ifotherwise i ∈_ [m1] _∀s ∈_ S (22)


_ui(s) =_

_for some function Φ : S →_ R.


We are going to, collectively, refer to the first m1 players of a 2-Team Zero-Sum game, G = (m :=
_m1 + m2, S := [n1] × . . . × [nm], u : S →_ R[m]), as team 1 and to the rest of them as team 2.
Notice that if we consider each team as a single player, then the two teams are playing a 2-Player
Zero-Sum game,[∀nsm ∈1+1S we have × . . . × n Gm[′]], and the utility function= (2, S[′] := S1 × S2, u u[′] :[′]k S[is the total utility of the corresponding team][′] _→_ R[2]) where S1 = [n1] × . . . × [nm1 ],[ k] S[, i.e.]2 =

_m1_ _m_


_u[′]1[(][s][) =]_


1

Φ(s) = Φ(s) and _u[′]2[(][s][) =][ −]_
_m1_


1

Φ(s) = Φ(s) . (23)
_m2_ _−_


_i=1_


_i=m1+1_


Note that, by definition, the 2-Team Hidden Matching Pennies game (see section 5) is a a 2-Team
Zero-Sum game. Let us consider the Replicator Dynamics of G given by the following dynamical
system of equations:

_θ˙i,j := θi,j(Esk_ **_θk_** [ui(j, s _i)]_ Esk **_θk_** [ui(s)])
_∼_ _−_ _−_ _∼_


1

_θi,jEsk_ **_θk_** [Φ(j, s _i)_ Φ(s)], if i [m1]

= _m1_ _∼_ _−_ _−_ _∈_


− _m[1]2_ _θi,jEsk∼θk_ [Φ(j, s−i) − Φ(s)], otherwise



where, as before, we can rewrite (D5) in terms of Ψ(x) := ESk _xk_ [Φ(S)] as
_∼_


(D5)


1

_θi,j(_ _[∂][Ψ(][θ][)]_ Ψ(θ)), if i [m1]
_m1_ _∂θi,j_ _−_ _∈_ (D6)

_θi,j(_ _[∂][Ψ(][θ][)]_ Ψ(θ)), otherwise .

_−_ _m[1]2_ _∂θi,j_ _−_


_θ˙i,j =_


Notice that the Replicator equations of each team are similar to the Replicator equations of a Potential game. In fact, it’s not difficult to prove the following lemma.

**Lemma 1. Let G = (m := m1 + m2, S := [n1] × . . . × [nm], u : S →** R[m]) be a 2-Team
_Zero-Sum game. If we assume the strategies of team 2 to be time-invariant, then the Replicator_
_Dynamics of G, given by (D5) (or (D6), equivalently), is a (m1-scaled) Shahshahani gradient in_
_andint M Π := int ∆1 : int Mn →1 ×int . . . M× is the natural projectionint ∆nm with potential Ψ[′]1[(][θ][) = Ψ]_ _[◦]_ [Π][1][(][θ][)][ where][ Ψ(][θ][) :=][ E][s]i[∼][θ]i [[Φ(][s][)]][,]

**_θi,j,_** _if i in team k_
Πk,i,j(θ) = 0, _otherwise ._ (24)


_Likewise, if we assume the strategies of team 1 to be time-invariant, then the Replicator Dynamics_
_of G is a (m2-scaled) Shahshahani gradient in int M with potential Ψ[′]2_ [=][ −][Ψ][ ◦] [Π][2][(][θ][)][.]

_Proof. This proof is similar to the proof of Proposition 1, but we need to perform the correct pro-_
jection before applying the definition of a gradient flow. Let θ ∈ int M. Without any loss of the
generality, let us assume that the strategies of team 2 are time-invariant, i.e., _θ[˙]i,j = 0 for all i ≥_ _m1._
Then, for every ξ ∈ Tθ(int M) we have


-----

_∂Ψ(θ)_

Ψ(θ) _ξi,j_
_∂θi,j_ _−_

 


**_θ, ξ_** **_θ =_** _m1_ _θ˙i,jξi,j =_ _m1_
_⟨_ [˙] _⟩_ _θi,j_

_i=1_ _j_

X X X

_m1_ _∂Ψ(θ)_

= _ξi,j_ Ψ(θ)

_i=1_ _j_ _∂θi,j_ _−_

X X


_m1_

_eθi,j_

_m1_

_i=1_ _j_

X X


_θi,j_
_m1_

_ξij =_


_m1_

_i=1_

X


_∂Ψ(θ)_

_ξi,j_
_∂θi,j_


_∂Ψ(Π1(θ))_
= _ξi,j =_ Ψ[′]1[(][θ][)][ ·][ ξ][ .]

_∂θi,j_ _∇_

X

Hence, by definition, we have that dΨ[′]1[(][θ][) = ˙]θ[♭], which implies the theorem.


**Proposition 2 (Metric tensors of the model space). Under mild regularity assumptions, we have**
_that, for any θ ∈_ R[M] _,_

_Fθ+δθ_ _Fθ_ = _δθ, Aθδθ_ + o( _δθ_ ) _where_ **_Aθ := Ex_** _px_ [ **_θFθ(x)_** **_θFθ(x)[⊺]] . (11)_**
_∥_ _−_ _∥[2]_ _⟨_ _⟩_ _∥_ _∥[2]_ _∼_ _∇_ _∇_

_Proof. The assumption on F we need to prove this results are the following:_

-  θ _Fθ(x) is almost surely differentiable, i.e., almost surely (in x),_
_7→_

_Fθ+δθ(x) = Fθ(x) + ⟨∇Fθ(x), δθ⟩_ + ∥δθ∥f (x, θ), ∀θ ∈ R[M] _,_ (25)

where f (x, δθ) _δθ_ 0 0 almost surely in x.
_→_ _→_

-  For small enough δθ ∈ R[M], The remainder of the Taylor expansion of Fθ has a finite
variance, i.e.,
Ex _px_ [f (x, δθ)[2]] < + _._ (26)
_∼_ _∞_


A consequence of these two assumption is that (by dominated convergence theorem and Jensen’s
inequality)
Ex _px_ [ _f_ (x, δθ) ] _δθ_ 0 0 and Ex _px_ [f (x, δθ)[2]] _δθ_ 0 0 . (27)
_∼_ _|_ _|_ _→_ _→_ _∼_ _→_ _→_

Let us now prove the desired property. We start by doing a Taylor expansion of θ _Fθ(x),_
_7→_

_Fθ+δθ(x) = Fθ(x) +_ _Fθ(x), δθ_ + _δθ_ _f_ (x, θ) .
_⟨∇_ _⟩_ _∥_ _∥_

Then we have that

_Fθ+δθ_ _Fθ_ = Ex _px_ [( _Fθ(x), δθ_ + f (x, θ) _δθ_ )[2]]
_∥_ _−_ _∥[2]_ _∼_ _⟨∇_ _⟩_ _∥_ _∥_

= Ex _px_ [( _Fθ(x)[⊺]δθ)[2]] + o(δθ)[2]_
_∼_ _∇_

= Ex _px_ [δθ[⊺] _Fθ(x)_ _Fθ(x)[⊺]δθ] + o(δθ)[2]_
_∼_ _∇_ _∇_

= δθ[⊺]Ex _px_ [ _Fθ(x)_ _Fθ(x)[⊺]]δθ + o(δθ)[2];_
_∼_ _∇_ _∇_


which concludes the proof.

**Proposition 3 (Natural Hidden Gradient dynamics). The flow induced by the geometry (11) is**

**_θ˙ = −A[†]θ[E][(][x][,][x][′][)][∼][p][[][∇][θ][L][x][,][x][′]_** [(][F][θ][(][x][)][, G][φ][(][x][′][))]] (D7)
**_φ˙_** = Bφ[†] [E][(][x][,][x][′][)][∼][p][[][∇][φ][L][x][,][x][′] [(][F][θ][(][x][)][, G][φ][(][x][′][))]]

_where Aθ := Ex∼px_ [∇θFθ(x)∇θFθ(x)[⊺]] and Bφ := Ex′∼px′ [∇φGφ(x)∇φGφ(x)[⊺]] and C _[†]_
_denotes the pseudo-inverse of a matrix C._


-----

_Proof. The proposition directly follows from Proposition 2 applied to the definition of (7). However,_
in order to convey more intuition we could use the definition that the natural gradient flow of the
objective function f induced by the distance d if


1

2λ[2][ d][2][(][F][θ][+][λδ][θ][, F][θ][)][ .]


**_θ˙ = arg min_** lim
_δθ_ _λ→0_ _λ_ _[f]_ [(][θ][ +][ λδ][θ][) +]


By using the L[2] distance and noting that when λ 0 we have f (θ + _λδθ) = f_ (θ)+ _λ_ _f_ (θ)[⊺]δθ +
1 _→_ _∇_
_o(λ) and_ 2λ[2][ ∥][F][θ][+][λδ][θ][ −] _[F][θ][∥][2][ =][ 1]2_ _[⟨][δ][θ][,][ A][θ][δ][θ][⟩]_ [+][ o][(1)][ we have that the RHS of the equation above]

is

arg min _f_ (θ)[⊺]δθ + [1]
_δθ_ _∇_ 2 _[⟨][δ][θ][,][ A][θ][δ][θ][⟩][;]_


which is minimized for δθ = −A[†]θ[∇][f] [(][θ][)][.]

A.3 OMITTED PROOFS OF SECTION 4

**Proposition 4. In the uni-dimensional case, the Natural Hidden Gradient flow D1 takes the form of**

**_θ˙ = −_** _[∇][θ]∥∇[L][(][f]θ_ _f[(][θ](θ[)][,g])∥[(][2][φ][))]_ _and_ **_φ˙_** = _[∇][φ]∥∇[L][(]φ[f]g[(][θ](φ[)][,g])∥[(][2][φ][))]_ _._ (D8)


_Proof. For the uni-dimensional case, Aθ = ∇f_ (θ)∇f (θ)[⊺] is a rank-1 matrix that projects any
vector in the direction of ∇f (θ) and scales it by ∥∇f (θ)∥[2]. Thus, by definition of the pseudoinverse, we have that for any vector u ∈ R[d]:

**_A[†]θ[u][ =][ ∇][f]_** [(][θ][)][⟨][u][,][ ∇][f] [(][θ][)][⟩] _._

_∥∇f_ (θ)∥[4]


Finally, notice that

**_θL(f_** (θ), g(φ)) = _f_ (θ) _[∂][(][f, g][(][φ][))]_
_∇_ _∇_ _∂f_

which leads to the stated proposition.


_f_ =f (θ) _[,]_


**Theorem 1. Let Ψ be the payoff of an HCC game (12) and consider the dynamics (D2). Then,**

_V (θ, φ) :=_ [1]2 [(][f] [(][θ][)][ −] _[f][ ∗][)][2][ +][ 1]2_ [(][g][(][φ][)][ −] _[g][∗][)][2]_ (13)

_is a Lyapunov function, i.e., it is positive, non-increasing, and null if and only if it evaluated at a_
_game solution. Moreover, if L is strictly convex-concave, we have that V is decreasing and that any_
_limit point (θ, φ) satisfies_ **_θL(f_** (θ), g(φ)) = **_φL(f_** (θ), g(φ)) = 0.
_∇_ _∇_


_Proof. By taking the time derivative of V (θ, φ), we get_

_f_ (θ) _∂L(f, g(φ))_
_V˙ (θ, φ) =_ ( _f_ (θ)(f (θ) _f_ ))[⊺] _∇_
_−_ _∇_ _−_ _[∗]_ _f_ (θ) _∂f_ _f_ =f (θ)

_∥∇_ _∥[2]_

_g(φ)_ _∂L(f_ (θ), g)
+ ( _g(φ)(g(φ)_ _g[∗]))[⊺]_ _∇_
_∇_ _−_ _g(φ)_ _∂g_ _g=g(φ)_

_∥∇_ _∥[2]_

= (f (θ) _f_ ) _[∂L][(][f, g][(][φ][)]_
_−_ _−_ _[∗]_ _∂f_ _f_ =f (θ) [+ (][g][(][φ][)][ −] _[g][∗][)]_ _[∂L][(][f]∂g[(][θ][)][, g][)]_ _g=g(φ)_ _[≤]_ [0]


-----

where the last inequality holds because L is convex-concave. Specifically, let L : R[M] _× R[N]_ _→_ R
be any differentiable convex-concave function with saddle point (f _[∗], g[∗]), then we have, respectively_

_f_ _f_ _,_ _f_ _L(f, g)_ _L(f_ _, g)_ _L(f, g)_ and _g_ _g[∗],_ _gL(f, g)_ _L(f, g)_ _L(f, g[∗]) ._
_−⟨_ _−_ _[∗]_ _∇_ _⟩≤_ _[∗]_ _−_ _⟨_ _−_ _∇_ _⟩≤_ _−_

By adding the two inequalities, we get

_f_ _f_ _,_ _f_ _L(f, g)_ + _g_ _g[∗],_ _gL(f, g)_ _L(f_ _, g)_ _L(f, g[∗])_ 0 (28)
_−⟨_ _−_ _[∗]_ _∇_ _⟩_ _⟨_ _−_ _∇_ _⟩≤_ _[∗]_ _−_ _≤_

where the last inequality holds because (f _[∗], g[∗]) is a saddle point. Hence, by definition, L is a_
Lyapunov function.

Finally, when L is strictly convex-concave, if there exists a limit point of (θ, φ) that is not a point
where **_θL(f_** (θ), g(φ)) = 0 and **_φL(f_** (θ), g(φ)) = 0 then by strict convex-concavity we get
_∇_ _∇_
that V should decrease by a “significant enough amount” to create a contradiction with the fact that
_V does converge._

Next, before proving the general case of Theorem 1, we’ll have to prove the following lemma:

**Lemma 2. Let (ui)i** [n] be a linearly independent family of vectors on R[d]. Then, the matrix
_∈_


**_uiu[⊺]i_** _[.]_ (29)
_i=1_

X


**_A :=_**


_is the Gram matrix of the family (ui)i_ [n] and and we have that **_ui, A[†]uj_** = δi,j, _i, j_ [n].
_∈_ _⟨_ _⟩_ _∀_ _∈_

_Proof. Let us introduce the matrix P := [u1, . . ., un][⊺]; we can easily verify that A = P_ [⊺]A. Let
**_P = UDV_** [⊺] be the SVD decomposition of P and, thus, A[†] = V (D[⊺]D)[†]V [⊺] where D[⊺]D is a
diagonal matrix. Then, we have

**_ui, A[†]uk_** = **_P_** [⊺]e[(][i][)], A[†]P [⊺]e[(][j][)] = **_V D[⊺]U_** [⊺]e[(][i][)], V (D[⊺]D)[†]V [⊺]V D[⊺]U [⊺]e[(][j][)]
_⟨_ _⟩_ _⟨_ _⟩_ _⟨_ _⟩_

= **_e[(][i][)], UD(D[⊺]D)[†]D[⊺]U_** [⊺]e[(][j][)] _._
_⟨_ _⟩_

To conclude this lemma, we just need to notice that the matrix D is a matrix with non-zero entries
on the diagonal and, since we assumed that the vectors in (ui)i [n] are linearly independent, we
_∈_
have that Di,i > 0, ∀i ∈ [n]. Thus, by a direct computation, we get that

**_D(D[⊺]D)[†]D[⊺]_** = In

which leads to **_ui, A[†]ui_** = δi,j.
_⟨_ _⟩_

**Theorem 2. Let Ψ be the payoff of a finite-sum HCC game given by (14) and consider the game**
_dynamics in (D3). Under Assumption 1, Assumption 2, we have that the quantity_


_V (θ, φ) := [1]_

2n


_n_

(Fθ(xi) _F_ (xi))[2] + [1]
_−_ _[∗]_ 2m
_i=1_

X


(Gφ(x[′]j[)][ −] _[G][∗][(][x][′]j[))][2]_ (15)
_j=1_

X


_is a Lyapunov function, i.e., is positive, non-increasing and null if and only if evaluated at a game_
_solution. Moreover, if L is strictly convex-concave, V is decreasing as long as (θ, φ) ̸= (θ[∗], φ[∗])_
_and if L is a µ-strongly convex-concave function we have that V is decreasing exponentially as_
_V (θ, φ) = V (θ0, φ0) exp(_ _µt)._
_−_


-----

_Proof. Similarly as the proof of Theorem 1, we consider the time derivative of V (θ, φ). For com-_
pactness, we are going to simplify the notation slightly by setting Fi := Fθ(xi), Gj := Gφ(x[′]j[)][,]
_Fi[∗]_ [:=][ F][ ∗][(][x][i][)][,][ G]j[∗] [:=][ G][∗][(][x]j[′] [)][, and][ L][i,j][ :=][ L][x]i[,][x][′]j [.]


_V˙ (θ, φ) = [1]_

_n_

= −

+

= −


_n_

_i=1(Fi −_ _Fi[∗][)][⟨∇][θ][F][i][,][ ˙]θ⟩_ + m[1]

X


_j=1(Gj −_ _G[∗]j_ [)][⟨∇][φ][G][j][,][ ˙]φ⟩

X


Xi=1(Fi − _Fi[∗][)][⟨∇][θ][F][i][,]([ A]j,kθ[†])∈X[m]×∇[θn]Lk,j(Fk, Gj)⟩_

_m_

(Gj _G[∗]j_ [)][⟨∇][φ][G][j][,][ B]φ[†] **_φLi,k(Fi, Gk)_**

Xj=1 _−_ (k,i)∈X[m]×∇[n] _⟩_


_n[2]m_

1

_nm[2]_

1

_n[2]m_

1

_nm[2]_


_n_
Xi=1(Fi − _F(j,ki[∗][)])∈X[m]⟨∇×[nθ]Fi, A[†]θ[∇][θ][F][k][⟩]_ _[∂L][k,j]∂F[(][F, G][j][)]_


_F =Fk_


_m_

(Gj _G[∗]j_ [)] **_φGj, Bφ[†]_** _[∇][φ][G][k][⟩]_ _[∂L][i,k][(][F][i][, G][)]_

Xj=1 _−_ (k,i)∈X[m]⟨∇×[n] _∂G_


_G=Gk_


From Lemma 2 we have that ⟨∇θFi, A[†]θ[∇][θ][F][k][⟩] [=][ n][ ·][ δ][i,k][,][ ∀][i][ ∈] [[][n][]][, k][ ∈] [[][m][]][, and that]
_⟨∇φGj, Bφ[†]_ _[∇][φ][F][k][⟩]_ [=][ m][ ·][ δ][j,k][. Hence, it follows]


_V˙ (θ, φ) =_
_−_ _nm[1]_


1

(Fi − _Fi[∗][)]_ _[∂L][i,j]∂F[(][F, G][j][)]_ _F =Fi_ [+] _nm_ (Gj − _G[∗]j_ [)] _[∂L][i,j]∂G[(][F][i][, G][)]_

_jiX∈∈[[mn]]_ _jiX∈∈[[mn]]_

= −⟨∂F L(F, G), F − _F_ _[∗]⟩_ + ⟨∂GL(F, G), G − _G[∗]⟩_


_G=Gj_


where [∂F L(F, G)](i,j) := _[∂L][i,j]∂F[(][F,G][j]_ [)] _F =Fi_, ∂GL(F, G)](i,j) := _[∂L][i,j]∂G[(][F][i][,G][)]_ _G=Gj_, and F, G, F _[∗],_

and G[∗] are indexed by (i, j), as well (while repeating vector elements as necessarily). Thus, using
the same reasoning as in Theorem 1, it follows that if L is convex-concave we have that V is nonincreasing, and, if L is strictly convex-concave, _V[˙] (θ, φ) < 0 whenever (θ, φ) ̸= (θ[∗], φ[∗]). Finally,_
if L is µ-strongly convex-concave, we have by definition that

_−⟨∂F L(F, G), F −_ _F_ _[∗]⟩_ + ⟨∂GL(F, G), G − _G[∗]⟩_

_≥−µ(∥F −_ _F_ _[∗]∥[2]_ + ∥G − _G[∗]∥[2]) = −µV (θ, φ)_


Thus we conclude that V (θ, φ) _V (θ0, φ0) exp(_ _µt)._
_≤_ _−_

A.4 OMITTED PROOFS OF SECTION 5

In order to prove (17), and (D9) we are, first, going to prove the following useful lemma:
**Lemma 3. Let hθ(i) := Exj** Ber(θj )[XOR(x1, . . ., xi)] where θ [0, 1][n], and i _n. Then the_
_∼_ _∈_ _≤_
_following equality holds:_


(1 2θj) . (30)
_−_
_j=1_

Y


1 2hθ(i) =
_−_


_Proof. The easiest way to prove this relationship is by induction on n ∈_ N. For n = 1, we only
need to verify that (30) holds for i = 1. Indeed, we have,


-----

1 2hθ(1) = 1 2Ex Ber(θ1)[XOR(x1)] = 1 2Ex Ber(θ1)[x1] = 1 2θ1 .
_−_ _−_ _∼_ _−_ _∼_ _−_

Next, let us assume that Lemma 3 holds for some n = n[′] _∈_ N. We are going to prove that Lemma 3
also holds for n = n[′] + 1, and this comes down in proving that (30) holds for i = n[′] + 1:

1 2hθ(n[′] + 1) = 1 2E[XOR(x1, . . ., xn′+1)] = 1 2E[E[XOR(x1, . . ., xn′+1) xn′+1]]
_−_ _−_ _−_ _|_
= 1 − 2(θn[′]+1E[XOR(x1, . . ., xn[′] _, 1)] + (1 −_ _θn[′]+1)E[XOR(x1, . . ., xn[′]_ _, 0)])_
= 1 2(θn′+1E[1 XOR(x1, . . ., xn′ )] + (1 _θn′+1)E[XOR(x1, . . ., xn′_ )])
_−_ _−_ _−_

= 1 2(θn′+1(1 _hθ(n[′])]) + (1_ _θn′+1)hθ(n[′])) = (1_ 2θn′+1)(1 2hθ(n[′]))
_−_ _−_ _−_ _−_ _−_

_n[′]_ _n[′]+1_


= (1 2θn′+1)
_−_


(1 2θj) =
_−_
_j=1_

Y


(1 2θj) .
_−_
_j=1_

Y


And we that, the proof by induction is complete.

**Proposition A.4. Let G = (n := n1** +n2, S := {0, 1}[n], u : S → R[n]) be a 2-Team Hidden Matching
_Pennies game with payoff function given by (16). Then, the expected payoff of the i-th member of_
_team k is given by (17)._

_Proof. The first equality follows, trivially, from the definition of Φ(s). All is left to prove is that_
Esk,i Ber(θk,i)[Φ(s)] = (1 2Es1,i Ber(θ1,i)[XOR(s1)])(1 2Es2,i Ber(θ2,i)[XOR(s2)]) for all
_−_ _∼_ _−_ _∼_ _−_ _∼_
_pθk ∈ :=[0 E, 1]sk,i[n]. We define, xBer(θk,i)[XOR(k = XOR(sk)]; hence,sk), k ∈_ [2]. Note that, by definition, xk ∼ Ber(pk), where
_∼_

Esk,i Ber(θk,i)[Φ(s)] = Esk,i Ber(θk,i)[1 2 **1XOR(s1)=XOR(s2)] = Exk** Ber(pk)[1 2 **1x1=x2** ]
_∼_ _∼_ _−_ _·_ _∼_ _−_ _·_

= Exk Ber(pk)[(1 2 XOR(x))] = 1 2hp(2) = (1 2p1)(1 2p2)
_∼_ _−_ _−_ _−_ _−_

= (1 2Es1,i Ber(θ1,i)[XOR(s1)])(1 2Es2,i Ber(θ2,i)[XOR(s2)]) .
_−_ _∼_ _−_ _∼_


**Proposition A.5. Let G = (n := n1** +n2, S := {0, 1}[n], u : S → R[n]) be a 2-Team Hidden Matching
_Pennies game with payoff function given by (16). Then, the RD of G is given by the dynamical system_
_of equations:_


_θ˙k,i = (_ 1)[k][−][1][ 2] _θk,i(1_ _θk,i)_
_−_ _nk_ _−_

_Proof. From (17) we have that_


(1 2θk,i) . (D9)
_−_

_kY[′]∈[2]_ _i[′]∈Y[nk′_ ]

(k,i)=(̸ _k[′],i[′])_


Esk,i Ber(θk,i)[uk,i(s)]
_∼_

= ( 1)[k][−][1][ 1] (1 2Es1,i Ber(θ1,i)[XOR(s1)])(1 2Es2,i Ber(θ2,i)[XOR(s2)])
_−_ _nk_ _−_ _∼_ _−_ _∼_


= (−1)[k][−][1][ 1]nk (1 − 2hθ1 (n1)(1 − 2hθ2 (n2) = (−1)[k][−][1][ 1]nk

Then, by the definition of RD of G, we get


(1 2θk,i) .
_−_

_kY∈[2]_ _i∈Y[nk]_


-----

**_θ˙k,i := θk,iEsk,i_** Ber(θk,i)[uk,i(0, s _k,i)_ _uk,i(s)]_
_∼_ _−_ _−_


= ( 1)[k][−][1][ 1] _θk,i_
_−_ _nk_


(1 2θk,i)
_−_ _−_

_i[′]∈Y[nk′_ ]
(k,i)=(̸ _k[′],i[′])_


(1 2θk,i)
_−_

_kY[′]∈[2]_ _i[′]∈Y[nk′_ ]


_k[′]∈[2]_


= ( 1)[k][−][1][ 2] _θk,i(1_ _θk,i)_
_−_ _nk_ _−_


(1 2θk,i) .
_−_

_i[′]∈Y[nk′_ ]
(k,i)=(̸ _k[′],i[′])_


_k[′]∈[2]_


**Theorem 3. Consider the Replicator Dynamics of G. Given any interior initial condition, the**
_resulting orbit is a cycle that satisfies the following n1 + n2 −_ 1 independent invariant functions:


_nk[log(θk,ik_ ) + log(1 _θk,ik_ )], ik [nk], k [2] . (19)
_k=1_ _−_ _∈_ _∈_

X


_Vi1,i2_ (θ) =


_Proof. For all k_ [2] and i [nk], we have
_∈_ _∈_


_nk(1_ 2θk,i)
_−_ if (k, i) (k[′], ik′ ) _k[′]_ [2]

_θk,i(1_ _θk,i)_ _[,]_ _∈{_ _|_ _∈_ _}_
_−_

0, otherwise .


_∂Vi1i2_ (θ)

_∂θk,i_

Subsequently, we have


_V˙i1i2_ (θ) = **_θVi1i2_** (θ), **_θ[˙]_** = 2
_⟨∇_ _⟩_


(1 2θk,i) 2
_−_ _−_
_i∈Y[nk]_


(1 2θk,i) = 0 .
_−_
_i∈Y[nk]_


_k∈[2]_


_k∈[2]_


Observe that the above imply the existence ofthe dynamics converge to a limit set of a single degree of freedom, i.e., a cycle. n1 + n2 − 1 independent invariant functions. Hence,

**Proposition A.6. Let G = (n := n1 + n2, S := {0, 1}[n], u : S →** R[n]) be a 2-Team Hidden
_Matching Pennies game with payoff function given by (16). Given a mixed-strategy profile (θ, 1 −_
**_θ), θ := (θ1, θ2)_** (0, 1)[n], (θ, 1 **_θ) is an equilibrium of G if and only if_** _ik,_ _k_ [2] such that
_∈_ _−_ _∃_ _∀_ _∈_
_θk,ik =_ [1]2 _[,][ ∀][k][ ∈]_ [[2]][.]

_Proof. We know that G is equivalent to a Hidden Matching Pennies game (Example 1) with_
payoff Ψ (θ) = (1 2f (θ1))(1 2g(θ2)), where f (θ1) := Es1,i Ber(θ1,i)[XOR(s1)], and
_−_ _−_ _∼_
_g(θ2) := Es2,i_ Ber(θ2,i)[XOR(s2)] are its hidden mappings. The only fully mixed-Nash equilib_∼_
rium of this Hidden Matching Pennies game is (f (θ1), g(θ2)) = ( [1]2 _[,][ 1]2_ [)][; hence, a mixed-strategy]

profile (θ, 1 − **_θ) is a fully mixed-Nash equilibrium of G, if and only if f_** (θ1) = g(θ2) = [1]2 [. From]

_f_ (θ1) = [1]2 [we get]


_n1_

(1 2θ1,i) = 0
_−_
_i=1_

Y


Es1,i Ber(θ1,i)[XOR(s1)] = [1] 1 2hθ1 (n1) = 0
_∼_ 2 _[⇐]⇒_ _−_ _⇐_

_i1_ [n1] : θ1,i = [1]
_⇐⇒∃_ _∈_ 2 _[.]_


-----

We remark that, for any ik [nk], k [2],
_∈_ _∈_


2 · nk[ 2[1] [log(][θ][k,i][k] [) +][ 1]2 [log(1][ −] _[θ][k,i][k]_ [)]]
_k=1_

X


_Vi1,i2_ (θ) :=


_nk[log(θk,ik_ ) + log(1 _θk,ik_ )] =
_−_
_k=1_

X


= 2 · nkH(Ber( [1]2 [)][,][ Ber(][θ][k,i][k] [))]

_k=1_

X

where H(p, q) is the cross-entropy of a distribution q relative to a distribution p. In other words,
every one of the invariant functions in (19) is the weighted sum of the cross entropy of two mixedstrategies (of the i1-th member of team 1, and the i2-th member of team 2) relative to the uniform
strategy. That is, each invariant function measures (up to a constant) the Kullback–Leibler divergence of two opposing members to an actual equilibrium of the game. Notice that, for any equilibrium point of the Hidden Matching Pennies game, there exists at least on such pair of opposing
members i1 [n1], and i2 [n2] such that
_∈_ _∈_

_DKL(Ber(_ [1]2 [)][ ∥] [Ber(][θ][1][,i][1] [)) =][ D][KL][(Ber(][ 1]2 [)][ ∥] [Ber(][θ][2][,i][2] [)) = 0][ .]


For the rest of this section we are going to consider the RD of a 2-Team Hidden Matching Pennies
game G = (n := n1 + n2, S := {0, 1}[n], u : S → R[n]) in a restricted setting, given by the following
dynamical system of equations:


0, if θk,i /∈ Sk,i
0, if θk,i = αk,i and (−1)[k]Dk,i(θ) < 0

0, if θk,i = βk,i and (−1)[k]Dk,i(θ) > 0

( 1)[k][−][1][ 2] _θk,i(1_ _θk,i)Dk,i(θ),_ otherwise
_−_ _nk_ _−_


(D10)


_θ˙k,i =_


where Dk,i(θ) := _k[′]∈[2]_ (k[′]j,j∈)[n=(̸ _k′k,i]_ )(1 − 2θk′,j), k ∈ [2] i ∈ [nk], and where we restrict each

mixed-strategy profile (θ, 1Q **_θ) such that θk,i_** Sk,i := [αk,i, βk,i], _k_ [2], i [nk]. We let
Ω be an orbit defined by this RD whose initial conditions satisfy[Q] _−_ _∈_ Assumption 3 ∀ _∈_ . This assumption ∈
serves a dual purpose. To begin with, it ensures that any orbit is initialized inside the restricted
parameter space that is defined by Sk,i. Furthermore, it makes sure the initial strategy profile has
full support, i.e., (θk,i(0), 1 _θk,i(0)) is an interior point of the simplex for all k_ [2], and i [nk].
_−_ _∈_ _∈_
It is easy to see that any dimension of the strategy space initially without support is impossible to be
updated by the RD in (D10); hence, it would be irrelevant for the analysis. Before we proceed, we
are going to introduce a couple of useful lemmas.

**Lemma 4. ∀k ∈** [2], and i ∈ [nk] if θk,i(0) ∈ Sk,i, then θk,i(t) ∈ Sk,i, ∀t ≥ 0.

_Proof.to prove our case by abduction. Let k ∈_ [2] and i ∈ [nk] such that θk,i(0) ∈ Sk,i =⇒ _αk,i ≤_ _θk,i(0) ≤_ _βk,i. We are going_

Suppose ∃t0 > 0 such that θk,i(t0) /∈ Sk,i and, without any loss of the generality, let us assume that
_θk,i(t0) > βk,i. We let T = {t ∈_ (0, t0) | θk,i(t) = βk,i and we note that, since θk,i(0) ≤ _βk,i, it_
is implied by the continuity of θk,i(t) (Equation D10) and by the Intermediate Value Theorem that
T ̸= ∅. Finally we define tmax = max(T).

Let us now consider the value of θk,i(t) for some t (tmax, t0) and observe that if θk,i(t) = βk,i
_∈_
we have

_t ∈_ T =⇒ _t ≤_ max(T) = tmax =⇒ _tmax < t ≤_ _tmax ._


-----

This contradiction implies that θk,i(t) = βk,i. However, if θk,i(t) < βk,i, the Intermediate Value
_̸_
Theorem, once again, implies ∃t[′] _∈_ (t, t0) such that θk,i(t[′]) = βk,i, which as before implies tmax <
_t[′]_ _tmax. Hence, it must be the case that, for all t_ (tmax, t0):
_≤_ _∈_

(D10)
_θk,i(t) > βk,i_ = _θk,i(t) = 0 ._
_⇒_ [˙]

However, by applying the Mean Value Theorem, if follows _t[′]_ (tmax, t0) such that
_∃_ _∈_

_θ˙k,i(t) =_ _[θ][k,i][(0)][ −]_ _[θ][k,i][(][t][max][)]_ = _[θ][k,i][(0)][ −]_ _[β][k,i]_ _> 0,_

_t0_ _tmax_ _t0_ _tmax_
_−_ _−_


which is once again a contradiction.

**Lemma 5. Under Assumption 3, if Sk = ∅, ∀k ∈** [2] then the following hold:

_(a) Ψ1,i1_ (θ(t))Ψ2,i2 (θ(t)) < 0 for all ik [nk], k [2], and t 0.
_∈_ _∈_ _≥_

_(b) Ψk,ik_ (θ(t)) preserves sign for all ik [nk], k [2].
_∈_ _∈_

_Proof. Since Sk = ∅_ for all k ∈ [2], it follows, by definition, that

1
Sk,i, _k_ [2], i [nk]
2 _∈[/]_ _∀_ _∈_ _∈_

Furthermore, by Assumption 3, we have that θk,i(0) ∈ Sk,i for all k ∈ [2], i ∈ [nk]. Hence, it
follows, by Lemma 4, that _k_ [2], i [nk], and t 0:
_∀_ _∈_ _∈_ _≥_


**_θk,i(t) ∈_** Sk,i =⇒ **_θk,i(t) ̸= 2 [1]_** [=]⇒ 1 − 2θk,i(t) ̸= 0 .

Then, by Equation 17, we have

_Ψk,i(θ(t)) = [(][−][1)][k][−][1]_ (1 2Es1,j Ber(θ1,j )[XOR(s1)])(1 2Es2,j Ber(θ2,j )[XOR(s2)])

_nk_ _−_ _∼_ _−_ _∼_


_n1_

(1 2θ1,j)
_−_
_j=1_

Y


_n2_

(1 2θ2,j)
_−_
_j=1_

Y


= [(][−][1)]nk[k][−][1] (1 − 2hθ1 )(1 − 2hθ2 ) = [(][−][1)]nk[k][−][1]


_nk′_

(1 2θk′,j(t)) = 0 .
_−_ _̸_
_j=1_

Y


= [(][−][1)][k][−][1]

_nk_


_k[′]=1_


That implies (a). We can now condition on Ψk,i(θ(0)). Since Ψk,i(θ(t)) = 0 for all t 0, it must
_̸_ _≥_
be the case that either Ψk,i(θ(0)) > 0 or Ψk,i(θ(0)) < 0; let us, first, assume the former case. We
are going to prove, by abduction, that Ψk,i(θ(t)) > 0, _t_ 0.
_∀_ _≥_

Suppose _t[′]_ _> 0 such that Ψk,i(θ(t[′]))_ 0. Since Ψk,i(θ(t)) = 0 for all t 0 it follows that
_∃_ _≤_ _̸_ _≥_
_Ψk,i(θ(t[′])) < 0 must be the case. However, by the continuity of Ψk,i(θ(t)) and the Intermediate_
Value Theorem, it follows that _t[′′]_ (0, t[′]) such that Ψk,i(θ(t[′′])) = 0, and that is, indeed, a
_∃_ _∈_
contradiction. It follows that it must be the case Ψk,i(θ(t)) > 0, _t_ 0.
_∀_ _≥_

In a similar manner we may prove that Ψk,i(θ(0)) < 0 = _Ψk,i(θ(t)) < 0,_ _t_ 0; hence, (b)
_⇒_ _∀_ _≥_

holds.


-----

**Theorem 4. Under Assumption 3, if Sk = ∅, ∀k ∈** [2], the restricted RD of G converge to

_θ1[∗],i_ [=] _α1,i,_ _if β1,i <_ [1]2 _i_ [n1] _θ1[∗],i_ [=] _β1,i,_ _if β1,i <_ 2[1] _i_ [n1]

_β1,i,_ _otherwise_ _∈_ _α1,i,_ _otherwise_ _∈_

 _or_ 

_θ2[∗],i_ [=] _β2,i,_ _if β2,i <_ [1]2 _i_ [n2] _θ2[∗],i_ [=] _α2,i,_ _if β2,i <_ [1]2 _i_ [n2]

_α2,i,_ _otherwise_ _∈_ _β2,i,_ _otherwise_ _∈_

 

_if |S| is even_ _if |S| is odd_

_where| S := {(k, i) | k ∈{z[2], i ∈_ [nk], αk,i} > [1]2 _[}][.]_ | {z }


(20)


_Proof. We begin by conditioning on the value of |S| and, since the proof is similar in both cases,_
and without any loss of the generality, we are going to assume that |S| is even. Since Sk = ∅ for all
_k ∈_ [2], i.e., [1]2 _∈[/]_ Sk,i for all k ∈ [2], i ∈ [nk], and, by Assumption 3, θk,i(0) ∈ Sk,i := [αk,i, βk,i]

for k ∈ [2], i ∈ [nk] it follows that θk,i(0) > [1]2 [, if][ α][k,i][ >][ 1]2 [;][ θ][k,i][(0)][ <][ 1]2 [; otherwise. Then, for all]

_i_ [n1], we have
_∈_


_nk_

(1 2θk,j(0))
_−_
_j=1_

Y


_Ψ1,i(θ(0)) = [1]_

_nk_


_k_

_k=1_ _j=1_

(1 2θk,j(0)) (1 2θk,j(0)) _> 0,_

 _−_  _·_  _−_ 

(k,j)∈S (k,j)∈/S

 [Y]   [Y] 


= [1]

_nk_


since |S| is even. Subsequently, by Lemma 5, Ψ1,i(θ(t)) > 0, ∀t ≥ 0. That implies that
_Ψ1,i(θ(t)) > 0,_ _i_ [n1], t 0, and, hence, by Lemma 5, we also have that Ψ2,i(θ(t)) <
_∀_ _∈_ _≥_
0, _i_ [n2], t 0. Take any k [2], and i [nk]. In order to complete the proof, we’ll have
_∀_ _∈_ _≥_ _∈_ _∈_
to condition on the value of k, and on whether (k, i) ∈ S. There are four cases in total that we”ll
have to consider, but, since in all of them we follow a similar reasoning, we’ll just go ahead and
demonstrate the single case of k = 1, and (k, i) ∈ S.

We are going to prove that there existsand, sincetion 3, and S Lemma 4k = ∅, we have that, we have α α11,i,i ≥ ≥ tθβ1[∗]11,i,i,i( >t[≥]) ≥[0][1]2[ such that][. That is,]β1,i for all[ θ][ θ][1][1][,i] t[,i][(] ≥[(][t][t][)][) =][ >]0[ 1]. Furthermore, since2[ β][for all][1][, i,][ ∀][ t][t][ ≥][ ≥][0][t][, and, hence,]1[∗],i[. By] (1[ Assump-], i) ∈ S,


_nk_

(1 2θk,j(t))
_−_
_j=1_

Y


_D1,i(θ(t)) :=_

_kY∈[2]_


(1 2θk,j(t)) =
_−_

(k,jj∈Y)=(1̸[nk],i)


1 2θ1,i(t)
_−_ _[·]_ _k=1_

Y


= n1
_·_


1 2θ1,i(t)
_−_ _[·][ Ψ][1][,i][(][t][)][ <][ 0][ .]_


Then, by Equation D10 it follows that ∀t ≥ 0:


0, if θ1,i = β1,i
2 (D11)

_θ1,i(1_ _θ1,i)D1,i(θ),_ otherwise .
_n1_ _−_


_θ˙1,i(t) =_


Hence, θ1,i = β1,i is the single attracting point of the dynamical system described by D11 and,
thathence, by definition,t[∗]k,i _∃t[∗]1,i_ _[≥]_ [0][ such that]k,i[,][ θ][ ∀][1][,i][t][ ≥][(][t][) =][t][∗]k,i[ θ][, and by letting]1[∗],i [=][ β][1][,i][,][ ∀][t][ ≥][ t][∗][t]1[∗],i[= max][. Similarly, we can prove](t[∗]k,i[)][,][ Theorem 4]
_∃_ _[≥]_ [0][ such that][ θ][k,i][(][t][) =][ θ][∗] _k∈[2]_
_i∈[nk]_

follows.


-----

**Theorem 5.invariant set defined by the[2], where Vi Under1,i2** (θ) is given as in Assumption 3 |S1|+ (|, ifS192|− S). _k1 ̸= independent invariant functions, ∅, ∀k ∈_ [2], then the restricted RD of Vi1,i2 (θ G), i converge to ank ∈ Sk, ∀k ∈

_Proof. We are going to begin by defining the following time-dependent set:_

C(t) := _{(k, i) | k ∈_ [2], i ∈ [nk], θk,i(t) ∈{αk,i, βk,i}}, if t ≥ 0
 _∅,_ otherwise .

We perform a time partitioning based on the values of C(t), t ≥ 0. Specifically, we let P =
_{(t1, t2) | t1, t2 ∈_ T : t /∈ T, ∀t ∈ (t1, t2)}, where

_T := {t ≥_ 0 | ∃ϵ0 > 0 : C(t − _ϵ) ̸= C(t), ∀ϵ ∈_ (0, ϵ0)} .

It is not difficult to see that the continuity of θ(t) implies that T consists entirely of isolated points
and, due to this fact, P is well-defined. Let I ∈ P be one of these partitions. We are going to prove
that _V[˙]i1,i2_ (θ(t)) ≥ 0, ∀ik ∈ Sk, ∀k ∈ [2], t ∈ I.

First of all, observe that, by definition, the following two properties have to hold:

(a) C(t1) = C(t2), ∀t1, t2 ∈ _I_

(b) By Equation D10, we have that ∀t ∈ _I,_


0, if (k, i) ∈ C(t)

(D12)

( 1)[k][−][1][ 2] _θk,i(1_ _θk,i)Dk,i(θ),_ otherwise .
_−_ _nk_ _−_


_θ˙k,i(t) =_


CFor any(t1) = i Ck ∈(t2),S ∀k, kt1, t ∈2 ∈[2]I, we proceed by conditioning on the value of, we distinct only three cases: C(t), t ∈ _I and, since_

(a) (k, ik) ∈ C(t), ∀k ∈ [2], t ∈ I.

(b) (k, ik) /∈ C(t), ∀k ∈ [2], t ∈ I.

(c) ∃k, k[′] _∈_ [2] such that (k, ik) ∈ C(t) and (k[′], ik[′] ) /∈ C(t) for all t ∈ I.


The analysis of the first two cases is relatively straightforward. Let t ∈ I; then, if (k, ik) ∈
C(t), ∀k ∈ [2] is the case, then by Equation D12, we have that _θ[˙]k,ik_ (t) = 0, ∀k ∈ [2] and,
hence,


_nk(1_ 2θk,i(t))

_θk,i(t)(1 −_ _θk,i(t))_ _θk,ik_ (t) = 0 .

 _−_ _[·][ ˙]_ 


_V˙i1,i2_ (θ(t)) = ( **_θ(t)Vi1,i2_** (θ(t)))[⊺]θ[˙](t) =
_∇_


_k=1_


On the other hand, if (k, ik) /∈ C(t), ∀k ∈ [2] is the case, then, once again, by Equation D12, we
have that _θ[˙]k,ik_ (t) = (−1)[k][−][1 2]nk _[θ][k,i][(1][ −]_ _[θ][k,i][)][D][k,i][(][θ][)][,][ ∀][k][ ∈]_ [[2]][. That implies,]


_nk(1_ 2θk,i(t))
_−_ _θk,i(t)(1_ _θk,i(t))Dk,i(θ(t))_

_θk,i(t)(1_ _θk,i(t))_ _nk_ _−_

 _−_ _[·][ (][−][1)][k][−][1][ 2]_


_V˙i1,i2_ (θ(t)) =


_k=1_


_nk_

(1 2θk,j(t))
_−_ _·_
_j=1_

Y


(−1)[k][−][1] = 0 .
_k=1_

X


= 2 ·


_k=1_


In order to proceed with the final case we’ll first need to prove a small technical lemma:


-----

_then one of the following holds:Lemma 6. If (k, i) ∈_ C(t) for some t ∈ I, I ∈ P = {(t1, t2) | t1, t2 ∈ T : t /∈ T, ∀t ∈ (t1, t2)}

_a) θk,i(t) = αk,i, ∀t ∈_ I.

_b) θk,i(t) = βk,i, ∀t ∈_ I.

To see that, let I ∈ P and (k, i) ∈ C(t) for some t ∈ I. Then it, holds, by definition, that

C(t1) = C(t2), ∀t1, t2 ∈ I =⇒ C(t[′]) = C(t), ∀t[′] _∈_ I

And, since (k, i) ∈ C(t), we also have that

(k, i) ∈ C(t[′]), ∀t[′] _∈_ I =⇒ _θk,i(t[′]) ∈{αk,i, βk,i}_

Let us assume that θk,i(t) = αk,i and suppose ∃t[′] _∈_ I such that θk,i(t[′]) ̸= αk,i =⇒ _θk,i(t[′]) = βk,i_
and αk,i = βk,i. By the Intermediate Value Theorem, it follows _t[′′]_ (min(t, t[′]), max(t, t[′])) such
that _̸_ _∃_ _∈_

_θk,i(t[′′]) ∈_ (αk,i, βk,i) =⇒ (k, i) /∈ C(t[′′])

That is a contradiction, and, hence, a) holds. a) follows by a similar argument, assuming θk,i(t) =
_βk, i is the case, instead._

Having established Lemma 6, we continue with the proof of Theorem 5. Let us assume that ∃k, k[′] _∈_

[2] such that (k, ik) C(t) and (k[′], ik′ ) / C(t). Then Lemma 6 implies that either θk,ik (t[′]) =
_∈_ _∈_
the former case and let us consider someαk,ik _, ∀t[′]_ _∈_ I or θk,ik (t[′]) = βk,ik _, ∀t[′]_ _t∈ ∈I. Let us assume, without any loss of the generality,I. Since Sk,ik ∈_ Sk, i.e., αk,ik ≤ 12 [, that implies]
1 2θk,ik (t) 0. Next, Let us consider the value of ( 1)[k][−][1]Dk,i(θ). We are going to prove by
_−_ _≥_ _−_
abduction that ( 1)[k][−][1]Dk,i(θ) 0.
_−_ _≤_

If (−1)[k][−][1]Dk,i(θ) > 0 then by Equation D10 we have thatθ[˙]k,ik (t) = (−1)[k][−][1 2]nk _[θ][k,i][(1][ −]_

_θk,i)Dk,i(θ)_ = 0, where the last inequality follows by Assumption 3. By the continuity θ(t), it
_̸_
follows that ∃ϵ0 > 0 such that ∀ϵ ∈ (0, ϵ0), θk,ik (t + ϵ) ̸= θk,ik (t) = αk,ik =⇒ (k, ik) /∈ C(t);
that is, indeed, a contradiction. It must then be the case that ( 1)[k][−][1]Dk,i(θ) 0 and, thus, we
_−_ _≤_
have that

_V˙i1,i2_ (θ(t)) = _nk′_ (1 − 2θk′,i(t))

_θk′,i(t)(1_ _θk′,i(t))_ _nk′_ _[θ][k][′][,i][(][t][)(1][ −]_ _[θ][k][′][,i][(][t][))][D][k][′][,i][(][θ][(][t][))]_
_−_ _[·][ (][−][1)][k][′][−][1][ 2]_

= 2 ( 1)[k][′][−][1] (1 2θk′,i(t))Dk′,i(θ(t)) = 2 ( 1) ( 1)[k][−][1] (1 2θk,i(t))Dk,i(θ(t)) 0 .
_·_ _−_ _·_ _−_ _·_ _−_ _·_ _−_ _·_ _−_ _≥_

Thus, we showed that in every case _V[˙]i1,i2_ (θ(t)) ≥ 0, ∀t ∈ I. However, since θ(t) is continuous
(since it is differentiable), we can extend this property for any t 0, i.e., _V[˙]i1,i2_ (θ(t)) 0, _t_ 0.
_≥_ _≥_ _∀_ _≥_
Finally, notice that Vi1,i2 (θ(t)) is bounded, and, hence, it follows that _Vi1,i2_ (θ(t)) is a Lyapunov
_−_
function (up to a constant) of the dynamical system described by Equation D10, and, Theorem 5
follows by the definition of a Lyapunov function.

B SUPPLEMENTARY EXPERIMENTAL RESULTS

B.1 EXPERIMENTAL RESULTS FOR 2-TEAM HIDDEN MATCHING PENNIES GAMES

In this section we present exemplary settings for the dynamics presented in section 5. For an
overview of the conditions that characterize the behaviors presented in these examples, we refer

-----

Figure 3: An example of the RD of a 2-Team Hidden Matching Pennies (Center) with no
restrictions applied in the parameters space (θ, 1 − **_θ) in (Left), and (Right). In this case, the_**
RD cycles for any initial point (θ(0), 1 − **_θ(0)). The evolution of θ(t), as a function of time,_**
_t ∈_ [0, 100] is depicted in (Bottom) along with the Lyapunov function given in (31).

ence the interested reader to section 5; for formal definitions and the proofs of these concepts, see
§A.4.

Let G = (n := n1 + n2, S := {0, 1}[n], u : S → R[n]) be a 2-Team Hidden Matching Pennies game
with n1 = n2 = 3 and payoff function given by (16). Figure 3 depicts the behavior of the RD in
an unrestricted instance of G, i.e., Sk,i = [0, 1] for all i ∈ [3], k ∈ [2]. The restrictions applied to
team 1 and team 2 are visualized by the feasible range of each member’s strategies (Figure 3 (Left),
and (Right), respectively). The black dot in each range indicates the initial strategy of each member,
i.e., θk,i(0). Note that, by Assumption 3, this strategy profile, (θ(0), 1 **_θ(0)), is assumed to lie_**
_−_
inside the feasible region enforced by the constraints Sk,i.

We solve the initial value problem of the ODE that corresponds to this RD using the RADAU integration method implemented by the scipy package in Python 3, and we perform 500 evaluations
over the time interval t ∈ [0, 100]. The orbit of the RD with initial parametrization θ(0) is depicted
as a curve on the F × G space defined by the hidden mappings in (18) (Figure 3 (Center)). The red
dot indicates the the point (f (θ1(t)), g(θ2(t)) at the end of the simulation, i.e., at time t = 100. The
corresponding strategies of each member are indicated by blue (team 1) and orange (team 2) dots
inside the corresponding feasible regions (Figure 3 (Left), and (Right)). The individual trajectory of
each θk,i, i [3], k [2] is depicted in Figure 3 (Bottom), where the curve labeled TkPi corre_∈_ _∈_
sponds to the trajectory of the i-th member of team k if k = 1, or the i _n1-th member of team k if_
_−_
_k = 2. In the case that the RD cycle, e.g., in the unrestricted setting, we depict one of the Lyapunov_
functions of the RD (Figure 3 (Bottom)). Specifically, the Lyapunov function of our choice is


_nk_ [log(θk,i(t)) + log(1 _θk,i(t))],_ (31)
_iX∈Sk_ _·_ _−_


_V (t) :=_


_|Sk|_


_k=1_


the average value of all the linearly independent Lyapunov functions defined in (19). We selected
this specific Lyapunov function as the average is, in general, more numerically stable and for compactness.


-----

In Figure 3, we verify that the RD of G, indeed, cycle in an unrestricted setting (Theorem 3).
The choice of initial points does not matter in this case; for completeness, we note that θ1 =
(0.1, 0.9, 0.2), and θ2 = (0.1, 0.9, 0.8) in all of the examples in this section.

Figure 4: An example of the RD of a 2-Team Hidden Matching Pennies (Center) in a restricted setting where [1]2 _∈[/]_ Sk,i for all i ∈ [3], k ∈ [2] ((Left), and (Right)). In this case,

the RD converges for any initial interior point (θ(0), 1 − **_θ(0)). The evolution of θ(t), as a_**
function of time, t ∈ [0, 100] is depicted in (Bottom).


As the first example in a restricted setting (Figure 4), we are going to enforce S1,1 = S1,3 =
_iS ∈2,1[3] = [0, k ∈.05[2], 0; hence,.4], and Assumption 3 S1,2 = S2,2 = is satisfied. Next, notice that S2,3 = [0.6, 0.95]. First, observe that[1]2_ _∈[/]_ Sk,i for all Sk,i ⊂ i ∈(0[3], 1), k for all ∈ [2].

It follows, by Theorem 4, that the RD should converge in this case (Figure 4 (Center), and (Bottom)),
and the point of convergence is, indeed, θ1[∗] [= (0][.][4][,][ 0][.][6][,][ 0][.][4)][, and][ θ]2[∗] [= (0][.][05][,][ 0][.][95][,][ 0][.][95)][, as given]
in Theorem 4.

Figure 5: An example of the RD of a 2-Team Hidden Matching Pennies (Center) in a restricted setting wherethe RD converges for any initial interior point[1]2 _[∈]_ [S][1][,i][, and][ 1]2 _∈[/]_ S2,i for all (θ(0) i, 1 ∈ −[3]θ(0)) ((Left), but the point of convergence, and (Right)). In this case

depends on the value of θ(0). The evolution of θ(t), as a function of time, t ∈ [0, 100] is
depicted in (Bottom).


-----

There exists a similar setting (Figure 5), where the RD of G converge, as well. Note, in this case,
whilei ∈ [3][1]2 in this particular example). Although we did not provide a convergence analysis for this∈[/] S2,i for all i ∈ [3], we let 2[1] _[∈]_ [S][1][,i][ for some][ i][ ∈] [[3]][ (specifically,][ 1]2 _[∈]_ [S][1][,i][ for all]

case, it is not difficult to see that the convergence guarantees from Theorem 4 can be generalized
to include this case. As is visualized in Figure 5 (Center), the exhibited behavior is a hybrid of the
two behaviors described by Theorem 4, and Theorem 5. In particular, the behavior of the dynamics
depends on the quadrant of the F × G space that the θ(t) lies. Ultimately though, the dynamics can
be shown to converge to a point θ[∗], which depends not only on the initialization θ(0) but also on
the restrictions in the space parameters, Sk,i, i ∈ [3], k ∈ [2]. The particular point of convergence
for this example is θ1[∗] [= (0][.][05][,][ 0][.][95][,][ 0][.][95)][, and][ θ]2[∗] [= (0][.][4][,][ 0][.][6][,][ 0][.][6)][, where the space restrictions]
are given as S2,1 = [0.05, 0.4], S2,2 = S2,3 = [0.6, 0.95], and S1,i = [0.05, 0.95] for all i ∈ [3].

Figure 6: An example of the RD of a 2-Team Hidden Matching Pennies (Center) in a restricted setting where [1]2 2

this case the RD converge to a cycle defined by, at least,[∈] [S][1][,i][, and][ 1] _[∈]_ [S][2][,j][ for some] |[ i, j]S1| +[ ∈] |S[[3]]2| −[ (][(Left)]1 linearly independent[, and][ (Right)][). In]
invariant functions for any initial interior point (θ(0), 1 − **_θ(0)) The evolution of θ(t), as a_**
function of time, t ∈ [0, 100] is depicted in (Bottom).


Finally, we present an example of cycling behavior in the restricted setting (Figure 6) where we
applied the restrictions S1,1 = S1,3 = [0.05, 0.8], S1,2 = S2,2 = [0.6, 0.95], S2,1 = [0.05, 0.4], and
S2,3 = [0.2, 0.95]. Note that [1]2

for all k [2] such that 2[1] _[∈]_ [S][1][,][1][,][ S][1][,][3][,][ S][2][,][3][; hence,][ |][S][1][|][ +][ |][S][2][|][ = 3][, and there exists][ i][k][ ∈] [[][n][k][]]

specifically, they converge to an invariant set defined by ∈ _[∈]_ [S][k,i][k] [. By][ Theorem 5][, it follows that the restricted RD cycle in this case;] V1,3(θ) = 0, and V3,3(θ) = 0 as given
by (19). This behavior is depicted in Figure 6 (Center). Notice how the Lyapunov function, V (θ)
(Figure 6 (Bottom)) is monotonically increasing, and stabilizes at approximately t = 25.


-----

