Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

William H Sandholm

RIEMANNIAN GAME DYNAMICS

We study a class of evolutionary game dynamics defined by balancing a gain determined by the game's payoffs against a cost of motion that captures the difficulty with which the population moves between states. Costs of motion are represented by a Riemannian metric, i.e., a state-dependent inner product on the set of population states. The replicator dynamics and the (Euclidean) projection dynamics are the archetypal examples of the class we study. Like these representative dynamics, all Riemannian game dynamics satisfy certain basic desiderata, including positive correlation and global convergence in potential games. Moreover, when the underlying Riemannian metric satisfies a Hessian integrability condition, the resulting dynamics preserve many further properties of the replicator and projection dynamics. We examine the close connections between Hessian game dynamics and reinforcement learning in normal form games, extending and elucidating a well-known link between the replicator dynamics and exponential reinforcement learning.

Introduction

Viewed abstractly, evolutionary game dynamics assign to every population game a dynamical system on the game's set of population states. Under most such dynamics, the vector of motion at a given population state depends only on payoffs and behavior at that state, implying that changes in aggregate behavior are determined by current strategic conditions. Such dynamics may thus be viewed as state-dependent rules for transforming current payoffs into feasible directions of motion.

In this paper, we introduce a family of evolutionary game dynamics under which the vector of motion z from any state x is obtained by balancing two forces. The first, the gain from motion, is obtained by adding the products of the strategies' payoffs at x with their rates of change under z. This quantity is the measure of agreement between payoffs and motion used in the standard monotonicity condition for game dynamics. 1 The second, the cost of motion, captures the difficulty with which the population moves from state x along vector z; different specifications of these costs define different members of our family of dynamics. These costs are usefully represented by means of a Riemannian metric, a state-dependent inner product used to evaluate lengths of and angles between vectors of motion. Accordingly, the dynamics studied here, defined by maximizing differences between gains and costs, are called Riemannian game dynamics.

The two archetypal examples of Riemannian game dynamics are the replicator dynamics [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF] and the (Euclidean) projection dynamics [START_REF] Nagurney | Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria[END_REF], both derived from fairly simple structures. First, the replicator dynamics are derived from the Shahshahani metric [START_REF] Shahshahani | A new mathematical framework for the study of linkage and selection[END_REF], under which the cost of increasing a strategy's relative frequency in the population is inversely proportional to said frequency. Second, the projection dynamics are obtained by measuring the cost of motion in the standard Euclidean fashion, independently of the population's current state. Other Riemannian metrics can be used in applications where different strategies have clear affinities, allowing the presence and performance of one strategy to positively influence the use of similar alternatives.

The metric's boundary behavior is the source of a fundamental dichotomy that is best explained by looking at our two prototypical examples above. Under the replicator dynamics: (i ) the law of motion for every game is continuous; (ii ) the set of utilized strategies remains constant along every solution trajectory; and (iii ) the dynamics' rest points are the restricted equilibria of the game -the states at which all strategies in use earn the same payoff. In contrast, under the Euclidean projection dynamics: (i ) the law of motion is typically discontinuous at the boundary of the simplex; (ii ) the set of utilized strategies may change infinitely often along the same solution trajectory; and (iii ) the dynamics' rest points are the Nash equilibria of the underlying game. Based on this behavior, we obtain a natural distinction between continuous and discontinuous Riemannian dynamics, each category sharing the boundary behavior of its prototype. In Section 4, we introduce a variety of examples of Riemannian dynamics from both classes; then, in Section 5, we show how these and other Riemannian dynamics can be provided with microfoundations using suitably constructed revision protocols.

A basic aim of our analysis is to demonstrate that many basic properties of the replicator and Euclidean projection dynamics extend to our substantially more general setting. In Section 6, we show that Riemannian dynamics satisfy the basic desiderata for evolutionary game dynamics: they heed a payoff monotonicity condition known as positive correlation, and they converge globally in the class of potential games. In the latter context, Riemannian game dynamics also provide a broad generalization of Kimura's maximum principle [START_REF] Kimura | On the change of population fitness by natural selection[END_REF][START_REF] Shahshahani | A new mathematical framework for the study of linkage and selection[END_REF]. This principle states that when agents are matched to play a normal form common interest game, the replicator dynamics move in the direction of maximal increase in average payoffs, provided that lengths of displacement vectors are evaluated using the Shahshahani metric. Extending this principle, we observe that Riemannian dynamics track the direction of steepest ascent of potential in any potential game, provided that displacements are evaluated using the Riemannian metric at hand.

Obtaining further results on stability, convergence, and global behavior requires additional structure on our dynamics -and hence on the underlying Riemannian metric. This structure is provided by an integrability condition. In prior work on game dynamics, such conditions have been imposed on the vector fields used to convert the strategies' payoffs into vectors of choice probabilities.2 By contrast, the integrability condition employed here is imposed on the matrix field that defines a Riemannian metric, requiring that it be expressible as the Hessian of a convex function. We call this function the potential of the metric, and we refer to the resulting dynamics as Hessian game dynamics. 3 Both the replicator dynamics and the Euclidean projection dynamics are members of this class. As we explain in Section 7, Hessian dynamics are continuous when their potential function becomes infinitely steep at the boundary of the simplex, leading to the distinction between continuous and discontinuous Hessian dynamics.

The key tool that we employ for the analysis of Hessian dynamics is the Bregman divergence [START_REF] Bregman | The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming[END_REF], an asymmetric measure of the "remoteness" of a given population state from any fixed target state. 4 By using the Bregman divergence as a Lyapunov function, we prove global convergence to Nash equilibrium in strictly contractive games and local stability of evolutionarily stable states under Hessian game dynamics. We also show that certain distinctive properties of the replicator dynamics in normal form games extend to all continuous Hessian dynamics -in particular, the convergence of time averages of interior solutions to the set of Nash equilibria, and the existence of simple sufficient conditions for permanence. Finally, we show that strictly dominated strategies are eliminated under continuous Hessian dynamics, a conclusion which does not extend to the discontinuous regime. 5Related work. There are very close connections between the dynamics considered here and dynamics studied by [START_REF] Hofbauer | Adaptive dynamics and evolutionary stability[END_REF], [START_REF] Hopkins | A note on best response dynamics[END_REF], and [START_REF] Harper | Escort evolutionary game theory[END_REF]. In order to have the machinery in place to make these connections clear, we postpone this discussion until Section 2.3.

There is a more surprising connection between Hessian dynamics and models of reinforcement learning in normal form games. [START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF], Hofbauer et al. (2009) and [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF] show that if players track the cumulative payoffs (or scores) of their strategies and choose mixed strategies at each instant by applying the logit choice rule to these scores, the evolution of mixed strategies is described by the replicator dynamics. 6 Combining our analysis here with that of [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF], we show that Hessian dynamics derived from a steep potential function also describe the evolution of mixed strategies under reinforcement learning. In addition to substantially generalizing existing results, our analysis provides an intuitive explanation for the tight links between the two processes. Section 8 describes these and other connections between Hessian dynamics and reinforcement learning in detail.

Population games and evolutionary dynamics

Notation. Let A = {α 1 , . . . , α n } be a finite set. The real space spanned by A will be denoted by R A and we will write δ αβ for the Kronecker deltas on A. We will also write K ≡ R A + for the nonnegative orthant of R A , K • ≡ R A ++ for its interior (the positive orthant), and R A 0 = {z ∈ R A : α z α = 0} for the subspace of vectors whose components sum to zero. Finally, in a slight abuse of notation, we will write R supp(x) = {z ∈ R A : z α = 0 whenever x α = 0} for the set of vectors in R A whose support is contained in the support of x ∈ R A .

2.1. Population games. Throughout this paper we focus on games played by a population of nonatomic agents. Our analysis extends to the multi-population setting without significant effort, but we focus on single-population games for simplicity and notational clarity.

During play, each agent chooses an action (or pure strategy) from a finite set A, and their payoff is determined by their choice of action and by the proportions x α ∈ [0, 1] of the population playing each action α ∈ A. Collectively, these proportions define a population state x = (x α ) α∈A ∈ R A , and we write X = ∆(A) = {x ∈ R A + : α x α = 1} for the set of population states (or state space) of the game. The payoff to an agent playing α ∈ A when the population state is x ∈ X is given by an associated payoff function v α : X → R, which we assume to be Lipschitz continuous. Putting all this together, a population game may be identified with a set of actions and their associated payoff functions, and will be denoted by G ≡ G(A, v).

A population state x * ∈ X is a Nash equilibrium (NE) of a population game G if

v α (x * ) ≥ v β (x *
) for all α ∈ supp(x * ) and for all β ∈ A.

(NE)

If x * satisfies (NE) and is pure (i.e. x * = e α for some α ∈ A), it is called a pure Nash equilibrium of G; if, in addition, (NE) holds as a strict inequality for all β / ∈ supp(x * ), x * is said to be a strict equilibrium of G.

A restriction of a game G is a population game G ≡ G (A , v ) that is defined by a subset A ⊆ A of the original game's action set and by payoff functions v α obtained by restricting the original payoff functions to the reduced state space X = ∆(A ) of G . If x ∈ X is a Nash equilibrium of some restriction of G, it will be called a restricted equilibrium; as such, x ∈ X is a restricted equilibrium of G if all strategies in its support earn equal payoffs.

Example 2.1 (Matching in normal form games). The simplest example of a population game is obtained by uniformly matching a population of agents to play a two-player symmetric normal form game with payoff matrix A = (A αβ ) n α,β=1 . Aggregating over all matches, the payoff to an α-strategist when the population is at state

x ∈ X is v α (x) = β∈A A αβ x β .
Example 2.2 (Potential games). A population game G is called a potential game [START_REF] Monderer | Potential games[END_REF][START_REF] Sandholm | Potential games with continuous player sets[END_REF] if there exists a potential function f defined on a neighborhood of X such that ∂f ∂x α = v α (x) for all α ∈ A and all x ∈ X .

(2.1)

Example 2.3 (Contractive games). A population game G is called (weakly) contractive [START_REF] Hofbauer | Stable games and their dynamics[END_REF] if

α∈A (v α (x ) -v α (x))(x α -x α ) ≤ 0 for all x, x ∈ X . (2.2) If (2.
2) binds only when x = x , G is called strictly contractive, whereas if (2.2) binds for all x, x ∈ X , G is called conservative. 7

2.2. Evolutionary dynamics. The term evolutionary dynamics refers to rules that assign to each population game G a dynamical system on its state space X . This is usually done by mapping each game to a law of motion, i.e. a differential equation of the form

ẋ = V (x). (D)
In most cases, the motion field V (x) of (D) is defined by introducing a mapping (x, π) → V (x, π) from state/payoff pairs to vectors, and then specifying that

V (x) ≡ V (x, v(x)).
In what follows, we will focus exclusively on such dynamics.

To ensure that solutions to (D) remain in X for all t ≥ 0, V (x) should not point outward from X ; formally, V (x) should lie in the tangent cone of X at x, defined here as

TC X (x) = {z ∈ R A 0 : z α ≥ 0 whenever x α = 0}. (2.3)
Under many evolutionary dynamics (including the replicator dynamics and other imitative dynamics), the support of x(t) remains invariant under (D), implying in turn that the interior of each face of X remains invariant under (D). When this is the case, V (x) actually lies in the tangent space to X at x, defined as

T X (x) = {z ∈ R A 0 : z α = 0 whenever x α = 0} ⊆ TC X (x).
(2.4)

Clearly, for every interior state x ∈ X • , we have T X (x) = TC X (x) = R A 0 . A basic monotonicity criterion linking (D) with the underlying game requires positive correlation between the strategies' payoffs and growth rates. Concretely, this means that

α∈A v α (x)V α (x) ≥ 0 for all x ∈ X , (PC)
with equality only if V (x) = 0. 8 If (D) satisfies (PC), every Nash equilibrium of G is a rest point of (D). For a detailed discussion, see [START_REF] Sandholm | Population Games and Evolutionary Dynamics. Economic learning and social evolution[END_REF].

We provide two prototypical examples of evolutionary dynamics below:

Example 2.4 (The replicator dynamics). The quintessential evolutionary game dynamics are the replicator dynamics of [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF]:

ẋα = x α v α (x) - β∈A x β v β (x) . (RD)
7 [START_REF] Hofbauer | Stable games and their dynamics[END_REF] use the name stable games instead of contractive, but Sandholm (2015) proselytizes for the terms employed here. In convex analysis, condition (2.2) is called monotonicity.

8 This and closely related conditions are considered by [START_REF] Friedman | Evolutionary games in economics[END_REF], [START_REF] Swinkels | Adjustment dynamics and rational play in games[END_REF], [START_REF] Sandholm | Potential games with continuous player sets[END_REF], and [START_REF] Demichelis | From evolutionary to strategic stability[END_REF].

Example 2.5 (The Euclidean projection dynamics). The other fundamental example we consider is the Euclidean projection dynamics of [START_REF] Nagurney | Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria[END_REF] (see also [START_REF] Friedman | Evolutionary games in economics[END_REF]Lahkar andSandholm, 2008). These are defined by ẋ = arg min

z∈TC X (x) v(x) -z 2 2 , (PD)
where z 2 = ( α z 2 α ) 1/2 denotes the ordinary Euclidean norm on R A . Geometrically, the dynamics (PD) are defined by taking the Euclidean projection of the payoff field v(x) onto the tangent cone TC X (x). Since TC X (x) = R A 0 on the interior X • of the simplex, we obtain the simple formula

ẋα = v α (x) - 1 |A| β∈A v β (x), (2.5)
valid for all interior x ∈ X • . For an explicit formula on the boundary of X , see Example 4.2.

2.3. Antecedents. The class of dynamics studied here is a substantial generalization of both the replicator dynamics and the projection dynamics. We now describe works from an assortment of fields that are antecedents of our approach.

The replicator equation (RD) for common interest games is a basic model from population genetics [START_REF] Schuster | Replicator dynamics[END_REF]. The fundamental theorem of natural selection, attributed to [START_REF] Fisher | The Genetical Theory of Natural Selection[END_REF], states that natural selection among genes increases overall population fitness. [START_REF] Kimura | On the change of population fitness by natural selection[END_REF] introduced a corresponding maximum principle showing that population fitness increases at a maximum rate under (RD), provided that one imposes a certain nonlinear constraint on the set of feasible changes in population frequencies (see Remark 3.2 in Section 3.3). Later, [START_REF] Shahshahani | A new mathematical framework for the study of linkage and selection[END_REF] and [START_REF] Akin | The geometry of population genetics[END_REF] put Kimura's maximum principle on a firm mathematical footing using tools from differential geometry -specifically, by introducing a suitable Riemannian metric (see Section 3.2). The derivation of the replicator dynamics in the latter papers provides a basic instance of the geometric construction of Riemannian dynamics developed in Section 3.6, while our construction based on balancing gains and costs can be viewed as an extension of Kimura's analysis (cf. Remark 3.2). [START_REF] Hofbauer | Adaptive dynamics and evolutionary stability[END_REF] model natural selection in populations of animals whose traits are represented by elements of a continuous set. They assume that all members of the population share the same trait x, except for an infinitesimal group of mutants whose traits differ infinitesimally from x. The evolution of the preponderant trait x follows a gradient-like process, moving in the direction that agrees with the play of the most successful local mutants. To obtain variations on this process, [START_REF] Hofbauer | Adaptive dynamics and evolutionary stability[END_REF] use a Riemannian metric to define the size and shape of the neighborhood of local mutants. When the trait space is X and the fitness of mutant y takes the linear form α y α v α (x), they showed that the evolution of x on the interior of X is given by

ẋα = β∈A g -1 αβ (x) - γ g -1 αγ (x) γ g -1 γβ (x) γ,κ g -1 γκ (x) v β (x), (2.6)
where g(x) is a field of symmetric positive definite matrices that defines the Riemannian metric in question (see Section 3.2). [START_REF] Hofbauer | Adaptive dynamics and evolutionary stability[END_REF] then observed that under the Shahshahani metric, the system (2.6) boils down to the replicator dynamics (RD). As we shall see, (2.6) describes the dynamics studied in this paper at all states x ∈ X in what we call the minimal-rank case (cf. Section 3.4).

In the course of analyzing perturbed best response dynamics [START_REF] Fudenberg | The Theory of Learning in Games, volume 2 of Economic learning and social evolution[END_REF] and variants of fictitious play [START_REF] Brown | Iterative solutions of games by fictitious play[END_REF], [START_REF] Hopkins | A note on best response dynamics[END_REF] introduced a class of game dynamics that are defined on the interior of X as

ẋα = β∈A M αβ (x)v β (x).
(2.7)

Here M (x) is a smoothly-varying field of symmetric matrices that are positive definite on R A 0 and map constant vectors to 0. Hopkins (1999) showed that the linearization of these dynamics agrees with that of perturbed best response dynamics up to a positive affine transformation. As a result, the local stability of rest points of (2.7) agrees with that of the corresponding rest points of perturbed best response dynamics with sufficiently small noise levels. As we show in Appendix A.1, the dynamics (2.6) satisfy Hopkins' conditions; conversely, all dynamics satisfying Hopkins' conditions can be expressed in the form (2.6). Thus, on the interior of X , the dynamics of [START_REF] Hopkins | A note on best response dynamics[END_REF] are equivalent to the dynamics studied here (Proposition A.3).

More recently, [START_REF] Harper | Escort evolutionary game theory[END_REF] used ideas from information geometry to define generalizations of the replicator dynamics, and employed concepts from Riemannian geometry to state and prove certain properties of the induced dynamics. Ignoring boundary issues, these dynamics are an important special case of ours -specifically, the class of separable dynamics that we introduce in Example 4.4.

Finally, we note here that there is a surprising and deep connection between the Hessian subclass of Riemannian game dynamics and a model of reinforcement learning recently examined by [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF]. We explore this relation in detail in Section 8.

Riemannian game dynamics

3.1. Gains, costs, and dynamics. We now define the dynamics we study as balancing a gain from motion, determined from the game's payoffs, against a cost of motion, a new primitive that captures the difficulty of motion along a given direction from a given state. To streamline our presentation, we focus below on interior states x ∈ X • ≡ int(X ), postponing the treatment of boundary states until the machinery needed to handle them is in place.

Given a population game G(A, v), the gain from motion from state x ∈ X along z ∈ R A is defined as

G v (z; x) = α∈A v α (x)z α , (3.1)
In words, the gain of motion measures the agreement between payoffs and vectors of motion as in the standard monotonicity criterion (PC). For an alternative interpretation, recall that the defining property (2.1) of a potential game with potential function f can be expressed as

α∈A ∂f ∂x α z α = α∈A v α (x)z α for all z ∈ R A and all x ∈ X . (3.2)
The left-hand side of (3.2) is the rate of change in the value of potential as the state moves away from x along z. Viewed in this light, the gain G v (z; x) extends the notion of "the rate of increase in potential" to games that do not admit a potential function. 9 In particular, the gain captures the alignment between the direction of motion z and the payoffs at state x; it is also linearly homogeneous in z, so it grows linearly as one increases the speed of motion in a fixed direction. By contrast, the cost of motion C(z; x) is a primitive that represents the intrinsic difficulty of moving from state x along a given displacement vector z. For concreteness, we assume that the costs of motion are positive, smoothly varying with the population state x, and quadratic in z. It is convenient to define costs C(z; x) for states x in the positive orthant K • ≡ R A ++ and for displacement vectors z in R A . 10 Then since costs are positive and quadratic in z, the cost function can be expressed as

C(x; z) = 1 2 z g(x)z, for all z ∈ R A and all x ∈ K • . (3.3)
where g is a smooth assignment of symmetric positive definite matrices g(x) to states x ∈ K • . To use the above to define the dynamics at interior population states, we posit that the vector of motion from state x ∈ X • maximizes the difference between the gain of motion G v (x; z) and the cost of motion C(x; z), subject to feasibility:

ẋ = arg max z∈R A 0 [G v (z; x) -C(z; x)].
(3.4)

We refer to the dynamics (3.4) as Riemannian game dynamics, for reasons that we will soon make clear. Before doing so, we show how the leading examples of these dynamics are derived from the ansatz (3.4) through suitable choices of the cost function C(x; z):

Example 3.1. A straightforward, state-independent choice for the cost of motion is

C(x; z) = 1 2 α∈A z 2 α . (3.5)
To solve the resulting maximization problem in (3.4), consider the Lagrangian

Λ(z, µ; x) = α∈A v α (x)z α - 1 2 z 2 α -µz α , (3.6)
where the last term is associated with the motion feasibility constraint α∈A z α = 0. A direct differentiation gives the optimality condition z α = v α (x) -µ, and the feasibility constraint yields

µ = |A| -1 α∈A v α (x). Substituting back into in (3.4) yields ẋα = v α (x) - 1 |A| α∈A v α (x). (3.7)
As we discussed in Section 2 (cf. Example 2.5), the system (3.7) describes the (Euclidean) projection dynamics of [START_REF] Nagurney | Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria[END_REF] on X • .

9

The logic here is similar to the original motivation for the definition of contractive games, which extends the idea of a game with a concave potential function to games that do not admit a potential [START_REF] Hofbauer | Stable games and their dynamics[END_REF]. The gain (3.1) is referred to as the "aggregate gross gain" by [START_REF] Zusai | Gains in evolutionary dynamics: a unifying approach to stability for contractive games and ESS[END_REF] in his general analysis of Lyapunov functions for contractive games and evolutionarily stable strategies. 10 We can interpret K • as the set of population states that could arise if the population size were allowed to vary. We could instead define costs only for states in X • and displacement vectors in R A 0 , at the price of additional abstraction: see Remark 3.1 below.

Example 3.2. For a basic state-dependent choice for the cost of motion, let

C(x; z) = 1 2 α∈A z 2 α x α (3.8)
The Lagrangian for the maximization problem in (3.4) is now

Λ(z, µ; x) = α∈A v α (x)z α - z 2 α 2x α -µz α .
(3.9)

Differentiating now yields the optimality condition z α = x α v α (x) -µx α , and feasibility implies that µ = β∈A x β v β (x). Substituting in (3.4), we obtain

ẋα = x α v α (x) - β∈A x β v β (x) .
(3.10)

The system (3.10) defines the replicator dynamics of [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF] (cf. Example 2.4). Although the derivation above assumed that x is interior, the expression (3.10) actually describes the replicator dynamics on all of X ; we explain why this is so in Section 3.4.

3.2. Costs of motion and Riemannian metrics. We now proceed with a reinterpretation of the costs of motion using notions from geometry. The fundamental notion here is that of a Riemannian metric, a position-dependent variant of the ordinary (Euclidean) scalar product between vectors. 11

To start, we recall that a scalar product on a subspace W of R A is a bilinear pairing •, • : W × W → R which satisfies the following for all w, w ∈ W :

(1) Symmetry: w, w = w , w .

(2) Positive definiteness: w, w ≥ 0, with equality if and only if w = 0. The norm of a vector w ∈ W is then defined as w = w, w The matrix g is known as the metric tensor of •, • and its components are g αβ = e α , e β . Clearly, a scalar product is represented uniquely by its metric tensor and vice versa, so we will move freely between the two representations in what follows. With all this in mind, a Riemannian metric on an open set U of R A is a C 1smooth assignment of scalar products •, • x to each x ∈ U -or, equivalently, as a smooth field g(x) of symmetric positive-definite matrices on U . In other words, a 11 To be clear, a Riemannian metric is not a metric in the sense of measuring distances between points in a metric space, but it induces such a distance function in a canonical way. For a comprehensive introduction to this topic, see the masterful account of [START_REF] Lee | Riemannian Manifolds: an Introduction to Curvature[END_REF][START_REF] Lee | Introduction to Smooth Manifolds[END_REF].

Riemannian metric prescribes a way of measuring lengths of and angles between displacement vectors at each x ∈ U .

The similarity in notation between the above and the definition of costs of motion is not a coincidence. Looking back at (3.4), we see that costs of motion and Riemannian metrics are both defined by means of a C 1 -smooth field of symmetric positive-definite matrices, with costs and norms being related via

C(x; z) = 1 2 z g(x)z = 1 2 z 2 x .
(3.13)

We summarize this connection as follows:

Observation 3.1. Specifying a cost function on K • is equivalent to endowing K • with a Riemannian metric.

Remark 3.1. Defining costs of motion and Riemannian metrics on the positive orthant K • allows us to work in standard coordinates, and simplifies passing from one to the other. That being said, we could equally well have taken a more parsimonious approach by defining costs of motion C(x; z) only for states x ∈ X • and feasible displacement vectors z ∈ R A 0 , and similarly working with Riemannian metrics •, • x on R A 0 for each x ∈ X • . In this approach, the equivalence between cost functions and Riemannian metrics can be derived from a standard bijection between quadratic forms and bilinear forms (see e.g., Friedberg et al., 2002, p. 433), but at the cost of an extra degree of abstraction.

Before proceeding, it is instructive to recast our previous examples in terms of Riemannian metrics:

Example 3.3. The Euclidean metric is defined by choosing g(x) to be the identity matrix:

g(x) = I = diag(1, . . . , 1) for all x ∈ K • .

(3.14) This metric corresponds to the cost function C(z; x) = 1 2 α z 2 α of Example 3.1, and yields the standard expressions w, w x = w w and w x =

√

w w, all independent of x.

Example 3.4. The Shahshahani metric is defined as

g(x) = diag(1/x 1 , . . . , 1/x n ) for all x ∈ K • . (3.15)
This metric corresponds to the cost function C(z; x) = 1 2 α z 2 α /x α of Example 3.2, and yields the Shahshahani inner product w, w x = α w α w α /x α . In contrast to its Euclidean counterpart, the Shahshahani metric is state-dependent: For instance, since e α x = x -1/2 α , the set of vectors at x with Shahshahani norm 1 is squeezed toward the x α axis as x α becomes small (cf. Fig. 1(b)).

We now present two further classes of metrics to which we return in Section 4:

Example 3.5. For p ≥ 0, the p-Shahshahani metric is defined as

g(x) = diag(1/x p 1 , . . . , 1/x p n ) for all x ∈ K • . (3.16)
This definition includes the Euclidean metric (p = 0) and the standard Shahshahani metric (p = 1) as special cases, and corresponds to the cost function

C(x; z) = 1 2 α∈A z 2 α x p α .
(3.17 Since 1

x p α / 1 x p β = (x β /x α ) p
, specifying larger values of p means raising the relative cost of changes in the use of rare strategies. For instance, if strategy α is half as prevalent in the population as strategy β, then changes in the use of α cost 2 p times as much as changes in the use of β.

Figs. 1(a)-1(c) illustrate the effects of increasing the value of p on costs of motion: when x α is small, increasing p increases the cost of moving toward and away from the x α = 0 boundary relative to the cost of moving along this boundary.

Example 3.6. Let A 1 , . . . , A m be a partition of A into m groups of intrinsically similar strategies, let [α] denote the group containing strategy α, let x [α] = β∈[α] x β denote the population share of all strategies that are "similar" to α in the above partition, and let s > 0 be a parameter representing the "strength" of the similarity relation. The nested Shahshahani metric is then defined as

g αβ (x) = δ αβ xα + s 1 x [α] if β ∈ [α], 0 otherwise. (3.18)
While the full expression for the cost function corresponding to the metric (3.18) is cumbersome, the cost of motion along the basic directions e β -e α takes a fairly simple form, namely

C(e β -e α ; x) =    1 2 1 xα + 1 x β if β ∈ [α], 1 2 1 xα + 1 x β + 1 2 s 1 x [α] + 1 x [β]
otherwise.

(3.19) Under (3.19), switches between strategies in the same group take the same form as under the Shahshahani cost function from Examples 3.2 and 3.4. On the other hand, switches between strategies in different groups are more costly, with the additional costs being inversely proportional to population shares of the groups and proportional to the strength of the similarity relation. Fig. 1(d) illustrates the costs of motion (3.19) from various states in X for partition A 1 = {1}, A 2 = {2, 3} and similarity strength s = 3. The unit balls near the x 1 = 0 boundary are elongated along that boundary to a greater extent than the balls near the other boundaries. This reflects the fact that, mutatis mutandis, a unit of cost buys more motion between strategies 2 and 3 than between the other pairs of strategies.

3.3. Derivation of the dynamics: the interior case. With the above machinery at hand, we can provide an explicit description of the game dynamics under study on the interior X • of X . To do so, fix a population game G ≡ G(A, v) and a Riemannian metric g on K • . Then, by (3.13), the associated Riemannian game dynamics are

ẋ = arg max z∈R A 0 [G v (z; x) -C(z; x)] = arg max z∈R A 0 α∈A v α (x)z α -1 2 z 2 x . (3.20)
As in Examples 3.1 and 3.2, to obtain an explicit expression for the vector of motion that solves the maximization problem (3.20), consider the Lagrangian

Λ(z, µ; x) = α∈A v α (x)z α -1 2 z 2 x -µ α∈A z α . (3.21)
Then, interpreting (v α (x)) α∈A as a row vector (see Section 3.6) and writing 1 = (1, . . . , 1) for the column vector of ones in the standard basis of R A , a simple differentiation yields the first-order optimality condition

v(x) = z g(x) + µ1 . (3.22)
Thus, after rearranging, we get

z = g -1 (x)[v(x) -µ1], (3.23)
where g -1 (x) denotes the inverse of the matrix g(x). Using the constraint α z α = 0 to solve for µ and substituting in (3.20), some easy algebra leads to the explicit expression

ẋ = g -1 (x) v(x) - v(x)g -1 (x)1 1 g -1 (x)1 1 . (3.24) Thus, if we set v (x) = g -1 (x)v(x) and n(x) = g -1 (x)1, (3.25)
we obtain

ẋ = v (x) - v (x), n(x) x n(x) 2 x n(x) = v (x) -α∈A v α (x) α∈A n α (x) n(x) (3.26)
We now revisit our two archetypal examples in the light of the explicit expression (3.26):

Example 3.7. If g(x) = I is the Euclidean metric, we get v (x) = v(x) and n(x) = 1, so (3.26) immediately boils down to (3.7). Therefore, when the cost of motion is defined using Euclidean lengths, the components of the displacement vector

ẋ equal those of v(x) up to a constant that ensures that ẋ ∈ R A 0 . Example 3.8. If g(x) = diag(1/x 1 , . . . , 1/x n ) is the Shahshahani metric of Exam- ple 3.4, we readily get v α (x) = x α v α (x)
and n α (x) = x α , so (3.26) boils down to the replicator dynamics (3.10). Thus, when costs are defined using the Shahshahani norm of the population displacement vector, changes in the use of rare strategies are more costly than changes in the use of common ones. As a consequence, the initial term of ẋα is proportional to both the payoff v α (x) of strategy α and to the mass x α of agents playing strategy α. The second term ensures that ẋ ∈ R A 0 , but here the normalization for strategy α is itself proportional to x α .

Remark 3.2. The derivation above is closely related to [START_REF] Kimura | On the change of population fitness by natural selection[END_REF] derivation of the replicator dynamics in common interest games, i.e., games in which v(x) = (Ax) for some symmetric matrix A. Such games admit the potential function f (x) = 1 2 x Ax (cf. Eq. (2.1)), which reports one-half of the population's average payoff. Using somewhat different language, [START_REF] Kimura | On the change of population fitness by natural selection[END_REF] proposed the population dynamics

ẋ = arg max α ∂f ∂x α z α : z ∈ TC X (x) and z 2 x = σ 2 v (x) . (3.27) Here α ∂f ∂xα z α is the rate of change of potential along z, • 2 x is the Shahshahani norm and σ 2 v (x) = α x α [v α (x)-β x β v β (x)]
2 denotes the variance in the population's payoffs at state x. It is easy to verify that (3.27) boils down to the replicator dynamics for the potential game v(x) = (Ax) .

3.4. The boundary case. We now turn to an important dichotomy that arises when extending the definition of the dynamics (3.20) to the boundary of X . To begin, recall from (2.4) that the tangent space T K (x) to the nonnegative orthant K at x is the linear subspace

T K (x) = {z ∈ R A : z α = 0 whenever x α = 0} = R supp(x) .
(3.28)

We then say that a Riemannian metric g on K • is extendable to K if the map x → g -1 (x) on K • admits a (necessarily unique) C 1 -smooth extension to K which we denote by g (so g (x) ≡ g -1 (x) for all x ∈ K • ), and which satisfies

T K (x) ⊆ im g (x) for all x ∈ K. (3.29)
In the above, im g (x) is the image (column space) of g (x); we henceforth call this set the domain of g at x and denote it by dom g(x). Proposition B.1 in Appendix B shows that if g is extendable in the sense of (3.29), then the field of scalar products associated with g also admits a unique continuous extension from

K • to K, with •, • x defined on dom g(x).
In what follows, we focus on two basic forms of extendability. First, if dom g(x) = R A for all x ∈ K, we say that g is full-rank extendable; instead, if dom g(x) = T K (x) for all x ∈ K, we say that g is minimal-rank extendable. We henceforth use the term "extendable" to refer to these two cases exclusively.

Example 3.9. The Euclidean metric has g (x) = g -1 (x) = I for all x ∈ K, so it is full-rank extendable by default.

Example 3.10. The Shahshahani metric has g x) for all x ∈ K. Thus, the Shahshahani metric is minimal-rank extendable, and the induced scalar product on dom g

(x) = g -1 (x) = diag(x 1 , . . . , x n ), so dom g(x) = T K (x) = R supp(
(x) = R supp(x) is w, w x = α∈supp(x)
w α w α /x α for all w, w ∈ T K (x).

(3.30)

Remark 3.3. Intuitively, minimal-rank extendable metrics partition K into the relative interiors of each of its faces (including K • itself). We will see that under the dynamics generated by such metrics, the relative interior of each face of X is an invariant set.

To extend the definition of the dynamics to the boundary bd(X ) of X , we introduce the cone of g-admissible vectors

Adm g (x) = TC X (x) ∩ dom g(x), (3.31)
This cone, which comprises all tangent vectors z ∈ TC X (x) that also lie in dom g(x), specifies the possible directions of motion at a given state x ∈ X . In particular, when x ∈ X • is interior, we have TC X (x) = T X (x) = R A 0 and dom g(x) = R A . Thus, the g-admissible set is the hyperplane

Adm g (x) = R A 0 ∩ R A = R A 0 , (3.32)
as anticipated in Eq. (3.20). Further instances of g-admissible cones are depicted in Section 3.4. The restriction to dom g(x) is needed because the norm z 2

x is only defined for z ∈ dom g(x). When g is extendable, the only case in which dom g(x) is not all of R A occurs when x ∈ bd(X ) and g is minimal-rank extendable, in which case dom g(x) = T X (x) = R supp(x) (cf. Example 3.10).

Riemannian game dynamics.

With all this at hand, we are finally in a position to extend the definition of the dynamics to all of X . Concretely, building on (3.20), the Riemannian game dynamics induced by an extendable g are

ẋ = arg max z∈Admg(x) [G v (z; x) -C(z; x)] = arg max z∈Admg(x) α∈A v α (x)z α -1 2 z 2 x (RmD)
Equation (3.26) showed that (RmD) can be expressed at interior states as where v (x) = g (x)v(x) and n(x) = g (x)1. After a slight rearrangement, we can also express the dynamics as a linear transformation of payoffs v(x):

ẋ = v (x) - v (x), n(x) x n(x) 2 x n(x) = v (x) -α∈A v α (x) α∈A n α (x) n(x) (3.33a)
ẋα = β∈A g αβ (x) - n α (x)n β (x) γ n γ (x) v β (x).
(3.33b) Equation (A.2b) in Appendix A provides a concise third expression for the dynamics on X • in terms of a pseudoinverse matrix.

If g is minimal-rank extendable, Proposition B.2 in Appendix B shows that (3.33) holds for all x ∈ X , provided that one uses g (x) in the definition (3.25) of v (x) and n(x). Proposition B.2 also shows that, in this case, one need only take the sums in the formulas (3.33) over the strategies in the support of x.

If instead g is full-rank extendable, extending (3.33) to boundary states requires solving a convex program whose inequality constraints may be active. For this reason, coordinate formulas for (RmD) may depend on the support of x -and, indeed, (RmD) may fail to be continuous at the boundary of X (see Example 4.2 below). With this in mind, it will be convenient to call the dynamics generated by minimal-rank extendable metrics continuous Riemannian dynamics, and those generated by full-rank extendable metrics discontinuous Riemannian dynamics.

3.6. Geometric derivation of the dynamics. In (RmD), the dynamics' vector of motion from x is defined to maximize the difference between the gain G v (z; x) = α∈A v α (x)z α and the cost of motion C(z; x) = 1 2 z 2

x over the set of admissible vectors z ∈ Adm g (x). We now show how these dynamics can be derived using a purely geometric approach, generalizing [START_REF] Shahshahani | A new mathematical framework for the study of linkage and selection[END_REF] derivation of the replicator dynamics in common interest games, and [START_REF] Nagurney | Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria[END_REF] definition of the Euclidean projection dynamics. In what follows, we rely on some basic ideas from Riemannian geometry; for a comprehensive treatment, we refer again to [START_REF] Lee | Riemannian Manifolds: an Introduction to Curvature[END_REF].

To start, we introduce ideas about duality that explain our convention of writing payoffs using row vectors and the notations v (x) and n(x) from Section 3.3. As in Section 3.2, let W is a subspace of R A . A linear functional ω : W → R acting on vectors w ∈ W is called a covector, and the space W * of such functionals is called the dual space of W . We write ω|w for the action of a covector ω ∈ W * on a vector w ∈ W ; to emphasize this pairing, the elements of W and W * are also referred to as primal and dual vectors respectively. When W = R A , we use the standard basis of R A to write everything in matrix notation, and distinguish vectors and covectors by writing primal vectors w ∈ R A as column vectors and dual vectors ω ∈ (R A ) * as row vectors. The action ω|w of ω on w is then given by the matrix product ω w = α ω α w α .

After mild manipulations, the definitions of Nash equilibrium (NE), positive correlation (PC), potential games (2.1) and contractive games (2.2) can be expressed in the form α v α (x)z α , where z is a tangent vector. Put differently, the payoff "vector" (v α (x)) α∈A acts as a linear functional on displacement vectors, and so should be regarded as a covector. This is why we represent payoffs v(x) in matrix notation as row vectors.

Example 3.11. The defining property (2.1) of potential games can be expressed as

Df (x)|z = v(x)|z for all z ∈ R A and all x ∈ X .
(3.34)

On the left-hand side, Df (x) denotes the derivative of f at x, a linear functional that acts on tangent vectors z ∈ R A to yield the directional derivative f (x; z). Thus, (3.34) can be expressed as an equality between covectors, viz. v(x) = Df (x).

Returning to our derivation of game dynamics, our aim in what follows is to find a vector field x → V (x) ∈ TC(x) that agrees to the greatest possible extent with the payoff covector field x → v(x), where this "agreement" is defined in terms of the Riemannian metric g. The derivation requires two steps: i) using a canonical transformation to convert the covector field into a vector field; and ii) projecting this field onto the cone of admissible vectors of motion.

For the first step, fix a Riemannian metric g on K • that is extendable to K as defined in Section 3.4. The primal equivalent of a covector ω ∈ (R A ) * at x ∈ K is the (necessarily unique) vector ω ∈ dom g(x) such that ω|w = ω , w x for all w ∈ dom g(x).

(3.35)

In matrix notation, it is easy to verify that

ω = g (x)ω , (3.36) in agreement with the definition v (x) = g (x)v(x) from (3.25).
For the second step, we transform each vector v (x) into a g-admissible vector by projecting it onto Adm g (x). Specifically, for all x ∈ X and w ∈ dom g(x), the projection of w at x is defined as

Π x (w) = arg min z∈Admg(x) w -z x .
(3.37)

The induced Riemannian dynamics are then defined as

ẋ = Π x (v (x)). (3.38) When x ∈ X • is interior, we have Adm g (x) = R A 0 by default, so Π x (w) is simply the orthogonal projection of w ∈ dom g(x) = R A onto R A
0 with respect to g. Accordingly, Π x (w) can be computed by finding a normal vector to R A 0 and subtracting this vector's contribution to w (as in the first step of the Gram-Schmidt orthonormalization process). To carry this out, observe that α z α = 0 for all z ∈ R A 0 , so the vector n(x) = g (x)1 defined in (3.25) satisfies n(x), z x = n(x) g(x)z = 1 g (x)g(x)z = 0 for all z ∈ R A 0 .

(3.39)

This shows that n(x) is a normal vector to T X (x) with respect to g(x). Thus, for all x ∈ X • , we can express the right-hand side of (3.38) as

Π x (v (x)) = v (x) -proj n(x) v (x) = v (x) - n(x), v (x) x n(x) 2 x n(x), (3.40)
in agreement with (3.26). More generally, for any state x ∈ X we have

Π x (v (x)) = arg min z∈Admg(x) v (x) -z x = arg min z∈Admg(x) v (x) 2 x + z 2 x -2 v (x), z x = arg max z∈Admg(x) v (x), z x -1 2 z 2 x -1 2 v (x) 2 x = arg max z∈Admg(x) v(x)|z -1 2 z 2 x .
(3.41)

The dynamics (3.38) and (RmD) are therefore identical. We will take advantage of this geometric representation of (RmD) freely in what follows.

Remark 3.4. In addition to building on Kimura's and Shahshahani's derivations of the replicator dynamics, the dual representations of Riemannian game dynamics have a close analogue in a class of game dynamics called target projection dynamics [START_REF] Friesz | Day-today dynamic network disequilibria and idealized traveler information systems[END_REF][START_REF] Sandholm | Excess payoff dynamics and other well-behaved evolutionary dynamics[END_REF]. These dynamics are defined on X as

ẋ = arg min x ∈X v(x) -x 2 2 -x, (3.42)
Using a version of (3.41), [START_REF] Tsakas | The target projection dynamic[END_REF] showed that (3.42) can also be expressed as

ẋ = arg max x ∈X v(x)|x -1 2 x -x 2 2 -x.
(3.43)

Examples

We now present a variety of examples of Riemannian game dynamics. We start by extending the interior expressions (3.7) and (3.10) for our two prototypical dynamics to allow for boundary states:

Example 4.1 (Replicator dynamics revisited). Let g be the Shahshahani metric, so g αβ (x) = δ αβ x β , n α (x) = x α , and v α (x) = x α v α (x). Since g is minimal-rank extendable, (3.33) yields the (continuous) Riemannian dynamics

ẋα = x α v α (x) - β x β v β (x) , (RD)
which are the replicator dynamics of [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF]. The dynamics' continuity is reflected in the fact that the formula (RD) is valid throughout X .

Example 4.2 (Projection dynamics revisited). Let g be the Euclidean metric. Starting from formulation (3.38), [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF] derived the following representation of the associated (discontinuous) Riemannian dynamics:

ẋα = v α (x) -|A(x)| -1 β∈A(x) v β (x) if α ∈ A(x), 0 otherwise, (4.1)
where A(x) is a subset of A that maximizes the average |A | -1 β∈A v β (x) over all subsets A ⊂ A that contain supp(x). These are the projection dynamics (PD) of [START_REF] Nagurney | Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria[END_REF]. The discontinuity of (PD) is reflected in the appearance of supp(x) in (4.1) via the definition of A(x).

Remark 4.1. The dynamics (RD) and (PD) highlight an important qualitative difference between Shahshahani and Euclidean projections, which is representative of continuous and discontinuous Riemannian dynamics respectively. The replicator dynamics (RD) comprise a Lipschitz continuous dynamical system on X which preserves the face structure of X , in that the relative interior of each face of X remains invariant. By contrast, the projection dynamics (PD) may fail to be continuous at the boundary of X . Thus, the relevant notion of a solution to (PD) is that of a Carathéodory solution, which allows for kinks at a measure zero set of times. As a result, solutions of (PD) may leave and re-enter the relative interior of any face of X in perpetuity.

The next example generalizes the previous two:

Example 4.3 (The p-replicator dynamics). For p ≥ 0, let g αβ (x) = δ αβ x -p β denote the p-Shahshahani metric introduced in Example 3.5. We then have g αβ (x) = δ αβ x p β , n α (x) = x p α , and v α (x) = x p α v α (x). Thus, (3.33) yields the p-replicator dynamics

ẋα = x p α v α (x) - β∈A x p β v β (x) β∈A x p β , (4.2)
valid for all interior x ∈ X • . These dynamics were first defined by [START_REF] Harper | Escort evolutionary game theory[END_REF]. Since g is minimal-rank extendable if and only if p > 0, the dynamics are defined throughout X via Eq. (4.2) for precisely these values of p. However, the dynamics are only Lipschitz continuous for p ≥ 1; see Example 4.6 and Section 6.1 below. Three values of p are worth highlighting:

(1) For p = 0, we obtain the projection dynamics (PD).

(2) For p = 1, we obtain the replicator dynamics (RD).

(3) For p = 2, we obtain the log-barrier dynamics, a system first examined by [START_REF] Bayer | The nonlinear geometry of linear programming I. Affine and projective scaling trajectories[END_REF] in the context of convex programming. 12 In the above dynamics, the value of p parametrizes the costs of changes in the use of less common strategies. This is illustrated in Fig. 3, which presents a collection of p-replicator phase portraits in standard Rock-Paper-Scissors:

A =   0 -1 1 1 0 -1 -1 1 0   . (4.3)
When p = 0, displacement costs are independent of the current state; thus the circular form of the payoffs (4.3) generates circular closed orbits, subject to feasibility constraints (Fig. 3(a)). As p increases, the costs of motion for uncommon strategies become more important relative to the game's payoffs (Figs. 3(b) and 3(c)).

As a direct consequence, the closed orbits of the dynamics are "flattened" near each face of the simplex, and are ultimately reshaped into a nearly triangular form (Fig. 3(d)).13 Fig. 3 also illustrates a basic dichotomy between continuous and discontinuous Riemannian dynamics. In the discontinuous regime (p = 0), there is a unique forward solution from every initial condition in X . However, solutions may enter and leave the boundary of X , and solutions from different initial conditions can merge in finite time. In the smooth regime (p ≥ 1), solutions exist and are unique in forward and backward time, and the support of the state remains fixed along each solution trajectory. Existence and uniqueness of solutions is treated formally in Section 6.1.

Example 4.4 (Separable metrics and their dynamics). A Riemannian metric g on K • is called separable if its metric tensor is of the form

g(x) = diag(1/φ(x 1 ), . . . , 1/φ(x n )), (4.4)
where φ : [0, ∞) → [0, ∞) is a continuous weighting function that is strictly positive on (0, ∞). For such metrics, we readily get

g (x) = diag(φ(x 1 ), . . . , φ(x n )), (4.5)
so g is minimal-rank extendable if lim z→0 + φ(z) = 0 and full-rank extendable otherwise. When (3.33) applies, the dynamics induced by g take the form

ẋα = φ(x α ) v α (x) - β φ(x β )v β (x) β φ(x β ) . (4.6)
Ignoring the dynamics' behavior at the boundary, (4.6) was studied by [START_REF] Harper | Escort evolutionary game theory[END_REF] under the name escort replicator dynamics, and was further examined by [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] and [START_REF] Bravo | On the robustness of learning in games with stochastically perturbed payoff observations[END_REF] in the context of game-theoretic learning (see Section 8). It is clear that the construction above generalizes immediately to allow different weighting functions for different strategies.

Moving beyond the separable case, Riemannian dynamics can also capture the effects of intrinsic relationships among the game's strategies.

Example 4.5 (Nested replicator dynamics). In Example 3.6, we defined the nested Shahshani metric as constant. A straightforward calculation shows that

g αβ (x) = δ αβ xα + s 1 x [α] if β ∈ [α], 0 otherwise, ( 4
g αβ (x) = x α δ αβ -s 1+s xαx β x [α] if β ∈ [α], 0 otherwise. (4.8)
It is evident from (4.8) that the metric g is minimal-rank extendable. Applying (3.33), we find that g generates the nested replicator dynamics: The imitative dynamics (NRD) were introduced by Mertikopoulos and Sandholm (2018) to model settings in which agents assess strategies using two distinct procedures: at rate s 1+s , an agent only compares the payoff of his current strategy α to those of strategies in group [α]; at rate 1 1+s , they compare the payoff of their current strategy to that of all other strategies. Fig. 4 presents phase diagrams of the dynamics (NRD) with s = 3 in the standard Rock-Paper-Scissors game. The two panels illustrate the consequences of two similarity groupings. In each case, the longest "side" of each closed orbit corresponds to the pair of similar strategies, which are switched between more easily than the remaining pairs of dissimilar strategies.

ẋα = x α   s 1 + s   v α (x) - 1 x [α] β∈[α] x β v β (x)   + 1 1 + s   v α (x) - β∈A x β v β (x)     (NRD) if x α > 0 and ẋα = 0 otherwise. R P S (a) A 1 = {R, P}, A 2 = {S} R P S (b) A 1 = {R, S}, A 2 = {P}
The following class of dynamics incorporates all of our previous examples. It is examined at depth in Sections 7 and 8:

Example 4.6 (Hessian Riemannian metrics and their dynamics). A generalization of the above class of examples can be obtained by considering Riemannian metrics that are defined as Hessians of convex functions. 14 To that end, let h : K → R be a continuous function on K such that (i ) h is C 3 -smooth on every positive suborthant of K.

(ii ) Hess h(x) is positive definite for all x ∈ K • . Then, h induces a natural Riemannian metric on K • defined as g = Hess h, (4.9)

or, in components:

g αβ (x) = ∂ 2 h(x) ∂x α ∂x β . (4.10)
When this is the case, we say that g is a Hessian Riemannian (HR) metric and we refer to h as the metric potential of g.

14

For the origins of the idea in geometry, see [START_REF] Duistermaat | On Hessian Riemannian structures[END_REF] and references therein; for applications to convex programming, see [START_REF] Bolte | Barrier operators and associated gradient-like dynamical systems for constrained minimization problems[END_REF] and [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF] As an example, the metric (3.18) that generates the nested dynamics (NRD) is an HR metric with potential

h(x) = α∈A x α log x α + s log x [α] .
(4.11)

Moreover, every separable metric of the form (4.4) is an HR metric with potential

h(x) = α∈A θ(x α ) (4.12)
for some smooth function θ : [0, +∞) → R with 1/θ (z) = φ(z). In particular, for p / ∈ {1, 2}, the p-replicator dynamics are generated by the potential

h p (x) = α∈A θ p (x α ) with θ p (z) = 1 (p-1)(p-2) z 2-p , (4.13)
and for p = 1 and p = 2, the corresponding potential functions are

h 1 (x) = α∈A x α log x α and h 2 (x) = - α∈A log x α , (4.14)
respectively. 15 The values p = 0, p = 1, and p = 2 partition the class of p-replicator dynamics into seven cases whose properties we summarize in Table 1. 16 Definition (4.9) is an integrability condition on the matrix field g. As with vector fields on simply connected domains, this can be characterized by a symmetry condition on the derivatives of g, 17 namely

∂g αγ ∂x β = ∂g βγ ∂x α for all α, β, γ ∈ A. (4.15)
15 It is possible to define the potential hp for all values of p using a single formula. Let θp(z) = (z 2-p + p(p -2)z -(p -1) 2 )/((p -1)(p -2)) when p = {1, 2}, and define θ 1 and θ 2 by analytic continuation. Linear and constant terms do not affect the resulting metric, and the explicit formulas for θ 1 and θ 2 follow from the fact that lim a→0 (z a -1)/a = log z.

16 When p ≥ 2, the potential hp becomes infinite on the boundary of K, violating a standing assumption for h; we address this technicality in Remark 7.1. Also, the (negative) Tsallis entropy [START_REF] Tsallis | Possible generalization of Boltzmann-Gibbs statistics[END_REF] mentioned in Table 1 is defined as Sq(x) = (q -1) -1 α (x q α -xα) for q ∈ (0, 1). 17 This characterization follows from the integrability condition for ordinary vector fields (i.e., symmetry of the Jacobian matrix) and the symmetry of g(x).

Conditions (4.9) and (4.15) differ fundamentally from integrability conditions appearing in previous work on game dynamics, which are imposed on the vector fields that define the dynamics. 18 In Section 7, we show that this integrability property provides important theoretical tools for the analysis of the induced Riemannian dynamics, which we call Hessian game dynamics.

Microfoundations via revision protocols

To provide microfoundations for deterministic game dynamics (D), one typically specifies a stochastic revision process that induces (D) in the so-called "mean field" limit. To do so, suppose that agents in the population are recurrently chosen at random and given the opportunity to switch strategies. What agents do when facing such opportunities is described by a revision protocol ρ whose components ρ αβ (x, π) describe the rates at which α-strategists who have received revision opportunities switch to strategy β, as a function of the current population state x and payoff vector π. 19 Together, a population game G ≡ G(A, v) and a revision protocol ρ induce the mean dynamics:

ẋα = β =α x β ρ βα (x, v(x)) -x α ρ αβ (x, v(x)) , (MD)
which describe the rate of change in the use of each strategy α as the difference between inflows into α from other strategies and outflows from α to other strategies. For a fixed protocol ρ, (MD) can be viewed as a map from population games v to laws of motion on X , as described in Section 2.2. 20 The prototype for this construction is, again, the replicator dynamics (RD). Three well-known protocols that generate (RD) are:

ρ αβ (x, π) = x β π β ,
(5.1a)

ρ αβ (x, π) = -x β π α , (5.1b) ρ αβ (x, π) = x β [π β -π α ] + , (5.1c)
with π assumed nonnegative in (5.1a) and nonpositive in (5.1b). 21 The x β appearing in the right-hand sides allows us to interpret (5.1a)-(5.1c) as imitative protocols, with a revising agent picking a candidate strategy by observing the choice and the payoff of a randomly chosen opponent. The protocols differ in how payoffs determine the rates at which switches are consummated. Protocols (5.1a) and (5.1b), due to [START_REF] Weibull | Evolutionary Game Theory[END_REF] and [START_REF] Björnerstedt | Nash equilibrium and evolution by imitation[END_REF], are respectively called imitation of success and imitation driven by dissatisfaction. In the former, imitation rates increase linearly in the opponent's payoff; in the latter, imitation rates decrease linearly in the revising agent's own payoff. Protocol (5.1c) is due to [START_REF] Helbing | A mathematical model for behavioral changes by pair interactions[END_REF] and [START_REF] Schlag | Why imitate, and if so, how? A boundedly rational approach to multi-armed bandits[END_REF], and is called pairwise proportional imitation.

18 See [START_REF] Hart | A general class of adaptive strategies[END_REF], [START_REF] Hofbauer | Stable games and their dynamics[END_REF]), and Sandholm (2010a[START_REF] Sandholm | Probabilistic interpretations of integrability for game dynamics[END_REF].

19 [START_REF] Weibull | Evolutionary Game Theory[END_REF] and [START_REF] Björnerstedt | Nash equilibrium and evolution by imitation[END_REF] introduce revision protocols for imitative dynamics. [START_REF] Sandholm | Population Games and Evolutionary Dynamics. Economic learning and social evolution[END_REF][START_REF] Sandholm | Population games and deterministic evolutionary dynamics[END_REF] extends this approach to more general classes of dynamics. 20 Solutions to (MD) may further be viewed as approximations to the sample paths of stochastic evolutionary models generated by the game G and protocol ρ: for a comprehensive treatment, see [START_REF] Benaïm | Deterministic approximation of stochastic evolution in games[END_REF] and [START_REF] Roth | Stochastic approximations with constant step size and differential inclusions[END_REF]. 21 Since the replicator dynamics (and all Riemannian game dynamics) are invariant to equal shifts in all strategies' payoffs, these assumptions about payoffs are innocuous.

Under (5.1c), a revising agent only considers switching if the opponent's payoff is higher than their own, and then does so at a rate proportional to the payoff difference. Substituting any of these protocols into (MD) and rearranging yields the replicator dynamics (RD). We now show that the revision protocols from this example can be generalized to cover wider ranges of Riemannian game dynamics, focusing again on interior population states: 22 Proposition 5.1. Let g be an extendable Riemannian metric such that g (x) is nonnegative for all x ∈ X • . Then up to a change of speed, the following protocols generate (RmD) as their mean dynamics on X • :

ρ αβ (x, π) = (g (x)1) α x α (πg (x)) β ,
(5.2a)

ρ αβ (x, π) = - (πg (x)) α x α (g (x)1) β , (5.2b)
where π is assumed nonnegative in (5.2a) and nonpositive in (5.2b). In addition, if g(x) is diagonal, the dynamics (RmD) are also generated (up to a change of speed ) by the protocol

ρ αβ (x, π) = g αα (x) x α g ββ (x)[π β -π α ] + .
(5.2c)

Proof. Substitute (5.2a)-(5.2c) with π = v(x), v (x) = (v(x)g (x)
) , and n(x) = (1g (x)) into (MD) to obtain

ẋ = v (x) β∈A n β (x) -n(x) β∈A v β (x).
(5.3)

Changing the speed at state x by dividing the right-hand side of (5.3) by s(x) = β n β (x) yields form (3.33a) of (RmD).

After a change of speed, the Riemannian dynamics (RmD) take the symmetric form (5.3), and this symmetry is a source of the appealing properties of the dynamics established below. By contrast, the random assignment of revision opportunities implies that, under the mean dynamics (MD), the outflow rate from each strategy α to other strategies is proportional to the popularity x α of the original strategy, resulting in an expression that is not symmetric. The factor x α appearing in the denominators in (5.2) also lets us recover the symmetric expression (5.3) from (MD).

The asymmetric treatment of current and candidate strategies under (5.2) is illustrated by our running examples:

Example 5.1 (p-replicator dynamics). Since p-replicator dynamics are generated by the Riemannian metric g(x) = diag(1/x p 1 , . . . , 1/x p n ), (5.2c) implies that these dynamics are induced by the revision protocols

ρ αβ (x, π) = x p-1 α x p β [π β -π α ] + .
(5.4)

22 Under minimal-rank extendible metrics, the result to follow also applies on the boundary.

Handling boundary states under full-rank extendable metrics requires modifications of the sort described in [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF], a direction we do not pursue here.

When p = 1, we have x p-1 α = 1 and x p β = x β , so (5.4) boils down to the pairwise proportional imitation protocol (5.2c) and induces the replicator dynamics (RD). When p = 0, we have x p-1 α = x -1 α and x p β = 1, so (5.4) gives (5.5) and induces the projection dynamics (PD) on X • . Protocol (5.5) was introduced by [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF], who interpret it as a model of "revision driven by insecurity": agents playing rare strategies are particularly likely to consider revising, while candidate strategies are chosen without regard for their current levels of use.

ρ αβ (x, π) = x -1 α [π β -π α ] + ,
While the revision protocols (5.2) are capable of generating many Riemannian dynamics (RmD), one can sometimes construct simpler protocols that take advantage of the structure of smaller classes of Riemannian dynamics. For the microfoundations of the nested replicator dynamics (NRD) and extensions thereof, we refer the reader to [START_REF] Mertikopoulos | Nested replicator dynamics and nested logit choice[END_REF].

General properties

In this section, we derive some general results for (RmD). In Section 6.1 we state a basic but technically challenging result on the existence and uniqueness of solutions. In Section 6.2 we show that the dynamics exhibit positive correlation with the game's payoffs, and we characterize the dynamics' rest points as either restricted equilibria or Nash equilibria. Finally, in Section 6.3 we study the global behavior of the dynamics in potential games.

6.1. Existence and uniqueness of solutions. To illustrate the possibilities for existence and uniqueness of solutions, it is useful to start with a simple example. Specifically, consider the p-replicator dynamics of Example 4.3 for a 2-strategy game with action set A = {1, 2} and payoff functions v 1 (x) = 1, v 2 (x) = 0.

When p = 1, we obtain the toy replicator equation

ẋ1 = x 1 (1 -x 1 ). (6.1)
Solutions to this equation exist and are unique for all t ∈ (-∞, ∞), and the support of x(t) is invariant. The pure states 0 and 1 are both rest points, and it is easy to check that the unique solution with initial condition

x 1 (0) = a ∈ (0, 1) is x 1 (t) = a/[a + (1 -a)e -t ].
When p = 0, we obtain the Euclidean projection dynamics

ẋ1 = 1/2 if x 1 < 1 0 if x 1 = 1. (6.2)
For every initial condition x 1 (0) ∈ [0, 1], this equation admits the unique forward solution x 1 (t) = x 1 (0) + t/2 for t ∈ [0, 2(1 -x 1 (0))) and x 1 (t) = 1 thereafter. Evidently, the support of x(t) is not invariant; also, backward solutions are not defined for all time, and solutions are not smooth in t when x 1 = 1 is reached. Finally, when p = 1/2, we obtain the differential equation

ẋ1 = x 1 (1 -x 1 ) √ x 1 + √ 1 -x 1 . (6.3)
Although this equation admits forward (and backward) solutions from every initial condition, these are no longer unique. Starting at x 1 (0) = 0, we have the stationary solution x 1 (t) = 0 for t ∈ [0, ∞); furthermore, one can verify by a direct -albeit tedious -calculation that there is another solution, namely x 1 (t) = 1 2 + t-2 4 1 + t -t 2 /4 for t ∈ [0, 4) and x 1 (t) = 1 thereafter. Additional solutions may linger at x 1 = 0 before emulating the previous solution trajectory.

The differences in behavior in the three cases above can be traced back to the properties of the underlying Riemannian metrics. First, the replicator dynamics are generated by the Shahshahani metric, which is minimal-rank extendable to all of X . In this case the induced dynamics (RmD) are Lipschitz continuous, so existence and uniqueness of solutions is guaranteed by the Picard-Lindelöf theorem (along with an argument to account for X being closed). Moreover, the support of x(t) is constant, and solutions exist in both forward and backward time (Sandholm, 2010b, Theorems 4.A.5 and 5.4.7).

On the other hand, the Euclidean projection dynamics (PD) are generated by a full-rank extendable metric. In such cases, the induced dynamics (RmD) are typically discontinuous, so the relevant solution notion is that of a Carathéodory solution, an absolutely continuous trajectory that satisfies (RmD) for almost all t ≥ 0. In the case of (PD), [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF] showed that every initial condition admits a unique Carathéodory forward solution; however, different solution orbits can merge in finite time, as illustrated in the previous example and in Fig. 3(a).

The following proposition shows that this behavior of (RD) and (PD) is representative of the minimal-rank and full-rank extendable cases respectively: Proposition 6.1. Let g be an extendable Riemannian metric.

(i ) If g is minimal-rank extendable, (RmD) admits a unique global solution from every initial condition in X ; moreover, each solution has constant support. (ii ) If g is full-rank extendable, (RmD) admits a unique forward Carathéodory solution from every initial condition in X .

Proposition 6.1 justifies the terminology continuous and discontinuous that we introduced in Section 3.5 to refer to dynamics induced by minimal-rank and fullrank metrics. The nontrivial part of Proposition 6.1 is the proof of part (ii): despite an apparent similarity, this result is considerably harder than the corresponding result of [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF] for (PD), so we relegate its proof to Appendix D. The main reason for this difficulty is that known uniqueness proofs for projected differential equations depend crucially on the Riemannian metric being constant throughout the dynamics' state space, an assumption that obviously fails here.

Of course, as can be seen from the continuous -but not Lipschitz continuoussystem (6.3), (RmD) may fail to admit unique solutions from initial conditions at the boundary of X if the underlying metric does not admit a Lipschitz continuous extension to the boundary of X . To avoid the resulting complications, we do not consider dynamics that are continuous but not Lipschitz continuous in the rest of the paper. 6.2. Basic properties. We now establish some basic relationships between (RmD) and the payoffs of the underlying game. We first show that (RmD) respects positive correlation: Proposition 6.2. The dynamics (RmD) satisfy (PC). (6.4) with equality if and only if V (x) = 0. The only step in (6.4) needing justification is the first inequality. For this step, we split the analysis into three cases. First, if x ∈ X • , the inequality binds because Π x orthogonally projects R A onto R A 0 = Adm g (x), which contains V (x). Second, if x ∈ bd(X ) and g is minimal-rank extendable, then v (x) ∈ R supp(x) , so the inequality binds because

Proof. Let V (x) = Π x (v (x)). We then claim that v(x)|V (x) = v (x), V (x) x ≥ Π x (v (x)), V (x) x = V (x) 2 x ≥ 0,
Π x projects R supp(x) orthogonally onto R A 0 ∩ R supp(x) = Adm g (x)
, which contains V (x). Finally, if x ∈ bd(X ) and g is full-rank extendable, Π x is the closest point projection of R A onto the tangent cone TC X (x). Hence, by Moreau's decomposition theorem (Hiriart-Urruty and Lemaréchal, 2001), we infer that v (x) -Π x (v (x)) lies in the normal cone

NC X (x) = {w ∈ R A : w, z x ≤ 0 for all z ∈ TC X (x)}. (6.5) Since V (x) ∈ Adm g (x) = TC X (x)
, the first inequality in (6.4) is immediate.

Proposition 6.2 is not particularly surprising: after all, the basic postulate behind (RmD) is that the dynamics' vector of motion is the closest feasible approximation to the game's payoff field, with the notion of closeness determined by the underlying Riemannian metric (or, equivalently, cost function). As we show below, this alignment can be exploited further to characterize the dynamics' rest points.

To that end, recall that one of the main attributes of the Euclidean projection dynamics (PD) is Nash stationarity:

x * ∈ X is a rest point if and only if it is a Nash equilibrium.

(NS)

This property does not hold under the replicator dynamics: for instance, every pure state of X is stationary under (RD). In this case, (NS) is replaced by the notion of restricted stationarity:23

x * ∈ X is a rest point if and only if it is a restricted equilibrium.

(RS)

Our next result shows that this difference between the projection and the replicator dynamics is representative of the discontinuous and continuous cases, and highlights one advantage of the former over the latter: Proposition 6.3.

(i ) Continuous Riemannian dynamics satisfy (RS).

(ii ) Discontinuous Riemannian dynamics satisfy (NS).

Proof. For (i), recall that the coordinate expression (3.33) for (RmD) always holds when g is minimal-rank extendable, and ẋα = 0 whenever x α = 0. Therefore, it suffices to check that x * ∈ X • is a rest point if and only if all the components of v(x * ) are equal. To that end, note that x * is a rest point of (3.33) if and only if

v (x * ) = γ v γ (x * ) γ n γ (x * ) n(x * ) ∝ n(x * ). (6.6)
In turn, this means that x * is a rest point of (RmD) if and only if v (x * ) ∝ n(x * ); our claim then follows from the fact that g (x * ) is invertible.

For (ii), assume that g if full-rank extendable and fix some x * ∈ X . It is easy to show that x * is a Nash equilibrium if and only if it satisfies the variational characterization

0 ≤ v(x * )|x -x * = v (x * ), x -x * x * for all x ∈ X , (6.7)
which says that v (x * ) lies in the normal cone NC X (x * ) of X at x * (cf. Eq. 6.5 above). Moreau's decomposition theorem then yields v (x * ) ∈ NC X (x * ) if and only if Π x * (v (x * )) = 0, so our assertion follows.

Remark 6.1. We note without proof that shifting all strategies' payoffs by the same amount has no effect on (RmD), and rescaling all strategies' payoffs by the same factor only changes the speed at which solution paths are traversed. In addition, on the face of X spanned by a subset A of A, continuous dynamics are invariant to changes in the payoffs of strategies outside of A .

6.3. Global convergence in potential games. Recall here that G ≡ G(A, v) is a potential game if v α (x) = ∂ α f (x)
for some potential function f : X → R (cf. Example 2.2). It then follows from Proposition 6.2 that f is a strict global Lyapunov function for (RmD), meaning that its value increases along (RmD) whenever the dynamics are not at rest. 24 For continuous Riemannian dynamics, a standard Lyapunov argument implies that all ω-limit points of (RmD) are rest points -and hence, by Proposition 6.3, restricted equilibria of G. However, this argument does not extend to discontinuous dynamics and Nash equilibria because it requires continuity of solutions with respect to initial conditions, a requirement which is difficult to prove in our case. To circumvent this obstacle, we establish a lower semi-continuous (l.s.c.) bound on the rate of change of the game's potential function. This bound then allows us to apply Proposition C.1 in Appendix C, which shows that, for dynamics on a compact set, such a bound on the rate of change of a Lyapunov function guarantees global convergence.

Proposition 6.4. Let G be a potential game with potential function f . Then, f is a strict Lyapunov function for (RmD) and every ω-limit point of (RmD) is a rest point of (RmD). These are restricted equilibria if (RmD) is continuous, and Nash equilibria if (RmD) is discontinuous.

Proof. Let V (x) = Π x (v (x)) and let x(t) be a solution of (RmD). Then, Proposition 6.2 yields

d dt f (x(t)) = Df (x(t))| ẋ(t) = v(x(t))|V (x(t)) ≥ 0, (6.8)
with equality if and only if V (x(t)) = 0. Hence, f is a strict global Lyapunov function for (RmD). When (RmD) is (Lipschitz) continuous, a standard argument shows that every ω-limit point of (RmD) is a rest point thereof (see e.g., Sandholm, 2010b, Theorem 7.B.3). The discontinuous case however requires a different treatment. To start, note that

d dt f (x(t)) = v(x(t))|V (x(t)) = v (x), Π x (v (x)) x ≥ V (x(t)) 2 x ≥ 0, (6.9)
where the first inequality follows from Moreau's decomposition theorem. Both inequalities bind if and only if V (x(t)) = 0; since the speed function x → V (x) x is lower semi-continuous (cf. Lemma C.2), Proposition C.1 shows that every ω-limit point of (RmD) is a rest point.

The classic analyses of [START_REF] Kimura | On the change of population fitness by natural selection[END_REF] and [START_REF] Shahshahani | A new mathematical framework for the study of linkage and selection[END_REF] showed that in common interest games, average payoffs are increased at a maximal rate under the replicator dynamics, provided that "maximal" is defined with respect to the Shahshahani metric. We conclude this section by deriving an analogous principle for all Riemannian game dynamics. To state it, define the gradient of a smooth function f :

K • → R with respect to g by gradf (x) = (Df (x) g -1 (x)) , (6.10)
that is, as the (necessarily unique) vector satisfying

Df (x)|z = gradf (x), z x for all z ∈ R A , x ∈ K • . (6.11)
Geometrically, the vector gradf (x) represents the direction of maximal increase of the function f at x with respect to the metric g. 25 We then have: Proposition 6.5. Let G be a potential game with potential function f and let g be an extendable Riemannian metric. Then, for all x ∈ X • , the vector field that defines (RmD) is the projection of gradf onto T X (x) with respect to g.

Proof. Since v(x) = Df (x), we have Π x (v (x)) = Π x (gradf (x)), as claimed.
Hence, at interior states, the dynamics (RmD) increase the value of potential at a maximal rate under the geometry defined by g, subject to feasibility. For discontinuous dynamics, this conclusion remains true even at boundary states. For continuous dynamics, the interior of each face of X is invariant under (RmD), so this conclusion holds provided that feasibility is understood to incorporate this additional constraint.

Hessian game dynamics

By virtue of the integrability property that defines them, potential games have desirable convergence properties under a wide range of evolutionary dynamics. By contrast, convergence results for other classes of games -for instance, contractive games and games with an evolutionarily stable state (ESS) -require additional structure, often taking the form of integrability properties built into the dynamics themselves. 26 In this section, we show that the integrability of Hessian Riemannian metrics allows us to generalize several properties of the replicator dynamics and the Euclidean projection dynamics to a substantially broader class of dynamics. These Hessian game dynamics, introduced in Example 4.6, take the form

ẋ = arg max z∈Admg(x) v(x)|z -1 2 z 2 x , g = Hess h, (HD)
where the continuous function h : K → R is C 3 -smooth on every positive suborthant of K, and where Hess h(x) is positive definite for all x ∈ K • . As we demonstrate 25 Specifically, this means that gradf (x) = arg max{Dzf (x) : z x = 1}; that this is so follows from the definition of gradf (x) and the Cauchy-Schwarz inequality.

26 See [START_REF] Hofbauer | Evolution in games with randomly disturbed payoffs[END_REF], Sandholm (2010a), and[START_REF] Zusai | Gains in evolutionary dynamics: a unifying approach to stability for contractive games and ESS[END_REF].

below, the integrability built into the dynamics (HD) is the source of a variety of stability and convergence results.

A key element of our analysis is the so-called Bregman divergence, which we introduce in Section 7.1. In Section 7.2, we establish global convergence to equilibrium in contractive games and local stability of ESSs, while Section 7.3 demonstrates the convergence of time-averages of interior trajectories to Nash equilibrium and provides sufficient conditions for permanence. Finally, Section 7.4 establishes the elimination of strictly dominated strategies under continuous Hessian dynamics.

7.1. Bregman divergences. When used as a tool for establishing convergence, Lyapunov functions typically measure some sort of "distance" between the current state and a target state x * . For Hessian dynamics, a natural point of departure is the potential function h of the metric g = Hess h that defines them. However, since the (game-specific) target state x * is independent of g, there is no reason that h itself should serve as a Lyapunov function. Instead, taking advantage of the convexity of h, we consider the difference between h(x * ) and the best linear approximation of h(x * ) from x.

Formally, the Bregman divergence of h [START_REF] Bregman | The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming[END_REF] is defined as

D h (x * , x) = h(x * ) -h(x) -h (x; x * -x), x * , x ∈ X , (7.1)
where h (x; x * -x) is the one-sided derivative of h at x along x * -x, i.e.,

h (x; x * -x) = lim t→0 + t -1 [h(x + t(x * -x)) -h(x)] . (7.2)
Since h is convex, we have D h (x * , x) ≥ 0, with equality if and only if x * = x. (7.3)

On the other hand, D h is not symmetric in x * and x, so it is not a bona fide distance function on X ; rather, D h (x * , x) describes the remoteness of x from the base point x * , hence the name "divergence".

Revisiting our two archetypal examples, the Euclidean metric is generated by the quadratic potential h(x) = 1 2 α x 2 α . Definition (7.1) then yields the Euclidean divergence

D Eucl (x * , x) = 1 2 α (x α -x * α ) 2 , (7.4a)
which is (uncharacteristically) symmetric in x * and x. Analogously, the Shahshahani metric is generated by the (negative) entropy h(x) = α x α log x α . A short calculation shows that the corresponding divergence function is the Kullback-Leibler (KL) divergence

D KL (x * , x) = α: x * α >0
x * α log(x * α /x α ), (7.4b) which has been used extensively in the analysis of the replicator dynamics [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF].

The key qualitative difference between the Euclidean divergence (7.4a) and the KL divergence (7.4b) is that the former is finite for all x, x * ∈ X , whereas the latter blows up to +∞ when supp(x * ) supp(x). The reason for this blow-up is that the entropy function h(x) = α x α log x α becomes infinitely steep as any boundary point x of X is approached from the interior of X , i.e., sup α∈A |∂ α h(x n )| → ∞ for every interior sequence x n converging to x. (7.5) When this is the case for all x ∈ bd(X ), we say that h is steep [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF][START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF]. At the opposite end of the spectrum, if Dh(x) exists for all x ∈ X , we say that h is nonsteep.

The link between the steepness of h and the finiteness of the associated Bregman divergence is provided by the following lemma: Lemma 7.1. Fix x * ∈ X and let D(x * ) denote the union of the relative interiors of the faces of X that contain x * , i.e., D(x * ) ≡ {x ∈ X : supp(x * ) ⊆ supp(x)}.

(7.6)

If h is steep, we have D h (x * , x) < ∞ for all x ∈ D(x * ); by contrast, if h is nonsteep, we have D h (x * , x) < ∞ for all x ∈ X .
Proof. If h is steep and x ∈ D(x * ), the smoothness of h on the face of X spanned by supp(x) ⊇ supp(x * ) implies that the directional derivative h (x; x * -x) exists and is finite, so D h (x * , x) is itself finite. If instead h is nonsteep, h (x; x * -x) exists and is finite for all x ∈ X , so again D h (x * , x) < ∞.

Beyond the positive definiteness property (7.3), the attribute of the Bregman divergence that recommends it as a Lyapunov function for (HD) is that the level sets of D h (x * , •) are perpendicular to all rays emanating from x * under g = Hess h. Formally, we have: Lemma 7.2. Let g = Hess h be an extendable HR metric and let x * ∈ X . Then, for every smooth curve x(t) with constant support containing that of x * , we have:

d dt D h (x * , x(t)) = ẋ(t), x(t) -x * x(t) . (7.7)
In particular, if D h (x * , x(t)) is constant, ẋ(t) is perpendicular to x(t)-x * . Finally, if h is nonsteep, the above conclusions hold for every smooth curve x(t) on X .

Proof. The proof is a direct application of the chain rule:

d dt D h (x * , x) = - α ∂h ∂x α ẋα + ∂h ∂x α d dt (x * α -x α ) + β ∂ 2 h ∂x α ∂x β (x * α -x α ) ẋβ = α,β (x * α -x α )g αβ (x) ẋβ = ẋ, x -x * x , (7.8)
where all summations are taken over the (constant) support A ≡ supp(x(t)) of x(t) and we used the fact that ẋα = 0 for α / ∈ A . Finally, in the nonsteep case, h is smooth throughout X , so the above holds for every smooth curve x(t).

Within the class of Hessian Riemannian metrics, steepness of h roughly corresponds to minimal-rank extendability of the metric g = Hess h, and nonsteepness to full-rank extendability. These analogies fail when the steepness of h does not adequately control the regularity of g near the boundary of X , or when g is minimalrank extendable but generates non-Lipschitz dynamics. Bearing this in mind, we use the term continuous Hessian dynamics for Riemannian dynamics generated by a minimal-rank extendable metric g = Hess h with steep h, and the term discontinuous Hessian dynamics for Riemannian dynamics generated by a full-rank extendable metric g = Hess h with nonsteep h. In what follows, we will tacitly assume that the dynamics (HD) are either continuous or discontinuous. 7.2. Contractive games and evolutionarily stable states. Recall that a population game G ≡ G(A, v) is called contractive if v(x ) -v(x)|x -x ≤ 0 for all x, x ∈ X , strictly contractive if the inequality is strict whenever x = x , and conservative if the inequality always binds (cf. Example 2.3). As is well known, the set of Nash equilibria of any contractive game is convex, and every strictly contractive game admits a unique Nash equilibrium [START_REF] Hofbauer | Stable games and their dynamics[END_REF].

Combining the defining inequality of strictly contractive games with the variational characterization of Nash equilibria (6.7), it follows that the (necessarily unique) Nash equilibrium of a strictly contractive game satisfies the inequality v(x)|x -x * ≤ 0 with equality only if x = x * .

(7.9) [START_REF] Hofbauer | Stable games and their dynamics[END_REF] call a state satisfying (7.9) a globally evolutionarily stable state (GESS). This is the global version of the seminal local solution concept of Maynard [START_REF] Smith | The logic of animal conflict[END_REF]: if (7.9) holds for all x = x * in a neighborhood of x * , then x * is called an evolutionarily stable state (ESS). 27 It is well known that the GESS x * of a strictly contractive game attracts all solutions of the replicator dynamics whose initial support contains that of x * ; by comparison, x * attracts all orbits of the Euclidean projection dynamics (PD). Theorem 7.3 extends these results to all Hessian dynamics (HD).

Theorem 7.3. Let G be the (necessarily unique) Nash equilibrium of a strictly contractive game G. Then:

(i ) For all continuous Hessian dynamics, D h (x * , •) is a strict decreasing Lyapunov function on D(x * ), and x * is asymptotically stable with basin D(x * ). (ii ) For all discontinuous Hessian dynamics, D h (x * , •) is a strict decreasing global Lyapunov function, and x * is globally asymptotically stable.

Proof. We begin with the continuous case. By Proposition 6.1(i), every solution x(t) of (HD) has constant support. Hence, if x(0) ∈ D(x * ), Lemma 7.2 yields:

d dt D h (x * , x) = ẋ, x -x * x = Π x (v (x)), x -x * x = v (x), x -x * x = v(x)|x -x * , (7.10a) ≤ 0, (7.10b)
where we used the definition of Π x for minimal-rank extendable metrics (cf. Section 3.6) to obtain (7.10a) and the definition (7.9) of a GESS for (7.10b). Since equality in (7.10) holds if and only if x = x * , we conclude that D h (x * , x) is a strict Lyapunov function on D(x * ). If we can show in addition that x(t) has no ω-limit points in X \D(x * ), then asymptotic stability with basin D(x * ) follows from standard arguments (see e.g., [START_REF] Sandholm | Population Games and Evolutionary Dynamics. Economic learning and social evolution[END_REF], Theorem 7.B.3). Assume therefore that x(t) admits an ω-limit point x ω = x * , so x(t n ) → x ω for some sequence of times t n ↑ ∞. Since | ẋα (t)| is bounded from above by V max ≡ sup x∈X max β |V β (x)| < ∞, there exists an open neighborhood U of x ω and positive a, δ, n 0 > 0 such that x(t) ∈ U and v(x(t))|x(t)-x * ≤ -a < 0 for all t ∈ [t n , t n +δ] and all n ≥ n 0 . Hence, by (7.10), we get (7.11) We thus get lim inf t→∞ D h (x * , x(t)) = -∞, a contradiction.

D h (x * , x(t n + δ)) -D h (x * , x(0)) ≤ tn+δ 0 v(x(s))|x(s) -x * ds ≤ -a(n -n 0 )δ.
For the discontinuous case, note first that since x * -x ∈ TC X (x), Moreau's decomposition theorem implies that Π x (v (x)), x -x *

x ≤ v (x), x -x * x . Thus, replacing the first equality in (7.10a) by an inequality, (7.10) shows that D h (x * , •) is a strict global Lyapunov function for (HD). Global asymptotic stability then follows from Proposition C.1.

The only implication of G being strictly contractive used in the previous proof is that its Nash equilibrium is a GESS. More generally, if a game admits an ESS x * , applying the above arguments in a neighborhood of x * defined by a level set of D h (x * , •) yields the following result:

Theorem 7.4. Evolutionarily stable states are asymptotically stable under (HD). [START_REF] Hofbauer | Adaptive dynamics and evolutionary stability[END_REF], [START_REF] Hopkins | A note on best response dynamics[END_REF][START_REF] Harper | Escort evolutionary game theory[END_REF] all offer results on the local stability of interior evolutionarily stable states under Riemannian game dynamics. [START_REF] Hofbauer | Adaptive dynamics and evolutionary stability[END_REF] showed that under all Riemannian (not necessarily Hessian) dynamics (RmD), the function L(x) = x-x * , x-x *

x * is a strict local Lyapunov function for interior ESSs x * , implying that x * is asymptotically stable. Likewise, [START_REF] Hopkins | A note on best response dynamics[END_REF] used linearization to establish local stability of regular interior ESSs [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF] under (RmD). Finally, [START_REF] Harper | Escort evolutionary game theory[END_REF] employed a version of the argument above to prove asymptotic stability of ESSs for separable Hessian dynamics of the form (4.4).

An important case of contractive games that do not admit an ESS is the class of conservative games, which include population games generated by matching in symmetric zero-sum games. Under the replicator dynamics, the KL divergence does not provide a strict Lyapunov function for conservative games, but rather a constant of motion. The following result extends this conclusion to all Hessian dynamics: Proposition 7.5. Let x * be a Nash equilibrium of a conservative game G. Then, D h (x * , •) is a constant of motion along any interior solution segment of (HD).

Proof. Simply note that (7.10) binds if G is conservative and x ∈ X • .

Remark 7.1. In the definition of (HD), we required that h be finite throughout X . This requirement is unnecessary for the preceding results when x * is interior; however, if x * lies on the boundary of X , the proofs of Theorems 7.3 and 7.4 do not go through because D h (x * , •) is no longer well-defined throughout D(x * ). Nevertheless, the results themselves remain true if g = Hess h is separable, allowing us to handle the p-replicator dynamics for p ≥ 2 (Example 4.3). To prove this, it suffices to replace the implicit summation in h (x; x * -x) over all strategies with a sum extending over only the strategies that lie in the support of x * . 7.3. Convergence of time-averaged trajectories and permanence. We now extend two classic results for the replicator dynamics in random matching games (Example 2.1) to Hessian dynamics. The results for these games take advantage of the linearity of payoffs v α (x) = β∈A A αβ x β in the population state.

The first such result states that if a solution x(t) of the replicator dynamics stays a positive distance away from the boundary of the simplex, then the time-averaged orbit x(t) = t -1 t 0 x(s) ds converges to the set of Nash equilibria of the underlying game [START_REF] Schuster | Self-regulation of behaviour in animal societies I: Symmetric contests[END_REF]. The class of games to which this result applies includes zero-sum games (cf. Proposition 7.5) and games satisfying sufficient conditions for permanence (cf. Proposition 7.7 below). The following proposition shows that this convergence property extends to all Hessian dynamics: Proposition 7.6. Let G be a random matching game and let x(t) be a solution orbit of (HD). If x(t) is contained in a compact subset of X • , the time-averaged orbit x(t) = t -1 t 0 x(s) ds converges to the set of Nash equilibria of G. In the case of the replicator dynamics, this is proved by introducing the auxiliary variables y α = log x α and using the fact that ẏ = ẋ/x. To extend this proof to (HD), we instead define y via the Bregman divergence of h: Proof of Proposition 7.6. Let y α = D h (e α , x), so ẏα = v(x)|x -e α = v(x)|xv α (x) by Lemma 7.2. Then, for all α, β ∈ A, we get (7.12) where c αβ = y α (0) -y β (0). Since x(t) is contained in a compact subset of X • , Lemma 7.1 implies that sup t y α (t) < ∞ for all α ∈ A. Thus, dividing both sides of (7.12) by t and taking the limit t → ∞, we obtain

y α (t) -y β (t) = c αβ + t 0 [v β (x(s)) -v α (x(s))] ds,
lim t→∞ [v α (x(t)) -v β (x(t))] = 0, (7.13)
where we have used the linearity of v α (x) = β A αβ x β in x to bring the integral into the arguments of v α and v β . Equation (7.13) implies that if x * is an ω-limit point of x(t), then v α (x * ) = v β (x * ) for all α, β ∈ A, so x * is a Nash equilibrium of G. Since X is compact, every solution of (HD) converges to its ω-limit set, and our assertion follows.

Proposition 7.6 applies when the population share of each strategy remains bounded away from zero along all interior solution trajectories, a property known as permanence. Formally, a dynamical system on X is called permanent if there exists a threshold δ > 0 such that every interior solution satisfies lim inf t→∞ x α (t) ≥ δ for all α ∈ A.

Hofbauer and Sigmund (1998) establish a sufficient condition for permanence under the replicator dynamics. Proposition 7.7 extends this result to all continuous Hessian dynamics, providing a sufficient condition for Proposition 7.6 to apply: Proposition 7.7. Let G be a random matching game. Assume that the dynamics (HD) are continuous and there exists some p ∈ X • such that v(x * )|p -x * > 0 for all boundary rest points x * of (HD).

(7.14)

Then, the dynamics (HD) are permanent.

The proof of Proposition 7.7 follows the proof technique of Theorem 13.6.1 of [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF], and is presented in Appendix D. 7.4. Dominated strategies. We conclude by considering the elimination and survival of dominated strategies under (HD). To that end, recall that α ∈ A is strictly dominated by β ∈ A if v α (x) < v β (x) for all x ∈ X . More generally, p ∈ X is strictly dominated by q ∈ X if v(x)|p < v(x)|q for all x ∈ X , meaning that the average payoff of a small influx of mutants is always higher when the mutants are distributed according to q rather than p. We then say that p ∈ X becomes extinct along x(t) if min{x α (t) : α ∈ supp(x * )} → 0 as t → ∞ -or equivalently, if there are no ω-limit points of x(t) in D(p).

Under the replicator dynamics, it is well known that dominated strategies become extinct along every interior solution trajectory [START_REF] Akin | Domination or equilibrium[END_REF]. As we show below, this elimination result extends to all continuous Hessian dynamics (HD):

Proposition 7.8. Under all continuous Hessian dynamics (HD), strictly dominated strategies become extinct along every interior solution orbit.

Proof. The proof follows a standard argument for the replicator dynamics, replacing the KL divergence (7.4b) with the Bregman divergence (7.1). Specifically, Lemma 7.2 implies that along any interior solution x(t),

d dt (D h (p, x) -D h (q, x)) = ẋ, x -p x -ẋ, x -q x = Π x (v (x)), q -p x = v (x), q -p x = v(x)|q -p , (7.15)
where the penultimate equality uses the fact that x ∈ X • . Since q strictly dominates p and v is continuous, we have v(x)|q -p ≥ a for some positive constant a > 0, implying that D h (p, x(t)) → ∞. Hence, by Lemma 7.1, we conclude that x(t) has no ω-limit points in D(p).

In general, the conclusion of Proposition 7.8 is false for discontinuous Hessian dynamics: [START_REF] Sandholm | The projection dynamic and the replicator dynamic[END_REF] construct a four-strategy game with a strictly dominated strategy that is played recurrently by a nonnegligible fraction of the population under the Euclidean projection dynamics (PD). The argument above shows that this strategy must become less common when the state is in the interior of X ; however, solutions to (PD) are able to enter and leave the boundary of X , and while there, dominated strategies may become more common. We conjecture that this construction can be suitably extended to all discontinuous Hessian dynamics, but we do not tackle this issue here.

Links with reinforcement learning

Under a variety of reinforcement learning processes for normal form games, mixed strategies evolve according to the replicator dynamics -see e.g., [START_REF] Börgers | Learning through reinforcement and replicator dynamics[END_REF], [START_REF] Posch | Cycling in a stochastic learning algorithm for normal form games[END_REF], [START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF], [START_REF] Hopkins | Two competing models of how people learn in games[END_REF] and Hofbauer et al. (2009). We conclude the paper by describing a broader connection between reinforcement learning and Hessian game dynamics. 8.1. Reinforcement learning. Our starting point is a class of reinforcement learning dynamics for N -player normal form games introduced by [START_REF] Coucheney | Penalty-regulated dynamics and robust learning procedures in games[END_REF] and [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF]. Over the course of play, each player maintains a score vector representing the cumulative payoffs of each of his strategies; then, at each moment in time, the player selects a mixed strategy by applying a choice map to this score vector, similar in function to the perturbed best response maps used in stochastic fictitious play and perturbed best response dynamics [START_REF] Fudenberg | The Theory of Learning in Games, volume 2 of Economic learning and social evolution[END_REF]Hofbauer andSandholm, 2002, 2007).

Formally, let v kα (x) denote the expected payoff of the α-th strategy of player k at mixed strategy profile x = (x 1 , . . . , x N ) in an N -player normal form game. The choice map Q k of player k is then defined as

Q k (y k ) = arg max x k ∈X k { y k |x k -h k (x k )}, (8.1)
where X k ≡ ∆(A k ) denotes the mixed strategy space of player k (A k being the corresponding strategy set), and h k : X k → R is a smooth, strongly convex penalty function. The reinforcement learning process described above can then be written as ẏk = v k (x)

x k = Q k (y k ). (RL)
Now, let g k = Hess h k and write n kα (x) = β∈A k g -1 k,αβ (x). [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] showed that when the mixed strategy profile x(t) is interior, its evolution under (RL) is given by

ẋkα = β∈A k g -1 k,αβ (x) - n kα (x)n kβ (x) γ n kγ (x) v kβ (x). (RLD)
A comparison with (3.33b) shows that the dynamics of mixed strategies under (RL) agree with the Hessian dynamics (HD) at interior states. 28 8.2. A common derivation of (HD) and (RLD). The derivation of (HD) here and of (RLD) in [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] have very different starting points, leaving the reasons behind their equivalence somewhat mysterious. We now make these reasons clearer by deriving both dynamics using a common set of tools. Here we present the basic idea behind the argument, using the theory of convex duality to establish the equivalence of versions of (HD) of (RLD) defined on the entire positive orthant K • . 29 Establishing the equivalence of the original processes on X • using this approach requires further ideas, which we present in Appendix A.2. The starting point for both (HD) and (RLD) is the potential function h, assumed here to be smooth, strongly convex, and steep at the boundary of K in the sense of (7.5). The convex conjugate of h is then defined as 30 h * (y) = sup (8.2)

Since h is steep and strongly convex, the supremum above is attained at a unique point Q K (y) ∈ K • (Rockafellar, 1970, Theorem 26.5). 31 By the first-order optimality conditions for (8.2), we then get

Q K (y) ≡ arg max x∈K • { y|x -h(x)} = (Dh) -1 (y), (8.3)
where (Dh) -1 is the inverse function of Dh. Applying the envelope theorem to (8.2), we then obtain Dh * (y) = Q K (y).

(8.4)

28 While we have defined Riemannian game dynamics for single population games and reinforcement learning for N -person normal form games, this difference is of no consequence. One can similarly define Riemannian game dynamics for multipopulation games, or a symmetrized reinforcement learning process for symmetric two-player normal form games (cf. Appendix A.2). 29 The usefulness of convex conjugates in analyzing maps of the form (8.1) is well known in learning and optimization -see e.g., [START_REF] Nemirovski | Problem Complexity and Method Efficiency in Optimization[END_REF], [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF]. 30 For a comprehensive treatment, see Rockafellar, 1970 or Hiriart-Urruty and Lemaréchal, 2001. 31 Since h is strongly convex, it is bounded below by a strictly convex quadratic function (Hiriart-Urruty and Lemaréchal, 2001, Theorem B.4.1.1), which in turn implies that the domain of h * is (R n ) * (Rockafellar, 1970, Corollary 13.1).

It follows from (8.3) and (8.4) that Dh(Dh * (y)) ≡ y, so differentiating and rearranging yields Hess h * (y) = (Hess h(x)) -1 (8.5) with the inverse of the Hessian matrix of h being evaluated at x = Q K (y).

We now introduce and compare full-dimensional analogues of continuous Hessian dynamics and (symmetric) reinforcement learning, taking the orthant K • as the state space (and so defining payoffs v on K • ). In the case of (HD), the fulldimensional domain makes projections redundant, so the induced dynamics take the form ẋ = v (x) = g -1 (x) v(x) = (Hess h(x)) -1 v(x) .

(HD K ) For its part, the full-dimensional analogue of (RL) is

ẏ = v(x), x = Q K (y), (RL K )
with Q K defined as in (8.3) above. Differentiating (RL K ) and applying (8.4) and (8.5) then yields ẋ = DQ K (y) v(x) = Hess h * (y) v(x) = (Hess h(x)) -1 v(x) .

(RLD K )

We can express this argument in words. By definition, (full-dimensional) Riemannian dynamics are obtained by transforming payoffs at an interior population state x using the matrix g -1 (x). In the Hessian case, the metric g admits a potential function h, so we have g -1 (x) = (Hess h(x)) -1 by definition. As for reinforcement learning, differentiation shows that the dynamics of the mixed strategy x are obtained by transforming payoffs at x by the derivative matrix DQ K (y) of the choice map (8.3). Basic facts about convex conjugacy imply that this derivative is equal to (Hess h(x)) -1 , where h is the penalty function that generates Q K . This argument establishes the equivalence of (HD K ) and (RLD K ). For a corresponding argument for the original processes (HD) and (RLD), see Appendix A.2. 8.3. Boundary behavior in the nonsteep regime. Since continuous Hessian dynamics coincide with the reinforcement scheme (RL) when the penalty functions h k are steep, certain results for interior trajectories -Propositions 7.6 and 7.8 in particular -can be obtained directly from the analysis of [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF]. On the other hand, in the nonsteep regime, (RLD) and (HD) agree at interior states, but their behaviors at the boundary differ in a fundamental way. Specifically, while the boundary behavior of discontinuous Hessian dynamics is defined using closest point projections, the reinforcement learning process (RL) for nonsteep h can no longer be reduced to mixed strategy dynamics at all. Instead one must work explicitly with the score variables y k , which continue to aggregate payoff data of all strategies, even those that are not used. Among other things, this means that a strong cumulative performance of an unused strategy will return it to use. This difference between how the processes are defined on the boundary has important consequences. For instance, while [START_REF] Sandholm | The projection dynamic and the replicator dynamic[END_REF] show that strictly dominated strategies may survive under the Euclidean projection dynamics, Mertikopoulos and [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] prove that the reinforcement learning process (RL) always eliminates dominated strategies, whether the penalty functions are steep or not. Under both processes, dominated strategies are initially eliminated along interior solution trajectories. But while they may resurface under (HD), the score variables of (RL) continue to register the poor performance of these strategies, ensuring that they remain extinct for all time.

With Lemma D.2 at hand, we finally obtain:

Proof of Lemma D.1. Define ġ(x) = ( ġαβ (x)) α,β∈A by ġαβ (x) = Dg αβ (x)|V (x) = κ∈A V κ (x) ∂ κ g αβ (x), and let K g = max α,β∈A max x∈X ġαβ (x) < ∞ (recall that g is C 1 ). Then, for all t ≥ 0 such that x(t) and x (t) are differentiable, we have Ṗ = 2 V (x ) -V (x), x -x x e -λt + (x -x) ġ(x)(x -x) e -λt -λ x -x 2 x e -λt ≤ -(λ -2K V -K g ) x -x 2 x e -λt , (D.5)

where we used Lemma D.2 to bound the second term in the first line. Taking λ > 2K V + K g then yields Ṗ ≤ 0; since x(t) and x (t) are absolutely continuous, we conclude that P (t) is nondecreasing.

We close this appendix with the proof of our permanence criterion:

Proof of Proposition 7.7. Define P : K → R as P (x) = -exp ( α p α D h (e α , x)) for x ∈ K • and P (x) = 0 for x ∈ bd(K). The steepness of h implies that P is continuous, while Lemma 7.2 implies that d dt log(P (x)) = Ψ(x) ≡ v(x)|p -x for all x ∈ X • . Hence, by Theorem 12.2.1 of [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF], it suffices to show that the function Ψ is an average Lyapunov function for (HD), meaning that, for every initial condition x(0) ∈ bd(X ), there is a t > 0 such that 1 t t 0 Ψ(x(s)) ds > 0.

(D.6)

We proceed by induction on the cardinality of the support of the initial condition. The claim is trivial if this cardinality is 1. For the inductive step, suppose that (D.6) holds when the cardinality is k ∈ {1, . . . , |A| -2}, and consider an initial condition x(0) whose support A has cardinality k+1. If x(t) converges to the boundary of the face X of X spanned by A , then our claim follows from the inductive hypothesis and the same arguments as in the proof of Theorem 12.2.2 in [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF]. If instead x(t) does not converge to the boundary of X , then there exists a δ > 0 and an increasing sequence of times t n ↑ ∞ with x α (t n ) ≥ δ > 0 for all α ∈ A . Then, letting xα (t) = t -1 t 0 x α (s) ds and ū(t) = t -1 t 0 v(x(s))|x(s) ds, we may assume (by descending to a subsequence of t n if necessary) that x(t n ) and ū(t n ) converge to some x * and ū * respectively as n → ∞.

We now claim that v α (x * ) = ū * for all α ∈ A , implying that x * is a restricted equilibrium of G. Indeed, let y α (t) = D h (e α , x(t)) for all α ∈ A . Then, ẏα = v(x)|x -v α (x) by Lemma 7.2, so the linearity of v(x) in x implies that

1 t t 0 v(x(s))|x(s) ds -v α (x(t)) = y α (t) -y α (0) t . (D.7)
Given that x(t n ) remains a minimal positive distance away from bd(X ), it follows that y α (t n ) is bounded from above for all α ∈ A . Therefore, the right-hand side of (D.7) vanishes as t n → ∞, implying in turn that v α (x * ) = ū * for all α ∈ A , as claimed. Now, since x * is a restricted equilibrium of G, Proposition 6.3 implies that it is a boundary rest point of (HD), so ū * = v(x * )|x * < v(x * )|p by (7.14). Moreover, since Ψ(x) = v(x)|p -x , setting t = t n in (D.6) yields

  R A , the definition above becomes most transparent by writing w = α w α e α and w = β w β e β in the standard basis {e α } α∈A of R A . Since •, • is positive definite and bilinear, there exists a positive-definite matrix g = (g αβ ) α,β∈A such that w, w = α,β∈A w α g αβ w β = w gw (w α g αβ w β = w gw. (3.12b)

  )

Figure 1 .

 1 Figure1. Unit balls on the 3-simplex under the metrics of Examples 3.3-3.6. For each base point x shown, the shaded regions comprise all tangent vectors z based at x that satisfy z 2x ≤ 1.

  Minimal-rank extendability..

Figure 2 .

 2 Figure2. Admissible sets under the Euclidean and Shahshahani metrics. For x ∈ X • , we have Admg(x) = TCX (x). For x ∈ bd(X ), we still have Admg(x) = TCX (x) in the Euclidean case, but the Shahshahani metric can only be extended to the tangent space Admg(x) = TX (x).

Figure 3 .

 3 Figure3. Phase portraits of the p-replicator dynamics in standard Rock-Paper-Scissors. As p ∈ [0, ∞) increases, the shape of the closed orbits changes from circular to triangular. When p = 0, solutions enter and leave the boundary of the simplex, but forward solutions exist and are unique. For p ≥ 1, forward and backward solutions exist, are unique, and their support is constant.

Figure 4 .

 4 Figure 4. Phase portraits of the nested replicator dynamics in standard Rock-Paper-Scissors with s = 3 for two similarity groupings.

{

  y|x -h(x)}, y ∈ (R A ) * .

  (s)) ds = t -1 n tn 0 v(x(s))|p -x(s) ds = v(x(t n ))|p -ū(t n ) (D.8)

Table 1 .

 1 . Regularity of the p-replicator dynamics and behavior of the metric potential function hp.

	p	name	regularity	potential
	0	projection discontinuous	quadratic
	(0, 1)	--	not Lipschitz	power law
	1	replicator	smooth	Gibbs entropy
	(1, 2)	--	smooth	Tsallis entropy
	2	log-barrier	smooth	logarithmic
	(2, ∞)	--	smooth	inverse power law

See Hart and Mas-Colell (2001),[START_REF] Hofbauer | Evolution in games with randomly disturbed payoffs[END_REF], andSandholm (2010a).

In the context of convex programming, gradient flows generated by Hessian Riemannian (HR) metrics of this sort have been explored at depth by[START_REF] Bolte | Barrier operators and associated gradient-like dynamical systems for constrained minimization problems[END_REF],[START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF],[START_REF] Mertikopoulos | On the convergence of gradient-like flows with noisy gradient input[END_REF], and many others.[START_REF] Laraki | Inertial game dynamics and applications to constrained optimization[END_REF] also examine the long-term rationality properties of a class of second-order, inertial game dynamics derived from HR metrics.

In the Shahshahani case, this boils down to the Kullback-Leibler divergence, which has seen wide use in the analysis of the replicator dynamics[START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF].

See Sandholm et al. (2008) and Section 7.4.

For related results, see also[START_REF] Börgers | Learning through reinforcement and replicator dynamics[END_REF],[START_REF] Posch | Cycling in a stochastic learning algorithm for normal form games[END_REF][START_REF] Hopkins | Two competing models of how people learn in games[END_REF].

That all of these dynamics feature closed orbits is not coincidental -see Proposition 7.5.

Recall here that x * is a restricted equilibrium if all strategies in its support earn equal payoffs.

Marciano Siniscalchi and an anonymous referee for very thoughtful reports. Part of this work was carried out during the authors' visit to the Hausdorff Research Institute for Mathematics at the University of Bonn in the framework of the Trimester Program "Stochastic Dynamics in Economics and Finance". PM is grateful for financial support from the French National Research Agency (ANR) under grant no. ANR-GAGA-13-JS01-0004-01 and the CNRS under grant no. PEPS-REAL.net-2016. WHS is grateful for financial support under NSF Grants SES-1155135, SES-1458992, and SES-1728853 and ARO Grant MSN201957.

1 See Friedman (1991), Swinkels (1993), Sandholm (2001), Demichelis and Ritzberger (2003), and condition (PC) below.

Appendix A. Connections with other game dynamics

Throughout this appendix, we write 1 ∈ R n for the n-dimensional column vector of ones and Φ = I -1 n 11 for the Euclidean orthogonal projection of R n onto R n 0 = {z ∈ R n : 1 z = 0} = span(1) ⊥ . 32 Recall also that the (Moore-Penrose) pseudoinverse of a matrix M ∈ R n×n is the unique matrix M + ∈ R n×n such that (i ) M + y = 0 whenever y ∈ range(M ) ⊥ ; and (ii ) M + y = x whenever x ∈ ker(M ) ⊥ , y ∈ range(M ), and M x = y (Friedberg et al., 2002, Sec. 6.7). Since a symmetric matrix M ∈ R n×n satisfies range(M ) = ker(M ) ⊥ , we have the following well-known algebraic characterization of pseudoinverses:

Lemma A.1. Let M ∈ R n×n be a symmetric matrix. Then, M + is the unique matrix that (i ) inverts M on ker(M ) ⊥ = range(M ); and (ii ) satisfies ker(M + ) = ker(M ).

A.1. Interior equivalence of Riemannian dynamics and Hopkins' dynamics. We now derive the equivalence between (RmD) and Hopkins' dynamics (2.7) on X • , as noted in Section 2.3. To begin with, we say that M ∈ R n×n is a Hopkins matrix if it is positive definite with respect to R n 0 and maps 1 to 0. The following lemma establishes a basic characterization of Hopkins matrices: Lemma A.2.

(i ) If S ∈ R n×n is symmetric positive-definite, then (ΦSΦ) + is a Hopkins matrix and

(ΦSΦ) + = S -1 -S -1 11 S -1 1 S -1 1 .

(A.1) (ii ) Conversely, if M is a Hopkins matrix, then M = (ΦSΦ) + , where S = M +11 is symmetric positive definite.

Proof. To prove part (i), let S be symmetric positive-definite. Then the symmetric matrix ΦSΦ is positive definite with respect to R n 0 and maps 1 to 0, so range(ΦSΦ) = ker(ΦSΦ) ⊥ = R n 0 . If we denote the right-hand side of (A.1) by S, a straightforward calculation shows that SΦSΦz = z for all z ∈ R n 0 and S1 = 0. Thus Lemma A.1 implies that S = (ΦSΦ) + . That this is a Hopkins matrix is immediate from the fact that range(ΦSΦ) = ker(ΦSΦ) ⊥ = R n 0 and Lemma A.1. To prove part (ii), let M be a Hopkins matrix and let S = M + 11 . Clearly S is symmetric positive-definite. Moreover, writing out (ΦSΦ) + using the right-hand side of (A.1) and simplifying the result yields (ΦSΦ) + = M . Proposition A.3 below establishes the equivalence between (2.7) and (RmD) on X • , and provides a concise third representation for both dynamics. Observe that (A.2c) is expression (3.33b) for (RmD) on X • , but written in matrix form.

Proposition A.3. Let ẋ = V (x) be a dynamical system on X • . Then, the following are equivalent: 32 In the above and what follows, W ⊥ denotes the orthogonal complement of a subspace W of R n , defined with respect to the ordinary Euclidean metric. Even though this might seem to suggest that the Euclidean metric plays a special role in what follows, it is just an artifact of writing everything in coordinates instead of abstractly; for a detailed discussion, see [START_REF] Lee | Riemannian Manifolds: an Introduction to Curvature[END_REF].

(i ) There is a smooth field of Hopkins matrices M : X

There is a smooth field of symmetric positive-definite matrices H :

There is a smooth Riemannian metric g on K • such that

Proof. The equivalence of (i) and (ii) follows from Lemma A.2, and the equivalence of (ii) and (iii) follows from Lemma A.2(i) with S = H(x) = g(x). 33

A.2. Continuous Hessian dynamics and reinforcement learning. We now complete the common derivation of (HD) and (RLD) on X • initiated in Section 8.2. Proposition A.3 above shows that the continuous Hessian dynamics (HD) can be expressed as ẋ = (ΦH(x)Φ) + v(x) .

(A.3)

We now extend the argument from Section 8.2 to show that the reinforcement learning dynamics (RLD) also take this form.

To that end, let

Imposing the Euclidean metric on R n 0 for convenience, we can identify (R n 0 ) * with the set of covectors whose components sum to zero, and write the derivative and Hessian of h Z at z ∈ Z • as

where the fact that the domain of h * Z is all of (R n 0 ) * follows from the compactness of Z. By the basics of convex conjugation (Rockafellar, 1970, Chapter 26), the maps

* are inverse to one another, so we have

with both sides of the equality in (A.8) understood as linear maps from R n 0 to itself. Now recall that the (symmetric) reinforcement learning process is defined by

(RL)

33 To formally complete the argument that (ii) implies (iii), we observe without proof that the field S on X • can be smoothly extended to K • .

The choice map Q, defined in (8.1) in terms of h, satisfies Q(y) = Q(yΦ) for all y ∈ R n . Thus, applying definition (A.4), we can express Q in terms of h Z as

(A.9) Hence, substituting (A.9) into (RL), differentiating, and using Eqs. (RL), (A.6), (A.8) and (A.9) yields

as specified in (A.3).

Appendix B. Extensions of Riemannian metrics

Here we present some technical results concerning the extension of Riemannian metrics from K • to K. Proposition B.1 shows that an extendable metric g on K induces a well-defined scalar product at all points of K: Proposition B.1. Let g be an extendable Riemannian metric on K. Then, for all x ∈ K, there exists a unique scalar product •, • x on dom g(x) such that w, w x k → w, w x for all w, w ∈ dom g(x) and for every interior sequence x k → x. Moreover, if g is minimal-rank extendable, we have g αβ (x) = 0 whenever α, β / ∈ supp(x).

Proof. Fix some x ∈ K and write g (x) = Q ΛQ where the diagonal matrix Λ consists of the eigenvalues of g (x) and Q is an orthogonal matrix (Q = Q -1 ) whose columns are the eigenvectors of g (x). Since g (x) is positive-semidefinite, its eigenvalues are nonnegative. Furthermore, since dom g(x) = im g (x), every eigenvector of a nonzero eigenvalue of g (x) must lie in dom g(x): indeed, if g (x)z = λz for some λ > 0, we will also have z = g (x)zλ -1 , i.e., z ∈ im g (x) = dom g(x). As a result, we may write g (x) = λ>0 λ u λ u λ where the summation is taken over all positive eigenvalues λ > 0 of g (x) (assumed for convenience to be distinct) and u λ is the corresponding column of Q. The metric tensor of the induced scalar product •, • x at x is then defined as the pseudoinverse (g (x)) + of g(x) (see Appendix A), given here by

Our continuity and uniqueness claims are then immediate. Finally, to show that g αβ (x) = 0 if α / ∈ supp(x) and g is minimal-rank extendable, simply note that g αβ (x) = e α g (x)e β = λ λ e α u λ u λ e β = 0 because all eigenvectors of g (x) with positive eigenvalues lie in R supp(x) = dom g(x).

Remark B.1. In the minimal-rank case, the scalar product •, • x on dom g(x) can be represented by the matrix g(x) = (g (x)) + . This means that the submatrix (g αβ (x)) α,β∈supp(x) is the inverse of the submatrix (g αβ (x)) α,β∈supp(x) while the remaining components (which have no geometric significance) are set to 0.

Next we establish the correctness of the formulas (3.33) for dynamics generated by a minimal-rank extendable metrics.

Proposition B.2. The formulas (3.33) describe (RmD) generated by a minimal-rank extendable metric g at all states x ∈ X ; moreover, the sums in (3.33) need only be taken over β ∈ supp(x).

Proof. The case x ∈ X • is covered in the text. Otherwise, if x ∈ bd(X ), the corresponding g-admissible set is

where the second equality follows from Remark B.1. Eq. (3.41) shows that the right-hand side of (RmD) is equal to Π x (v (x)). In light of the facts above, (3.40) shows that Π x (v (x)) is equal to the right-hand side of (3.33a), the novelty being that v α (x) and n α (x) vanish whenever α / ∈ supp(x). These claims prove the first statement in the proposition. To establish the second statement, simply observe that g αβ (x) = 0 whenever α or β is not in supp(x) by Proposition B.1, so including β / ∈ supp(x) in the sums in (3.33) is irrelevant.

Appendix C. Convergence and stability in dynamical systems

C.1. Definitions. Throughout this appendix, we focus on the dynamics

and we assume that they admit unique solutions from every initial condition. With this in mind, we say that x * is an ω-limit point of the solution orbit x(t) if there is an increasing sequence of times t n ↑ ∞ such that x(t n ) → x * . We further say that x * is Lyapunov stable if, for every neighborhood U of x * , there exists a neighborhood U of x * such that every solution orbit x(t) that starts in U is contained in U for all t ≥ 0. Finally, we say that x * is attracting if there is a neighborhood U of x * such that every solution that starts in U converges to x * , and x * is called asymptotically stable if it is Lyapunov stable and attracting. In this case, the maximal (relatively) open set of states from which solutions converge to x * is called the basin of x * ; if the basin of x * is all of X , we say that x * is globally asymptotically stable.

C.2. A global convergence result.

A standard result from dynamical systems states that if a smooth dynamical system on a compact set admits a strict global Lyapunov function, all ω-limit points are rest points (see e.g., Sandholm, 2010b, Theorem 7.B.3). The proof of this result relies on the continuity of solutions on initial conditions, a property which is not easily established for discontinuous dynamics. In Proposition C.1 below, we present a global convergence result that does not require continuity of solutions in initial conditions, but instead relies on a l.s.c. lower bound on the derivative of the Lyapunov function. To state it, let

denote the set of rest points of the dynamics (D). We then have:

Proposition C.1. Let x(t) be an absolutely continuous solution orbit of (D) and let Γ + = x(R + ) denote the set of points visited by x(t). Assume further that RP is closed and there exist functions L : X → R and φ :

(ii ) φ is lower semi-continuous and φ(x) = 0 if and only if x ∈ RP.

(iii ) DL(x)|V (x) ≥ φ(x) for all x ∈ Γ + . Then, x(t) converges to RP.

Proof. By absolute continuity and Conditions (i) and (iii) above, we get

i.e., L is nondecreasing along x(t). Furthermore, since X is compact, x(t) admits at least one ω-limit point x * ∈ cl(Γ + ) ⊆ X . Assume now that x(t) admits an ω-limit point x ω such that V (x ω ) = 0. Since RP is closed, Condition (ii) implies that there is a compact neighborhood K of x ω and some a > 0 such that φ(x) ≥ a > 0 for all x ∈ K. With this in mind, we consider two complementary cases below:

Case 1 . Suppose there exists some T ≥ 0 such that x(t) ∈ K for all t ≥ T . Then φ(x(t)) ≥ a for all t ≥ T , so (C.2) yields lim t→∞ L(x(t)) = ∞, a contradiction.

Case 2 . Assume instead that, for all T ≥ 0, we have x(t) / ∈ K for some t ≥ T . In this case, there exist open neighborhoods U and U of x ω with cl(U ) ⊆ U ⊂ K, and interlaced sequences t n , t n ↑ ∞ such that, for all n: (i )

To apply Proposition C.1 to discontinuous Riemannian dynamics in potential games, we need the following result:

Lemma C.2. The speed of motion V (x) x of the dynamics (RmD) is l.s.c. on X .

Proof. If the dynamics (RmD) are continuous, our claim follows immediately from the continuity of the underlying metric -in fact, V (x) x is continuous in this case. Otherwise, if (RmD) is discontinuous, recall that V (x) ≡ Π x (v (x)) is simply the projection of v (x) on the tangent cone TC X (x) to X at x (because Adm g (x) = TC X (x) in that case). Therefore, if we write V ⊥ (x) = v (x) -V (x) for the projection of v (x) on the normal cone NC X (x) to X at x, Moreau's decomposition theorem and the Cauchy-Schwarz inequality yield

for all z ∈ TC X (x), with the inequality binding if and only if z ∝ V (x). We thus obtain the characterization

Note now that the correspondence x → TC X (x) is l.s.c. because it is constant on the interior of each face of X and TC X (x) ⊆ TC X (y) whenever supp(x) ⊆ supp(y). This shows that the constraint correspondence x → TC X (x)∩B(x) of (C.5) is l.s.c.; since the objective function v (x), z x of (C.5) is jointly continuous in x and z, a precursor to the maximum theorem (Aliprantis and Border, 1999, Lemma 16.30) implies that x → V (x) x is itself l.s.c., as claimed.

Appendix D. Additional proofs

In this appendix, we collect some proofs that are too technical for the main text. We begin with the proof of Proposition 6.1 regarding the existence and uniqueness of solutions to (RmD). As noted in Section 6, we only need to prove part (ii), which concerns the case of full-rank extendable metrics. Existence of forward solutions of (RmD) on X follows from general results of [START_REF] Aubin | Differential Inclusions[END_REF] on solutions to discontinuous differential equations; see [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF] for a summary of their argument. Thus, it remains to show that forward solutions to (RmD) from each initial condition in X are unique. This conclusion follows from the following lemma: Lemma D.1. Let x(t) and x (t) be solutions to (RmD), and let

If λ > 0 is large enough, then P (t) is nonincreasing.

Given this lemma, we immediately obtain:

Proof of Proposition 6.1. Let x(t) and x (t) be solutions of (RmD) with x(0) = x (0). We then get P (t) = P (0) = 0 for all t ≥ 0, so x(t) = x (t) for all t ≥ 0.

To prove Lemma D.1, we need one final auxiliary result. Let V (x) = Π x (v (x)) denote the right-hand side of (RmD). Then, as we show below, V satisfies a onesided Lipschitz condition with respect to the underlying metric: Lemma D.2. There exists some K V > 0 such that

Proof of Lemma D.2. Write w(x) = v (x) and w ⊥ (x) = w(x) -Π x (w(x)). Since g is full-rank extendable, Π x is the orthogonal projection onto TC X (x) with respect to •, • x . We thus obtain V (x ) -V (x), x -x x = w(x ) -w(x), x -x x -w ⊥ (x ) -w ⊥ (x), x -x x = w(x ) -w(x), x -x x + w ⊥ (x), x -x x + w ⊥ (x ), x -x x + (w ⊥ (x )) (g(x ) -g(x))(x -x)

≤ K w x -x 2

x + (w ⊥ (x )) (g(x ) -g(x))(x -x), (D.3) where the bound for the first term in the last line follows from the Cauchy-Schwarz inequality and the Lipschitz continuity of w, while the rest follows from Moreau's decomposition theorem. To bound the last term, write g α (x) for the α-th row of g(x), let W ⊥ max = max α∈A max x∈X w ⊥ α (x), and let • 2 denote the standard Euclidean norm. Then, if C > 0 is chosen sufficiently large, we get (w ⊥ (x )) (g(x ) -g(x))(x -x)

x . (D.4) In the above, the first inequality is an immediate corollary of the Cauchy-Schwarz inequality; the last one follows from the equivalence of norms on R A and the fact that g is C 1 on X ; finally, C can be chosen independently of x and x because X is compact. Combining (D.3) and (D.4) completes our proof. so lim n→∞ t -1 n tn 0 Ψ(x(s)) ds = v(x * )|p -ū * > 0. This establishes (D.6) for large enough t = t n , completing our proof.