# A geometric decomposition of finite games: Convergence
## vs. recurrence under exponential weights

Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski

► To cite this version:

Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski. A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights. ICML 2024 - 41st International Conference on Machine Learning, Jul 2024, Vienna, Austria. hal-04629310

HAL Id: hal-04629310

https://hal.science/hal-04629310v1

Submitted on 29 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A GEOMETRIC DECOMPOSITION OF FINITE GAMES: CONVERGENCE VS. RECURRENCE UNDER EXPONENTIAL WEIGHTS

DAVIDE LEGACCI*, PANAYOTIS MERTIKOPOULOS*, AND BARY PRADELSKI‡

**ABSTRACT.** In view of the complexity of the dynamics of learning in games, we seek to decompose a game into simpler components where the dynamics' long-run behavior is well understood. A natural starting point for this is Helmholtz's theorem, which decomposes a vector field into a potential and an incompressible component. However, the geometry of game dynamics – and, in particular, the dynamics of exponential / multiplicative weights (EW) schemes – is not compatible with the Euclidean underpinnings of Helmholtz's theorem. This leads us to consider a specific Riemannian framework based on the so-called *Shahshahani metric*, and introduce the class of *incompressible games*, for which we establish the following results: First, in addition to being volume-preserving, the continuous-time EW dynamics in incompressible games admit a constant of motion and are *Poincaré recurrent* – i.e., almost every trajectory of play comes arbitrarily close to its starting point infinitely often. Second, we establish a deep connection with a well-known decomposition of games into a potential and harmonic component (where the players' objectives are aligned and anti-aligned respectively): a game is incompressible if and only if it is harmonic, implying in turn that the EW dynamics lead to Poincaré recurrence in harmonic games.

## 1. INTRODUCTION

One of the driving open questions in game-theoretic learning is whether – and under what conditions – players eventually learn to emulate rational behavior through repeated interactions. Put differently, whether a game-theoretic learning process converges to a rational outcome, what type of outcome this could be, under which mode of convergence, in which games, etc. This question has long been one of the mainstays of non-cooperative game theory, and it has recently received increased attention owing to a surge of breakthrough applications in machine learning and AI, from generative adversarial networks (GANs), to multi-agent reinforcement learning and online ad auctions.

Depending on the precise context, this question may admit a wide range of answers, from positive to negative. Starting with the positive, a folk result states that if the players of a finite game follow a no-regret learning process, the players' empirical frequency of play converges in the long run to the set of coarse correlated equilibria (CCE) – also known as the game's *Hannan set* [29]. This result has been pivotal for the development of the field because no-regret play can be achieved through fairly simple myopic processes like the

<footnote>* UNIV. GRENOBLE ALPES, CNRS, INRIA, GRENOBLE INP, LIG, 38000 GRENOBLE, FRANCE.</footnote>

<footnote>‡ CNRS, MAISON FRANÇAISE D'OXFORD, 2-10 NORHAM ROAD, OXFORD, OX2 6SE, UNITED KINGDOM.
*E-mail addresses:* davide.legacci@univ-grenoble-alpes.fr, panayotis.mertikopoulos@imag.fr, bary.pradelski@cnrs.fr.</footnote>

<footnote n="2020">2020 *Mathematics Subject Classification*. Primary 91A10, 91A26; secondary 68Q32, 68T02.</footnote>

<footnote>*Key words and phrases*. Harmonic games; incompressible games; Helmholtz decomposition; no-regret learning; replicator dynamics; Shahshahani metric; Poincaré recurrence.</footnote>

<footnote>The authors are grateful to Victor Boone and Marco Scarsini for fruitful discussions.</footnote>
exponential / multiplicative weights (EW) update scheme [7, 8, 58, 83] and its many variants [71, 76, 79]. On the downside however (a) this convergence result does not concern the actual strategies employed by the players day-to-day; and (b) in many games, the notion of a CCE can lead to outcomes that fail even the weakest axioms of rationalizability. For example, as was shown by Viossat & Zapechelnyuk [82], players may enjoy *negative regret* for all time, but still play *only strictly dominated strategies* for the entire horizon of play.

This takes us to the negative end of the spectrum. If we focus on the evolution of the players' strategies, a series of well-known impossibility results by Hart & Mas-Colell [31, 32] have established that there are no uncoupled learning dynamics – deterministic or stochastic, in either continuous or discrete time – that converge to Nash equilibrium (NE) in *all* games from any initial condition.<fnref n="1" /> In turn, this lends further weight to the question of determining in which games a learning process converges to Nash equilibrium in the day-to-day sense, and in which it does not.

In this regard, the class of games with arguably the strongest convergence guarantees is the class of potential games [66]. Here, the dynamics of EW methods are known to converge, in both continuous and discrete time, and even when the players only have bandit, payoff-based information at their disposal [33, 37]. By contrast, in two-player, zero-sum games (ZSGs) with fully mixed equilibria (like Matching Pennies) the standard implementation of the EW algorithm diverges, even with perfect, mixed payoff observations [64]; the so-called “optimistic” variant of Rakhlin & Sridharan [71] converges at a geometric rate if run with perfect payoff observations [85] but diverges if such information is not available [38–40]; and, finally, the continuous-time version of the EW dynamics – the *replicator dynamics* – is *Poincaré recurrent*, i.e., the trajectory of play returns infinitely close to where it started, infinitely often [63, 69].

Going back to the two classes of games above, potential games are quite special in that the players' incentives are *aligned* (their externalities are positive); on the other hand, in two-player zero-sum games, the players' incentives are *anti-aligned* (externalities are negative). Largely motivated by this observation, Candogan et al. [14] introduced a principled framework of decomposing a game into a *potential* and a *harmonic* component: the potential component of the game captures interactions that amount to a common interest game, while the harmonic component captures the conflicts between the players' interests.<fnref n="2" /> In this way, the decomposition of Candogan et al. [14] effectively maps all games to a spectrum ranging from *fully aligned* (when the harmonic component of the game is zero) to *fully anti-aligned* (when the potential component is zero).

Building on this decomposition, a natural question that arises is whether a similar conclusion can be drawn for the players' *learning dynamics*. Specifically, focusing for concreteness on continuous time (which eliminates complications related to the players' hyperparameters or feedback structure), a key question is whether the space of games can be likewise mapped to a “convergence spectrum”, with (global) convergence on one end, and global non-convergence / Poincaré recurrence on the other. A version of this question was already treated in a series of follow-up works by Candogan et al. [15, 16, 17] who showed that the best-response dynamics remain convergent in slight perturbations of potential games.

<footnote n="1">¹The adjective “uncoupled” refers here to learning processes where a player’s update rule does not explicitly depend on the other players’ strategies.</footnote>

<footnote n="2">²The class of harmonic games contains some zero-sum games (like Matching Pennies), but not all; likewise, the class of zero-sum games contains some harmonic games (e.g., when all players have the same number of strategies), but not all. In general, the classes of harmonic and zero-sum games are distinct, and they represent different incarnations of “anti-aligned objectives”.</footnote>
However, moving further toward the class of harmonic games hit an important obstacle, and
has remained an open question since the original work of Candogan et al. [14]: except for
some special cases, *the behavior of the replicator dynamics in harmonic games is not well*
*understood.*

**Our contributions.** In view of the above, our paper’s overarching objective is to derive a dynamics-driven decomposition of games – and, in so doing, to shed light on the dynamics of harmonic games. Motivated by Helmholtz’s theorem for the decomposition of vector fields into a potential and an incompressible, divergence-free component, we first seek to define a class of *incompressible games* at the opposite end of potential games. However, the geometry of the dynamics turns out to be incompatible with the standard Euclidean geometry of the simplex, so we are led to consider a nonlinear Riemannian structure on the simplex, the Shahshahani metric [75]. This ends up complicating the construction significantly, but it allows us to show that the class of incompressible games that we introduce has the characteristic property that the players’ learning dynamics are *volume-preserving* (i.e., a set of initial conditions does not decrease in volume relative to the Shahshahani metric).

As a consequence of this, the class of incompressible games is shown to exhibit two fairly unexpected properties:

(1) *A game is harmonic if and only if it is incompressible, and the decomposition of a game into a potential and incompressible component (relative to the Shahshahani metric) is equivalent to that of Candogan et al. [14].*

(2) *Incompressible games are conservative*, i.e., the dynamics admit a constant of motion.
Both properties are surprising, for different reasons. The first, because harmonic and
incompressible games have completely different origins: the former is coming from the
combinatorial decomposition of Candogan et al. [14], the latter from the kernel of the
Shahshahani divergence operator, so there is no reason to expect these notions to coincide.
The second, because volume preservation and constants of motion are two complementary
and independent properties, so the fact that the former implies the latter is quite mysterious.<fnref n="3" />

Building further on the above, we also show that *the EW dynamics are Poincaré recurrent in harmonic games*. By itself, this provides a partial answer to the open-ended question of whether harmonic games should be placed in the non-convergent end of the spectrum [14]. Moreover, to the best of our knowledge, Poincaré recurrence in the context of game-theoretic learning has been so far established only in zero-sum games with a fully mixed equilibrium and variations of the above [12, 63, 69]. Seeing as harmonic games are related to zero-sum games (though neither property implies or is implied by the other, cf. Remark D.2), this result identifies an important new class of games where no-regret learning in continuous time fails to converge.

**Related work.** Before the general definition of harmonic games by Candogan et al. [14], specific instances thereof were already studied in the context of cyclic games, the battle of the sexes, buyer/seller games, and crime deterrence games [18, 23, 27, 36, 78]. Building on these early works, Abdou et al. [1], Li et al. [57], Wang et al. [84] proposed a weighted versions of the decomposition by Candogan et al. [14] based on different inner products on the space of games. Cheng et al. [19] proposed in particular a concise derivation of the decomposition of Candogan et al. [14] with applications to (network) evolutionary games and

<footnote n="3">³Notably, Flokas et al. [26] showed that the EW dynamics are volume-preserving in every game relative to a different volume form on the simplex; however, only very special classes of games admit a constant of motion – cf. the discussion following Theorem 3.</footnote>
near-potential games. Hwang & Rey-Bellet [42] present a projection-based decomposition method, equivalent to that of Candogan et al. [14] for finite games and that applies also to mixed extensions of normal form games with continuous action spaces.

On the interplay between decomposition methods and dynamics, beyond the already mentioned follow-up works by Candogan et al. [15, 16, 17] on near-potential games, Cheung & Tao [20] applied volume analysis techniques to the canonical decomposition of a game into zero-sum and coordination components [9, 45] to characterize bimatrix games where standard classes of no-regret learning exhibit Lyapunov chaos. More recently, Letcher et al. [55] employed a decomposition argument to design a novel algorithm for finding stable fixed points in differentiable games. The machinery we develop in this work connects the differential-geometric Hodge/Helmholtz decomposition to a constrained setting, thus providing a partial answer to an open question raised in Letcher et al. [55]; however, there is a key difference between the spirit of our approach and that of Letcher et al. [55], that we discuss in Appendix E.1.

To the best of our knowledge, the only other works in the literature that study the dynamics of harmonic games are the papers by Li et al. [56] and Cheng et al. [19], which discuss a dynamical equivalence between basis games and evolutionary harmonic games. Except for these works, we are not aware of a similar approach in the literature.

## 2. PRELIMINARIES

### 2.1. Elements of game theory.
To fix notation, we begin by recalling some basics from game theory, roughly following Fudenberg & Tirole [28]. First, a finite game in normal form consists of a finite set of players $i \in \mathcal{N} \equiv \{1, \dots, N\}$, each equipped with (i) a finite set of actions – or pure strategies – indexed by $\alpha_i \in A_i = \{0, 1, \dots, m_i\}$ (so $|A_i| = m_i + 1$); and (ii) a payoff function $u_i: \prod_j A_j \to \mathbb{R}$, which determines the player's reward $u_i(\alpha)$ at a given action profile $\alpha = (\alpha_1, \dots, \alpha_N)$. Collectively, we will write $\mathcal{A} = \prod_i A_i$ for the game's action space and $\Gamma \equiv \Gamma(\mathcal{N}, \mathcal{A}, u)$ for the game with primitives as above.

During play, players may randomize their choices by playing mixed strategies, i.e., probability distributions $x_i \in \mathcal{X}_i := \Delta(\mathcal{A}_i)$ over $\mathcal{A}_i$. In this case, we will write $x_{i\alpha_i}$ for the probability with which player $i \in \mathcal{N}$ selects $\alpha_i \in \mathcal{A}_i$ under $x_i$, and we will identify $\alpha_i \in \mathcal{A}_i$ with the mixed strategy that assigns all weight to $\alpha_i$ (thus justifying the terminology “pure strategies”). Then, writing $x = (x_i)_{i \in \mathcal{N}}$ for the players' strategy profile and $\mathcal{X} = \prod_i \mathcal{X}_i$ for the game's strategy space, the players' mixed payoffs under $x \in \mathcal{X}$ will be $u_i(x) := \mathbb{E}_{\alpha \sim x}[u_i(\alpha)] = \sum_{\alpha \in \mathcal{A}} u_i(\alpha) x_\alpha$ where, in a slight abuse of notation, we write $x_\alpha = \prod_i x_{i\alpha_i}$ for the joint probability of playing $\alpha \in \mathcal{A}$ under $x$.

For notational convenience, we will also write $(x_i; x_{-i}) = (x_1, \dots, x_i, \dots, x_N)$ for the strategy profile where player $i$ plays $x_i \in \mathcal{X}_i$ against the strategy $x_{-i} \in \mathcal{X}_{-i} := \prod_{j \neq i} \mathcal{X}_j$ of all other players (and likewise for pure strategies). In this notation, each player's individual payoff field is defined as

$$v_i(x) = (u_i(\alpha_i; x_{-i}))_{\alpha_i \in A_i} \qquad (1)$$

so the mixed payoff of player $i \in \mathcal{N}$ under $x \in \mathcal{X}$ becomes

$$u_i(x) = \sum_{\alpha_i \in A_i} u_i(\alpha_i; x_{-i}) x_{i\alpha_i} = v_i(x)^\top \cdot x_i. \qquad (2)$$

In view of the above, the aggregate payoff field $v(x) = (v_1(x), \dots, v_N(x))$ collectively captures all strategic information of the game, so we will use it interchangeably as a more compact description of the game $\Gamma(\mathcal{N}, \mathcal{A}, u)$.
The most widely used solution concept in game theory is that of a *Nash equilibrium* (NE), i.e., a strategy profile $x^* \in \mathcal{X}$ which discourages unilateral deviations in the sense that

$$u_i(x^*) \geq u_i(x_i; x_{-i}^*) \quad \text{for all } x_i \in \mathcal{X}_i, i \in \mathcal{N}. \qquad (\text{NE})$$

Since a game's equilibria only depend on pairwise payoff comparisons, two games $\Gamma(\mathcal{N}, \mathcal{A}, u)$ and $\Gamma'(\mathcal{N}, \mathcal{A}, u')$ are called *strategically equivalent* – and we write $\Gamma \sim \Gamma'$ – if, for all $\alpha, \beta \in \mathcal{A}$ and all $i \in \mathcal{N}$, we have

$$u'_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i}) = u_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i}). \qquad (3)$$

Clearly, strategically equivalent games yield identical payoff comparisons per player, so they share the same set of Nash equilibria.

**2.2. A strategic decomposition of games.** One of the most important classes of normal form games is the class of potential games (PGs). First introduced by Monderer & Shapley [66], potential games enjoy several properties of interest – existence of equilibria in pure strategies, lack of best-response cycles, convergence of standard learning dynamics and algorithms, etc. Formally, a finite game $\Gamma$ is said to be a potential game if it admits a potential function $\phi: \mathcal{X} \to \mathbb{R}$ such that

$$u_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i}) = \phi(\beta_i; \alpha_{-i}) - \phi(\alpha_i; \alpha_{-i}) \qquad (\text{PG})$$

for all $\alpha, \beta \in \mathcal{A}$ and all $i \in \mathcal{N}$. Equivalently, in terms of mixed payoffs, this condition can be rewritten in differential form as

$$v(x)^{\top}(x' - x) = \partial\phi(x; x' - x) \quad \text{for all } x, x' \in \mathcal{X} \qquad (4)$$

where $\phi(x) := \sum_{\alpha} \phi(\alpha) x_{\alpha}$ denotes the mixed extension of $\phi$ to $\mathcal{X}$, and $\partial\phi(x; z) = \lim_{t \to 0^+} [\phi(x+tz) - \phi(x)]/t$ denotes the (one-sided) directional derivative of $\phi$ at $x$ along $z$.

Potential games capture strategic interactions with “aligned incentives” (as in common interest and congestion games). Dually to this, Candogan et al. [14] introduced the class of harmonic games (HGs) as those with “anti-aligned incentives”, viz.

$$\sum_{i \in \mathcal{N}} \sum_{\beta_i \in \mathcal{A}_i} [u_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i})] = 0 \qquad (\text{HG})$$

for all $\alpha \in \mathcal{A}$, meaning that the net incentive to deviate toward and away from any pure strategy profile is zero. In contrast to potential games, harmonic games generically do not admit pure equilibria and they possess non-terminating best-response paths, so they can be seen as “orthogonal” to potential games.

This observation was made precise by Candogan et al. [14] who showed that any finite game admits the strategic decomposition

$$\Gamma = \Gamma_{\text{pot}} + \Gamma_{\text{harm}} \qquad (5)$$

where $\Gamma_{\text{pot}}$ is potential and $\Gamma_{\text{harm}}$ is harmonic.<fnref n="4" /> This decomposition is achieved by representing $\Gamma$ as a weighted preference graph, endowing said graph with a specific, Euclidean-like structure, and using the combinatorial Helmholtz decomposition theorem [43] to obtain (5). In general, this decomposition is only unique up to strategic equivalence: more precisely, if $\Gamma$ admits the alternative decomposition $\Gamma = \Gamma'_{\text{pot}} + \Gamma'_{\text{harm}}$ with $\Gamma'_{\text{pot}}$ potential and $\Gamma'_{\text{harm}}$ harmonic, then $\Gamma'_{\text{pot}}$ is strategically equivalent to $\Gamma_{\text{pot}}$ and $\Gamma'_{\text{harm}}$ to $\Gamma_{\text{harm}}$. We will return to this decomposition later.

<footnote n="4">⁴The notation $\Gamma + \Gamma'$ for two games $\Gamma \equiv \Gamma(\mathcal{N}, \mathcal{A}, u)$ and $\Gamma' \equiv \Gamma'(\mathcal{N}, \mathcal{A}, u')$ denotes the game with the same player/action structure as $\Gamma$ and $\Gamma'$, and payoff functions $u_i + u'_i$ for all $i \in \mathcal{N}$.</footnote>
### 3. LEARNING VIA EXPONENTIAL WEIGHTS

Throughout our paper, we will focus on dynamic learning processes where the players seek to myopically improve their individual payoffs over time. A crucial requirement in this regard is the minimization of the players' regret, that is, the difference between a player's cumulative payoff and the player's best strategy in hindsight. Formally, assuming that play evolves in continuous time, the regret of a player $i \in \mathcal{N}$ relative to a sequence of play $x(t) \in \mathcal{X}$, $t \ge 0$, is defined as

$$ \mathrm{Reg}_i(T) = \max_{p_i \in \mathcal{X}_i} \int_0^T [u_i(p_i; x_{-i}(t)) - u_i(x(t))] dt \quad (6) $$

and we say that player $i$ has no regret if $\mathrm{Reg}_i(T) = o(T)$.

The archetypal method for attaining no regret is the so-called exponential/multiplicative weights (EW) update scheme, whereby an action is played with probability that is exponentially proportional to its cumulative payoff. This simple stimulus-response model goes back to Vovk [83], Littlestone & Warmuth [58] and Auer et al. [7], and, in our setting, it boils down to the dynamics

$$ y_i(t) = y_i(0) + \int_0^t v_i(x(t)) dt \quad x_i(t) = \mathrm{LC}_i(y_i(t)) \quad (\mathrm{EW}) $$

where $\mathrm{LC}_i: \mathbb{R}^{A_i} \to \mathcal{X}_i$ denotes the *logit choice map*

$$ \mathrm{LC}_i(y_i) = \frac{(\exp(y_{i\alpha_i}))_{\alpha_i \in \mathcal{A}_i}}{\sum_{\alpha_i \in \mathcal{A}_i} \exp(y_{i\alpha_i})}. \quad (7) $$

As was first shown by [48, 79], the dynamics (EW) enjoy a *constant*, $O(1)$ regret bound, namely

$$ \mathrm{Reg}_i(T) \le \log |\mathcal{A}_i|. \quad (8) $$

Owing to this remarkable regret guarantee, (EW) and its variants have become the “gold standard” for no-regret learning; for an introduction to the vast corpus of literature surrounding the topic, we refer the reader to [6, 52, 76].

One last important property of (EW) is that, by a standard calculation, the evolution of the players' mixed strategies $x_i \in \mathcal{X}_i$ under (EW) follows the *replicator dynamics* of Taylor & Jonker [81], viz.

$$ \dot{x}_{i\alpha_i} = x_{i\alpha_i}[u_i(\alpha_i; x_{-i}) - u_i(x)] \quad (\mathrm{RD}) $$

The replicator dynamics (RD) comprise the cornerstone of evolutionary game theory and, as such, their rationality properties have been the subject of intense study in the literature, cf. [37, 74, 86] and references therein. For all these reasons, the dynamics (EW)/(RD) will be our main focus in the sequel.

### 4. THE GEOMETRY OF EXPONENTIAL WEIGHTS

We now turn to our overarching objective, that is, to identify in which classes of games we can expect the dynamics of exponential/multiplicative weights to converge, and in which classes we cannot. Our main tool for this will be *Helmholtz's theorem*, a simpler variant of the *Hodge decomposition theorem*, itself one of the most foundational results in differential geometry [11, 24, 34].

To set the stage for the analysis to come, we begin by presenting the original Helmholtz decomposition of vector fields in the Euclidean setting of $\mathbb{R}^n$. Subsequently, we develop the geometric background needed to define and describe the class of *incompressible games* later in this section.
4.1. **The Helmholtz decomposition.** Consider the dynamics

$$ \dot{x} = F(x) \qquad (\text{Dyn}) $$

induced by some sufficiently smooth vector field $F: \mathbb{R}^n \to \mathbb{R}^n$ on $\mathbb{R}^n$. Helmholtz's theorem states that, if $F$ decays at infinity as $\|F(x)\| = o(\|x\|^{-2})$, it can be resolved as

$$ F(x) = \nabla \phi(x) + B(x) \qquad (9) $$

where $\phi: \mathbb{R}^n \to \mathbb{R}$ is a scalar potential for $F$ and the vector field $B: \mathbb{R}^n \to \mathbb{R}^n$ is incompressible, i.e., it has vanishing divergence:

$$ \nabla \cdot B(x) := \sum_{a=1}^{n} \partial B_a / \partial x_a = 0 \quad \text{for all } x \in \mathbb{R}^n. \qquad (10) $$

The decomposition (9) is known as the *Helmholtz decomposition* of $F$, and it is particularly important from a dynamical standpoint because its two components exhibit “orthogonal” behaviors in terms of convergence. More precisely, by standard Lyapunov arguments, the flow $\dot{x} = \nabla\phi(x)$ of the gradient component of $F$ generically converges to the critical set of $\phi$ [46]. On the other hand, Liouville’s theorem shows that the flow $\dot{x} = B(x)$ of the incompressible component of $F$ is volume-preserving,<fnref n="5" /> so it does not admit any stable attractors (asymptotically stable points or limit cycles). In this sense, the potential component of $F$ represents the convergent part of (Dyn), while the incompressible component encapsulates the non-convergent part thereof.

In view of the above, a natural idea to characterize convergent and non-convergent behaviors under (RD) would be to apply Helmholtz’s theorem to the vector field

$$ \begin{aligned} v_{i\alpha_i}^{\sharp}(x) &:= x_{i\alpha_i}[u_i(\alpha_i; x_{-i}) - u_i(x)] \\ &= x_{i\alpha_i} \left[ v_{i\alpha_i}(x) - \sum_{\beta_i \in A_i} x_{i\beta_i} v_{i\beta_i}(x) \right] \end{aligned} \qquad (11) $$

of (RD) that describes the evolution of the players’ mixed strategies under (EW). Unfortunately however, a direct decomposition of $v^\sharp$ into a potential and incompressible component – in the sense of Helmholtz’s theorem – is not well-aligned with the properties of the underlying game.

To see this, consider the single-player game with actions “A” and “B” and payoffs $u(\mathbf{A}) = 0$ and $u(\mathbf{B}) = 1$. Since there is only one player, the game admits the potential function $\phi(x) = u(x) = 0 \cdot x_{\mathbf{A}} + 1 \cdot x_{\mathbf{B}} = x_{\mathbf{B}}$, so it is a potential one. However, the replicator dynamics for this toy example are

$$ \begin{aligned} \dot{x}_{\mathbf{A}} &= v_{\mathbf{A}}^{\sharp}(x) \equiv x_{\mathbf{A}}[0 - u(x)] = -x_{\mathbf{A}}x_{\mathbf{B}} \\ \dot{x}_{\mathbf{B}} &= v_{\mathbf{B}}^{\sharp}(x) \equiv x_{\mathbf{B}}[1 - u(x)] = x_{\mathbf{B}} - x_{\mathbf{B}}^2 \end{aligned} \qquad (12) $$

and a simple check shows that $\partial_{\mathbf{B}}v_{\mathbf{A}}^\sharp = -x_{\mathbf{A}} \neq 0 = \partial_{\mathbf{A}}v_{\mathbf{B}}^\sharp$. By a routine application of Poincaré’s lemma, this further shows that $v^\sharp(x)$ is not the gradient of a potential function in the sense of (9). As a result, the game is not a potential one in the sense of Helmholtz’s theorem.

The above shows that the property of (RD) being a potential system in the sense of Helmholtz (which is more relevant from a dynamical standpoint) is not aligned with the property of admitting a potential in the sense of Monderer & Shapley [66] (which is more relevant from a game-theoretic standpoint). In view of this, our goal in the sequel will be to bridge this gap by means of an alternate decomposition in which the discrepancy between “strategically potential” and “dynamically potential” games disappears.

<footnote n="5">⁵Applications of Liouville’s theorem [5] in the context of game dynamics go back at least to Amann & Hofbauer [3], Hofbauer & Sigmund [37] and Weibull [86, pp. 175-227].</footnote>
<figure><img src="image_2.png" /><figcaption>**Figure 1:** Unit balls on the orthant and the simplex under the Shahshahani metric (left and right respectively). Notice how the Shahshahani metric distorts distances near the boundary and flattens the balls along the axis that they are closest to.</figcaption></figure>

## 4.2. The geometry of the replicator dynamics.
The starting point of our analysis is the observation that, under (RD), players track the direction of steepest individual payoff ascent; however, this ascent is not defined relative to the standard Euclidean geometry of $\mathbb{R}^n$ (which underlies Helmholtz's theorem), but relative to a non-Euclidean structure known as the Shahshahani metric.

To make this precise, we begin by introducing the notion of a *Riemannian metric*, a fundamental geometric concept which generalizes the ordinary Euclidean scalar product between vectors. Formally, a *Riemannian metric* on an open set $\mathcal{U}$ of $\mathbb{R}^n$ is a smooth assignment of an *inner product* to each $x \in \mathcal{U}$, i.e., a family of bilinear pairings $\langle \cdot, \cdot \rangle_x$, $x \in \mathcal{U}$, that satisfies the following requirements for all $z, z' \in \mathbb{R}^n$ and all $x \in \mathcal{U}$:

(1) Symmetry: $\langle z, z' \rangle_x = \langle z', z \rangle_x$.

(2) Positive-definiteness: $\langle z, z \rangle_x \ge 0$ with equality iff $z = 0$.

This definition can be made more concrete in the standard frame $\{e_a\}_{a=1}^n$ of $\mathbb{R}^n$ by defining the *metric tensor* of $\langle \cdot, \cdot \rangle_x$ as the matrix $g(x) \in \mathbb{R}^{n \times n}$ with entries

$$g_{ab}(x) = \langle e_a, e_b \rangle_x \quad \text{for } a, b = 1, \dots, n. \qquad (13)$$

The Shahshahani metric [75] on the positive orthant $\mathbb{R}_{++}^n$ of $\mathbb{R}^n$ is then defined as

$$g_{ab}(x) = \delta_{ab}/x_a \quad \text{for all } x \in \mathbb{R}_{++}^n \qquad (14)$$

where $\delta_{ab}$ denotes the standard Kronecker delta.

Importantly, the Shahshahani unit spheres $S_x := \{z \in \mathbb{R}^n : \langle z, z \rangle_x = 1\}$ at $x$ become increasingly flattened along the $x_a$-axis as $x_a \to 0$ (for an illustration, Fig. 1 below). Because of this distortion, the notion of a “gradient” and the “direction of steepest ascent” must both be redefined to account for the fact that all displacements of interest take place in the (open) unit simplex $\Delta^\circ = \{x \in \mathbb{R}_{++}^n : \sum_a x_a = 1\}$ of $\mathbb{R}^n$.

To do so, we proceed as follows: Given a differentiable function $f: \mathbb{R}_{++}^n \to \mathbb{R}$, we define the *its Shahshahani gradient along* $\Delta^\circ$ as the vector field $\text{grad } f(x)$ which is (a) tangent to $\Delta^\circ$; and (b) satisfies the defining relation

$$\langle \text{grad } f(x), z \rangle_x = \partial f(x; z) \qquad (15)$$

for all $x \in \Delta^\circ$ and all $z$ that are tangent to $\Delta^\circ$ (i.e., $\sum_a z_a = 0$ in the standard basis of $\mathbb{R}^n$). This relation clearly mirrors the corresponding Euclidean definition $\nabla f(x)^\top \cdot z = \partial f(x; z)$,
and as we show in Appendix A, it can be equivalently characterized as the direction of “steepest ascent”, namely

$$ \mathrm{grad} f(x) \propto \arg \max \{ \partial f(x; z) : z \in \mathbb{S}_x, \sum_a z_a = 0 \}. \quad (16) $$

In other words, grad $f(x)$ points in the direction that maximizes the rate of increase of $f$ at $x$ among all vectors that are tangent to $\Delta^\circ$ and have unit Shahshahani norm.

Now, to obtain an explicit expression for grad $f(x)$ in the standard basis of $\mathbb{R}^n$, note that (15) gives

$$ \sum_{a=1}^{n} \frac{[\mathrm{grad} f(x)]_a z_a}{x_a} = \sum_{a=1}^{n} \frac{\partial f}{\partial x_a} z_a \quad (17) $$

for all $z \in \mathbb{R}^n$ such that $\sum_a z_a = 0$. Then, as we show in Appendix C, solving this equation yields the expression

$$ [\mathrm{grad} f(x)]_a = x_a \left[ \frac{\partial f}{\partial x_a} - \sum_{b=1}^{n} x_b \frac{\partial f}{\partial x_b} \right]. \quad (18) $$

This last expression is strongly reminiscent of the vector field $v^\sharp$ defining (RD), a link which we make precise below.

Now, to return to a game-theoretic context, let $\mathcal{X}_i^\circ$ denote the relative interior of the mixed strategy space $\mathcal{X}_i \equiv \Delta(\mathcal{A}_i)$, and endow $\mathbb{R}_{++}^{\mathcal{A}_i}$ with the Shahshahani metric as above. We then define the individual payoff gradient of player $i \in \mathcal{N}$ as the vector field $\mathrm{grad}_i u_i$ which is (a) tangent to $\mathcal{X}_i^\circ$; and (b) satisfies the defining relation

$$ \langle \mathrm{grad}_i u_i(x), z_i \rangle = \partial u_i(x; z_i) \quad (19) $$

for all $z_i \in \mathbb{R}^{\mathcal{A}_i}$ that are tangent to $\mathcal{X}_i^\circ$ at $x_i$ (that is, $\sum_{\alpha_i \in \mathcal{A}_i} z_{i\alpha_i} = 0$). Then, by invoking the explicit expression (18) and observing that $\partial u_i / \partial x_{i\alpha_i} = u_i(\alpha_i; x_{-i})$, we finally obtain the following geometric characterization of the replicator dynamics.

**Proposition 1.** Under the Shahshahani metric, (RD) is equivalent to the steepest individual payoff ascent dynamics

$$ \dot{x}_i = \mathrm{grad}_i u_i(x) \quad (20) $$

i.e., $v_i^\sharp(x) = \mathrm{grad}_i u_i(x)$ for all $i \in \mathcal{N}$.

A version of this result appears without proof in [51]; for completeness, we defer the details of the proof of Proposition 1 to Appendix C. What is more important for our purposes is that, as we show in Appendix C.3, if the game admits a potential in the sense of (PG), combining Proposition 1 and Eqs. (4) and (15) shows that (RD) is a Shahshahani potential system, that is, $\dot{x} = \mathrm{grad} \phi$.

As far as we are aware, the closest result to Proposition 1 in the literature is Kimura's maximum principle [47] which states that, in potential games, (RD) is a Shahshahani gradient system – thus lifting the discrepancy between the “dynamic” and “strategic” notions of potential that arose before. Proposition 1 provides a broad generalization of this principle to the effect that, in any game, players following (EW)/(RD) track the direction of steepest unilateral payoff ascent, provided that displacements are measured relative to the Shahshahani metric.

**4.3. Incompressible games.** Going back to the Helmholtz decomposition (9), we see that it involves two Euclidean differential operators, the gradient $\nabla \phi$ and the divergence $\nabla \cdot B$. Eq. (15) shows how to redefine gradients relative to the Shahshahani metric, but the corresponding construction for the divergence is more intricate. The reason for this is that (RD) has an inert degree of freedom along $(1, \dots, 1)$, so the standard definition of the divergence on the
ambient space of the simplex is not appropriate [25, Chap. 6]. To circumvent this, we will introduce a more parsimonious representation of (RD) which has no redundant directions; we do this first in the case of a single player with action set $\mathcal{A} = \{0, 1, \dots, m\}$, and only reinstate the player index $i \in \mathcal{N}$ toward the end of this section.

To proceed, consider the coordinate transformation

$$ \pi_0(x_0, x_1, \dots, x_m) = (x_1, \dots, x_m) \qquad (21) $$

which maps the standard unit simplex of $\mathbb{R}^{m+1}$ to the “corner of cube”

$$ \mathcal{C} = \{ \tilde{x} \in \mathbb{R}_+^m : \sum_{\mu=1}^m \tilde{x}_\mu \le 1 \} \qquad (22) $$

of $\mathbb{R}^m$ by eliminating $x_0$ (i.e., by replacing the constraint “summing to 1” with “summing to at most 1”).<fnref n="6" /> Then, for all $\mu = 1, \dots, m$, the dynamics (RD) become

$$ \begin{aligned} \frac{d\tilde{x}_{\mu}}{dt} &= \dot{x}_{\mu} = x_{\mu} \left[ v_{\mu}(x) - \sum_{\alpha=0}^{m} x_{\alpha} v_{\alpha}(x) \right] \\ &= \tilde{x}_{\mu} \left[ \tilde{v}_{\mu}(\tilde{x}) - \sum_{\nu=1}^{m} \tilde{x}_{\nu} \tilde{v}_{\nu}(\tilde{x}) \right] \end{aligned} \qquad (\text{RD}_0) $$

where, in obvious notation, we set

$$ \tilde{v}_{\mu}(\tilde{x}) = v_{\mu}(x) - v_{0}(x) \quad \text{for all } \mu = 1, \dots, m. \qquad (23) $$

Seeing as the dynamics evolve in an open set of $\mathbb{R}^m$ (as opposed to a hyperplane of $\mathbb{R}^{m+1}$), there is no longer any redundancy in the dynamics' degrees of freedom. In view of this, we will need to “push forward” the Shahshahani metric from $\mathbb{R}^{m+1}$ to $\mathbb{R}^m$ (or, more precisely, the positive orthants thereof) in a way that is compatible with $\pi_0$.

To do so, we begin by noting that the preimage of the standard frame $\{\tilde{e}_{\mu}\}_{\mu=1}^m$ of $\mathbb{R}^m$ restricted to the tangent space $\mathcal{Z}$ of $\Delta$ in $\mathbb{R}^{m+1}$ is

$$ \pi_0^*(\tilde{e}_{\mu}) := e_{\mu} - e_0 \quad \text{for all } \mu = 1, \dots, m. \qquad (24) $$

Accordingly, as we explain in more detail in Appendix B, the metric transported in this way to the interior $\mathcal{C}^\circ$ of $\mathcal{C}$ will be given by the metric tensor

$$ \tilde{g}_{\mu\nu}(\tilde{x}) = \langle \tilde{e}_{\mu}, \tilde{e}_{\nu} \rangle_{\tilde{x}} = \langle e_{\mu} - e_0, e_{\nu} - e_0 \rangle_x = \frac{\delta_{\mu\nu}}{x_{\mu}} + \frac{1}{x_0} \qquad (25) $$

for all $\mu, \nu = 1, \dots, m$ and all $\tilde{x} \in \mathcal{C}^\circ$.

We now have all the ingredients required to define the Shahshahani divergence operator on the interior $\mathcal{C}^\circ$ of $\mathcal{C}$. Since $\mathcal{C}^\circ$ is an open subset of $\mathbb{R}^m$ (which was not the case for the relative interior $\Delta^\circ$ of $\Delta$ in $\mathbb{R}^{m+1}$), the Shahshahani divergence of a vector field $\tilde{F}: \mathcal{C}^\circ \to \mathbb{R}^m$ may be defined by the Riemannian expression<fnref n="7" />

$$ \mathrm{div} \, \tilde{F}(\tilde{x}) := \frac{1}{\sqrt{\det \tilde{g}(\tilde{x})}} \sum_{\mu=1}^{m} \frac{\partial}{\partial \tilde{x}_{\mu}} \left( \sqrt{\det \tilde{g}(\tilde{x})} \tilde{F}_{\mu}(\tilde{x}) \right) \qquad (26) $$

<footnote n="6">⁶This coordinate transformation goes back at least to Ritzberger & Vogelsberger [72]; see also Weibull [86, p.227].</footnote>

<footnote n="7">⁷The divergence on a Riemannian manifold is a generalization of the divergence operator from vector calculus to curved spaces; for details, see Appendix A.3.</footnote>
with $\tilde{g}$ given by (25). In particular, when applied to each player's individual steepest ascent payoff field $v_i^\#(x) = \text{grad}_i u_i(x)$, the coordinate expression (26) yields

$$ \text{div}_i v_i^\#(\tilde{x}) = \frac{1}{\sqrt{\det \tilde{g}_i(\tilde{x}_i)}} \sum_{\mu_i=1}^{m_i} \frac{\partial}{\partial \tilde{x}_{i\mu_i}} \left( \sqrt{\det \tilde{g}_i(\tilde{x}_i)} v_{i\mu_i}^\#(\tilde{x}) \right) \quad (27) $$

where, in view of Eqs. (11) and (23), and in a slight – but suggestive – abuse of notation, we have set

$$ v_{i\mu_i}^\#(\tilde{x}) := \tilde{x}_{i\mu_i} \left[ \tilde{v}_{i\mu_i}(\tilde{x}) - \sum_{\nu_i=1}^{m_i} \tilde{x}_{i\nu_i} \tilde{v}_{i\nu_i}(\tilde{x}) \right] \quad (28) $$

with $\tilde{v}_{i\mu_i}(\tilde{x}) = v_{i\mu_i}(x) - v_{i,0}(x)$ defined as in (23) for all $i \in \mathcal{N}$ and all $\mu_i = 1, \dots, m_i$.

With all this in hand, we are finally in a position to define incompressible games:

**Definition 1.** A finite game $\Gamma \equiv \Gamma(\mathcal{N}, \mathcal{A}, u)$ will be called *incompressible* relative to the Shahshahani metric when

$$ \text{div} v^\#(\tilde{x}) := \sum_{i \in \mathcal{N}} \text{div}_i v_i^\#(\tilde{x}) = 0. \quad (29) $$

We should stress here that Definition 1 is motivated by purely geometric considerations, and provides a “complement” to the class of potential games in a geometric context. In this regard, our goal in the sequel will be to use this definition as the basis for a Helmholtz-like decomposition relative to the Shahshahani metric and, in so doing, we understand the dynamic and game-theoretic implications of such a decomposition. We carry this out in the next section.

# 5. ANALYSIS AND RESULTS

**5.1. A geometric decomposition of games.** To recap, our analysis so far has highlighted the relation between the Shahshahani metric and learning under (EW) / (RD). On that account, the first question that we seek to address is whether Helmholtz's theorem can be extended to the present context, and whether such a decomposition resolves the dynamic/strategic disconnect that underlies the “vanilla” Helmholtz decomposition. Our first result below answers this question in the positive.

**Theorem 1.** Every finite game $\Gamma$ can be decomposed as

$$ \Gamma = \Gamma_{\text{pot}} + \Gamma_{\text{inc}} \quad (30) $$

where $\Gamma_{\text{pot}}$ is potential and $\Gamma_{\text{inc}}$ is incompressible. In particular, at the vector field level, we have

$$ v^\# = \text{grad} \phi + B \quad (31) $$

where $\phi$ is a potential for $\Gamma_{\text{pot}}$ and $B$ is incompressible in the sense of (29).

Theorem 1 comes as a consequence of Theorem 2, which relates harmonic to incompressible games, and which we state later in this section. Because the calculations are fairly lengthy and involved, we defer all relevant details to Appendix D, and we focus here on the game-theoretic implications of Theorem 1.

A first conclusion that can be drawn from Theorem 1 is that the decomposition (30) points two concrete building blocks of the space of games: potential games and incompressible games. With regard to the potential component, Theorem 1 resolves the dynamic-strategic disconnect that arose when we applied the standard Helmholtz decomposition to (RD): the component $\Gamma_{\text{pot}}$ of (30) also admits a Shahshahani potential in the sense of (15), so there is no longer any mismatch between the two viewpoints.
The role of the incompressible component is less transparent, but it is clarified by the striking equivalence below:

**Theorem 2.** A finite game is harmonic if and only if it is incompressible. In particular, up to strategic equivalence, the decompositions (5) and (30) coincide.

This result hinges on a series of geometric calculations involving the explicit coordinate expression of the Shahshahani divergence operator (26); we defer this calculation to Appendix D, where we discuss all relevant details. What is more important for our purposes is that Theorem 2 provides a fairly unexpected – and operationally significant – interpretation of incompressible games: even though incompressible games were introduced solely based on their relation with the Shahshahani metric – and, through that, to the learning dynamics (EW) – they are characterized by the same “negative externalities” property (HG) which states that the net incentive to deviate toward and/or away from any pure strategy profile is zero. As we shall see below, this strategic “conservation of incentives” is mirrored in the evolution of learning in incompressible / harmonic games under (EW).

**5.2. Dynamic considerations.** We now turn to our paper’s second major objective: understanding the behavior of learning under (EW) in the class of harmonic/incompressible games.

The first thing to note here is that, as in the Euclidean case, incompressibility is inherently tied to volume preservation. However, in contrast to the Euclidean case, volumes must now be measured relative to the Shahshahani metric. The relevant device in our Riemannian setting is the notion of the *Shahshahani volume form*, defined on the (open) unit simplex $\Delta^\circ$ of $\mathbb{R}^{m+1}$ as

$$ \mathrm{vol}(\mathcal{U}) = \int_{\pi_0(\mathcal{U})} \sqrt{\det \tilde{g}(\tilde{x})} \, d\tilde{x}_1 \cdots d\tilde{x}_m \quad (32) $$

where $\mathcal{U}$ is an open subset of $\Delta^\circ$ and $\tilde{g}(\tilde{x})$ is the coordinate representation of the Shahshahani metric in the “corner-of-cube” coordinates $\tilde{x} = \pi_0(x)$ of Section 4.3.

As we discuss in Appendix A, the Riemannian version of Liouville’s theorem states that, if the vector field $v^\#(x)$ is incompressible, the dynamics $\dot{x} = v^\#(x)$ are *volume-preserving* in the sense that

$$ \mathrm{vol}(\mathcal{U}_t) = \mathrm{vol}(\mathcal{U}_0) \quad (33) $$

where $\mathcal{U}_0 \subseteq \Delta^\circ$ is an open set of initial conditions and $\mathcal{U}_t$ is the image of $\mathcal{U}_0$ after following the flow of $v^\#$ for time $t$. We thus get the following result:

**Proposition 2.** If $\Gamma$ is incompressible, (RD) is *volume-preserving under the Shahshahani volume form* (32).

This result (which we prove and discuss in detail in Appendix D) suggests that (EW) is unlikely to converge in the class of incompressible – and therefore *harmonic* – games. In particular, Proposition 2 should be contrasted to a result of Flokas et al. [26], who showed that (EW) is volume-preserving for every game relative to the Euclidean volume form on the “dual” space of the score variables $y_i$. We stress here however that the volume-preservation result of [26] applies to every game, a property which plays a crucial role in showing that any asymptotically stable state of (EW) / (RD) must be a pure strategy profile (in fact, a strict Nash equilibrium) [26, 86]. By contrast, Proposition 2 does not apply to all games and essentially, is an equivalence: if a game is not incompressible, the Riemannian version of Liouville’s formula (which we state formally in Appendix A) shows that (RD) is expanding (resp. contracting) in areas of positive (resp. negative) divergence, and is not volume-preserving overall.
<figure><img src="image_3.png" /><figcaption>**Figure 2:** The evolution of (EW) in three randomly generated harmonic games with random initial conditions (left: 2 × 2; middle: 3 × 2; right: 2 × 2 × 2). In all cases, the dynamics are Poincaré recurrent and cycle the game’s Nash equilibria (depicted in red). None of these games is zero-sum; the left and right games are strategically equivalent to a ZSG, while the middle is not – cf. Remark D.2. For visual clarity, we have highlighted a randomly selected orbit in each case, and the arrows indicate the direction in which orbits are traversed. In Appendix E.2 we include a series of trajectories of (EW)/(RD) for a convex combination of potential and a harmonic game, showing how Poincaré recurrence breaks down as the relative magnitude of the potential component increases.</figcaption></figure>

In this sense, the Shahshahani volume form is more descriptive, and allows for a finer understanding of the flow of (RD). In fact, as we show in Appendix D, incompressibility under the Shahshahani metric induces a further striking structural property:

**Theorem 3.** If $\Gamma$ is incompressible, the induced dynamics (EW) / (RD) admit a constant of motion. Specifically, there exists a function $E: \mathcal{X}^\circ \to \mathbb{R}$ such that $E(x(t)) = E(x(0))$ for every initial condition $x(0) \in \mathcal{X}^\circ$.

This result is surprising because it ties together two drastically different – and, to a certain extent, distinctly independent – properties: volume preservation on the one hand, and the existence of conserved quantities on the other. In the context of learning under (EW) / (RD), the existence of constants of motion has only been established for very special classes of games, namely two-player zero-sum games with an interior equilibrium [37, p. 75], positive affine transformations or polymatrix/network versions of the above [63, 68, 69], and certain other games with a min-max structure. In this regard, Theorem 3 serves to identify a much wider class of N-player games, not necessarily with a min-max structure, where the no-regret dynamics (EW) are conservative.

A concrete consequence of the above is that, in view of Theorem 3, the trajectories of (EW) in incompressible games are constrained to move on the level sets of a certain function. In fact, as we show in Appendix D.3, this function is convex, so its level sets are concentric topological spheres (as boundaries of convex sets, namely the function’s sublevel sets). In turn, this means that the phase space of the dynamics foliates into an ensemble of spheres, each of which constrains the evolution of (EW). In a certain sense, this is the closest that one can get to proving periodic behavior in general dynamics – and, in fact, by the Poincaré-Bendixson theorem, it is easy to see that the dynamics are periodic when (RD) has effective dimension 2 or 3 (so in the case of 2 × 2, 2 × 3 and 2 × 2 × 2 games, cf. Fig. 2).

This brings us to our final result on the long-run behavior of the dynamics (EW) / (RD): Even when periodicity fails, it only fails by an arbitrarily small amount.
**Theorem 4.** If $\Gamma$ is harmonic, the dynamics (EW)/(RD) are Poincaré recurrent. Specifically, for almost every initialization $x(0) \in \mathcal{X}^\circ$, the induced trajectory $x(t)$ returns arbitrarily close to $x(0)$ infinitely often: there exists an increasing sequence of times $t_n \uparrow \infty$ such that $x(t_n) \to x(0)$.

Theorem 4 (which we prove in Appendix D) shows that the behavior of (EW)/(RD) in harmonic games is orthogonal to their behavior in potential games: in the latter, every orbit eventually converges to Nash equilibrium; in the former, the system's orbits cycle back in an almost-periodic manner to (a neighborhood of) their starting points infinitely often (cf. Fig. 2). This provides a partial negative answer to an open question of Candogan et al. [14] regarding the convergence of the replicator dynamics in harmonic games, and shows that potential and harmonic games are orthogonal to each other also in the sense of learning.

## 6. CONCLUDING REMARKS

We find the equivalence between harmonic and incompressible games particularly intriguing as it links four otherwise distinct and independent notions: (i) a standard class of game-theoretic learning schemes (which lead to no-regret, so players become more efficient over time); (ii) the existence of anti-aligned incentives (encoded by the notion of a harmonic game); and, through the surprising property of volume preservation, (iii) the existence of a constant of motion and (iv) Poincaré recurrence (the prototypical manifestation of non-convergent, quasi-periodic behavior). Theorem 4 in particular shows that the interplay between these notions is significantly more intricate than what the strong no-regret properties of (EW) might suggest: in harmonic games, the players' long-run behavior under the dynamics of exponential/multiplicative weights is Poincaré recurrent and fails to converge, even though the empirical distribution of play converges to the game's set of coarse correlated equilibria.

Under this light, the decomposition of a game into a potential and a harmonic/incompressible component is strongly reminiscent of Conley's decomposition theorem [21] which states that any dynamical system can be decomposed into an attracting, convergent part, and a chain-recurrent part. Of course, Conley's theorem concerns a decomposition of the game's state space, not the flow itself; nonetheless, this alignment between the dynamic and strategic components of a game hints at a much deeper connection which opens up many directions for further research.

One such direction concerns the general class of follow-the-regularized-leader (FTRL) dynamics [76, 77], of which (EW)/(RD) is a special case: concretely, we conjecture here that Poincaré recurrence holds for harmonic games in the *entire* class of FTRL dynamics. While close in spirit, the techniques presented in this paper do not extend to the class of FTRL dynamics because the analogue of Theorem 2 fails to hold for dynamics other than (EW)/(RD), so there is no longer a clear link between incompressibility and harmonicity. We leave this question open for the future.

## ACKNOWLEDGMENTS

This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA-0003), the "Investissements d'avenir" program (ANR-15-IDEX-02), the LabEx PERSYVAL (ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.
APPENDIX A. BASIC FACTS AND DEFINITIONS FROM RIEMANNIAN GEOMETRY

Riemannian geometry, a cornerstone of differential geometry, provides a powerful framework for analyzing spaces endowed with a metric structure. At its core lies the notion of a *Riemannian manifold*, a smooth manifold endowed with a smoothly varying inner product structure on its tangent spaces. This structure allows for the definition of gradient directions of smooth functions, lengths of curves, angles between tangent vectors, and various notions of curvature, enabling the study and analysis of geometric properties of the manifold, and of dynamical systems defined thereon. In what follows, we provide a quick dictionary of some of the basic notions that we use throughout our paper.

A.1. **Riemannian manifolds.** A smooth manifold $\mathcal{M}$ of dimension $n$ is a Hausdorff, second countable topological space equipped with a collection of *local charts* $(U_\alpha, \pi_\alpha)$, where each $U_\alpha$ is an open subset of $\mathcal{M}$ and each $\pi_\alpha: U_\alpha \to \mathbb{R}^n$ is a homeomorphism onto an open subset of $\mathbb{R}^n$.<fnref n="8" /> Points in the co-domain of each local chart are called *local coordinates*.

The tangent space $T_x \mathcal{M}$ of a smooth manifold $\mathcal{M}$ at a point $x \in \mathcal{M}$ is the vector space of all derivations on the space of smooth functions defined on an open neighborhood of $x$; the dimension of $T_x \mathcal{M}$ is the same as the dimension of $\mathcal{M}$.

Intuitively, a smooth manifold can be thought of as a topological space that *locally* resembles $\mathbb{R}^n$; typical example of smooth manifolds include smooth surfaces in the Euclidean space. Building on this intuition, the tangent space $T_x \mathcal{M}$ of $\mathcal{M}$ can be thought of as the space of all possible “directions” or “velocities” one can move in from the point $x$ without leaving the surface. For instance, if $\mathcal{M}$ is the Earth’s surface, $T_x \mathcal{M}$ at a point $x$ would be the plane including vectors representing north, south, east, west – but not upwards.

*Remark A.1.* Another fundamental example of smooth manifold is the Euclidean space $\mathbb{R}^n$ itself, with the identity map as a chart. Its tangent space at any point $x$ is an $n$-dimensional vector space, hence isomorphic to $\mathbb{R}^n$; in the following we will identify the tangent space $T_x \mathbb{R}^n$ with $\mathbb{R}^n$ itself. ◇

A *Riemannian manifold* ($\mathcal{M}, g$) is a smooth manifold $\mathcal{M}$ together with a smoothly varying positive definite symmetric bilinear form $g_x : T_x \mathcal{M} \times T_x \mathcal{M} \to \mathbb{R}$ defined on each tangent space $T_x \mathcal{M}$ with $x \in \mathcal{M}$. This form, called the *Riemannian metric*, assigns to each pair of tangent vectors $z, z'$ at a point $x$ a real number $g_x(z, z')$, satisfying:

(1) Smoothness: The map $x \mapsto g_x$ is smooth.

(2) Positive definiteness: For all $x \in \mathcal{M}$ and $z \in T_x \mathcal{M}$, $g_x(z, z) \ge 0$ with equality iff $z = 0$.

(3) Symmetry: For all $x \in \mathcal{M}$ and $z, z' \in T_x \mathcal{M}$, $g_x(z, z') = g_x(z', z)$.

Throughout this work use equivalently the notations $g_x(z, z') \equiv \langle z, z' \rangle_x \equiv z^T \cdot g_x \cdot z$ for all $z, z' \in T_x \mathcal{M}$, where in the third expression $g_x$ is a $\dim \mathcal{M} \times \dim \mathcal{M}$-dimensional matrix and · denotes matrix multiplication.

Finally, a *vector field* $X$ on $\mathcal{M}$ is a smooth map $x \mapsto X(x) \in T_x \mathcal{M}$ that for all points $x$ on the manifold gives a vector $z = X(x)$ in the tangent space to $\mathcal{M}$ at $x$. A vector field $X$ on $\mathcal{M}$ can be written locally as a linear combination $X = \sum_{a=1}^{\dim \mathcal{M}} X^a e_a$, where $X^a: \mathcal{M} \to \mathbb{R}$ is a smooth function on the manifold and $e_a$ is a *basis vector field*, i.e., $e_a(x)$ is the $a$-th element in a basis of $T_x \mathcal{M}$, for all $x \in \mathcal{M}$ and all $a = 1, \dots, \dim \mathcal{M}$. An ordered collection $\{e_a\}_{a=1,\dots,\dim \mathcal{M}}$ of such basis vector fields is called *frame bundle*.

<footnote n="8">⁸The charts are required to satisfy also the compatibility condition that the *transition maps* $\pi_\alpha \circ \pi_\beta^{-1}: \pi_\beta(U_\alpha \cap U_\beta) \to \pi_\alpha(U_\alpha \cap U_\beta)$ are smooth whenever $U_\alpha \cap U_\beta \neq \emptyset$.</footnote>
A.2. **Riemannian gradients.** Given a Riemannian manifold $(\mathcal{M}, g)$ and a smooth function $f: \mathcal{M} \to \mathbb{R}$, a Riemannian metric allows to define a special vector field on $\mathcal{M}$:

**Definition 2.** The gradient of $f$ is the vector field grad $f$ on $\mathcal{M}$ defined by

$$ \langle \mathrm{grad} f(x), z \rangle_x = \partial f(x; z) \in \mathbb{R}, \qquad (A.1) $$

for all points $x \in \mathcal{M}$ and all tangent vectors $z \in T_x \mathcal{M}$.

The components of grad $f$ can be expressed in any local chart as follows: let $X = e_a$ be a basis vector field with $a \in \{1, \dots, \dim \mathcal{M}\}$, and denote by $[df(x)]_a := \partial f(x; e_a(x))$ the directional derivative of $f$ at $x$ in the direction of $e_a(x)$.

**Lemma A.1 (Components of gradient field).** For all $x \in \mathcal{M}$, the components of grad $f$ are given by the matrix multiplication between the inverse matrix of the metric $g^{-1}$, and the array of basis directional derivatives df:

$$ \mathrm{grad} f(x) = g^{-1}(x) df(x). \qquad (A.2) $$

*Proof.* Write $G_a(x) := [\mathrm{grad} f(x)]_a$. By symmetry of $g$,

$$ \langle \mathrm{grad} f(x), e_a(x) \rangle_x = \sum_{b,c=1}^{\dim \mathcal{M}} g_{bc}(x) G_b(x) \delta_{ac} = \sum_{b=1}^{\dim \mathcal{M}} g_{ba}(x) G_b(x) = [g(x)G(x)]_a. $$

By definition of gradient this expression is equal to $[df(x)]_a$, so we get the matrix equation $g(x)G(x) = df(x)$ for all $x \in \mathcal{M}$. Since $g(x)$ is positive-definite for all $x \in \mathcal{M}$ we can multiply from the left both sides of this equations by the inverse matrix $g^{-1}(x)$ to get (A.2). ■

*Remark A.2 (Euclidean vs. non-Euclidean gradient).* The Euclidean metric in $\mathbb{R}^n$ is represented by the identity matrix $g_{ab}(x) = \delta_{ab}$, from which the familiar result that the gradient of a function is the array of basis directional derivatives, or differential, of $f$: $\mathrm{grad} f(x) = [\partial f(x; e_a)]_{a=1}^n = df(x)$. In a non-Euclidean setting, the difference between the gradient and the differential of a function is given by the (inverse) metric tensor. ◇

Gradients give directions of maximal rate of change. Given a smooth function $f: \mathcal{M} \to \mathbb{R}$ on a Riemannian manifold $(\mathcal{M}, g)$, the gradient of $f$ at $x$ gives the direction of maximal rate of change of $f$ at $x$; we make this precise with the following lemma.

**Lemma A.2.** On a Riemannian manifold $(\mathcal{M}, g)$ let $Z_x \subset T_x \mathcal{M} := \{z \in T_x \mathcal{M} : \|z\|_x = 1\}$ be the set of directions at $x$, i.e., the set of tangent vectors at $x$ of unitary norm, where $\|z\|_x := \sqrt{\langle z, z \rangle_x}$ is the norm induced by the Riemannian inner product. Then for all smooth functions $f: \mathcal{M} \to \mathbb{R}$ and for all $x \in \mathcal{M}$,

$$ \frac{\mathrm{grad} f(x)}{\|\mathrm{grad} f(x)\|_x} = \arg \max_{z \in Z_x} \{\partial f(x; z)\}. \qquad (A.3) $$

*Proof.* By definition of gradient, $\partial f(x; z) = \langle \mathrm{grad} f(x), z \rangle_x$. By Cauchy-Schwarz inequality, we have $|\langle z, z' \rangle_x| \le \|z\|_x \|z'\|_x$ for all $z, z' \in T_x \mathcal{M}$ with equality iff $z \propto z'$, thus $\partial f(x; z)$ is maximized in the direction $z \propto \mathrm{grad} f(x)$. ■

A.3. **Riemannian divergence.** In vector calculus, the divergence is a differential operator mapping a vector field $X$ to a function:

$$ \mathrm{div} X = \sum_{a=1}^{\dim \mathcal{M}} \frac{\partial}{\partial x_a} X^a \quad [\mathrm{Euclidean}]. \qquad (A.4) $$
This operator captures how much the field is locally spreading out or converging at a given point: loosely speaking, if the divergence is positive in the neighborhood of a point, the vector field is locally spreading out (e.g., the outward-radial field $X(x, y) = (x, y)$); if it is negative, the vector field is locally converging (e.g., the inward-radial field $X(x, y) = (-x, -y)$); and if it is zero, the field is neither locally spreading out nor converging (e.g., the hyperbolic field $X(x, y) = (x, -y)$ or the spherical field $X(x, y) = (y, -x)$).

Let $\mathcal{X}$ and $\mathfrak{F}$ denote respectively the space of vector fields and smooth functions on a Riemannian manifold $(\mathcal{M}, g)$. To generalize the divergence operator to this setting one must take into account how the volume element of the metric $g$ changes from point to point, and this in turn depends on the determinant $\det g$ – cf. Eq. (A.11). With this idea in mind, we give the following generalization of the Euclidean divergence operator to a Riemannian setting [44, 53, 54].

**Definition 3.** The divergence operator div: $\mathcal{X} \to \mathfrak{F}$ on a Riemannian manifold $(\mathcal{M}, g)$ is defined by

$$ \mathrm{div} X = \frac{1}{\sqrt{D}} \sum_{a=1}^{\dim \mathcal{M}} \frac{\partial}{\partial x_a} \left( \sqrt{D} X^a \right) \quad \text{for all } X \in \mathcal{X}, \qquad (A.5) $$

where $D := \det g$. ◇

*Remark A.3.* If $(\mathcal{M}, g)$ is the standard Euclidean space equipped with the Euclidean metric then the constant term $\sqrt{D}$ is not affected by the partial derivatives and cancels out with $(\sqrt{D})^{-1}$, giving back the familiar Eq. (A.4). ◇

Note that Eq. (A.5) can be rewritten by product rule as

$$ \mathrm{div} X = \sum_{a=1}^{\dim \mathcal{M}} \left( \frac{\partial_a \sqrt{D}}{\sqrt{D}} \right) X^a + \sum_{a=1}^{\dim \mathcal{M}} \partial_a X^a, \qquad (A.6) $$

where $\partial_a$ is a shorthand for $\frac{\partial}{\partial x_a}$.

**Example A.1 (Divergence on the sphere).** The determinant of the Euclidean metric in $\mathbb{R}^3$ induced on the unit sphere in standard spherical coordinates fulfills $\sqrt{\det g} = \sin \theta$, so by Eq. (A.6) the divergence of the vector field $X(\theta, \phi) = (X^\theta, X^\phi)$ is

$$ \mathrm{div} X = \partial_\theta X^\theta + \partial_\phi X^\phi + \frac{X^\theta}{\tan \theta}. $$

In particular the divergence of a longitudinal vector field $X = (1, 0)$ is $\frac{1}{\tan \theta}$, which diverges to infinity a the north pole, is zero at the equator, and diverges to minus infinity at the south pole. This captures the fact that a small set of initial conditions starting close to the north pole and evolving along flow of $X$ quickly expands moving towards the equator; the rate of expansion decreases until the equator is crossed, after which the flow lines converge at increasingly higher rate towards the south pole.

Conversely, the divergence of a latitudinal vector field $X = (0, 1)$ is 0, capturing the fact that the volume of a small set of initial conditions remains constant along the flowlines parallel to the equator. ◇

Riemannian divergence on product manifold. In this section we show that the divergence operators on two Riemannian manifolds naturally induce a divergence operator on the product manifold.

Let $(\mathcal{M}, g_{\mathcal{M}})$ and $(\mathcal{M}', g_{\mathcal{M}'})$ be Riemannian manifolds with coordinates $x$ and $x'$ respectively, with $g_{\mathcal{M}}$ represented by the matrix $(g_{\mathcal{M}})_{ij}$ for $i, j = 1, \dots, \dim \mathcal{M}$, and $g_{\mathcal{M}'}$ represented
by the matrix $(g_{\mathcal{M}'})_{hk}$ for $h, k = 1, \dots, \dim \mathcal{M}'$. Consider the product manifold $P = \mathcal{M} \times \mathcal{M}'$ with $\dim P = \dim \mathcal{M} + \dim \mathcal{M}'$, coordinates $(x, x')$, and metric $g(x, x') := g_{\mathcal{M}}(x) + g_{\mathcal{M}'}(x')$. The matrix representing the metric $g$ is the block diagonal matrix with the matrices of $g_{\mathcal{M}}$ and $g_{\mathcal{M}'}$ on the diagonal, so $\det g = \det g_{\mathcal{M}} \det g_{\mathcal{M}'}$. In the following we denote $D := \det g = D_{\mathcal{M}} D_{\mathcal{M}'}$.

A vector field $X$ on $\mathcal{M}$ locally written as $X(x) = \sum_{i=1}^{\dim \mathcal{M}} X^i(x) e_{x_i}$ can be naturally seen as a vector field $X$ on $P$, given by $X(x, x') = \sum_{A=1}^{\dim P} X^A(x, x') e_A = \sum_{i=1}^{\dim \mathcal{M}} X^i(x) e_{x_i} + \sum_{j=1}^{\dim \mathcal{M}'} 0 e_{x'_j}$. With this identification in mind, two vector fields $X$ on $\mathcal{M}$ and $X'$ on $\mathcal{M}'$ naturally give a vector field $Z$ on $P$ by $Z(x, x') := X(x) + X'(x') = \sum_{i=1}^{\dim \mathcal{M}} X^i(x) e_{x_i} + \sum_{j=1}^{\dim \mathcal{M}'} X'^j(x') e_{x'_j}$.

**Lemma A.3** (The divergence operator does not mix coordinates). Let $X$ be a vector field on a Riemannian manifold $(\mathcal{M}, g)$ and $X'$ a vector field on a Riemannian manifold $(\mathcal{M}', g')$. Then the vector field $Z = X + X'$ on the product manifold $(P = \mathcal{M} \times \mathcal{M}', g = g_{\mathcal{M}} + g_{\mathcal{M}'})$ fulfills

$$ \mathrm{div}_g Z = \mathrm{div}_{g_{\mathcal{M}}} X + \mathrm{div}_{g_{\mathcal{M}'}} X'. \qquad (A.7) $$

*Proof.* The div operator acts linearly on vector fields [53], so

$$ \mathrm{div}_g Z = \mathrm{div}_g X + \mathrm{div}_g X' \quad \text{by linearity of div.} $$

So if we show that $\mathrm{div}_g X = \mathrm{div}_{g_{\mathcal{M}}} X$ we are done. This is true since the coordinates of the two manifolds remain decoupled under the Cartesian product operation, so they are acted upon only by derivatives of the corresponding type:

$$ \begin{aligned} \mathrm{div}_g X &= \sum_{A=1}^{\dim P} \left( \frac{\partial_A \sqrt{D}}{\sqrt{D}} \right) X^A + \sum_{A=1}^{\dim P} \partial_A X^A \\ &= \sum_{i=1}^{\dim \mathcal{M}} \left( \frac{\partial_{x_i} (\sqrt{D_{\mathcal{M}}} \sqrt{D_{\mathcal{M}'}})}{\sqrt{D_{\mathcal{M}}} \sqrt{D_{\mathcal{M}'}}} \right) X^i + \sum_{i=1}^{\dim \mathcal{M}} \partial_{x_i} X^i + \sum_{j=1}^{\dim \mathcal{M}'} 0. \end{aligned} $$

Now $\partial_{x_i} (\sqrt{D_{\mathcal{M}}} \sqrt{D_{\mathcal{M}'}}) = \partial_{x_i} (\sqrt{D_{\mathcal{M}}}) \sqrt{D_{\mathcal{M}'}}$, so the terms containing $\sqrt{D_{\mathcal{M}'}}$ simplify:

$$ \mathrm{div}_g X = \sum_{i=1}^{\dim \mathcal{M}} \left( \frac{\partial_{x_i} (\sqrt{D_{\mathcal{M}}})}{\sqrt{D_{\mathcal{M}}} \sqrt{D_{\mathcal{M}'}}} \right) X^i + \sum_{i=1}^{\dim \mathcal{M}} \partial_{x_i} X^i = \mathrm{div}_{g_{\mathcal{M}}} X. \quad \blacksquare $$

**A.4. Flows on manifolds.** We recall here a few concepts from the theory of dynamical systems on manifolds. We refer the reader to Lee [53, Ch. 9,16] for the general theory and to Flokas et al. [26] for a concise treatment in the context of no-regret learning. For a detailed account of the theory of ordinary differential equations and deterministic dynamical systems in continuous time in the context of multipopulation evolutionary dynamics we refer the reader to the excellent introduction by Weibull [86, Ch. 6], and in particular to Section 6.6 for a general discussion on the Euclidean version of Liouville's theorem, and to sections 5.2.2 and 5.8.2 for relevant applications.

Given a smooth vector field $X \in \mathcal{X}$ on a smooth manifold $\mathcal{M}$, a smooth global integral curve of $X$ is a smooth curve $\gamma: \mathbb{R} \to \mathcal{M}$ such that $\dot{\gamma}(t) = X(\gamma(t))$ for all $t \in \mathbb{R}$. The point $\gamma(0)$ is called starting point of $\gamma$. If a smooth global integral curve $\gamma$ of $X$ with starting point $x$ exists, then it is the unique maximal solution to the initial value problem

$$ \dot{\gamma} = X(\gamma), \quad \gamma(0) = x. \qquad (\mathrm{IVP}) $$
Given a smooth manifold $\mathcal{M}$, a smooth global flow on $\mathcal{M}$ is a smooth map $\theta: \mathbb{R} \times \mathcal{M} \to \mathcal{M}$ such that for all $t, s \in \mathbb{R}$ and $x \in \mathcal{M}$, $\theta(t, \theta(s, x)) = \theta(t + s, x)$ and $\theta(0, x) = x$. Given a smooth global flow, fixing $t \in \mathbb{R}$ one can define the orbit map $\theta_t: \mathcal{M} \to \mathcal{M}$ by $\theta_t(x) = \theta(t, x)$; the orbit map of a smooth global flow can be shown to be a diffeomorphism of $\mathcal{M}$ onto itself with inverse $(\theta_t)^{-1} = \theta_{-t}$. Similarly, by fixing $x \in \mathcal{M}$ one can define the curve $\theta^x: \mathbb{R} \to \mathcal{M}$ by $\theta^x(t) = \theta(t, x)$.

Given a smooth global flow $\theta$ and a smooth vector field $X \in \mathcal{X}$ on a smooth manifold $\mathcal{M}$, we say that $\theta$ is the flow of $X$ if $X(\theta^x(t)) = \dot{\theta}^x(t)$ for all $t \in \mathbb{R}$ and $x \in \mathcal{M}$. If $X$ admits a global flow, then $\theta^x: \mathbb{R} \to \mathcal{M}$ is an integral curve of $X$ with starting point $x$, hence a solution to the initial value problem (IVP) – equivalently, the orbit map $\theta_t: \mathcal{M} \to \mathcal{M}$ maps any initial condition $x \in \mathcal{M}$ to the point $\gamma(t)$, where $\gamma$ is the maximal solution to the initial value problem (IVP).

A vector field may not always admit a global flow, since it may not always be the case that every integral curve is defined for all time. The Fundamental Theorem of Flows [53, Th. 9.12] asserts that every smooth vector field on a smooth manifold determines a unique local maximal smooth flow;<fnref n="9" /> the proof is an application of the existence, uniqueness, and smoothness theorem for solutions of ordinary differential equations. For the scope of this work note that the trajectories of (RD) on $\mathcal{X}^\circ$ are defined for all $t \in \mathbb{R}$, so the replicator vector field $v^\#$ defines a smooth global flow on $\mathcal{X}^\circ$.

Next, we look at the relation between the Riemannian divergence of a vector field defined in Appendix A.3, and the volume of a set of initial conditions evolving along the flow of such vector field. We warm up in an Euclidean setting, before moving to a Riemannian one. The Euclidean Liouville's theorem. Consider a vector field $X \in \mathcal{X}$ on $\mathcal{M} = \mathbb{R}^n$ that admits a global flow $\theta: \mathbb{R} \times \mathbb{R}^n \to \mathbb{R}^n$. For any open set $\mathcal{U} \subset \mathbb{R}^n$ and any $t \in \mathbb{R}$ denote by $\mathcal{U}_t$ the image of $\mathcal{U}$ under the orbit map $\theta_t: \mathbb{R}^n \to \mathbb{R}^n$:

$$ \mathcal{U}_t := \theta_t(\mathcal{U}) = \{\theta_t(x) : x \in \mathcal{U}\} \subseteq \mathbb{R}^n. \qquad (A.8) $$

Note that $\mathcal{U}_{t=0} = \mathcal{U}$, since the orbit map $\theta_0$ is the identity map on $\mathbb{R}^n$.

A fundamental result of classical mechanics known as Liouville's theorem [5] relates the Euclidean divergence (A.4) of the vector field $X$, which is a function $\mathrm{div} X: \mathbb{R}^n \to \mathbb{R}$, with the Euclidean volume of an open set of initial conditions evolving along the flow of $X$:

**Theorem (Euclidean Liouville's theorem).** Given a smooth vector field $X$ in $\mathbb{R}^n$ and an open set $\mathcal{U} \subset \mathbb{R}^n$,

$$ \frac{d}{dt} \mathrm{vol}(\mathcal{U}_t) = \int_{\mathcal{U}_t} \mathrm{div} X dx, \qquad (A.9) $$

for all $t \in \mathbb{R}$ such that the flow of $X$ is defined.

*Proof.* See e.g., Arnold [5, Ch. 3].

<figure><img src="image_4.png" /></figure>

If a map $\phi: \mathbb{R}^n \to \mathbb{R}^n$ fulfills $\mathrm{vol}(\mathcal{U}) = \mathrm{vol}(\phi\mathcal{U})$ for all open subsets $\mathcal{U} \subset \mathcal{M}$ we say that the map is *volume-preserving*. An immediate corollary of Liouville's theorem is that the orbit maps of vector fields with zero divergence are volume-preserving:

**Corollary (Conservation of Euclidean volume).** If a vector field $X$ in $\mathbb{R}^n$ fulfills $\mathrm{div} X = 0$, then

$$ \mathrm{vol}(\mathcal{U}_t) = \mathrm{vol}(\mathcal{U}) \qquad (A.10) $$

for all open sets $\mathcal{U} \subset \mathbb{R}^n$ and all $t \in \mathbb{R}$ such that the flow of $X$ is defined.

<footnote n="9">⁹The definition of local maximal flow is analogue to that of global flow, restricting the domain to a suitable open subset $\mathcal{D} \subset \mathbb{R} \times \mathcal{M}$.</footnote>
*Proof.* If div $X = 0$ the right hand side of Eq. (A.9) vanishes, hence vol $\mathcal{U}_t$ is constant whenever the flow of $X$ is defined. ■

The Riemannian Liouville's theorem. The constructions of the previous paragraph generalize to the more general setting of Riemannian manifolds [53, Ch. 16]. Given a smooth vector field $X \in \mathcal{X}$ that admits a global flow $\theta$ on a Riemannian manifold $(\mathcal{M}, g)$ of dimension $n$, let $\mathcal{U}_t = \theta_t(\mathcal{U})$ be the image of any open subset $\mathcal{U} \subseteq \mathcal{M}$ under the orbit map $\theta_t: \mathcal{M} \to \mathcal{M}$, as in Eq. (A.8). To generalize the Euclidean Liouville's theorem to this Riemannian setting we need the appropriate notions of divergence of a vector field and volume of an open set on a Riemannian manifold. The appropriate generalization of the divergence operator is given by Eq. (A.5); the appropriate notion of volume on a Riemannian manifold is the following [53, Ch. 16]: If $\mathcal{U}$ is an open subset completely contained in the domain of a single smooth chart $(\mathcal{V}, \pi)$ of $\mathcal{M}$, then its Riemannian volume is<fnref n="10" />

$$ \mathrm{vol}\mathcal{U} = \int_{\pi(\mathcal{U})} \sqrt{\det \tilde{g}(\tilde{x})} d\tilde{x}, \qquad (A.11) $$

where $\pi: \mathcal{U} \to \mathbb{R}^n$ is an homeomorphism onto an open subset $\tilde{\mathcal{U}} := \pi(\mathcal{U})$ of $\mathbb{R}^n$ mapping $x \in \mathcal{M}$ to $\tilde{x} \in \tilde{\mathcal{U}}$; and $\tilde{g}$ is the effective representation of the Riemannian metric $g$ on $\tilde{\mathcal{U}}$ (cf. Appendix B.4).

With these definitions at hand we can state the Riemannian version of Liouville's theorem:

**Theorem (Riemannian Liouville's theorem).** Given a vector field $X \in \mathcal{X}$ on a Riemannian manifold $(\mathcal{M}, g)$ and an open set $\mathcal{U} \subseteq \mathcal{M}$,

$$ \frac{d}{dt} \mathrm{vol}(\mathcal{U}_t) = \int_{\pi(\mathcal{U}_t)} \mathrm{div} X dx \qquad (A.12) $$

for all $t \in \mathbb{R}$ such that the flow $\theta$ of $X$ is defined, where $\mathcal{U}_t = \theta_t(\mathcal{U})$ and $\pi_0$ is a chart whose domain contains $\mathcal{U}_t^{11}$.

*Proof.* See e.g., Lee [53, Ch. 16]. ■

<figure><img src="image_5.png" /></figure>

As in the Euclidean case, if a map $\phi: \mathcal{M} \to \mathcal{M}$ fulfills vol($\mathcal{U}$) = vol($\phi\mathcal{U}$) for all open subsets $\mathcal{U} \subseteq \mathcal{M}$ we say that the map is volume-preserving; and the orbit maps of vector fields with zero Riemannian divergence are volume-preserving.

**Corollary (Conservation of Riemannian volume).** If a vector field $X \in \mathcal{X}$ on a Riemannian manifold fulfills $\mathrm{div} X = 0$ then

$$ \mathrm{vol}(\mathcal{U}_t) = \mathrm{vol}(\mathcal{U}), \qquad (A.13) $$

where $\mathcal{U}_t = \theta_t(\mathcal{U})$, for all open sets $\mathcal{U} \subseteq \mathcal{M}$ and all $t \in \mathbb{R}$ such that the flow $\theta$ of $X$ is defined.

*Proof.* The proof is identical to the one for the Euclidean counterpart. ■

<figure><img src="image_6.png" /></figure>

<footnote n="10">¹⁰The definition extends to arbitrary open subsets of $\mathcal{M}$ by a partition of unity argument.</footnote>

<footnote n="11">¹¹As discussed in Lee [53] the result does not depend on the choice of smooth chart whose domain contains $\mathcal{U}_t$.</footnote>
Poincaré recurrence. The last notion we need is that of *Poincaré recurrence*, a property of volume-preserving maps on sets of finite volume. We present a measure-theoretic version of Poincaré’s classical recurrence theorem, and adapt it to our Riemannian framework.

Given a measure space<fnref n="12" /> $(\Omega, \mu)$, we say that $(\Omega, \mu)$ is *finite* if $\mu(\Omega) < \infty$, and that a map $\phi: \Omega \to \Omega$ is *measure preserving* if $\mu(\phi(U)) = \mu(U)$ for all measurable subsets $U \subseteq \Omega$. Given a finite measure that is invariant under some map one has the following theorem [10]:

**Theorem (Poincaré – Measure setting).** Let $(\Omega, \mu)$ be a finite measure space, and let $\phi: \Omega \to \Omega$ be a measure preserving mapping. Let $U$ be a measurable subset of $\Omega$. Then almost every point $x \in U$ is infinitely recurrent with respect to $U$, that is, the set $\{n \in \mathbb{N} : \phi^n x \in U\}$ is infinite.

*Proof.* See e.g., Bekka et al. [10, Th. 1.7]. ■

<figure><img src="image_7.png" /></figure>

*Remark A.4.* The Riemannian volume Eq. (A.11) on a Riemannian manifold $(\mathcal{M}, g)$ defines a measure $\mu$ on the Borel sigma-algebra of $\mathcal{M}$ by $\mu(\mathcal{U}) = \text{vol}\mathcal{U}$, hence a Riemannian manifold is in particular a measure space [80], on which Poincaré's theorem applies. Furthermore every Riemannian manifold is a separable metric space,<fnref n="13" /> so one can formulate a Riemannian version of Poincaré's theorem: given a Riemannian manifold $(\mathcal{M}, g)$ of finite volume and a volume-preserving map $\phi: \mathcal{M} \to \mathcal{M}$, almost every point $x \in \mathcal{M}$ is $\phi$-recurrent, that is, there is a strictly increasing sequence of integers $t_n \uparrow \infty$ such that $\lim_{n \to \infty} \phi^{t_n} x \to x$; see Bekka et al. [10, Corollary 1.8].

The tools presented in this appendix will be used in Appendix D to prove some of the main results of this paper, namely that a game is incompressible if and only if it is harmonic (via a Riemannian divergence operator); that replicator dynamics on incompressible games are volume-preserving with respect to a non-Euclidean Riemannian structure (via Liouville's theorem); and that replicator dynamics on incompressible games exhibit Poincaré recurrence (via Poincaré's theorem).

## APPENDIX B. EFFECTIVE REPRESENTATION OF GAMES

Given the finite normal form game $\Gamma = \Gamma(\mathcal{N}, \mathcal{A}, u)$ let $A_i \equiv m_i + 1$ be the number of pure strategies of player $i \in \mathcal{N}$, and denote the set of their pure strategies as $\mathcal{A}_i = \{0_i, 1_i, \dots, m_i\}$. Define $\tilde{\mathcal{A}}_i := \{1_i, \dots, m_i\}$; in the following the index $\alpha_i \in \mathcal{A}_i$ runs from $0_i$ to $m_i$, and the index $\mu_i \in \tilde{\mathcal{A}}_i$ runs from $1_i$ to $m_i$, unless otherwise specified.

Finite games in this form carry two intrinsic redundancies. First, $m_i$ out of the $m_i + 1$ components of the mixed strategy $x_i \in \mathcal{X}_i$ of player $i$ are sufficient to completely specify it, since the remaining one is constrained by $\sum_{\alpha_i} x_i \alpha_i = 1$. Second, two strategically equivalent games, albeit having different payoff functions, effectively represent the same game, since they display the same strategical and dynamical properties.<fnref n="14" /> For this reason it is desiderable to introduce a *reduced* or *effective* representation of a game, in which (1) the mixed strategy of each player is represented by an $m_i$-dimensional object, and (2) strategically equivalent games are “clearly” the same, in a sense to be made precise.

<footnote n="12">¹²Recall that a measure space $(\Omega, \mu)$ is a set $\Omega$ with a countable-addictive function $\mu$ from the sigma-algebra $\Sigma$ of $\Omega$ into the nonnegative real numbers (including infinity) such that $\Omega(\emptyset) = 0$, and that any element in $\Sigma$ is called a *measurable* subset of $\Omega$.</footnote>

<footnote n="13">¹³The distance between two points being the infimum of the lengths of piecewise geodesics joining them [54, 67].</footnote>

<footnote n="14">¹⁴As discussed in Candogan et al. [14] strategically equivalent games have the same set of equilibria, but in general different efficiency (e.g., Pareto optimality).</footnote>
<figure><img src="image_8.png" /><figcaption>**Figure 3:** Maps (B.1) and (B.2) between the open corner of cube $C^\circ$ in $\mathbb{R}^m$ and the open simplex $X^\circ$ in $\mathbb{R}^{m+1}$ for $m = 2$. In light red are the tangent spaces $TC^\circ = \mathbb{R}^2$ and $TX^\circ = \mathcal{Z}$, where $\mathcal{Z}$ is the hyperplane $\mathcal{Z} = \{(x_0, x_1, x_2) \in \mathbb{R}^3 : x_0+x_1+x_2 = 0\}$. The basis vectors $\tilde{e}_1 = (1, 0)$ and $\tilde{e}_2 = (0, 1)$ of $TC^\circ$ are mapped by Eq. (B.21) to the vectors $\tilde{e}_1 = e_1 - e_0 = (-1, 1, 0)$ and $\tilde{e}_2 = e_2 - e_0 = (-1, 0, 1)$ in $\mathcal{Z}$.</figcaption></figure>

To this end consider for each player the coordinates transformation between their strategy space $\mathcal{X}_i = \Delta(\mathcal{A}_i) = \{x_i \in \mathbb{R}_+^{m_i+1} : \sum_{\alpha_i \in \mathcal{A}_i} x_{i\alpha_i} = 1\}$ and the corner of cube simplex $\mathcal{C}_i = \{\tilde{x}_i \in \mathbb{R}_+^{m_i} : \sum_{\mu_i \in \tilde{\mathcal{A}}_i} \tilde{x}_{i\mu} \le 1\}$ given by

$$ \iota_0: \begin{array}{rcl} \mathcal{C}_i & \to & \mathcal{X}_i \\ \tilde{x}_i & \mapsto & x_i \end{array} \quad \text{such that} \quad \left\{ \begin{array}{ll} x_{i0_i} = 1 - \sum_{\mu_i=1}^{m_i} \tilde{x}_{i\mu_i} & \\ x_{i\mu_i} = \tilde{x}_{i\mu_i} & \text{for all } \mu_i \in \{1, \dots, m_i\}. \end{array} \right. \qquad (B.1) $$

This map is visualized in Fig. 3 with its obvious inverse<fnref n="15" />

$$ \pi_0: \begin{array}{rcl} \mathcal{X}_i & \to & \mathcal{C}_i \\ x_i & \mapsto & \tilde{x}_i \end{array} \quad \text{such that} \quad \tilde{x}_{i\mu_i} = x_{i\mu_i} \quad \text{for all } \mu_i \in \{1, \dots, m_i\}. \qquad (B.2) $$

This standard reduction technique goes back at least to Ritzberger & Vogelsberger [72, p. 4], and is employed in many other works [13, 22, 35, 37, 50, 51, 59, 81, 86].

In the following we consider only interior strategies by restricting $\iota_0$ to $\iota_0|_{C_i^\circ} : C_i^\circ \to \mathcal{X}_i^\circ$ (and we will denote $\iota_0|_{C^\circ}$ just by $\iota_0$). Geometrically, the reason to consider the relative interior of the strategy space is that $\mathcal{X}_i^\circ$ is a smooth manifold of dimension $m_i$ with a global chart $\pi_0$ onto the open corner of cube $\mathcal{C}_i^\circ$, which is an open subset of $\mathbb{R}^{m_i}$; on the other hand, $\mathcal{X}_i$ is not a smooth manifold (cf. Appendix A). For a dynamical justification of the restriction to the interior of $\mathcal{X}_i$, cf. Eq. (C.2) and the surrounding discussion.

Under the maps $\iota_0$ and its inverse $\pi_0$ the open corner of cube and the open simplex are fundamentally the same object; the corner of cube representation retains all the information existing on the simplex in a more efficient way, getting rid of the redundant degree of freedom. Thus, all the objects and structures defined on the open simplex $\mathcal{X}_i^\circ$ as a subspace of $\mathbb{R}_{++}^{m_i+1}$ – such as payoff functions and payoff fields, vector fields and metrics – must admit via Eqs. (B.1) and (B.2) an equivalent representation on the open corner of cube $\mathcal{C}_i^\circ$, that we'll

<footnote n="15">¹⁵The maps $\iota_0$ and $\pi_0$ are labeled by 0 to denote the fact the we express $x_{i0_i}$ as a function of the remaining coordinates; this choice comes without any loss of generality, i.e., it would be equivalent to consider the map $\iota_\alpha$ such that $x_{i\alpha_i} = 1 - \sum_{\mu_i \neq \alpha_i} \tilde{x}_{i\mu_i}$, and $x_{i\mu_i} = \tilde{x}_{i\mu_i}$ for all $\mu_i \neq \alpha_i$.</footnote>
<figure><img src="image_9.png" /><figcaption>**Figure 4:** A (2 × 2) game. Left: The strategy space of each player $i \in \{1, 2\}$ in a (2 × 2) game is the 1-dimensional open simplex $X_i^\circ$ as a subspace of $\mathbb{R}^2$; the tangent space $T X_i^\circ$ is the line $x_0 + x_1 = 0$. Right: The strategy space $X_1^\circ \times X_2^\circ$ of a 2 × 2 game is a subset of $\mathbb{R}^4$, so we represent the open corner of cube $C^\circ = C_1^\circ \times C_2^\circ = \{(\tilde{x}_1, \tilde{x}_2) : \tilde{x}_1 > 0, \tilde{x}_2 > 0, \tilde{x}_1 < 1, \tilde{x}_2 < 1\}$ as an open subset of $\mathbb{R}^2$. Its tangent space $T C^\circ$ is the whole $\mathbb{R}^2$.</figcaption></figure>

refer to interchangeably as reduced or effective. As opposed to effective, we will refer to objects defined on $X_i^\circ$ as full.

In the next paragraphs we will present for each open simplex $X_i^\circ$ and its corresponding open corner of cube $C_i^\circ$ the effective representation of payoff functions and payoff fields, replicator dynamics, tangent vectors, and metric tensors. The end result of this reduction procedure is the effective representation of the mixed extension of a finite game $\Gamma(\mathcal{N}, \mathcal{A}, u)$, in which all the relevant objects are defined on (the interior of) the product corner of cube $C = \prod_{i \in \mathcal{N}} C_i$, rather than on the “redundant” original strategy space $\mathcal{X} = \prod_{i \in \mathcal{N}} X_i$.

**B.1. Effective representation of payoff functions and payoff fields.** The effective representation of mixed strategies is given precisely by Eq. (B.2). Since payoff functions are scalar functions of these strategies, the effective representation $\tilde{u}_i : C_i^\circ \to \mathbb{R}$ of the payoff function $u_i : X_i^\circ \to \mathbb{R}$ is obtained as the restriction of $u_i$ to $C_i^\circ$, i.e.,

$$ \tilde{u}_i(\tilde{x}) = u_i(x) \qquad (B.3) $$

for all $i \in \mathcal{N}$, and all $\tilde{x} \in C^\circ$, $x \in \mathcal{X}$ related by Eq. (B.1).

Just like the full payoff field is obtained differentiating the full payoff functions, the reduced payoff field is obtained differentiating the reduced payoff functions:<fnref n="16" />

$$ v_{i\alpha_i}(x) = u_i(\alpha_i; x_{-i}) = \frac{\partial u_i}{\partial x_{i\alpha_i}}(x) \implies \tilde{v}_{i\mu_i}(\tilde{x}) := \frac{\partial \tilde{u}_i}{\partial \tilde{x}_{i\mu_i}}(\tilde{x}). \qquad (B.4) $$

*Remark B.1 (Individual differential).* Eq. (B.4) says that the components of the full (resp. reduced) payoff field $v_i$ (resp. $\tilde{v}_i$) are obtained by partial differentiation of the payoff function $u_i$ (resp. $\tilde{u}_i$) of player $i \in \mathcal{N}$ with respect to their mixed strategies $x_i$ (resp. $\tilde{x}_i$). As mentioned in Remark A.2 we refer to the array of partial derivatives of a function as differential of the function; since we are differentiating each payoff function only with respect to the variables relative to one player, we say that the full (resp. reduced) payoff field of a

<footnote n="16">¹⁶In more geometrical terms, $\tilde{u}_i$ (resp. $\tilde{v}_i$) is the pull-back of $u_i$ (resp. $v_i$) along $\iota_0$.</footnote>
player is the individual differential of the full (resp. reduced) payoff function of the player, and for each $i \in \mathcal{N}$ we write

$$v_i = d_i u_i \quad \text{and} \quad \tilde{v}_i = \tilde{d}_i \tilde{u}_i. \qquad (B.5)$$

We have the following useful lemma to compute partial derivatives in effective coordinates:

**Lemma B.1.** Let $f: \mathcal{X}^\circ \to \mathbb{R}$ be a differentiable function and $\tilde{f}: \mathcal{C}^\circ \to \mathbb{R}$ its effective representation. Then

$$\frac{\partial}{\partial \tilde{x}_{i\mu_i}} \tilde{f}(\tilde{x}) = \left( \frac{\partial}{\partial x_{i\mu_i}} - \frac{\partial}{\partial x_{i0_i}} \right) f(x), \qquad (B.6)$$

for all $i \in \mathcal{N}$, $\mu_i \in \tilde{\mathcal{A}}_i$, and all $x \in \mathcal{X}^\circ$ and $\tilde{x} \in \mathcal{C}^\circ$ related by Eq. (B.1).

*Proof.* Fix $i \in \mathcal{N}$ and $\mu_i \in \tilde{\mathcal{A}}_i$. By the chain rule, $\frac{\partial}{\partial \tilde{x}_{i\mu_i}} \tilde{f}(\tilde{x}) = \sum_{j \in \mathcal{N}} \sum_{\alpha_j=0_j}^{m_j} \frac{\partial x_{j\alpha_j}}{\partial \tilde{x}_{i\mu_i}} \frac{\partial}{\partial x_{j\alpha_j}} f(x)$. By Eq. (B.1), $\frac{\partial x_{j0_j}}{\partial \tilde{x}_{i\mu_i}} = -\delta_{ij}$ and $\frac{\partial x_{j\nu_j}}{\partial \tilde{x}_{i\mu_i}} = \delta_{ij}\delta_{\mu_i\nu_i}$ for all $\nu_j \in \{1, \dots, m_j\}$, and we conclude expanding the sum and substituting. ■

Applying the previous lemma to Eq. (B.4) we get the reduced expression of the payoff field:

$$\tilde{v}_{i\mu_i}(\tilde{x}) = v_{i\mu_i}(x) - v_{i0_i}(x), \qquad (B.7)$$

with $x = \iota_0(\tilde{x})$ for all $\tilde{x} \in \mathcal{C}^\circ$ and all $i \in \mathcal{N}$, $\mu_i = 1, \dots, m_i$, in agreement with Eq. (23) in the main text. The first order version of this equation gives an important relation between the Jacobian matrices of the full and reduced effective fields:

**Lemma B.2.** The components of the Jacobian matrix of the effective payoff field are given by

$$\frac{\partial \tilde{v}_{i\nu_i}}{\partial \tilde{x}_{j\mu_j}}(\tilde{x}) = \left( \frac{\partial}{\partial x_{j\mu_j}} - \frac{\partial}{\partial x_{j0_j}} \right) (v_{i\nu_i} - v_{i0_i}) (x) \qquad (B.8)$$

with $x = \iota_0(\tilde{x})$ for all $\tilde{x} \in \mathcal{C}^\circ$, $i, j \in \mathcal{N}$, $\nu_i \in \{1, \dots, m_i\}$ and $\mu_j \in \{1, \dots, m_j\}$.

*Proof.* Immediate by Lemma B.1 and Eq. (B.7). ■

Next is a simple but important property of payoff fields:

**Lemma B.3.** For every player $i \in \mathcal{N}$ and for every pure strategy $\alpha_i \in \mathcal{A}_i$, the component $v_{i\alpha_i}$ of the payoff field $v$ does not depend on the mixed strategy of player $i$:

$$\frac{\partial v_{i\alpha_i}}{\partial x_{i\beta_i}} = 0 \qquad (B.9)$$

for all players $i \in \mathcal{N}$ and all $\alpha_i, \beta_i \in \mathcal{A}_i$. Analogously, for the reduced payoff field,

$$\frac{\partial \tilde{v}_{i\mu_i}}{\partial \tilde{x}_{i\nu_i}} = 0 \qquad (B.10)$$

for all players $i \in \mathcal{N}$ and all $\mu_i, \nu_i \in \tilde{\mathcal{A}}_i$.

*Proof.* The first statement is immediate by the fact that $v_{i\alpha_i}(x)$ is the partial derivative with respect to $x_{i\alpha_i}$ of the multilinear function $u_i(x)$; the second follows from Lemma B.2. ■

This property will be crucial in the proof of Proposition D.1 in Appendix D.
**Example B.1** (2 × 2 game – Effective payoff). Consider a 2 × 2 game with $\mathcal{A}_1 = \mathcal{A}_2 = \{0, 1\}$ and $\tilde{\mathcal{A}}_1 = \tilde{\mathcal{A}}_2 = \{1\}$. The mixed strategies in full and effective representations are respectively

$$x = ((x_{1,0}, x_{1,1}), (x_{2,0}, x_{2,1})) \in \mathcal{X}_1 \times \mathcal{X}_2 \qquad (\text{B.11a})$$

$$\tilde{x} = (\tilde{x}_{1,1}, \tilde{x}_{2,1}) \equiv (\tilde{x}_1, \tilde{x}_2) \in \mathcal{C}_1 \times \mathcal{C}_2, \qquad (\text{B.11b})$$

where in the second line we drop an index since $\tilde{\mathcal{A}}_i$ is a singleton; cf. Fig. 4. The full and effective payoff functions are

$$\begin{align}
u_i(x) &= x_{1,0} x_{2,0} u_i(0,0) + x_{1,0} x_{2,1} u_i(0,1) + x_{1,1} x_{2,0} u_i(1,0) + x_{1,1} x_{2,1} u_i(1,1) \nonumber \\
\tilde{u}_i(\tilde{x}) &= \tilde{x}_1 \tilde{x}_2 [u_i(0,0) - u_i(0,1) - u_i(1,0) + u_i(1,1)] + \tilde{x}_1 [-u_i(0,0) + u_i(1,0)] \nonumber \\
&\quad + \tilde{x}_2 [-u_i(0,0) + u_i(0,1)] + u_i(0,0). \tag{B.12a}
\end{align}$$

Note that the full payoffs are polynomials of degree 2 with each term of the same degree, while the reduced payoffs are polynomials of degree 2 with terms of all possible degrees.

The two full payoff fields, with two components each, are

$$v_1(x) = \begin{pmatrix} x_{2,0} & u_1(0,0) + x_{2,1} & u_1(0,1) \\ x_{2,0} & u_1(1,0) + x_{2,1} & u_1(1,1) \end{pmatrix} \qquad v_2(x) = \begin{pmatrix} x_{1,0} & u_2(0,0) + x_{1,1} & u_2(1,0) \\ x_{1,0} & u_2(0,1) + x_{1,1} & u_2(1,1) \end{pmatrix}, \quad (\text{B.13})$$

whereas the two reduced payoff fields, with one component each, are

$$\tilde{v}_1(\tilde{x}) = \tilde{x}_2[u_1(0,0) - u_1(0,1) - u_1(1,0) + u_1(1,1)] - u_1(0,0) + u_1(1,0) \qquad (\text{B.14a})$$

$$\tilde{v}_2(\tilde{x}) = \tilde{x}_1[u_2(0,0) - u_2(0,1) - u_2(1,0) + u_2(1,1)] - u_2(0,0) + u_2(0,1). \qquad (\text{B.14b})$$

Note that $v_i(x)$ does not depend on $x_i$, and $\tilde{v}_i(\tilde{x})$ does not depend on $\tilde{x}_i$, as expected by Lemma B.3. ◇

Effective payoff field and strategical equivalence. The expression for the effective payoff field can be used to show that two games are strategically equivalent if and only if they are described by the same effective payoff field. Before making this precise, we give here a simple but powerful lemma that we will use often in the following:

**Lemma B.4** (Vanishing of multilinear extension). Given a finite game $\Gamma = \Gamma(\mathcal{N}, \mathcal{A}, u)$ let $F: \mathcal{A} \to \mathbb{R}$ be a real function of pure strategy profiles and $\tilde{F}: \mathcal{X} \to \mathbb{R}$ its multilinear extension, i.e.,

$$\bar{F}(x) = \mathbb{E}_{\alpha \sim x}[F(\alpha)] = \sum_{\alpha \in \mathcal{A}} F(\alpha) \prod_{i \in \mathcal{N}} x_{i\alpha_i} = \sum_{\alpha \in \mathcal{A}} F(\alpha) x_{\alpha} \qquad (\text{B.15})$$

Then $F(\alpha) = 0$ for all $\alpha \in \mathcal{A}$ if and only if $\bar{F}(x) = 0$ for all $x \in \mathcal{X}$.

*Proof.* If $F(\alpha) = 0$ for all $\alpha \in \mathcal{A}$ the conclusion is immediate. Conversely, assume that $\bar{F}(x) = 0$ for all $x \in \mathcal{X}$. In particular, for any $\alpha \in \mathcal{A}$, this holds true for the mixed strategy $x_{i\beta_i} = \delta_{\alpha_i\beta_i}$ in which each player $i$ assigns all weight to $\alpha_i$, i.e., $0 = \bar{F}(x) = \sum_{\beta \in \mathcal{A}} F(\beta) \prod_{i \in \mathcal{N}} \delta_{\alpha_i \beta_i} = F(\alpha)$. ■

We now move on to show that two games are strategically equivalent if and only if they are described by the same effective payoff field. Recall from Eq. (3) in the main text that two finite games $\Gamma(\mathcal{N}, \mathcal{A}, u)$ and $\Gamma'(\mathcal{N}, \mathcal{A}, u')$ are strategically equivalent if

$$u'_i(\beta_i; \alpha_{-i}) - u'_i(\alpha_i; \alpha_{-i}) = u_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i}) \qquad (3)$$

for all $i \in \mathcal{N}$ and all $\alpha, \beta \in \mathcal{A}$. If two games $\Gamma$ and $\Gamma'$ are strategically equivalent, we write $\Gamma \sim \Gamma'$.
**Proposition B.1.** Two finite games are strategically equivalent if and only if they have the same effective payoff field.

The proof of this result is better broken into steps.

Firstly, following Candogan et al. [14] we give the following definition and lemma:

**Definition 4 (Non-strategic game).** A finite normal form game $\Gamma(\mathcal{N}, \mathcal{A}, k)$ is called non-strategic if all players are indifferent between all of their choices:

$$k_i(\beta_i, \alpha_{-i}) = k_i(\alpha_i, \alpha_{-i}) \qquad (B.16)$$

for all $i \in \mathcal{N}$, all $\alpha_{-i} \in \mathcal{A}_{-i}$, and all $\alpha_i, \beta_i \in \mathcal{A}_i$.

**Lemma B.5.** Two finite games $\Gamma(\mathcal{N}, \mathcal{A}, u)$, $\Gamma'(\mathcal{N}, \mathcal{A}, u')$ are strategically equivalent if and only if their difference is a non-strategic game.

*Proof.* Let $\Gamma - \Gamma'$ be non-strategic; then $k := u' - u$ fulfills Eq. (B.16), and rearranging the terms we immediately get Eq. (3). Conversely let $\Gamma$ and $\Gamma'$ be strategically equivalent, and set $k := u' - u$; again rearrange the terms in Eq. (3) to immediately conclude that $k$ fulfills Eq. (B.16). ■

Secondly, we give the following characterization of non-strategic games:

**Proposition B.2.** A finite game $\Gamma(\mathcal{N}, \mathcal{A}, k)$ is non-strategic if and only if its effective payoff field $\tilde{v}$ vanishes identically.

*Proof.* Let $\Gamma$ be non-strategic. Then its effective payoff field fulfills

$$\begin{aligned} \tilde{v}_{i\mu_i}(\tilde{x}) &= v_{i\mu_i}(x) - v_{i0_i}(x) = k_i(\mu_i, x_{-i}) - k_i(0_i, x_{-i}) \\ &= \sum_{\alpha_{-i}} x_{-i\alpha_{-i}} [k_i(\mu_i, \alpha_{-i}) - k_i(0_i, \alpha_{-i})] = 0 \end{aligned} \qquad (B.17)$$

for all $\tilde{x} \in \mathcal{C}$, all $i \in \mathcal{N}$, and all $\mu_i \in \{1, \dots, m_i\}$, where the last equality holds by definition of non-strategic game.

Conversely, let the effective payoff field $\tilde{v}(\tilde{x})$ of $\Gamma$ be identically zero for all $\tilde{x} \in \mathcal{C}$. Then by Eq. (B.7) all the components $v_{i\alpha_i}(x) = k_i(\alpha_i, x_{-i})$ of the full payoff field are equal to each other, i.e., $k_i(\alpha_i, x_{-i}) = k_i(\beta_i, x_{-i})$ for all $x \in \mathcal{X}$ and $\alpha_i, \beta_i \in \mathcal{A}_i$, which in turn implies that $k_i(\alpha_i, \alpha_{-i}) = k_i(\beta_i, \alpha_{-i})$ by Lemma B.4. ■

Finally, by Lemma B.5, Proposition B.2 is equivalent to Proposition B.1:

*Proof of Proposition B.1.* Given two finite games $\Gamma(\mathcal{N}, \mathcal{A}, u)$, $\Gamma'(\mathcal{N}, \mathcal{A}, u')$ we have the following implications:

$$\Gamma \sim \Gamma' \iff \Gamma - \Gamma' \text{ is non-strategic} \iff \tilde{v} - \tilde{v}' = 0 \iff \tilde{v} = \tilde{v}' \qquad (B.18)$$

which concludes the proof. ■

**B.2. Effective representation of the replicator dynamics.** We report here for ease of reference the full replicator dynamics Eqs. (11) and (RD) and its effective representation Eqs. (28) and (RD$_0$), already derived in the main text:

$$\dot{x}_{i\alpha_i} = v_{i\alpha_i}^{\sharp}(x) = x_{i\alpha_i} \left[ v_{i\alpha_i}(x) - \sum_{\beta_i=0}^{m_i} x_{i\beta_i} v_{i\beta_i}(x) \right] \quad \text{for all } i \in \mathcal{N} \text{ and } \alpha_i \in \{0, \dots, m_i\}, \qquad (11)$$

$$\dot{x}_{i\mu_i} = v_{i\mu_i}^{\sharp}(\tilde{x}) = \tilde{x}_{i\mu_i} \left[ \tilde{v}_{i\mu_i}(\tilde{x}) - \sum_{\nu_i=1}^{m_i} \tilde{x}_{i\nu_i} \tilde{v}_{i\nu_i}(\tilde{x}) \right] \quad \text{for all } i \in \mathcal{N} \text{ and } \mu_i \in \{1, \dots, m_i\}. \qquad (28)$$
Remark B.2. We prefer the notation $v_{i\mu_i}^\sharp$ over the more correct $\tilde{v}_{i\mu_i}^\sharp$ for the *effective* replicator vector field for notational simplicity when there is no risk of ambiguity, and reinstate the tilde $\tilde{\tau}$ when we want to stress the difference between the full and effective representations of the replicator field. ◇

B.3. **Effective representation of tangent vectors.** As we saw, the map $\iota_0$ can be used to obtain the effective representation of points in the strategy space (i.e., mixed strategies) and of scalar functions of these points (i.e., functions of mixed strategies); the effective representation of vectors that are tangent to the strategy space requires more care.

The open corner of cube $C_i^\circ$ is an open subset of $\mathbb{R}_{+1}^{m_i}$ in its own right, so its tangent space is the whole euclidean space, that we denote by $T C_i^\circ \equiv \mathbb{R}^{m_i}$. On the other hand $X_i^\circ$ is an open subset of an affine hyperplane in $\mathbb{R}_{++}^{m_i+1}$, and its tangent space is give by the hyperplane $Z_i$, the linear subspace in $\mathbb{R}^{m_i+1}$ of vectors whose components add up to zero, cf. Lemma C.1 and Fig. 3.

A basis vector $\tilde{e}_{i\mu_i}$ of $\mathbb{R}^{m_i}$ must correspond via $\iota_0$ to a vector tangent to the simplex, i.e., a vector in $Z_i$, that we want to determine. Since $\tilde{Z}_i$ is a linear subspace of $\mathbb{R}^{m_i+1}$, it must be possible to express via $\iota_0$ this sought after vector as a linear combination of basis vectors $\{e_{i\alpha_i}\}_{\alpha_i \in \{0, \dots, m_i\}}$ of $\mathbb{R}^{m_i+1}$, for all $\mu_i \in \{1, \dots, m_i\}$.

The way to obtain this identification comes from an important result in differential geometry [53]: given a smooth map between two spaces such as $\iota_0: C_i^\circ \to X_i^\circ$, its differential induces a linear map $d\iota_0: \mathbb{R}^{m_i} \to Z_i$ between the tangent spaces to the two spaces. The matrix representing this differential is the Jacobian matrix $J$ of $\iota_0$, so (dropping temporarily the player index $i$ for notational simplicity) a basis vector $\tilde{e}_\mu \equiv \tilde{e}_{i\mu_i}$ of $\mathbb{R}^m \equiv \mathbb{R}^{m_i}$ is mapped to the vector $d\iota_0(\tilde{e}_\mu) \in \mathcal{Z} \subset \mathbb{R}^{m+1}$ of component $[d\iota_0(\tilde{e}_\mu)]_\alpha = [d\iota_0(\tilde{e}_{i\mu_i})]_{i\alpha_i}$ given by

$$[d\iota_0(\tilde{e}_\mu)]_\alpha = \sum_{\nu=1}^{m} J_{\alpha\nu} [\tilde{e}_\mu]_\nu \qquad (B.19)$$

for all $\alpha \in \{0, \dots, m\}$. Since $\tilde{e}_\mu$ is a basis vector its $\nu$-th component is given by the Kronecker delta $\delta_{\mu\nu}$, so

$$d\iota_0(\tilde{e}_\mu) = \sum_{\alpha=0}^{m} [d\iota_0(\tilde{e}_\mu)]_\alpha e_\alpha = \sum_{\alpha=0}^{m} J_{\alpha\mu} e_\alpha = \sum_{\alpha=0}^{m} \frac{\partial x_\alpha}{\partial \tilde{x}_\mu} e_\alpha \qquad (B.20)$$

for all $\mu \in \{1, \dots, m\}$. Again by Eq. (B.1) we have $\frac{\partial x_0}{\partial \tilde{x}_\mu} = -1$ and $\frac{\partial x_\nu}{\partial \tilde{x}_\mu} = \delta_{\mu\nu}$ for all $\mu, \nu \in \{1, \dots, m\}$, so after reinserting the player index we get $d\iota_0(\tilde{e}_{i\mu_i}) = e_{i\mu_i} - e_{i0_i}$. For notational simplicity in the following we drop the differential of the $\iota_0$ map and denote $d\iota_0(\tilde{e}_{i\mu_i})$ just by $\tilde{e}_{i\mu_i}$, so that in conclusion

$$\tilde{e}_{i\mu_i} = e_{i\mu_i} - e_{i0_i} \qquad (B.21)$$

for all $i \in \mathcal{N}$ and all $\mu_i \in \{1, \dots, m_i\}$; cf. Fig. 3 for a visual example.

B.4. **Shahshahani metric.** As discussed in Section 4, the Euclidean metric is not attuned with the dynamical properties of replicator dynamics. For this reason Shahshahani [75] introduced a metric that “[...] turns out to be surprisingly effective in clarifying the dynamics of the [replicator dynamical] system”. In this section we present this metric in its full and effective representations, along with some of its geometrical properties.

A remark on notation: we include where needed the player index $i \in \mathcal{N}$ for ease of comparison with the other sections of this work; all expressions hold true with exactly the same form if it is omitted.
**Definition 5.** The Shahshahani metric on the positive orthant $\mathbb{R}_{++}^{m_i+1}$ is the smoothly varying positive definite symmetric bilinear form $g_{x_i}: \mathbb{R}_{++}^{m_i+1} \times \mathbb{R}_{++}^{m_i+1} \to \mathbb{R}$ represented by the $(m_i+1) \times (m_i+1)$ matrix$^{17}$

$$g_{i\alpha_i\beta_i}(x_i) := \frac{\delta_{\alpha_i\beta_i}}{x_i\alpha_i} \qquad (B.22)$$

for all $x_i \in \mathbb{R}_{++}^{A_i}$ and $\alpha_i, \beta_i \in \{0, \dots, m_i\}$.

Effective Shahshahani metric. The components of the effective metric tensors $\tilde{g}_{\tilde{x}_i}$ on $\mathcal{C}_i^\circ$ are obtained by Eq. (13) as the inner product between effective tangent vectors, that by Eq. (B.21) is

$$\begin{aligned}
\tilde{g}_{i\mu_i\nu_i}(\tilde{x}) &= \langle \tilde{e}_{i\mu_i}, \tilde{e}_{i\nu_i} \rangle_{\tilde{x}} = \langle e_{i\mu_i} - e_{i0_i}, e_{i\nu_i} - e_{i0_i} \rangle_x \\
&= \sum_{\alpha_i\beta_i} \frac{\delta_{\alpha_i\beta_i}}{x_i\alpha_i} (\delta_{\alpha_i\mu_i} - \delta_{\alpha_i0_i})(\delta_{\beta_i\nu_i} - \delta_{\beta_i0_i}) \\
&= \frac{\delta_{\mu_i\nu_i}}{x_i\mu_i} - \frac{\delta_{i\mu_i0_i}}{x_i\mu_i} - \frac{\delta_{i\nu_i0_i}}{x_i\nu_i} + \frac{1}{x_i0_i}.
\end{aligned} \qquad (B.23)$$

The second and third terms vanish, so in conclusion

$$\tilde{g}_{i\mu_i\nu_i}(\tilde{x}_i) = \frac{\delta_{\mu_i\nu_i}}{\tilde{x}_i\mu_i} + \frac{1}{1 - \sum_{\rho_i=1}^{m_i} \tilde{x}_i\rho_i} \qquad (B.24)$$

for all $i \in \mathcal{N}$, all $\mu_i, \nu_i \in \{1, \dots, m_i\}$, and all $\tilde{x}_i \in \mathcal{C}_i^\circ$, in agreement with Eq. (25).

Determinant of the Shahshahani metric. Since the matrix representing the full Shahshahani metric is diagonal its determinant is immediately given by

$$\det g_i(x_i) = \frac{1}{\prod_{\alpha_i=0}^{m_i} x_i \alpha_i}. \qquad (B.25)$$

The determinant of the Shahshahani metric $\tilde{g}_i$ in its effective representation then follows after a standard calculation based on the matrix determinant lemma, viz.

$$\det \tilde{g}_i(\tilde{x}_i) = \frac{1}{\left(1 - \sum_{\mu_i=1}^{m_i} \tilde{x}_i \mu_i\right) \prod_{\nu_i=1}^{m_i} \tilde{x}_i \nu_i} = \frac{1}{x_i 0_i \prod_{\nu_i=1}^{m_i} \tilde{x}_i \nu_i}. \qquad (B.26)$$

The fact that the determinant of the full and reduced metric formally agree is a particularity of the Shahshahani metric, and is in general not true for Riemannian metrics.

Shahshahani unitary spheres. As discussed in Section 4 in the main text, the Shahshahani unit sphere $S_{x_i} := \{z \in \mathbb{R}_{++}^{m_i+1} : g_{x_i}(z, z) = 1\}$ at $x_i \in \mathbb{R}_{++}^{m_i+1}$ becomes increasingly flattened along the $x_i\alpha_i$-axis as $x_i\alpha_i \to 0$, as depicted in Fig. 1. Indeed (omitting for a second the player index $i$) the Shahshahani unit sphere at $x$,

$$\{z \in \mathbb{R}_{++}^{m_i+1} \text{ such that } g_x(z, z) = \sum_{\alpha\beta} \frac{\delta_{\alpha\beta}}{x_\alpha} z_\alpha z_\beta = \sum_{\alpha} \frac{z_\alpha^2}{x_\alpha} = 1\}, \qquad (B.27)$$

is an hyper-ellipse with the size of the $\alpha$-th axis going to zero as $x_\alpha \to 0$.

**Remark B.3.** As discussed in Example C.1, the behavior of the Shahshahani metric as the boundary is approached, responsible for the shrinking of unit spheres describe above, is also the key feature that confines the replicator dynamics to the interior of the strategy space. $\diamond$

<footnote>$^{17}$Recall that $T_x \mathbb{R}_{++}^{m_i+1} \cong \mathbb{R}_{++}^{m_i+1}$ by Remark A.1.</footnote>
This concludes our (by no means exhaustive) treatment of the geometrical properties of the Shahshahani metric; for an in-depth treatment we refer the reader to Akin [2] and Shahshahani [75]. In Appendix C we turn at some of its dynamical properties and at its deep connection with the replicator dynamics; on this matter see also [30, 37, 51, 61, 65].

## APPENDIX C. REPLICATOR DYNAMICS AS AN INDIVIDUAL SHAHSHAHANI GRADIENT SYSTEM

In this appendix we discuss the relation between the Shahshahani metric and the replicator dynamics.

Given a finite normal form game $\Gamma(\mathcal{N}, \mathcal{A}, u)$, the evolution of the players' mixed strategies $x_i \in \mathcal{X}_i = \Delta(\mathcal{A}_i) = \{x_i \in \mathbb{R}_+^{\mathcal{A}_i} : \sum_{\alpha_i \in \mathcal{A}_i} x_{i\alpha_i} = 1\}$ under the exponential weights learning scheme evolves according to the replicator dynamical system, that is

$$ \dot{x}_{i\alpha_i} = x_{i\alpha_i} [u_i(\alpha_i; x_{-i}) - u_i(x)] = x_{i\alpha_i} \left[ v_{i\alpha_i}(x) - \sum_{\beta_i \in \mathcal{A}_i} x_{i\beta_i} v_{i\beta_i}(x) \right] \quad (\text{RD}) $$

for all $i \in \mathcal{N}$ and $\alpha_i \in \mathcal{A}_i$. We define $v_{i\alpha_i}^{\#}(x) := x_{i\alpha_i} \left[ v_{i\alpha_i}(x) - \sum_{\beta_i \in \mathcal{A}_i} x_{i\beta_i} v_{i\beta_i}(x) \right]$ as in Eq. (11) in the main text, and write the replicator system more compactly as<fnref n="18" />

$$ \dot{x}_i = v_i^{\#}(x). \quad (C.1) $$

Interior and parallelism. For (C.1) to make sense $v_i^{\#}(x)$ must point in a direction parallel to $\mathcal{X}_i$ for all $x$ along the trajectory. The notion of “parallelism” breaks down at the boundary of $\mathcal{X}_i$, but for each player $i$ the interior of $\mathcal{X}_i$ is invariant under $v_i^{\#19}$. So by restricting our attention to dynamics with initial conditions $x_i(t_0)$ in the open mixed strategies space,

$$ \mathcal{X}_i^{\circ} = \{x_i \in \mathbb{R}_{++}^{\mathcal{A}_i} : \sum_{\alpha_i \in \mathcal{A}_i} x_{i\alpha_i} = 1\}, \quad (C.2) $$

we are sure that $x_i(t) \in \mathcal{X}_i^{\circ}$ for all times $t$ and all players, avoiding boundary issues. This means that under (RD) each pure strategy of each player has a non-zero probability to be played at all times, i.e., $x_{i\alpha_i} \neq 0$ for all $i \in \mathcal{N}$ and all $\alpha_i \in \mathcal{A}_i$.

Now unburdened from boundary issues we can give a precise notion of parallelism: a vector is parallel to $\mathcal{X}_i^{\circ}$ if its components sum to zero.

**Lemma C.1** (Tangent space to open simplex). *The tangent space to the open simplex $\mathcal{X}_i^{\circ} \subset \mathbb{R}_{++}^{\mathcal{A}_i}$ for any $x_i \in \mathcal{X}_i^{\circ}$ is the hyperplane in $\mathbb{R}^{\mathcal{A}_i}$ of vectors whose components sum up to zero:*

$$ Z_i := \mathrm{T}_{x_i} \mathcal{X}_i^{\circ} = \{z_i \in \mathbb{R}^{\mathcal{A}_i} : \sum_{\alpha_i} z_{i\alpha_i} = 0\}. \quad (C.3) $$

*Proof.* The open simplex $\mathcal{X}_i^{\circ}$ is the level set of value 1 of the smooth function $S_i : \mathbb{R}_{++}^{\mathcal{A}_i} \to \mathbb{R}$, $S_i(x_i) = \sum_{\alpha_i} x_{i\alpha_i}$. The differential $dS_i = \mathbf{1}_i := (1, \dots, 1)$ of $S_i$ is a surjective linear map from $\mathbb{R}^{\mathcal{A}_i}$ to $\mathbb{R}$ that does not depend on $x_i$, so by a standard theorem [53, Prop. 5.38] the tangent space to $\mathcal{X}_i^{\circ}$ at any point is the kernel of $dS_i$, that is $\{z_i \in \mathbb{R}^{\mathcal{A}_i} : \mathbf{1}_i^{\top} \cdot z_i = 0\}$. ■

<footnote n="18">¹⁸The notation $v^{\#}$ is reminiscent of the sharp operator, of common use in differential geometry [53]. This is no coincidence: the payoff field $v$ can be seen as a dual vector field or 1-form in $\mathbb{R}^A$, and replicator dynamics follow the flow lines of the primal-vector field obtained as the Shahshahani sharp of the reduced payoff dual-vector field, as briefly discussed in Appendix F. This primal-dual interpretation is discussed in detail in [61].</footnote>

<footnote n="19">¹⁹If $x_{i\alpha_i}(t_0) = 0$ then $x_{i\alpha_i}(t) = 0$ for all $t$ since $\dot{x}_{i\alpha_i} \propto x_{i\alpha_i}$, cf. Hofbauer & Sigmund [37]. As shown in Example C.1, this key dynamical feature bounding the replicator dynamics to the interior of the strategy space, is a consequence of the functional form of the Shahshahani metric.</footnote>
As a sanity check note that $v_i^\sharp$ evaluated at any $x \in \mathcal{X}$ is parallel to $\mathcal{X}_i$, since $\sum_{\alpha_i} v_{i\alpha_i}^\sharp(x) = \sum_{\alpha_i} x_{i\alpha_i} [u_i(\alpha_i; x_{-i}) - u_i(x)] = 0$ for all $i \in \mathcal{N}$ and all $x \in \mathcal{X}$.

**C.1. Full Shahshahani metric and individual gradient.** As discussed in Appendix B, the objects defining a game and a learning dynamics admit a full, redundant representation; and an effective one. In this section we use objects in the full representation to prove Proposition 1 from the main text, stating that that replicator dynamics are equivalent to the steepest individual payoff ascent dynamics with respect to the Shahshahani metric. In the next section, making use of the reduced representation, we present an alternative and more concise proof of the same result.

Given a finite game in normal form $\Gamma(\mathcal{N}, \mathcal{A}, u)$ let the mixed strategy of each player evolve according to (RD). For each player $i \in \mathcal{N}$ endow the positive orthant $\mathbb{R}_{++}^{A_i}$ with the Shahshahani metric given by Eq. (14) in the main text, and discussed in further detail in Appendix B.4. Using this metric we can give the following

**Definition 6.** The individual payoff gradient $\mathrm{grad}_i u_i$ of the payoff function $u_i$ is the vector field on $\mathbb{R}_{++}^{A_i}$ that is (a) parallel to $\mathcal{X}_i^\circ$, i.e., $\sum_{\alpha_i} [\mathrm{grad}_i u_i(x)]_{\alpha_i} = 0$ for all $x \in \mathcal{X}^\circ$; and (b) fulfills

$$ \langle \mathrm{grad}_i u_i(x), z_i \rangle = \partial u_i(x; z_i) \qquad (19) $$

for all $i \in \mathcal{N}$, $x \in \mathcal{X}^\circ$, and $z_i \in \mathbb{R}^{A_i}$ that are tangent to $\mathcal{X}_i^\circ$ (that is, $\sum_{\alpha_i \in \mathcal{A}_i} z_{i\alpha_i} = 0$).

*Remark C.1.* The definition is well-posed. From the material in Appendix A, we can use a Riemannian metric on $\mathbb{R}_{++}^{A_i}$ to define the gradient of a function by specifying the value of its inner product at all points with all vectors $z_i \in \mathbb{R}^{A_i}$. Condition (b) specifies this value for vectors in the hyperplane parallel to the simplex, leaving a degree of freedom to be specified - namely, the value of the inner product between the gradient and vectors that are normal to the simplex. Condition (a) fixes this gauge by requiring the gradient itself to be parallel to the simplex, thus giving zero inner product with normal vectors. This gauge-fixing procedure will be crucial in the proof of Proposition 1. ◇

We are now in position to prove Proposition 1 from the main body of the article, that we restate here for ease of reference:

**Proposition 1.** Under the Shahshahani metric, (RD) is equivalent to the steepest individual payoff ascent dynamics

$$ \dot{x}_i = \mathrm{grad}_i u_i(x) \qquad (20) $$

i.e., $v_i^\sharp(x) = \mathrm{grad}_i u_i(x)$ for all $i \in \mathcal{N}$.

*Proof.* Write $G_i := \mathrm{grad}_i u_i$; we have to show that

$$ G_{i\alpha_i}(x) = x_{i\alpha_i}[u_i(\alpha_i; x_{-i}) - u_i(x)] \qquad (C.4) $$

for all $x \in \mathcal{X}^\circ$, $i \in \mathcal{N}$, and $\alpha_i \in \mathcal{A}_i$. Let $z_i \in T_{x_i} \mathcal{X}_i^\circ$ be a tangent vector; by Eq. (B.22) its Shahshahani inner product with $G_i(x)$ is

$$ \langle G_i(x), z_i \rangle = \sum_{\alpha_i \beta_i} \frac{\delta_{\alpha_i \beta_i}}{x_{i\alpha_i}} G_{i\alpha_i} z_{i\beta_i} = \sum_{\alpha_i} \frac{G_{i\alpha_i}}{x_{i\alpha_i}} z_{i\alpha_i} \qquad (C.5) $$

for all $x \in \mathcal{X}^\circ$ (note in particular that $x_{i\alpha_i} \neq 0$). By condition (b) in the individual payoff gradient's definition, this inner product is also equal to $\langle G_i(x), z_i \rangle = \partial u_i(x, z_i) =$
$\sum_{\alpha_i} z_{i\alpha_i} \frac{\partial u_i(x)}{\partial x_{i\alpha_i}}$; equating the two expressions and rearranging the sums one gets

$$ \sum_{\alpha_i} z_{i\alpha_i} \left( \frac{G_{i\alpha_i}(x)}{x_{i\alpha_i}} - \frac{\partial u_i(x)}{\partial x_{i\alpha_i}} \right) = 0. \quad (*) $$

Denote the term in brackets by $B_{i\alpha_i}(x) := \frac{G_{i\alpha_i}(x)}{x_{i\alpha_i}} - \frac{\partial u_i(x)}{\partial x_{i\alpha_i}}$ and let $B_i(x) = (B_{i\alpha_i}(x))_{\alpha_i \in A_i}$; Eq. (*) then reads $z_i \cdot B_i(x) = 0$.

If we required this to hold for all $z_i \in \mathbb{R}^{A_i}$ then $B_i(x)$ should vanish identically; but since $z_i \in T_{x_i} \mathcal{X}_i^\circ$ it follows that $B_i(x)$ must belong to the annihilator of $T_{x_i} \mathcal{X}_i^\circ$, that is $\text{Span } \mathbf{1}_i$. In other words, the components of $B_i(x)$ must all be the same:

$$ B_{i\alpha_i}(x) = B_{i\beta_i}(x) = c_i(x) \quad \forall \alpha_i, \beta_i \in A_i, \quad \forall x \in \mathcal{X}^\circ, \quad (C.6) $$

for some function $c_i: \mathcal{X}^\circ \to \mathbb{R}$.

We can get to this result more explicitly also by expanding the sum in (*) and eliminating one of the components of $z_i$. Let $m_i + 1$ be the number of pure strategies of player i, and denote the set of their pure strategies by $A_i = \{0_i, 1_i, \dots, m_i\}$. Then letting the index $\alpha_i$ run from $0_i$ to $m_i$ and the index $\mu_i$ run from $1_i$ to $m_i$ we get

$$ \begin{aligned} 0 = \sum_{\alpha_i} z_{i\alpha_i} B_{i\alpha_i}(x) = z_{i0_i} B_{i0_i}(x) &+ \sum_{\mu_i} z_{i\mu_i} B_{i\mu_i}(x) = \\ &- \sum_{\mu_i} z_{i\mu_i} B_{i0_i}(x) + \sum_{\mu_i} z_{i\mu_i} B_{i\mu_i}(x) = \sum_{\mu_i} z_{i\mu_i} (B_{i\mu_i}(x) - B_{i0_i}(x)). \end{aligned} \quad (C.7) $$

This time the $z_{i\mu_i}$-s are $m_i$ unconstrained numbers, so the term in bracket must vanish identically, and we recover the sought after result that the components of $B_i(x)$ must all be the same. Plugging this fact in the definition of $B_{i\alpha_i}$ and solving for $G_{i\alpha_i}$ we get

$$ G_{i\alpha_i}(x) = x_{i\alpha_i} \left( \frac{\partial u_i(x)}{\partial x_{i\alpha_i}} + c_i(x) \right). \quad (C.8) $$

So far we only used condition (b) in Definition 6 of individual gradient. The last step consists of invoking condition (a) to fix the value of $c_i$ (this is the gauge-fixing procedure mentioned in Remark C.1):

$$ 0 = \sum_{\alpha_i} G_{i\alpha_i}(x) = \left( \sum_{\alpha_i} x_{i\alpha_i} \frac{\partial u_i(x)}{\partial x_{i\alpha_i}} \right) + c_i(x). \quad (C.9) $$

To conclude, $\partial u_i / \partial x_{i\alpha_i} = u_i(\alpha_i; x_{-i})$ by Eq. (2), so $c_i(x) = -u_i(x)$ and $G_{i\alpha_i}(x) = x_{i\alpha_i}[u_i(\alpha_i; x_{-i}) - u_i(x)]$. ■

### C.2. Effective Shahshahani metric and individual gradient.
In the previous section we work with objects in the full representation, showing that the individual gradients of the payoff functions give to the full expression (RD) of replicator dynamics. By working with object in the effective representation we can provide an alternative and more concise proof for this fact: in such representation the parallelism condition (a) in Definition 6 is automatically fulfilled, and one can use Lemma A.1 to verify that the individual gradients with respect to the effective Shahshahani metric (B.24) of the effective payoff functions give the effective replicator field (RD$_0$).

*Alternative proof of Proposition 1.* We need to verify that the matrix identity

$$ \tilde{v}_{i\mu_i}^{\sharp}(\tilde{x}) = [\tilde{g}_i^{-1} \tilde{d}_i \tilde{u}_i]_{\mu_i} = [\tilde{g}_i^{-1} \tilde{v}_i]_{\mu_i}(\tilde{x}) \quad (C.10) $$
<figure><img src="image_10.png" /><figcaption>**Figure 5:** Euclidean (orange) vs. Shahshahani (blue) individual payoff gradients in a 2 × 2 potential and harmonic game (left and right respectively). Dark dotted lines represent payoff contours, and red dotted lines (left figure only) represent contours of the potential function. The replicator dynamical system (C.16) is equivalent to individual Shahshahani gradient ascent; the figure shows how the functional form of the inverse Shahshahani metric given by Eq. (C.15), decaying to zero as the boundary is approached, is the key feature that confines replicator dynamics (blue) to the interior of the strategy space, whereas Euclidean steepest individual payoff ascent (orange) leads to hitting the boundary in finite time. The payoffs used in these examples are $u_1 = (2, 0, 3, 1)$, $u_2 = (2, 3, 0, 1)$ in Prisoner's Dilemma, that is potential with potential function $\phi = (-1, 0, 0, 1)$; and $u_1 = (3, -3, -3, 3)$, $u_2 = (-3, 3, 3, -3)$ in rescaled Matching Pennies, that is harmonic.</figcaption></figure>

holds true for all $i \in \mathcal{N}$, all $\mu_i \in \{1, \dots, m_i\}$, and all $\tilde{x} \in \mathcal{C}^o$. The effective replicator field $\tilde{v}_{i\mu_i}^{\sharp}(\tilde{x})$ on the left hand side is given by Eq. (28) (cf. Remark B.2 for the notation); the first equality comes from Lemma A.1 for the components of the gradient field; and the second equality holds true because the individual differential of the effective payoff function is the effective payoff field by Eq. (B.5).

The inverse matrix $\tilde{g}_i^{-1}$ of the effective Shahshahani metric (B.24) can be computed by the Sherman-Morrison formula:

$$ \tilde{g}_i^{-1}(\tilde{x}) = \delta_{\mu_i \nu_i} \tilde{x}_{i\mu_i} - \tilde{x}_{i\mu_i} \tilde{x}_{i\nu_i} \qquad (C.11) $$

for all $i \in \mathcal{N}$, $\mu_i$, $\nu_i \in \{1, \dots, m_i\}$, $\tilde{x} \in \mathcal{C}^o$; cf. [51, Sec. 2]. By matrix multiplication one then gets the sought after expression for the effective replicator field:

$$ \sum_{\nu_i} \tilde{g}_{i\mu_i\nu_i}^{-1} \tilde{v}_{i\nu_i}(\tilde{x}) = \sum_{\nu_i} (\delta_{\mu_i\nu_i} \tilde{x}_{i\mu_i} - \tilde{x}_{i\mu_i} \tilde{x}_{i\nu_i}) \tilde{v}_{i\nu_i} = \tilde{x}_{i\mu_i} \left[ \tilde{v}_{i\mu_i}(\tilde{x}) - \sum_{\nu_i} \tilde{x}_{i\nu_i} \tilde{v}_{i\nu_i}(\tilde{x}) \right] = \tilde{v}_{i\mu_i}^{\sharp}(\tilde{x}). \qquad (C.12) $$

<figure><img src="image_11.png" /></figure>

In conclusion, the effective replicator dynamics are given by individual steepest ascent on effective payoff functions with respect to the effective Shahshahani metric. It is illustrative to see in a simple example how the functional form of the effective Shahshahani metric guarantees that such dynamics remain confined to the interior of the strategy space.

**Example C.1** (Shahshahani metric and replicator dynamics in a 2 × 2 game). In a 2 × 2 game the effective strategy space of each player is one dimensional, i.e., $\mu_i$ and $\nu_i$ belong to the singleton $\{1_i\}$ for $i \in \{1, 2\}$. As discussed in Example B.1 the two reduced payoff fields,
with one component each, are

$$ \tilde{v}_1(\tilde{x}_1, \tilde{x}_2) = \tilde{x}_2[u_1(0,0) - u_1(0,1) - u_1(1,0) + u_1(1,1)] - u_1(0,0) + u_1(1,0) \quad (C.13) $$

$$ \tilde{v}_2(\tilde{x}_1, \tilde{x}_2) = \tilde{x}_1[u_2(0,0) - u_2(0,1) - u_2(1,0) + u_2(1,1)] - u_2(0,0) + u_2(0,1) \quad (C.14) $$

By Eq. (C.11) the effective inverse Shahshahani metric on each 1-dimensional open corner of cube $C^\circ = (0,1) \subset \mathbb{R}$ has only one component given by

$$ \begin{aligned} \tilde{g}_1^{-1}(\tilde{x}_1, \tilde{x}_2) &= \tilde{x}_1(1 - \tilde{x}_1) \\ \tilde{g}_2^{-1}(\tilde{x}_1, \tilde{x}_2) &= \tilde{x}_2(1 - \tilde{x}_2) \end{aligned} \quad (C.15) $$

This functional form of the inverse Shahshahani metric is the key feature alluded at in Remark B.3 that confines the replicator dynamics to the interior of the strategy space $C$, as opposed to steepest individual payoff ascent with respect to the Euclidean metric, that leads to hitting the boundary in finite time. Expanding $\tilde{g}_i^{-1}$ around $\tilde{x}_i = 0.5$ we see that $\tilde{g}_i^{-1}(\tilde{x}) \approx 0.25$, i.e., toward the middle of the open corner of cube $C^\circ$ the Shahshahani metric is just a rescaled version of the Euclidean metric $\tilde{g}_i^{-1} = 1$. On the other hand $\lim_{\tilde{x}_i \to 0^+} \tilde{g}_i^{-1}(\tilde{x}) = \lim_{\tilde{x}_i \to 1^-} \tilde{g}_i^{-1}(\tilde{x}) = 0$, i.e., toward the boundary of $C^\circ$ the inverse Shahshahani metric goes to zero, dampening the dynamics and bounding it to the interior of $C$:

$$ \left\{ \begin{aligned} \tilde{v}_1^\sharp(\tilde{x}) &= \dot{\tilde{x}}_1 = \tilde{g}_1^{-1}\tilde{v}_1 = \tilde{x}_1(1 - \tilde{x}_1)\tilde{v}_1(\tilde{x}) = \tilde{x}_1[\tilde{v}_1(\tilde{x}) - \tilde{x}_1\tilde{v}_1(\tilde{x})] \\ \tilde{v}_2^\sharp(\tilde{x}) &= \dot{\tilde{x}}_2 = \tilde{g}_2^{-1}\tilde{v}_2 = \tilde{x}_2(1 - \tilde{x}_2)\tilde{v}_2(\tilde{x}) = \tilde{x}_2[\tilde{v}_2(\tilde{x}) - \tilde{x}_2\tilde{v}_2(\tilde{x})] \end{aligned} \right. \quad (C.16) $$

which are Eq. (28) for a 2 × 2 game (cf. Remark B.2 for the notation). The orbits of this dynamical system are plotted in Fig. 5 for Prisoner's Dilemma (potential) and Matching Pennies (harmonic). ◇

### C.3. Differential characterizations of potential games.
We conclude this appendix with two characterizations of exact potential games in the sense of Monderer & Shapley [66].

**Definition 7.** The effective payoff field $\tilde{v}$ of a finite game $\Gamma(\mathcal{N}, \mathcal{A}, u)$ is called exact if it is the differential of a function, namely if there exist a function $\phi: \mathcal{A} \to \mathbb{R}$, called potential, such that $\tilde{v}_i(\tilde{x}) = \tilde{d}_i\tilde{\phi}(\tilde{x})$ for all $\tilde{x} \in \mathcal{C}$ and all $i \in \mathcal{N}$.

**Remark C.2.** We denote a function $\phi: \mathcal{A} \to \mathbb{R}$ and its multilinear extension $\phi: \mathcal{X} \to \mathbb{R}$, $\phi(x) = \sum_{\alpha} x_{\alpha}\phi(\alpha)$ by the same symbol, and it is understood that it is the multilinear extension undergoing differentiation. As in Remark B.1, the differential df of a differentiable function $f$ is the array of partial derivatives of the function. A tilde denotes as usual effective objects, and $\tilde{d}_i$ denotes the array of partial derivatives with respect to the $\tilde{x}_i$ coordinates. ◇

Recall from the main text that a finite game $\Gamma$ is exact-potential in the sense of Monderer & Shapley [66] if it admits a potential function $\phi: \mathcal{X} \to \mathbb{R}$ such that

$$ u_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i}) = \phi(\beta_i; \alpha_{-i}) - \phi(\alpha_i; \alpha_{-i}) \quad (PG) $$

for all $\alpha, \beta \in \mathcal{A}$ and all $i \in \mathcal{N}$. The notion of exactness for the effective payoff field allows for an equivalent characterization:

**Lemma C.2.** A finite game $\Gamma(\mathcal{N}, \mathcal{A}, u)$ is exact-potential in the sense of Monderer & Shapley [66] if and only if its effective payoff field $\tilde{v}$ is exact.

*Proof.* Assume that $\tilde{v}$ is exact with potential $\phi$. Then by chain rule $\tilde{v}_{i\mu_i}(\tilde{x}) = \tilde{\partial}_{i\mu_i}\tilde{\phi}(\tilde{x}) = (\partial_{i\mu_i} - \partial_{i0_i})\phi(x)$, for all $i \in \mathcal{N}$, $\mu_i \in \{1, \dots, m_i\}$, and $\tilde{x} \in \mathcal{C}$. Since $\tilde{v}_{i\mu_i}(\tilde{x}) = v_{i\mu_i}(x) - v_{i0_i}(x)$ we conclude that $u_i(\alpha_i, x_{-i}) - u_i(0_i, x_{-i}) = \phi(\alpha_i, x_{-i}) - \phi(0_i, x_{-i})$ for all $i \in \mathcal{N}$, $\alpha_i \in \{0, \dots, m_i\}$, and $x \in \mathcal{X}$, implying in turn that the game is potential by Lemma B.4.
Conversely, assume that $\Gamma(\mathcal{N}, \mathcal{A}, u)$ is potential; then the sequence of arguments is reversed without any change, showing that $\tilde{v}$ is exact. ■

In the context of population games this result can be found in Sandholm [74, Chapter 3.2.2]. The interpretation of this lemma is the following: Recall by Eq. (B.5) that the effective payoff field $\tilde{v}$ of a game is the array of individual differentials of the effective payoff functions, i.e., $\tilde{v} = (\tilde{d}_i\tilde{u}_i)_{i \in \mathcal{N}}$. As such, in general $\tilde{v}$ is not the differential of a function; Lemma C.2 says that a game is potential precisely when this is the case, namely when $\tilde{v} = (\tilde{d}_i\tilde{\phi})_{i \in \mathcal{N}} = \tilde{d}\tilde{\phi}$.

The differential characterization of potential games given above, relying on the notion of exact effective payoff field, is intrinsic of a game and *independent* of any choice of metric. Yet, if a Riemannian metric on $\mathcal{X}^\circ$ is available, the metric's non-degeneracy allows for another characterization of potential games, in a sense dual to the one given above.

Given a Riemannian metric $g$ on $\mathcal{X}^\circ$, and leveraging Lemma A.1 relating the gradient and the differential of a function via the matrix of the metric, we say that a vector field $F$ on $\mathcal{X}^\circ$ is the gradient of a function $\phi$ if $F = g^{-1} \cdot d\phi$, where $\cdot$ denotes matrix multiplication. With this in mind we can give the following

**Lemma C.3.** Given a Riemannian metric $g$ on $\mathcal{X}^\circ$, a finite game $\Gamma(\mathcal{N}, \mathcal{A}, u)$ is an exact potential game if and only if its field of effective individual payoff gradients, denoted by $\tilde{v}^\sharp$, is the gradient of a function, namely if there exists a function $\phi: \mathcal{A} \to \mathbb{R}$ such that $\tilde{v}^\sharp = \tilde{g}^{-1} \cdot \tilde{d}\tilde{\phi}$.

*Proof.* The field of effective individual payoff gradients of a game is

$$ \tilde{v}^{\sharp} = (\tilde{g}_{i}^{-1} \cdot \tilde{d}_{i} \tilde{u}_{i})_{i \in \mathcal{N}} = (\tilde{g}_{i}^{-1} \cdot \tilde{v}_{i})_{i \in \mathcal{N}}. \qquad (C.17) $$

This field is a gradient if there exists a function $\phi: \mathcal{A} \to \mathbb{R}$ such that

$$ \tilde{v}^{\sharp} = \tilde{g}^{-1} \cdot \tilde{d}\tilde{\phi} = (\tilde{g}_{i}^{-1} \cdot \tilde{d}_{i}\tilde{\phi})_{i \in \mathcal{N}}, \qquad (C.18) $$

where $\tilde{\phi}: \mathcal{C} \to \mathbb{R}$ is the effective representation of the multilinear extension of $\phi: \mathcal{A} \to \mathbb{R}$. By non degeneracy of the Riemannian metric $g$, the effective field of individual gradients is a gradient if and only if $\tilde{v}_i = \tilde{d}_i\tilde{\phi}$ for all $i \in \mathcal{N}$, i.e., if the effective payoff field is exact, which is equivalent to $\Gamma(\mathcal{N}, \mathcal{A}, u)$ being an exact potential game by Lemma C.2. ■

An example of this result is given by Kimura's maximum principle [47, 75], which states that, in potential games, replicator dynamics (that is, the dynamics given by the field of individual payoff Shahshahani gradients) is a Shahshahani gradient system. Lemma C.3 provides a broad generalization of this principle: in a potential game, given any metric $g$, the dynamics given by the field of individual payoff $g$-gradients is a $g$-gradient dynamics in its own right.

Full potential games. By Lemma C.2, a finite game in normal form is potential if and only if its *effective* payoff field is exact. In the context of population games, Sandholm [74, Chapter 3.1] calls a game such that the *full* payoff field is exact, i.e., $v = d\phi$, a *full potential game*. One can show that if the full payoff field of the game is exact then the *effective* payoff field is exact too, but the converse needs not be true. In other words, $v = d\phi$ is a sufficient but not necessary condition for a game to be potential. We illustrate this fact with a simple example; for further details on the relation between potential games and full potential games we refer the reader to Sandholm [74, Chapter 3.2.3].
**Example C.2.** Consider the 2 × 2 potential game with payoffs u and potential function φ given by

$$u = \begin{pmatrix} (2, 2) & (0, 3) \\ (3, 0) & (1, 1) \end{pmatrix}, \quad \phi = \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}. \qquad (C.19)$$

The corresponding replicator dynamics are plotted in Fig. 5, left. Replacing for notational simplicity $(x_{1,0}, x_{1,1}) \to (x_0, x_1)$ and $(x_{2,0}, x_{2,1}) \to (y_0, y_1)$ we have from Example B.1 that the full payoff field is

$$v(x_0, x_1, y_0, y_1) = (2y_0, 3y_0 + y_1, 2x_0, 3x_0 + x_1). \qquad (C.20)$$

A simple check shows that $\partial_{y_0}v_{x_1} = 3 \neq 0 = \partial_{x_1}v_{y_0}$ which, by a routine application of Poincaré's lemma [41], implies that $v$ is not the differential of a function. On the other hand, the reduced payoff field is

$$\tilde{v}(\tilde{x}_1, \tilde{y}_1) = (1, 1), \qquad (C.21)$$

which is exact, since it is the differential of any function $\tilde{\phi}(\tilde{x}_1, \tilde{y}_1) = \tilde{x}_1 + \tilde{y}_1 + \text{const}$. Note that the multilinear extension of the potential function of the game is $\phi(x_0, x_1, y_0, y_1) = -x_0y_0 + x_1y_1$, and its reduced form is $\phi(\tilde{x}_1, \tilde{y}_1) = -(1 - \tilde{x}_1)(1 - \tilde{y}_1) + \tilde{x}_1\tilde{y}_1 = \tilde{x}_1 + \tilde{y}_1 - 1$, showing that, albeit the full payoff field is not exact, the reduced payoff field is the differential of the reduced multilinear extension of the potential function of the game.

## APPENDIX D. PROOFS ON INCOMPRESSIBLE GAMES

The results presented here heavily rely on the mathematical tools of Appendix A, which we therefore recommend reading first.

**D.1. Shahshahani divergence.** In this section we prove the results given in Section 5. They all revolve around the expression of the Shahshahani divergence of the effective replicator field that – as discussed in more detail in Appendix A.3 – is given by Eq. (27) from the main text:

$$\operatorname{div}_i v_i^{\sharp}(\tilde{x}) = \frac{1}{\sqrt{\det \tilde{g}_i(\tilde{x}_i)}} \sum_{\mu_i=1}^{m_i} \frac{\partial}{\partial \tilde{x}_{i\mu_i}} \left( \sqrt{\det \tilde{g}_i(\tilde{x}_i)} v_{i\mu_i}^{\sharp}(\tilde{x}) \right) \quad \text{for all } i \in \mathcal{N}. \qquad (27)$$

By Lemma A.3, the divergence operator on a product manifold – which in our case is the product $C^\circ = \prod_i C^\circ_i$ of open corner of cubes, where the effective game described in Appendix B lives – is given by the sum of the divergence operators on the factor manifolds, which justifies Definition 1 of incompressible games given in Section 4:

**Definition 1.** A finite game $\Gamma \equiv \Gamma(\mathcal{N}, \mathcal{A}, u)$ will be called *incompressible* relative to the Shahshahani metric when

$$\operatorname{div} v^{\sharp}(\tilde{x}) := \sum_{i \in \mathcal{N}} \operatorname{div}_i v_i^{\sharp}(\tilde{x}) = 0. \qquad (29)$$

We devote the rest of this section to the proof of the following result:

**Proposition D.1.** *The Shahshahani divergence of the effective replicator field of a finite game $\Gamma(\mathcal{N}, \mathcal{A}, u)$ is*

$$\operatorname{div} v^{\sharp}(\tilde{x}) = +\frac{1}{2} \sum_{i \in \mathcal{N}} \sum_{\alpha_i \in \mathcal{A}_i} (v_{i\alpha_i}(x) - u_i(x)). \qquad (D.1)$$
Proof. To prove this result we will first compute $div_i v_i^\#(\tilde{x})$ for some $i \in \mathcal{N}$, dropping the index $i$ for notational simplicity. Recall by Eq. (A.6) that the expression for the divergence can be rewritten by product rule as the sum of two terms, one metric-dependent and one metric-independent:

$$ \operatorname{div}_i v_i^\#(\tilde{x}) \underset{\sim}{\overset{\text{Drop } i \text{ index}}{\equiv}} \operatorname{div} v^\#(\tilde{x}) = \sum_{\mu=1}^{m} \left( \frac{\partial_{\tilde{x}_\mu} \sqrt{\det \tilde{g}}}{\sqrt{\det \tilde{g}}} \right) v_\mu^\#(\tilde{x}) + \sum_{\mu=1}^{m} \partial_{\tilde{x}_\mu} v_\mu^\#(\tilde{x}), \quad (D.2) $$

where $\partial_{\tilde{x}_\mu}$ is a shorthand for $\frac{\partial}{\partial \tilde{x}_\mu}$, and $\det \tilde{g}$ is given by Eq. (B.26):

$$ \det \tilde{g}(\tilde{x}) = \frac{1}{\left(1 - \sum_{\mu=1}^{m} \tilde{x}_{\mu}\right) \prod_{\nu=1}^{m} \tilde{x}_{\nu}} = \frac{1}{x_0 \prod_{\nu=1}^{m} \tilde{x}_{\nu}}. \quad (B.26) $$

Metric-independent term of the divergence. Denote by $\bar{v}(x) := \sum_\alpha x_\alpha v_\alpha(x)$, and by $\tilde{v}(\tilde{x}) := \sum_\mu \tilde{x}_\mu \tilde{v}_\mu(\tilde{x})$, so that the full and effective replicator dynamics (with player index suppressed) read

$$ \dot{x}_{\alpha} = v_{\alpha}^{\#}(x) = x_{\alpha}[v_{\alpha}(x) - \bar{v}(x)] \quad \text{for all } \alpha = 0, \dots, m, \quad (D.3a) $$

$$ \dot{\tilde{x}}_{\mu} = v_{\mu}^{\#}(\tilde{x}) = \tilde{x}_{\mu}[\tilde{v}_{\mu}(\tilde{x}) - \bar{v}(\tilde{x})] \quad \text{for all } \mu = 1, \dots, m. \quad (D.3b) $$

Remark D.1. Reinserting for the scope of this remark the player index, a simple check shows that $\tilde{v}_i(\tilde{x}) = \bar{v}_i(x) - v_{i0_i}(x)$; note that $\bar{v}_i(x)$ is precisely the full payoff function $u_i(x)$, while $\tilde{v}_i(\tilde{x})$ is not the effective payoff function $\tilde{u}_i(\tilde{x})$, the difference between the two being precisely $v_{i0_i}(x)$. $\diamond$

As usual, the indices $\mu$ and $\nu$ appearing in the following expressions are understood to run over $1, \dots, m$; and the indices $\alpha$ and $\beta$ are understood to run over $0, \dots, m$. With these notational caveats in place, the metric-independent term of the divergence reads

$$ \begin{aligned} \sum_{\mu} \partial_{\tilde{x}_{\mu}} v_{\mu}^{\#}(\tilde{x}) &= \sum_{\mu} \partial_{\tilde{x}_{\mu}} (\tilde{x}_{\mu}(\tilde{v}_{\mu}(\tilde{x}) - \tilde{v}(\tilde{x}))) \\ &= \sum_{\mu} (\tilde{v}_{\mu} - \bar{v}) + \sum_{\mu} \tilde{x}_{\mu} \partial_{\tilde{x}_{\mu}} \tilde{v}_{\mu} - \bar{v} - \sum_{\mu \nu} \tilde{x}_{\mu} \tilde{x}_{\nu} \partial_{\tilde{x}_{\mu}} \tilde{v}_{\nu}. \end{aligned} \quad (D.4) $$

By Lemma B.3 the second and fourth terms vanish: re-inserting the player index $i \in \mathcal{N}$, $\frac{\partial \tilde{v}_{i\nu_i}}{\partial \tilde{x}_{i\mu_i}}(\tilde{x}) = 0$ since the components of the reduced payoff field of player $i \in \mathcal{N}$ do not depend on the mixed coordinates of player $i$. This leads to

$$ \sum_{\mu} \partial_{\tilde{x}_{\mu}} v_{\mu}^{\#}(\tilde{x}) = \sum_{\mu} (v_{\mu} - v_0 - \bar{v} + v_0) - \bar{v} + v_0 = \sum_{\alpha} (v_{\alpha} - \bar{v}), \quad (D.5) $$

and in conclusion the metric-independent term of the divergence $\operatorname{div} v^\#(\tilde{x})$ is

$$ \sum_{\mu} \partial_{\tilde{x}_{\mu}} v_{\mu}^{\#}(\tilde{x}) = \sum_{\alpha} (v_{\alpha}(x) - \bar{v}(x)), \quad (D.6) $$

where it is understood that effective objects (i.e., containing the effective payoff field $\tilde{v}$) are evaluated at $\tilde{x}$, and full objects (i.e., containing the full payoff field $v$) are evaluated at $x$, with $x$ and $\tilde{x}$ related as usual by the map $\pi_0$ of Eq. (B.2).

In settings with non-multilinear utility functions, such as games with continuous action sets and differentiable payoff functions [55, 62, 73], the terms of Eq. (D.4) containing derivatives of the payoff field do not necessarily vanish; as a reference for possible applications to these settings we provide below the version of Eq. (D.6) including such terms. To this end denote
by $B = J\tilde{v}$ the Jacobian matrix of the effective payoff field, i.e., $B_{\nu\mu} = \partial_{\tilde{x}_{\mu}}\tilde{v}_{\nu}$, and recall that $\tilde{v}_{\mu} = v_{\mu} - v_0$ to rewrite Eq. (D.4) as

$$ \sum_{\mu} \partial_{\tilde{x}_{\mu}} v_{\mu}^{\sharp}(\tilde{x}) = \sum_{\alpha} (v_{\alpha} - \bar{v}) + \left( \sum_{\mu} \tilde{x}_{\mu} B_{\mu\mu} - \sum_{\mu\nu} \tilde{x}_{\mu} \tilde{x}_{\nu} B_{\mu\nu} \right). \quad (D.7) $$

The idea now is that of re-arranging the terms that contain effective coordinates $\tilde{x}$ and combine them into objects expressed in terms of full coordinates $x$. After a straightforward but tedious computation leveraging Lemma B.2 the second term on the right hand side can be expressed in terms of full objects as

$$ \sum_{\mu} \tilde{x}_{\mu} B_{\mu\mu} - \sum_{\mu\nu} \tilde{x}_{\mu} \tilde{x}_{\nu} B_{\mu\nu} = \sum_{\alpha} x_{\alpha} \partial_{\alpha} v_{\alpha} - \sum_{\alpha\beta} x_{\alpha} x_{\beta} \partial_{\alpha} v_{\beta}. \quad (D.8) $$

Metric-dependent term of the divergence. A direct computation shows that

$$ \frac{\partial_{\tilde{x}_{\mu}} \sqrt{\det \tilde{g}}}{\sqrt{\det \tilde{g}}} = -\frac{1}{2} \frac{\tilde{x}_{0} - \tilde{x}_{\mu}}{\tilde{x}_{0} \tilde{x}_{\mu}}. \quad (D.9) $$

Again, one needs to manipulate the terms containing effective coordinates to express them in terms of full coordinates. After an elementary but lengthy calculation, we obtain that the metric-dependent term of the divergence $\mathrm{div} v^{\sharp}(\tilde{x})$ is

$$ \sum_{\mu} v_{\mu}^{\sharp}(\tilde{x}) \frac{\partial_{\tilde{x}_{\mu}} \sqrt{\det \tilde{g}}}{\sqrt{\det \tilde{g}}} (\tilde{x}) = -\frac{1}{2} \sum_{\alpha} (v_{\alpha}(x) - \bar{v}(x)). \quad (D.10) $$

Conclusion. Summing Eqs. (D.6) and (D.10) and re-inserting the player index we finally get

$$ \mathrm{div}_i v_i^{\sharp}(\tilde{x}) = +\frac{1}{2} \sum_{\alpha_i \in A_i} (v_{i\alpha_i}(x) - u_i(x)), \quad (D.11) $$

and the proof is completed by summing over the player index $i \in \mathcal{N}$. ■

To conclude this section we provide an equivalent expression for the Shahshahani divergence of the effective replicator field. For all $i \in \mathcal{N}$ define the barycenter $b_i \in \mathcal{X}_i$ as the point with coordinates

$$ \mathbf{b}_{i\alpha_i} := \frac{1}{A_i} \quad \text{for all } \alpha_i \in A_i \quad (D.12) $$

on the mixed strategy space $\mathcal{X}_i$ of player $i \in \mathcal{N}$, where $A_i = |A_i|$ is the number of pure strategies of player $i$. Similarly, define $\mathbf{1}_i := (1, \dots, 1) \in \mathbb{R}^{A_i}$. Then

**Lemma D.1 (Equivalent expression of the Shahshahani divergence).** The Shahshahani divergence of the effective replicator field of a finite game $\Gamma(\mathcal{N}, \mathcal{A}, u)$ fulfills

$$ - \mathrm{div} v^{\sharp}(\tilde{x}) = \frac{1}{2} \sum_{i \in \mathcal{N}} \sum_{\alpha_i \in A_i} (u_i - v_{i\alpha_i})(x) = \frac{1}{2} \sum_i A_i v_i(x) \cdot (x_i - \mathbf{b}_i). \quad (D.13) $$

*Proof.* From Proposition D.1 and the application of definitions it follows that

$$ \begin{aligned} - \mathrm{div} v^{\sharp}(\tilde{x}) &= \frac{1}{2} \sum_{i \in \mathcal{N}} \sum_{\alpha_i \in A_i} (u_i - v_{i\alpha_i})(x) = \frac{1}{2} \sum_i (A_i u_i - v_i \cdot \mathbf{1}_i)(x) \\ &= \frac{1}{2} \sum_i A_i (u_i - v_i \cdot \mathbf{b}_i)(x) = \frac{1}{2} \sum_i A_i v_i(x) \cdot (x_i - \mathbf{b}_i). \quad \blacksquare \end{aligned} $$
D.2. **Incompressible games are precisely harmonic games.** The expression of the Shahshahani divergence of the field of individual Shahshahani payoff gradients of a game div $v^\#(\tilde{x})$ allows to establish an important connection between incompressible games, i.e., those game for which div $v^\#$ vanishes identically, and the harmonic games introduced by Candogan et al. [14]. Recall by Eq. (HG) that a game is harmonic if

$$ \sum_{i \in \mathcal{N}} \sum_{\beta_i \in \mathcal{A}_i} [u_i(\beta_i; \alpha_{-i}) - u_i(\alpha_i; \alpha_{-i})] = 0 \qquad (\text{HG}) $$

for all $\alpha \in \mathcal{A}$. With this at hand we can prove Theorem 2:

**Theorem 2.** A finite game is harmonic if and only if it is incompressible. In particular, up to strategic equivalence, the decompositions (5) and (30) coincide.

*Proof.* Begin by noting that the Eq. (HG) characterizing harmonic games can be recast as $F(\alpha) = 0$ for all $\alpha \in \mathcal{A}$, with $F: \mathcal{A} \to \mathbb{R}$ defined by

$$ \begin{aligned} F(\alpha) &:= \sum_{i \in \mathcal{N}} \sum_{\beta_i \in \mathcal{A}_i} (u_i(\beta_i, \alpha_{-i}) - u_i(\alpha_i, \alpha_{-i})) \\ &= \sum_i \left[ \left( \sum_{\beta_i} u_i(\beta_i, \alpha_{-i}) \right) - A_i u_i(\alpha) \right]. \end{aligned} \qquad (\text{D.14}) $$

We claim that the Shahshahani divergence of the effective replicator field of a finite game is (up to a factor of 1/2) the multilinear extension of the function $F$ defined above:

$$ \operatorname{div} v^{\#}(\tilde{x}) = \frac{1}{2} \bar{F}(x) := \frac{1}{2} \sum_{\alpha \in \mathcal{A}} x_{\alpha} F(\alpha), \qquad (\text{D.15}) $$

for all $\tilde{x} \in \mathcal{C}$. If we show this the proof is concluded, since invoking Lemma B.4 we have

$$ \begin{aligned} & \text{harmonic} \iff F \equiv 0, \\ & \text{incompressible} \iff \bar{F} \equiv 0, \\ & F \equiv 0 \iff \bar{F} \equiv 0. \end{aligned} \qquad (\text{D.16}) $$

Eq. (D.15) is verified by a standard multilinear calculation:

$$ \bar{F}(x) = \sum_{\alpha \in \mathcal{A}} x_{\alpha} F(\alpha) = \sum_{i} \left[ \left( \sum_{\beta_i} u_i(\beta_i, x_{-i}) \right) - A_i u_i(x) \right] = \sum_{i} (v_i \cdot \mathbf{1}_i - A_i u_i)(x) \quad (\text{D.17}) $$

for all $x \in \mathcal{X}$; so from Lemma D.1 we have that $\operatorname{div} v^\# = 1/2 \bar{F}$, concluding the proof. ■

Having established the equivalence between harmonic and incompressible games, the following decomposition result comes as an immediate corollary of the strategic decomposition (5):

**Theorem 1.** Every finite game $\Gamma$ can be decomposed as

$$ \Gamma = \Gamma_{\text{pot}} + \Gamma_{\text{inc}} \qquad (30) $$

where $\Gamma_{\text{pot}}$ is potential and $\Gamma_{\text{inc}}$ is incompressible. In particular, at the vector field level, we have

$$ v^{\#} = \operatorname{grad} \phi + B \qquad (31) $$

where $\phi$ is a potential for $\Gamma_{\text{pot}}$ and $B$ is incompressible in the sense of (29).
**Proof.** As shown by Candogan et al. [14] every finite game can be decomposed as the sum of a potential and a harmonic game, which gives the decomposition $\Gamma = \Gamma_{pot} + \Gamma_{inc}$ in light of the fact that a game is incompressible if and only if it is harmonic.

As for the second point, the field of individual gradients of the incompressible game $\Gamma_{inc}$ is incompressible by definition; and Lemma C.3 asserts that a game is an exact potential game in the sense of Monderer & Shapley [66] if and only if its effective field of individual gradients is the Riemannian gradient of a function $\phi$, i.e., the field $v^\sharp$ of the potential game $\Gamma_{pot}$ can be expressed as grad $\phi$. ■

### D.3. Dynamics on incompressible games and Poincaré's recurrence.
Finally we turn our attention at the dynamical properties of replicator dynamics on incompressible games; our first result is a consequence of the Riemannian version of Liouville's theorem presented in Appendix A.4.

**Proposition 2.** If $\Gamma$ is incompressible, (RD) is volume-preserving under the Shahshahani volume form (32).

**Proof.** By definition, a game is incompressible if and only if the Shahshahani divergence of the field $v^\sharp(\tilde{x})$ vanishes identically. Since (RD) is the dynamical system on $C^\circ$ given by $\dot{\tilde{x}} = v^\sharp(\tilde{x})$, as a consequence of Liouville's theorem (cf. Eq. (A.13)) we have that $\text{vol}(U_t) = \text{vol}(U)$ for all open sets $U \subseteq C^\circ$ and all $t \in \mathbb{R}$, meaning that (RD) is volume-preserving with respect to the Shahshahani volume form. ■

Our next result shows that replicator dynamics on incompressible games admit a constant of motion.

**Theorem 3.** If $\Gamma$ is incompressible, the induced dynamics (EW) / (RD) admit a constant of motion. Specifically, there exists a function $E: X^\circ \to \mathbb{R}$ such that $E(x(t)) = E(x(0))$ for every initial condition $x(0) \in X^\circ$.

**Proof.** For each $i \in \mathcal{N}$ consider the Kullback-Leibler divergence with respect to the barycenter $KL_{b_i}: X_i^\circ \to \mathbb{R}$,

$$KL_{b_i}(x_i) = \sum_{\alpha_i \in \mathcal{A}_i} b_{i\alpha_i} \log \frac{b_{i\alpha_i}}{x_{i\alpha_i}}. \qquad (D.18)$$

and scale it by the number $A_i$ of pure strategies of player $i$:

$$E_i(x_i) := A_i KL_{b_i}(x_i) = - \left( A_i \log A_i + \sum_{\alpha_i \in \mathcal{A}_i} \log x_{i\alpha_i} \right). \qquad (D.19)$$

The derivative of $E_i$ along a solution trajectory of (RD) is $\frac{d}{dt}E_i(x_i(t)) = -\sum_{\alpha_i \in \mathcal{A}_i} \frac{\dot{x}_{i\alpha_i}}{x_{i\alpha_i}} = -\sum_{\alpha_i \in \mathcal{A}_i}[v_{i\alpha_i}(x) - u_i(x)]$, so by Proposition D.1,

$$\text{div} v^\sharp(\tilde{x}(t)) = -\frac{1}{2} \frac{d}{dt} \sum_{i \in \mathcal{N}} E_i(x_i(t)) \quad \text{along RD.} \qquad (D.20)$$

It follows that the $A_i$-weighted sum $E: X^\circ \to \mathbb{R}$ of Kullback-Leibler divergences with respect to the barycenter,

$$E(x) := \sum_{i \in \mathcal{N}} E_i(x_i) = \sum_{i \in \mathcal{N}} A_i KL_{b_i}(x_i) = - \left( \sum_{i \in \mathcal{N}} \sum_{\alpha_i \in \mathcal{A}_i} \log x_{i\alpha_i} + \text{const} \right), \qquad (D.21)$$

is a constant of motion for the (EW) / (RD) dynamics on incompressible games, with $\text{const} = \sum_i A_i \log A_i$. ■
The function $E: \mathcal{X}^\circ \to \mathbb{R}$ is a nonnegative weighted sum of convex functions, hence it is convex. Its sublevel sets are then compact convex sets, and as such homeomorphic to closed balls, making in turn their boundaries – the level sets of $E$ – homeomorphic to $[(\sum_i A_i) - N - 1]$-dimensional spheres. Since RD solution trajectories are constrained to the level sets of the integral of motion $E$, this shows that $\mathcal{X}^\circ$ admits a foliation under replicator dynamics on harmonic games with leaves given by concentric topological spheres, as mentioned in Section 5 in the main body of the article.

Remark D.2 (Harmonic vs. zero-sum games). In two-player ZSGs with an interior Nash equilibrium $x^*$ the sum of Kullback-Leibler divergences with respect to said equilibrium, $\sum_i KL_{x^*}(x_i)$, is a constant of motion for replicator dynamics [63]. Harmonic games and ZSGs have non-trivial intersection; in particular, normalized harmonic games where all players have the same number of strategies are zero-sum [14]. In this case the $A_i$-s factor out from Eq. (D.21), and the two constants of motions coincide, up to affine transformations.

Despite having non-trivial intersection, harmonic and ZSGs exhibit some very different properties. A ZSG can also be a potential game, while the only harmonic game which admits a potential is the zero game (up to strategic equivalence)[14]; Harmonic games always admit a fully mixed equilibrium [14], while ZSGs do not (that is, not always); ZSGs may admit strict Nash equilibria, while harmonic games never do; replicator dynamics are recurrent in ZSGs with a fully mixed equilibrium [63] but convergent in ZSGs with a strict equilibrium [60], while they are always recurrent in harmonic games (Theorem 4). As minimal example setting apart harmonic and zero-sum games consider the $2 \times 3$ game with payoffs

$$u_1 = \begin{pmatrix} a & b & -a-b \\ -a & -b & a+b \end{pmatrix} \quad \text{and} \quad u_2 = -\frac{2}{3}u_1. \qquad (D.22)$$

This game is harmonic for every choice of $a, b \in \mathbb{R}$, and never zero-sum (except for the trivial case). ◇

Poincaré recurrence in mixed strategy space. We turn now to our last result, namely to the fact that replicator dynamics on harmonic games are recurrent in the sense of Poincaré [70].

Several works in the literature [63, 69] discuss Poincaré recurrence in the context of zero-sum games with an interior Nash equilibrium, and positive affine transformations or polymatrix/network versions of the above. The idea is to transform via a suitable diffeomorphism the replicator system in the interior of the strategy space to a system which is divergence-free under the Euclidean metric; and to show that, under this transformations, all the orbits of RD in the particular class of games at hand are bounded, e.g., by exhibiting a constant of motion with bounded level sets.

We tackle the problem from a different angle: our proof relies on the fact that in harmonic games the replicator system itself – without undergoing any transformation – is volume-preserving under the Shahshahani metric, and that the Shahshahani volume of the space of mixed strategies is finite; the conclusion then follows from the Riemannian versions of Poincaré's theorem presented in Appendix A.4.

**Theorem 4.** If $\Gamma$ is harmonic, the dynamics (EW)/(RD) are Poincaré recurrent. Specifically, for almost every initialization $x(0) \in \mathcal{X}^\circ$, the induced trajectory $x(t)$ returns arbitrarily close to $x(0)$ infinitely often: there exists an increasing sequence of times $t_n \uparrow \infty$ such that $x(t_n) \to x(0)$.

*Proof.* By Remark A.4, Poincaré's theorem applies to a Riemannian manifold $(M, g)$ given that (a) there is a volume preserving map $\phi: M \to M$, and (b) the manifold has finite $g$-volume. By Proposition 2, the flow of the replicator vector field $\tilde{v}^g$ on incompressible (i.e.,
harmonic) games is volume-preserving with respect to the effective Shahshahani metric on the open corner of cube.<fnref n="20" /> Hence, if we show that the Shahshahani volume of the open corner of cube is finite, namely that vol<sub>Sha</sub> C° < ∞, by Poincaré's theorem we can conclude that the solution trajectories of replicator dynamics on incompressible games return arbitrarily close to almost every starting point x̃ ∈ C°.

To show that the volume of the $m_i$-dimensional open corner of cube $C^o_{m_i}$ with respect to the effective Shahshahani metric fulfills vol<sub>Sha</sub> $C^o_{m_i} < \infty$ for all $i \in \mathcal{N}$ and all natural $m_i$ we resort to a transformation first introduced by Akin [2, p. 39] and discussed e.g., by Sandholm [74, p. 228] and Laraki & Mertikopoulos [51, Example 3.1]. Suppressing for a moment the player index, Akin [2] shows that the map $A: \mathbb{R}^{m+1}_{>0} \to \mathbb{R}^{m+1}_{>0}$, $A_\alpha(x) = 2\sqrt{x_\alpha}$ for $\alpha \in \{0, \dots, m\}$, is an isometry between the $m$-dimensional open simplex $\mathcal{X}^\circ$ endowed with the Shahshahani metric and the portion of the radius-2 $m$-hypersphere in the positive hyperoctant of $\mathbb{R}^{m+1}$ endowed with the Euclidean metric. Isometries between Riemannian manifolds preserve volumes,<fnref n="21" /> so (reinstating the player index $i \in \mathcal{N}$) the Shahshahani volume of the $m_i$-dimensional open simplex is the Euclidean $m_i$-volume of the portion of the $m_i$-hypersphere of radius 2 in the positive orthant of $\mathbb{R}^{m_i+1}$, that is

$$ \mathrm{vol}_{\mathrm{Sha}} \chi_i^o = \frac{\pi^{\frac{m_i+1}{2}}}{\Gamma(\frac{m_i+1}{2})} < \infty \quad \text{for all } m_i \in \mathbb{N} \text{ and } i \in \mathcal{N}, \qquad (\mathrm{D.23}) $$

where $\Gamma$ is the gamma function. By construction, the map $\iota_0: C^o_i \to \chi_i^o$ is an isometry between the open corner of cube with the reduced Shahshahani metric and the open simplex with the full Shahshahani metric, so Eq. (D.23) gives also the sought-after volume of the open corner of cube, finite as required. Finally, since the volume of a product manifold is the product of the factor manifolds, we have that vol<sub>Sha</sub>(C°) = $\prod_i \mathrm{vol}_{\mathrm{Sha}}(C^o_i) < \infty$. ■

**Remark D.3.** An alternative formula to compute the volume of the open simplex under the Shahshahani metric is the following. Suppress the player index $i \in \mathcal{N}$ for notational simplicity, and let as usual $\mu, \nu \in \{1, \dots, m\}$. The determinant of the Shahshahani metric $\tilde{g}$ in its effective representation is given by Eq. (B.26), so by Eq. (A.11) the volume of the $m$-dimensional open corner of cube $C^o_m$ with respect to the effective Shahshahani metric is

$$ \begin{align} \mathrm{vol}_{\mathrm{Sha}} C_m^o &= \int_{C^o} \sqrt{\det \tilde{g}} \, d\tilde{x}^1 \dots d\tilde{x}^m \nonumber \\ &= \int_{\tilde{x}_1 > 0, \dots, \tilde{x}_m > 0, \sum_\mu \tilde{x}_1 < 1} \sqrt{\det \tilde{g}} \, d\tilde{x}^1 \dots d\tilde{x}^m \nonumber \\ &= \int_{\tilde{x}_1:0}^1 \int_{\tilde{x}_2:0}^{1-\tilde{x}_1} \dots \int_{\tilde{x}_m:0}^{1-\tilde{x}_1 - \dots - \tilde{x}_{m-1}} \frac{1}{\sqrt{(1-\sum_\mu \tilde{x}_\mu) \prod_\nu \tilde{x}_\nu}} \, d\tilde{x}^m \dots d\tilde{x}^1 \tag{D.24} \\ &= \int_{\tilde{x}_1=0}^{\xi_1} \frac{d\tilde{x}^1}{\sqrt{\tilde{x}_1}} \int_{\tilde{x}_2=0}^{\xi_2} \frac{d\tilde{x}^2}{\sqrt{\tilde{x}_2}} \dots \int_{\tilde{x}_{m-1}=0}^{\xi_{m-1}} \frac{d\tilde{x}^{m-1}}{\sqrt{\tilde{x}_{m-1}}} \int_{\tilde{x}_m=0}^{\xi_m} \frac{d\tilde{x}^m}{\sqrt{\tilde{x}_m (\xi_m - \tilde{x}_m)}} \nonumber \end{align} $$

with $\xi_m = 1 - \tilde{x}_1 - \dots - \tilde{x}_{m-1}$. One can check for a few values of $m$ that the integrals are in agreement with Eq. (D.23), for example vol<sub>Sha</sub> $C^o_{m=1} = \pi$, vol<sub>Sha</sub> $C^o_{m=2} = 2\pi$, vol<sub>Sha</sub> $C^o_{m=3} = \pi^2$. ◇

<footnote n="20">²⁰More precisely, the orbit map $\theta_t: C^o \to C^o$ of the replicator vector field is volume-preserving under the Shahshahani metric; cf. Appendix A.4.</footnote>

<footnote n="21">²¹To be precise, orientation-preserving isometries between Riemannian manifolds preserve volumes; see Lee [54].</footnote>
The proof of the fact replicator dynamics exhibit Poincaré recurrence in harmonic games relies on the facts that (a) the flow of RD is Shahshahani-incompressible in the space of mixed strategies precisely in such games, and (b) the Shahshahani volume of the open simplex is finite. Both of these phenomena are quite peculiar, as we discuss in the next section.

### D.4. On the special nature of the Shahshahani geometry.
We conclude this appendix with a discussion of the fact that the Shahshahani metric is intrinsically related to the replicator dynamics (cf. Proposition 1), but not at all to the simplicial complex of the game's response graph endowed with the Euclidean metric. In particular, incompressible games are defined completely independently of the harmonic games of Candogan et al. [14], and it is only through the lengthy calculations of this appendix (Proposition D.1, which ultimately leads to Theorem 2) that the two structures are shown to be, in fact, compatible.

It is this difference in the origin of harmonic and incompressible games – Euclidean-combinatorial on one side, dynamical/geometric in a Shahshahani framework on the other – which makes the equivalence of harmonic and incompressible games, in our opinion, unexpected. This idea is supported by the following example:

**Example D.1.** Since harmonic games are defined relative to the Euclidean metric on the simplicial complex of the game's response graph, it would make sense to consider the Euclidean projection dynamics on the simplex (less widely used than the replicator / exponential weights dynamics, but still a valid choice of game dynamics). Following Friedman [27], Lahkar & Sandholm [49], Mertikopoulos & Sandholm [61], in the interior of the simplex these dynamics take the simple form

$$ \dot{x}_{i\alpha_i} = v_{i\alpha_i}(x) - \frac{1}{|\mathcal{A}_i|} \sum_{\beta_i \in \mathcal{A}_i} v_{i\beta_i}(x) \quad \text{for all } x \in \mathcal{X}^\circ, i \in \mathcal{N}, \alpha_i \in \mathcal{A}_i. \quad (\text{D.25}) $$

The RHS of these dynamics is simply the (Euclidean) projection of $v_i(x)$ onto $\mathcal{X}_i^\circ$. In this regard, the definition of the divergence boils down to the standard form from calculus, cf. Eq. (A.4). However, since by Lemma B.3 $v_i(x)$ does not depend on $x_i$, it follows that the Euclidean projection dynamics are incompressible under the Euclidean metric in the space of mixed strategies for all games, not only for harmonic games.

Put differently, all games are incompressible under the Euclidean metric, so the equivalence between harmonic and incompressible games does not hold for the Euclidean metric on the simplex: pictorially,

$$ \begin{align*} (g = \text{Shahshahani metric}) &\implies (g\text{-incompressible game} \iff \text{harmonic game}), \\ (g = \text{Euclidean metric}) &\implies (g\text{-incompressible game} \iff \text{any game}). \end{align*} $$

## APPENDIX E. ADDITIONAL RELATED WORK

### E.1. Comparison with the work by Letcher et al. [55].
Our work addresses an open issue raised by Letcher et al. [55], who state that "Candogan et al. derive a Hodge decomposition for games that is closely related in spirit to our generalized Helmholtz decomposition – although the details are quite different. Their losses are multilinear, which is easier than our setting, but they have constrained solution sets, which is harder in many ways. Their approach is based on combinatorial Hodge theory [43] rather than differential and symplectic geometry. Finding a best-of-both-worlds approach that encompasses both settings is an open problem."

The machinery we developed does touch on both worlds above, as it connects the differential-geometric Hodge/Helmholtz decomposition to a constrained setting. However, there is a key difference between the spirit of our approach and that of [55]: Letcher et al.
[55] do not propose a decomposition of games. The authors identify two classes of games with well-understood dynamical properties based on the symmetric and skew-symmetric part of the game's Jacobian matrix, and use the symmetric and skew-symmetric components of this matrix to introduce Symplectic Gradient Adjustment (SGA), an algorithm for finding stable fixed points in differentiable game.

In more detail, Letcher et al. [55] consider the individual gradients $\xi$ of a game with differentiable losses, and decompose the Jacobian matrix $J$ of $\xi$ into its symmetric and skew-symmetric part, $J = S + A$. They then call a game potential if $A = 0$, and Hamiltonian if $S = 0$. Hamiltonian games exhibit non-convergent behavior under standard gradient descent methods which is similar to that of incompressible games under EW/RD. However, given a game with individual gradient field $\xi$, it is not possible in general to find a potential game $\xi_P$ and a Hamiltonian game $\xi_H$ such that $\xi = \xi_P + \xi_H$, the problem with this approach being that the Jacobian of a vector field is a coordinate-dependent object that does not have an intrinsic geometrical meaning, and its skew-symmetric component is in general not integrable. By contrast, Theorem 1 provides precisely such a decomposition for normal form games into a potential and incompressible/harmonic component, resolving the dynamic-strategic disconnect that arises when trying to naively apply the standard Helmholtz decomposition to the field of individual gradients of a game.

**E.2. Combination of potential and harmonic games and dynamics.** In this section we include a sequence of replicator dynamics trajectories on a convex combination of a harmonic and a potential game, showing how Poincaré recurrence breaks down as the relative magnitude of the potential component increases. More precisely, given the payoff $u_p$ of a potential game and the payoff $u_h$ of a harmonic game, we run RD on the game with payoff $u := \gamma u_p + (1-\gamma)u_h$, with $\gamma \in [0, 1]$. Fig. 6 shows the resulting trajectories for a $2 \times 2 \times 2$ with $u_p$ and $u_h$ given respectively by the following tables:

$$ \begin{bmatrix} u_1[0,0,0] = -14 & u_2[0,0,0] = -16 & u_3[0,0,0] = -7 \\ u_1[1,0,0] = -8 & u_2[1,0,0] = -16 & u_3[1,0,0] = 0 \\ u_1[0,1,0] = -18 & u_2[0,1,0] = 2 & u_3[0,1,0] = 2 \\ u_1[1,1,0] = -7 & u_2[1,1,0] = 7 & u_3[1,1,0] = 8 \\ u_1[0,0,1] = 13 & u_2[0,0,1] = 6 & u_3[0,0,1] = 8 \\ u_1[1,0,1] = 8 & u_2[1,0,1] = 0 & u_3[1,0,1] = 4 \\ u_1[0,1,1] = -8 & u_2[0,1,1] = -1 & u_3[0,1,1] = -8 \\ u_1[1,1,1] = 1 & u_2[1,1,1] = 7 & u_3[1,1,1] = -4 \end{bmatrix} $$

$$ \begin{bmatrix} u_1[0,0,0] = 7 & u_2[0,0,0] = -15 & u_3[0,0,0] = -8 \\ u_1[1,0,0] = 2 & u_2[1,0,0] = -3 & u_3[1,0,0] = 4 \\ u_1[0,1,0] = 1 & u_2[0,1,0] = -10 & u_3[0,1,0] = 1 \\ u_1[1,1,0] = 7 & u_2[1,1,0] = 2 & u_3[1,1,0] = -6 \\ u_1[0,0,1] = -29 & u_2[0,0,1] = 23 & u_3[0,0,1] = -8 \\ u_1[1,0,1] = -6 & u_2[1,0,1] = -9 & u_3[1,0,1] = -6 \\ u_1[0,1,1] = 24 & u_2[0,1,1] = 0 & u_3[0,1,1] = 0 \\ u_1[1,1,1] = 0 & u_2[1,1,1] = 4 & u_3[1,1,1] = 5 \end{bmatrix} $$
<figure><img src="image_12.png" /><figcaption>**Figure 6:** Replicator trajectories in an ensemble of 2 × 2 × 2 games with payoff $u := \gamma u_p + (1 - \gamma)u_h$ given by the convex combination of a harmonic and a potential game. The value of the parameter $\gamma$ is shown in the legend of each plot, and $u_p, u_h$ are given in Appendix E.2. Each trajectory is color-coded so that deeper shades of blue-purple correspond to later times, with the arrows indicating the direction in which orbits are traversed. Light blue markers represent initial points for the orbits; dark blue markers are stationary points for the replicator dynamics; and dark red points are Nash equilibria. For visual clarity, we have highlighted in orange one of the plotted orbits. As expected, RD is recurrent (in particular, periodic) in the harmonic case $\gamma = 0$, and converges to a pure NE in the potential case $\gamma = 1$.</figcaption></figure>

As expected, RD is recurrent (in particular, periodic) in the harmonic case $\gamma = 0$, and converges to a pure NE in the potential case $\gamma = 1$. We leave the rationality properties of no-regret learning schemes in convex combinations of potential and harmonic games as an open direction for future research.

## APPENDIX F. A GEOMETRIC TOUR

A reader familiar with differential geometry won't have failed to realize that we have been trying to explain some fundamental geometrical concepts in an intuitive, yet not completely rigorous, way. This is an unavoidable price to pay if we wish to present results to an audience not necessarily familiar with the geometrical theory they rely upon.

For that reader, here is a quick tour about what is going on, that can be safely skipped by anyone not interested in the geometrical intricacies underlying the constructions we presented. A notation aside: as usual, for each $i \in \mathcal{N}$, the index $\alpha_i \in \mathcal{A}_i$ runs from $0_i$ to $m_i$ and the index $\mu_i \in \tilde{\mathcal{A}}_i$ runs from $1_i$ to $m_i$. It is understood that whenever the index $i$ appears in an equation such equation holds true for all $i \in \mathcal{N}$, unless otherwise specified.

* Each open strategy space $\mathcal{X}_i^\circ = \Delta^\circ(\mathcal{A}_i)$ is a smooth submanifold of $\mathbb{R}^{A_i}$ of dimension $m_i = A_i - 1$;

* $\pi_0: \mathcal{X}_i^\circ \to \mathcal{C}_i^\circ$ is a global chart and $\iota_0: \mathcal{C}_i^\circ \to \mathcal{X}_i^\circ$ the corresponding parametrization;

* $\mathcal{X}^\circ = \prod_i \mathcal{X}_i^\circ$ has the standard smooth structure of product submanifold in $\mathbb{R}^A = \prod_i \mathbb{R}^{A_i}$;
* the differential of the parametrization $d\iota_0$ is an isomorphism between $T\mathcal{C}_i^\circ = \mathbb{R}^{m_i}$ and $T\mathcal{X}_i^\circ \subset \mathbb{R}^{m_i+1}$ allowing to express the $m_i$ basis vectors $\{\tilde{\partial}_{i\mu_i}\}_{\mu_i \in \{1, \dots, m_i\}}$ of $T\mathcal{X}_i^\circ$ in the chart $\pi_0$ as a linear combination of the $m_i + 1$ basis vectors $\{\partial_{i\alpha_i}\}_{\alpha_i \in \{0, \dots, m_i\}}$ of $\mathbb{R}^{m_i+1}$ in the standard Cartesian frame as

$$ \tilde{\partial}_{i\mu_i} = \partial_{i\mu_i} - \partial_{i0_i} \quad \text{for all } \mu_i \in \{1, \dots, m_i\}. $$

* Analogously, the pull-back of the $m_i + 1$ basis 1-forms $\{dx^{i\alpha_i}\}_{\alpha_i \in \{0, \dots, m_i\}}$ in $\mathbb{R}_{++}^{A_i}$ along $\iota_0$ in terms of the $m_i$ basis 1-forms $\{d\tilde{x}^{i\mu_i}\}_{\mu_i \in \{1, \dots, m_i\}}$ on $\mathcal{X}_i^\circ$ gives

$$ dx^{i0_i} = - \sum_{\mu_i} d\tilde{x}^{i\mu_i} \quad \text{and} \quad dx^{i\mu_i} = d\tilde{x}^{i\mu_i} \quad \text{for all } \mu_i \in \{1, \dots, m_i\}. $$

* Payoff functions $u_i: \mathcal{X} \to \mathbb{R}$ are actually multilinear functions on the whole $u_i: \mathbb{R}^A \to \mathbb{R}$;

* each “effective payoff function” $\tilde{u}_i$ is the pull-back along the inclusion of $u_i$, i.e., a smooth function on $\mathcal{X}_i^\circ$;

* each payoff field $v_i = d_i u_i$ is a 1-form on $\mathbb{R}^{A_i}$ and $v = \sum_i v_i$ is a 1-form on $\mathbb{R}^A$;

* the “effective payoff field” $\tilde{v}_i$ is the pull-back along the inclusion of $v_i$, i.e., a 1-form on $\mathcal{X}_i^\circ$;

* the ambient Shahshahani metric on $\mathbb{R}^A$,

$$ g(x) = \sum_{i \in \mathcal{N}} \sum_{\alpha_i \beta_i} \frac{\delta_{\alpha_i \beta_i}}{x_i \alpha_i} dx^{i\alpha_i} \otimes dx^{i\beta_i}, $$

is pulled back to the effective Shahshahani metric on $\mathcal{X}^\circ$,

$$ \tilde{g}(\tilde{x}) = \sum_{i \in \mathcal{N}} \sum_{\mu_i \nu_i} \left( \frac{\delta_{\mu_i \nu_i}}{\tilde{x}_i \mu_i} + \frac{1}{x_i 0_i} \right) d\tilde{x}^{i\mu_i} \otimes d\tilde{x}^{i\nu_i}. $$

It is a standard fact in differential geometry [53] that if $\iota: (S, g) \hookrightarrow (M, G)$ is a Riemannian submanifold$^{22}$ with metric $g$ induced by the ambient metric $G$, then the sharp isomorphism $\sharp$, the pull-back along the inclusion $\iota^*$, and the orthogonal projection $P_G$ commute, in the sense that $P_G(\alpha^\sharp_G) = (\iota^*\alpha)^\sharp_G$ is a vector field on $S$ for all 1-forms $\alpha$ on $M$. With this in place, each replicator field $v_i^\sharp(x)$ is equivalently

* the orthogonal projection on $\mathcal{X}_i^\circ$ with respect to the ambient Shahshahani metric of the ambient sharp of the 1-form $v_i$ (this point of view is adopted in Mertikopoulos & Sandholm [61]);

* the sharp with respect to the pull-back metric of the pull-back 1-form $\tilde{v}_i$;

* the individual gradient with respect to the pull-back Shahshahani metric of the pull-back payoff function $\tilde{u}_i$.

In our notation $v_i^\sharp$ is a vector field parallel to $\mathcal{X}^\circ$, i.e., a vector field legitimately defined on the whole ambient space $\mathbb{R}^A$ that evaluated at $x \in \mathcal{X}^\circ$ gives a vector in the tangent space $T_x \mathcal{X}^\circ$ as a linear subspace of $T_x \mathbb{R}^A$, so $v_i^\sharp$ has $m_i + 1$ components. On the other hand $\tilde{v}_i^\sharp$ is a vector field on $\mathcal{X}^\circ$ with $m_i$ components, well-defined without the need to see $\mathcal{X}^\circ$ as an immersed submanifold.

The reason to go through the reduction procedure of the replicator field and the Shahshahani metric is that what matters from a dynamical standpoint is the divergence of $\tilde{v}^\sharp$ as a vector field on $\mathcal{X}^\circ$, but in general given a vector field $X$ parallel to a Riemannian submanifold $\iota: (S, g) \hookrightarrow (M, G)$ there is not a simple relation between its the divergence with respect to

<footnote>$^{22}$That is, $\iota: S \to M$ is a smooth injective immersion and $(M, G)$ is a Riemannian manifold.</footnote>
the ambient metric and its divergence with respect to the pull-back metric (in particular, $div_g X \neq (div_G X) \circ \iota$); for details see do Carmo [25, Ch. 6]. This ultimately makes it necessary to compute the effective versions (resp. pulled back and projected) of the metric and the vector field at hand.

## REFERENCES

[1] Abdou, J., Pnevmatikos, N., Scarsini, M., and Venel, X. Decomposition of Games: Some Strategic Considerations. Mathematics of Operations Research, 47(1):176-208, February 2022. ISSN 0364-765X. doi: 10.1287/moor.2021.1123.

[2] Akin, E. The Geometry of Population Genetics. Lecture Notes in Biomathematics 31. Springer-Verlag Berlin Heidelberg, 1 edition, 1979. ISBN 978-3-540-09711-2 978-3-642-93128-4.

[3] Amann, E. and Hofbauer, J. Permanence in lotka-volterra and replicator equations. In Ebeling, W. and Peschel, M. (eds.), Lotka-Volterra Approach to Cooperation and Competition in Dynamic Systems. Akademie-Verlag, Berlin, 1985.

[4] Amari, S.-i. and Nagaoka, H. Methods of Information Geometry. American Mathematical Soc., 2000. ISBN 978-0-8218-4302-4.

[5] Arnold, V. I. Mathematical Methods of Classical Mechanics. Number 60 in Graduate Texts in Mathematics. Springer, New York, NY, 2 edition, 1989.

[6] Arora, S., Hazan, E., and Kale, S. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012.

[7] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995.

[8] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.

[9] Basar, T. and Ho, Y.-C. Informational properties of the Nash solutions of two stochastic nonzero-sum games. Journal of Economic Theory, 7(4):370-387, April 1974. ISSN 0022-0531. doi: 10.1016/0022-0531(74)90110-0.

[10] Bekka, M. B., Bekka, M. E. B., and Mayer, M. Ergodic Theory and Topological Dynamics of Group Actions on Homogeneous Spaces, volume 269. Cambridge University Press, 2000.

[11] Bhatia, H., Norgard, G., Pascucci, V., and Bremer, P.-T. The Helmholtz-Hodge Decomposition—A Survey. IEEE Transactions on Visualization and Computer Graphics, 19(8):1386-1404, August 2013.

[12] Boone, V. and Piliouras, G. From Darwin to Poincaré and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory, October 2019.

[13] Bravo, M. and Mertikopoulos, P. On the robustness of learning in games with stochastically perturbed payoff observations. Games and Economic Behavior, 103 (John Nash Memorial issue):41-66, May 2017.

[14] Candogan, O., Menache, I., Ozdaglar, A., and Parrilo, P. A. Flows and decompositions of games: harmonic and potential games. Mathematics of Operations Research, 36(3):474-503, 2011.

[15] Candogan, O., Ozdaglar, A., and Parrilo, P. A. Dynamics in Near-Potential Games. 2011. doi: 10.48550/ARXIV.1107.4386.

[16] Candogan, O., Ozdaglar, A., and Parrilo, P. A. Learning in near-potential games. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp. 2428-2433, December 2011. doi: 10.1109/CDC.2011.6160867.

[17] Candogan, O., Ozdaglar, A., and Parrilo, P. A. Near-Potential Games: Geometry and Dynamics. ACM Transactions on Economics and Computation, 1(2):11:1-11:32, May 2013. ISSN 2167-8375. doi: 10.1145/2465769.2465776.

[18] Candogan, U. O. Dynamic Strategic Interactions: Analysis and Mechanism Design. Thesis, Massachusetts Institute of Technology, 2013.

[19] Cheng, D., Liu, T., Zhang, K., and Qi, H. On Decomposed Subspaces of Finite Games. IEEE Transactions on Automatic Control, 61(11):3651-3656, November 2016. ISSN 1558-2523. doi: 10.1109/TAC.2016.2525936.

[20] Cheung, Y. K. and Tao, Y. Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions. In International Conference on Learning Representations, October 2020.
[21] Conley, C. C. *Isolated Invariant Set and the Morse Index*. American Mathematical Society, Providence, RI, 1978.

[22] Coucheney, P., Gaujal, B., and Mertikopoulos, P. Penalty-regulated dynamics and robust learning procedures in games. *Mathematics of Operations Research*, 40(3):611–633, August 2015.

[23] Cressman, R., Morrison, W. G., and Wen, J.-F. On the Evolutionary Dynamics of Crime. *The Canadian Journal of Economics / Revue canadienne d'Economique*, 31(5):1101–1117, 1998. ISSN 0008-4085. doi: 10.2307/136461.

[24] de Rham, G. *Differentiable Manifolds: Forms, Currents, Harmonic Forms*. Springer Science & Business Media, 1984.

[25] do Carmo, M. P. *Riemannian Geometry*. Birkhäuser Boston, 1 edition, 1992.

[26] Flokas, L., Vlatajis-Gkaragkounis, E. V., Lianeas, T., Mertikopoulos, P., and Piliouras, G. No-regret learning and mixed Nash equilibria: They do not mix. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[27] Friedman, D. Evolutionary games in economics. *Econometrica*, 59(3):637–666, 1991.

[28] Fudenberg, D. and Tirole, J. *Game Theory*. The MIT Press, 1991.

[29] Hannan, J. Approximation to Bayes risk in repeated play. In Dresher, M., Tucker, A. W., and Wolfe, P. (eds.), *Contributions to the Theory of Games, Volume III*, volume 39 of *Annals of Mathematics Studies*, pp. 97–139. Princeton University Press, Princeton, NJ, 1957.

[30] Harper, M. Information geometry and evolutionary game theory. *arXiv preprint arXiv:0911.1383*, 2009.

[31] Hart, S. and Mas-Colell, A. Uncoupled dynamics do not lead to Nash equilibrium. *American Economic Review*, 93(5):1830–1836, 2003.

[32] Hart, S. and Mas-Colell, A. Stochastic uncoupled dynamics and Nash equilibrium. *Games and Economic Behavior*, 57:286–303, 2006.

[33] Héliou, A., Cohen, J., and Mertikopoulos, P. Learning with bandit feedback in potential games. In *NIPS '17: Proceedings of the 31st International Conference on Neural Information Processing Systems*, 2017.

[34] Hodge, W. V. D. *The Theory and Applications of Harmonic Integrals*. CUP Archive, May 1989. ISBN 978-0-521-35881-1.

[35] Hofbauer, J. Evolutionary dynamics for bimatrix games: A Hamiltonian system? *Journal of Mathematical Biology*, 34(5):675, May 1996. ISSN 1432-1416. doi: 10.1007/BF02409754.

[36] Hofbauer, J. and Schlag, K. H. Sophisticated imitation in cyclic games. *Journal of Evolutionary Economics*, 10(5):523–543, September 2000. ISSN 1432-1386. doi: 10.1007/s001910000049.

[37] Hofbauer, J. and Sigmund, K. *Evolutionary Games and Population Dynamics*. Cambridge University Press, Cambridge, UK, 1998.

[38] Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[39] Hsieh, Y.-G., Antonakopoulos, K., and Mertikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In *COLT '21: Proceedings of the 34th Annual Conference on Learning Theory*, 2021.

[40] Hsieh, Y.-G., Antonakopoulos, K., Cevher, V., and Mertikopoulos, P. No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation. In *NeurIPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems*, 2022.

[41] Hubbard, J. H. and Burke Hubbard, B. *Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach (5th Edition)*. Matrix Editions, September 2015.

[42] Hwang, S.-H. and Rey-Bellet, L. Strategic decompositions of normal form games: Zero-sum games and potential games. *Games and Economic Behavior*, 122:370–390, July 2020. ISSN 0899-8256. doi: 10.1016/j.geb.2020.05.003.

[43] Jiang, X., Lim, L.-H., Yao, Y., and Ye, Y. Statistical ranking and combinatorial Hodge theory. *Mathematical Programming*, 127(1):203–244, 2011.

[44] Jost, J. *Riemannian Geometry and Geometric Analysis*. Universitext. Springer International Publishing, Cham, 2017.
[45] Kalai, A. T. and Kalai, E. Cooperation and competition in strategic games with private information. In *Proceedings of the 11th ACM Conference on Electronic Commerce*, EC '10, pp. 345-346, New York, NY, USA, June 2010. Association for Computing Machinery. ISBN 978-1-60558-822-3. doi: 10.1145/1807342.1807397.

[46] Khalil, H. K. *Nonlinear Systems*. Pearson College Div, Upper Saddle River, N.J, subsequent edition, January 2002. ISBN 978-0-13-067389-3.

[47] Kimura, M. On the change of population fitness by natural selection. *Heredity*, 12:145-167, 1958.

[48] Kwon, J. and Mertikopoulos, P. A continuous-time approach to online optimization. *Journal of Dynamics and Games*, 4(2):125-148, April 2017.

[49] Lahkar, R. and Sandholm, W. H. The projection dynamic and the geometry of population games. *Games and Economic Behavior*, 64:565-590, 2008.

[50] Laraki, R. and Mertikopoulos, P. Higher order game dynamics. *Journal of Economic Theory*, 148(6): 2666-2695, November 2013.

[51] Laraki, R. and Mertikopoulos, P. Inertial game dynamics and applications to constrained optimization. *SIAM Journal on Control and Optimization*, 53(5):3141-3170, October 2015.

[52] Lattimore, T. and Szepesvári, C. *Bandit Algorithms*. Cambridge University Press, Cambridge, UK, 2020.

[53] Lee, J. M. *Introduction to Smooth Manifolds*. Graduate Texts in Mathematics. Springer-Verlag New York, 2 edition, 2012.

[54] Lee, J. M. *Introduction to Riemannian Manifolds*, volume 176 of *Graduate Texts in Mathematics*. Springer International Publishing, Cham, 2018. ISBN 978-3-319-91754-2 978-3-319-91755-9. doi: 10.1007/978-3-319-91755-9.

[55] Letcher, A., Balduzzi, D., Racanière, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. Differen-
tiable Game Mechanics. *Journal of Machine Learning Research*, 20(84):1-40, 2019. ISSN 1533-7928.

[56] Li, C., Liu, T., He, F., Cheng, D., Qi, H., and Hong, Y. On finite harmonic games. In *2016 IEEE 55th Conference on Decision and Control (CDC)*, pp. 7024–7029, December 2016. doi: 10.1109/CDC.2016.7799351.

[57] Li, C., Cheng, D., and He, F. A Note On Orthogonal Decomposition of Finite Games, May 2019.

[58] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. *Information and Computation*, 108(2):212-261, 1994.

[59] Mertikopoulos, P. and Moustakas, A. L. The emergence of rational behavior in the presence of stochastic perturbations. *The Annals of Applied Probability*, 20(4):1359-1388, July 2010.

[60] Mertikopoulos, P. and Sandholm, W. H. Learning in games via reinforcement and regularization. *Mathematics of Operations Research*, 41(4):1297-1324, 2016.

[61] Mertikopoulos, P. and Sandholm, W. H. Riemannian game dynamics. *Journal of Economic Theory*, 177:315-364, 2018.

[62] Mertikopoulos, P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff functions. *Mathematical Programming*, 173(1-2):465-507, January 2019.

[63] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In *SODA '18: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms*, 2018.

[64] Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In *ICLR '19: Proceedings of the 2019 International Conference on Learning Representations*, 2019.

[65] Mladenovic, A., Sakos, I., Gidel, G., and Piliouras, G. Generalized natural gradient flows in hidden convex-concave games and gans. 2021.

[66] Monderer, D. and Shapley, L. S. Potential games. *Games and Economic Behavior*, 14(1):124-143, 1996.

[67] Munkres, J. R. *Topology*. Pearson Higher Ed, 1999.

[68] Nagarajan, S. G., Balduzzi, D., and Piliouras, G. From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics. In *Proceedings of the 37th International Conference on Machine Learning*, pp. 7186-7196. PMLR, November 2020.
[69] Piliouras, G. and Shamma, J. S. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence. In *SODA '14: Proceedings of the 25th annual ACM-SIAM Symposium on Discrete Algorithms*, 2014.

[70] Poincaré, H. *Sur Le Problème Des Trois Corps et Les Équations de La Dynamique*. Mémoire couronné du prix de SM le Roi Oscar II, 1889.

[71] Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In *NIPS '13: Proceedings of the 27th International Conference on Neural Information Processing Systems*, 2013.

[72] Ritzberger, K. and Vogelsberger, K. The Nash field. 1990.

[73] Rosen, J. B. Existence and uniqueness of equilibrium points for concave $N$-person games. *Econometrica*, 33(3):520–534, 1965.

[74] Sandholm, W. H. *Population Games and Evolutionary Dynamics*. MIT Press, Cambridge, MA, 2010.

[75] Shahshahani, S. M. *A New Mathematical Framework for the Study of Linkage and Selection*. Number 211 in Memoirs of the American Mathematical Society. American Mathematical Society, Providence, RI, 1979.

[76] Shalev-Shwartz, S. Online learning and online convex optimization. *Foundations and Trends in Machine Learning*, 4(2):107–194, 2011.

[77] Shalev-Shwartz, S. and Singer, Y. Convex repeated games and Fenchel duality. In *NIPS' 06: Proceedings of the 19th Annual Conference on Neural Information Processing Systems*, pp. 1265–1272. MIT Press, 2006.

[78] Smith, J. M. and Hofbauer, J. The “battle of the sexes”: A genetic model with limit cycle behavior. *Theoretical Population Biology*, 32(1):1–14, August 1987. ISSN 0040-5809. doi: 10.1016/0040-5809(87) 90035-9.

[79] Sorin, S. Exponential weight algorithm in continuous time. *Mathematical Programming*, 116(1):513–528, 2009.

[80] Spivak, M. *Calculus On Manifolds: A Modern Approach To Classical Theorems Of Advanced Calculus*. CRC Press, Boca Raton, 1965. ISBN 978-0-429-50190-6. doi: 10.1201/9780429501906.

[81] Taylor, P. D. and Jonker, L. B. Evolutionary stable strategies and game dynamics. *Mathematical Biosciences*, 40(1-2):145–156, 1978.

[82] Viossat, Y. and Zaepelnyuk, A. No-regret dynamics and fictitious play. *Journal of Economic Theory*, 148(2):825–842, March 2013.

[83] Vovk, V. G. Aggregating strategies. In *COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory*, pp. 371–383, 1990.

[84] Wang, Y., Liu, T., and Cheng, D. From weighted potential game to weighted harmonic game. *IET Control Theory & Applications*, 11(13):2161–2169, 2017. ISSN 1751-8652. doi: 10.1049/iet-cta.2016.1454.

[85] Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-point optimization. In *ICLR '21: Proceedings of the 2021 International Conference on Learning Representations*, 2021.

[86] Weibull, J. W. *Evolutionary Game Theory*. MIT Press, Cambridge, MA, 1995.