Saeed Hadikhanloo
email: saeed.hadikhanloo@tweag.io

Rida Laraki
email: rida.laraki@dauphine.fr

PANAYOTIS MERTIKOPOULOS ♯ Sylvain Sorin
email: sylvain.sorin@imj-prg.fr.

LEARNING IN NONATOMIC GAMES, PART I: FINITE ACTION SPACES AND POPULATION GAMES

Keywords: 2020 Mathematics Subject Classification. Primary 91A22, 91A26, secondary 37N40, 68Q32 Learning, nonatomic games, fictitious play, dual averaging, evolutionary stability, Nash equilibrium, variational inequalities

We examine the long-run behavior of a wide range of dynamics for learning in nonatomic games, in both discrete and continuous time. The class of dynamics under consideration includes fictitious play and its regularized variants, the best reply dynamics (again, possibly regularized), as well as the dynamics of dual averaging / "follow the regularized leader" (which themselves include as special cases the replicator dynamics and Friedman's projection dynamics). Our analysis concerns both the actual trajectory of play and its time-average, and we cover potential and monotone games, as well as games with an evolutionarily stable state (global or otherwise). We focus exclusively on games with finite action spaces; nonatomic games with continuous action spaces are treated in detail in Part II.

Introduction

The study of evolutionary dynamics in population games has been the mainstay of evolutionary game theory ever since the inception of the field in the mid-1970's. Such dynamics are typically derived from biological models or economic microfoundations that express the net growth rate of a type (or strategy) within a population as a function of the relative frequency of all other types. Thus, owing to the flexibility of this general framework, these considerations have generated an immense body of literature; for an introduction to the topic, we refer the reader to the masterful treatments of Hofbauer & Sigmund [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF], Weibull [START_REF] Weibull | Evolutionary Game Theory[END_REF], and the more recent, panoramic survey of Sandholm [START_REF] William | Population Games and Evolutionary Dynamics[END_REF][START_REF] William | Population games and deterministic evolutionary dynamics[END_REF].

Our paper takes a complementary approach and aims to examine the long-run behavior of learning procedures in nonatomic games. While the topic of learning in games with a finite number of players is fairly well-studied -see e.g., the classic works of Fudenberg & Levine [START_REF] Fudenberg | The Theory of Learning in Games, volume 2 of Economic learning and social evolution[END_REF] and Cesa-Bianchi & Lugosi [START_REF] Cesa | Prediction, Learning, and Games[END_REF] -the same cannot be said for learning in population games. On that account, our goal in this paper is to provide a synthetic treatment for a wide range of dynamics for learning in nonatomic games, unifying along the way a number of existing results in the literature.

We pursue this goal in two parts. In the current paper, we focus exclusively on games with shared, finite action spaces; games with continuous (and possibly player-dependent) action spaces are significantly more complicated, so their study is deferred to the companion paper [START_REF] Hadikhanloo | Learning in nonatomic games, Part II: Continuous action spaces and mean-field games[END_REF].

Overview of the paper. To specify the general framework under consideration one has to: a) Describe the family of games to be studied: These are anonymous nonatomic games and two concrete classes thereof, potential and monotone games; the relevant details are provided in Section 2. b) Identify the solution concepts involved: We will mainly focus on Nash equilibria and variants of evolutionarily stable states, expressed throughout as solutions of an associated variational inequality; this is also described in Section 2. c) Define the dynamics under study: This is the content of Section 3, where we begin by recalling the standard fictitious play procedure of Brown [START_REF] Brown | Iterative solutions of games by fictitious play[END_REF] and Robinson [START_REF] Robinson | An iterative method for solving a game[END_REF], its regularized variants [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF], and its continuous-time analogue, the best reply dynamics of Gilboa & Matsui [START_REF] Gilboa | Social stability and equilibrium[END_REF]. Subsequently, we introduce a general class of dynamics known as dual averaging -or "follow the regularized leader" -and which contains as special cases the replicator dynamics of Taylor & Jonker [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF] and the projection dynamics of Friedman [START_REF] Friedman | Evolutionary games in economics[END_REF].

The dynamics we examine evolve in both discrete and continuous time: the continuoustime analysis is presented in Section 4 and comprises the template for the discrete-time analysis that follows in Section 5. In both cases, our analysis builds on previous work and results by Monderer & Shapley [START_REF] Monderer | Potential games[END_REF], Sandholm [START_REF] William | Potential games with continuous player sets[END_REF], Hofbauer & Sigmund [START_REF] Hofbauer | Evolutionary game dynamics[END_REF], Hofbauer & Sandholm [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF][START_REF] Hofbauer | Stable games and their dynamics[END_REF], Hofbauer et al. [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF] and Mertikopoulos & Sandholm [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Mertikopoulos | Riemannian game dynamics[END_REF]. In this context, some of the new results that we present in our paper can be summarized as follows: a) We establish a precise link between (regularized) fictitious play and dual averaging: informally, fictitious play best-responds to the average population state whereas dual averaging best-responds to the average population payoff profile. b) We determine the equilibrium convergence properties of vanishingly regularized fictitious play in continuous time. c) We provide a range of conditions for the convergence of dual averaging trajectories to evolutionarily stable states, in both discrete and continuous time (and possibly with a variable learning rate).

Finally, in Section 6, we discuss several extensions of these results beyond single-population nonatomic games, and we provide a preview of the issues that arise in nonatomic games with continuous action spaces -the topic of interest of the follow-up paper [START_REF] Hadikhanloo | Learning in nonatomic games, Part II: Continuous action spaces and mean-field games[END_REF].

Preliminaries

2.1. Nonatomic games. A (single-population) nonatomic game is defined by the following primitives:

• A population of players. This is modeled by the unit interval I = [0, 1] endowed with the Lebesgue measure µ. The nonatomic aspect means that the behavior of a set of players with zero measure has no impact on the game (see below).

• A set of pure strategies A = {1, . . . , A}. Following Schmeidler [START_REF] Schmeidler | Equilibrium points of nonatomic games[END_REF], the players' strategic behavior is defined as a measurable function χ : I → A, with χ(i) ∈ A denoting the pure strategy of player i. Given a pure strategy α ∈ A, the inverse image χ -1 (α) = {i ∈ I : χ(i) = α} will be called the set of "α-strategists", and the corresponding pushforward measure x := χ♯µ ≡ µ • χ -1 on A will be called the state of the population. This measure will be the main variable of interest; for convenience, we will view x as an element of the simplex X := ∆(A) and we will write x α = µ(χ -1 (α)) for the relative frequency of α-strategists in the population.

• A family of continuous payoff functions u α : X → R, α ∈ A. Specifically, u α (x) denotes the payoff to α-strategists when the state of the population is x ∈ X . Collectively, we will also write F (x) = (u α (x)) α∈A for the population's payoff vector at state x.

The above definition specifies a population game G ≡ G(A, F ), cf. Sandholm [START_REF] William | Population Games and Evolutionary Dynamics[END_REF] and references therein. In this definition, players are anonymous in the sense that their payoffs factor through the state of the population and do not depend on specific players choosing specific strategies. For more intricate classes of nonatomic games (possibly involving idiosyncratic components), see Schmeidler [START_REF] Schmeidler | Equilibrium points of nonatomic games[END_REF] and Mas-Colell [START_REF] Mas-Colell | On a theorem of Schmeidler[END_REF].

2.2. Equilibria, stability, and variational inequalities. In population games, an equilibrium is defined as a population state x * ∈ X in which almost all players are satisfied with their choice of strategy. Formally,

x * ∈ X is an equilibrium of G if u α (x * ) ≥ u β (x * ) for all α ∈ supp(x * ), β ∈ A, (Eq)
where supp(x * ) denotes the support of x * . Equivalently, this requirement for x * ∈ X can be stated as a Stampacchia variational inequality (SVI) of the form

⟨F (x * ), x -x * ⟩ ≤ 0 for all x ∈ X . (SVI)
Equilibria can also be seen as fixed points of the continuous endomorphism x → Π X (x+F (x)), where Π X denotes the Euclidean projector on X . By standard fixed point arguments, it follows that the game's set of equilibria is nonempty; we will denote this set as Eq(G).

Remark. In operator theory and optimization, the direction of (SVI) is typically reversed because optimization problems are usually formulated as minimization problems. The utility maximization viewpoint is more common in the literature on population games, so we will maintain this sign convention throughout.

An alternative characterization of equilibria is by means of the best-response correspondence BR : X ⇒ X , defined here as

BR(x) := arg max x ′ ∈X ⟨F (x), x ′ ⟩, (1)
We then have the following string of equivalences:

x * ∈ BR(x * ) ⇐⇒ supp(x * ) ⊆ BR(x * ) ⇐⇒ x * ∈ Eq(G) (2)
i.e., the equilibria of the game correspond to the fixed points of BR. One can easily show that, under our assumptions, this correspondence has a closed graph and convex compact non-empty values. By Kakutani's fixed point theorem, Eq(G) -that is, the set of fixed points of BR -is nonempty and compact. We will also consider the associated Minty variational inequality (MVI) for x * ∈ X , namely

⟨F (x), x -x * ⟩ ≤ 0 for all x ∈ X . (MVI)
For concreteness, we will write SVI(G) and MVI(G) for the set of solutions of (SVI) and (MVI) respectively. In terms of structural properties, MVI(G) is convex and, under our continuity assumption for F , it is straightforward to verify that MVI(G) ⊆ SVI(G) ≡ Eq(G). In this regard, (MVI) represents an "equilibrium refinement" criterion for G (see also Section 2.3 below).

In more detail, (MVI) is intimately related to the seminal notion of evolutionary stability that was introduced by Maynard Smith & Price [START_REF] Smith | The logic of animal conflict[END_REF] and formed the starting point of evolutionary game theory. To make this link precise, recall that a population state x * ∈ X is an evolutionarily stable state of G [START_REF] Smith | The logic of animal conflict[END_REF][START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] William | Population Games and Evolutionary Dynamics[END_REF], if

⟨F (δx + (1 -δ)x * ), x -x * ⟩ < 0 (ESS)
for all sufficiently small δ > 0 and all states x ̸ = x * . Analogously, x * ∈ X is a neutrally stable state (NSS) of G if (ESS) holds as a weak inequality, i.e.,

⟨F (δx + (1 -δ)x * ), x -x * ⟩ ≤ 0 (NSS)
for all sufficiently small δ > 0 and all x ∈ X . Finally, x * is said to be a globally evolutionarily stable state (resp. globally neutrally stable state) of G if (ESS) [resp. (NSS)] holds for all δ ∈ (0, 1]. In obvious notation, we will write ESS(G), NSS(G), GESS(G) and GNSS(G) for the respective set of states of G (by definition GESS(G) consists of at most a single point).

Characterizations and implications.

A concise characterization of these notions of stability was derived by Taylor [START_REF] Peter | Evolutionarily stable strategies with two types of player[END_REF] and Hofbauer et al. [START_REF] Hofbauer | A note on evolutionarily stable strategies and game dynamics[END_REF], who showed that x * ∈ ESS(G) if and only if there exists a neighborhood U of x * in X such that

⟨F (x), x -x * ⟩ < 0 for all x ∈ U \ {x * }, (3)
and, furthermore, if we can take U = X above, then GESS(G) = {x * }. For the corresponding neutral versions, we have x * ∈ NSS(G) if and only if (3) holds on U as a weak inequality, and x * ∈ GNSS(G) if and only if we can take U = X in this case. This characterization of GNSS(G) corresponds precisely to the solution set of (MVI); in particular, we have the following string of inclusions:

GESS GNSS MVI ESS NSS Eq SVI ⊆ ⊆ ≡ ⊆ ⊆ ⊆ ⊆ ≡ (4)
In general, the above inclusions are all one-way; in the next section, we discuss two important cases where some of them become equivalences.

Classes of games.

The following classes of games will play an important role in the sequel:

(1) Potential games: these are games that admit a potential function, i.e., a function P : X → R such that F = ∇P on X , or, more generally,

P ′ (x; x ′ -x) = ⟨F (x), x ′ -x⟩ for all x, x ′ ∈ X , (Pot)
where P ′ (x; z) := lim t→0 + [P (x + tz) -P (x)]/t denotes the one-sided directional derivative of P at x along z. If G is a potential game, any local maximum of P is an equilibrium of G, and any strict local maximum of P is an ESS of G. For a detailed treatment of potential games in population games extending the initial study of Monderer & Shapley [START_REF] Monderer | Potential games[END_REF], see Sandholm [START_REF] William | Potential games with continuous player sets[END_REF][START_REF] William | Population Games and Evolutionary Dynamics[END_REF].

(2) Monotone games: these are games that satisfy the monotonicity condition

⟨F (x ′ ) -F (x), x ′ -x⟩ ≤ 0 for all x, x ′ ∈ X . (Mon)
This condition implies that every equilibrium of G is neutrally stable, so we get the following equivalences:

MVI(G) ≡ GNSS(G) = NSS(G) = Eq(G) ≡ SVI(G) (5)
In this class, the existence of equilibria relies only on the minmax theorem [START_REF] Minty | On the generalization of a direct method of the calculus of variations[END_REF].

Going further, a game is called strictly monotone if (Mon) holds as a strict inequality for all x ′ ̸ = x. In this case, we have the stronger equivalence

GESS(G) = ESS(G) = Eq(G), (6)
i.e., all inclusions in (4) become two-way. Moreover, Eq(G) is a singleton which is also the unique GESS of the game.

The intersection of potential and monotone (resp. strictly monotone) games occurs when G admits a concave (resp. strictly concave) potential. The most important example of such games is the class of nonatomic congestion games that arise in routing and transportation theory, cf. Dafermos [START_REF] Dafermos | Traffic equilibrium and variational inequalities[END_REF].

2.4. Regularization. In the sequel, we will often consider "regularized" best responses that are single-valued. These are defined as follows:

Definition 2.1. A regularizer on X is a function h : R A → R ∪ {∞} such that: (1) h is supported on X , i.e., dom h = {x ∈ R A : h(x) < ∞} = X .
(2) h is strictly convex and continuous on X .

Given a regularizer on X , we further define:

a) The associated choice map Q h : R A → X given by

Q h (v) := arg max x ′ ∈X {⟨v, x ′ ⟩ -h(x ′ )}. (7a)
b) The regularized best response to a population state x ∈ X :

BR h (x) := arg max x ′ ∈X {⟨F (x), x ′ ⟩ -h(x ′ )} = Q h (F (x)). (7b)
Remark 2.1. By our assumptions for h (continuity and strict convexity), Q h and BR h are both well-defined and single-valued as correspondences. Moreover, by the strict convexity of h, it follows that the convex conjugate h * (y) = max x∈X {⟨y, x⟩ -h(x)} of h is differentiable and satisfies

Q h (v) = ∇h * (v) for all v ∈ R A . ( 8
)
Remark 2.2. By construction, BR h (approximately) best-responds to strategies, while Q h best-responds to payoff vectors. For this reason, we will sometimes refer to Q h as a "payoffbased" regularized best response (as opposed to "strategy-based" regularized best response for BR h ).

Moving forward, for part of our analysis, we will also require one (or both) of the regularity conditions below:

(1) h is K-strongly convex on X , i.e.,

h(λx + (1 -λ)x ′ ) ≤ λh(x) + (1 -λ)h(x ′ ) - K 2 λ(1 -λ)∥x ′ -x∥ 2 (StrCvx)
for all x, x ′ ∈ X and all λ ∈ [0, 1].

(2) The subdifferential ∂h of h admits a continuous selection; specifically, writing X h := dom ∂h = {x : ∂h(x) ̸ = ∅} for the "prox-domain" of h, we posit that there exists a continuous map ∇h :

X h → R A such that ∇h(x) ∈ ∂h(x) for all x ∈ X h . (Diff)
By replacing best responses with regularized best responses in the definition of equilibria, we also define the notion of a regularized equilibrium as follows: Definition 2.2. Given a regularizer h on X and a regularization weight ε > 0, we define an ε-regularized equilibrium of G as a profile x * ∈ X such that x * ∈ BR εh (x * ). The set of ε-regularized equilibria of G will be denoted as Eq εh (G).

Under (Diff), x * ∈ X is an ε-regularized equilibrium if and only if

⟨F (x * ) -ε ∇h(x * ), x * -x⟩ ≥ 0 for all x ∈ X . (9)
In this regard, ε-regularized equilibria can be seen as Nash equilibria of the "ε-regularized" game

G ε ≡ G ε (A, F ε ) with payoff profile F ε (x) := F (x) -ε ∇h(x); more concisely, Eq ε (G) = Eq(G ε ).
Equilibria and regularized equilibria are related by the next hemicontinuity property, itself a consequence of the maximum theorem of Berge [START_REF] Berge | Topological Spaces[END_REF].

Lemma 1. Let x *
ε ∈ Eq ε (G), ε > 0, be a family of regularized equilibria of G. Then, in the limit ε → 0, any accumulation point of x * ε is an equilibrium of G. We close this section with a concrete illustration of the above concepts:

Example 2.1 (Logit choice). An important example of regularization corresponds to the entropic regularizer h(x) = α∈A x α log x α which, by a standard calculation, leads to the choice map

Λ(v) = (e v1 , . . . , e v A ) e v1 + • • • + e v A . (10)
This map is commonly referred to as the logit choice map [START_REF] Daniel | Conditional logit analysis of qualitative choice behavior[END_REF], and the corresponding fixed points x * = Λ(F (x * )/ε) are known as logit equilibria; for a detailed discussion, see van Damme [START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF], McKelvey & Palfrey [START_REF] Mckelvey | Quantal response equilibria for normal form games[END_REF], Sandholm [START_REF] William | Population Games and Evolutionary Dynamics[END_REF], and references therein. It is also well known that the entropic regularizer is 1-strongly convex relative to the L 1 -norm, so Λ is 1-Lipschitz continuous, cf. Shalev-Shwartz [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF].

♢

Dynamics

In this section, we introduce a wide range of dynamics for learning in nonatomic games, in both continuous and discrete time. The unifying principle of the dynamics under study is that agents play a best response -regularized or otherwise -to some version of the history of play: the empirical population frequencies, or the players' average gains. For historical reasons, we begin with the discrete-time framework in Section 3.1, and we present the corresponding continuous-time dynamics in Section 3.2.

3.1. Discrete-time processes. In the discrete-time case, we will consider the evolution of the population state X n ∈ X over a series of epochs n = 1, 2, . . . (corresponding for example to generations in an evolutionary context). In turn, this population state is determined by a recursive update rule -or algorithm -that defines the dynamics in question. Depending on the manner of "best-responding" and the signal that the agents are best-responding to, we have the following dynamics.

Fictitious play. Dating back to Brown [START_REF] Brown | Iterative solutions of games by fictitious play[END_REF] and Robinson [START_REF] Robinson | An iterative method for solving a game[END_REF], fictitious play (FP) posits that agents best-respond to the empirical frequency (or "time average") Xn = (1/n) n k=1 X k of their population state. Concretely, this means that the population state evolves according to the process X n+1 ∈ BR( Xn ) = arg max x∈X ⟨F ( Xn ), x⟩.

(FP) In terms of empirical frequencies, we have the recursive dynamics

Xn+1 -Xn ∈ 1 n + 1 [BR( Xn ) -Xn ]. (11)
In contrast to the sequence of actual population states X n ∈ X , n = 1, 2, . . . , the stationary points of the time-averaged process [START_REF] Dafermos | Traffic equilibrium and variational inequalities[END_REF] are straightforward to characterize. Indeed, any fixed point x * of (11) satisfies

0 ∈ BR(x * ) -x * , (12)
i.e., x * is stationary under [START_REF] Dafermos | Traffic equilibrium and variational inequalities[END_REF] if and only if it is an equilibrium of G.

Regularized fictitious play. A variant of the original fictitious play algorithm is the "regularized" version in which best responses are replaced by regularized best responses. In particular, given an underlying regularizer h on X and a corresponding regularization weight ε > 0, the regularized fictitious play (RFP) process is defined as

X n+1 = BR εh ( Xn ) = arg max x∈X V εh ( Xn , x) (RFP) with V εh (x ′ , x) = ⟨F (x ′ ), x⟩ -εh(x) (13
) Then, as before, in terms of empirical frequencies, we have

Xn+1 -Xn ∈ 1 n + 1 [BR εh ( Xn ) -Xn ]. (14)
As in the case of (FP), the stationary points of the time-averaged dynamics (RFP) are given by the fixed point equation

0 ∈ BR εh (x * ) -x * , (15)
i.e., they are precisely the ε-regularized equilibria of G (cf. Definition 2.2).

Remark. In the literature, this process is sometimes referred to as "smooth" or "perturbed" fictitious play, cf. Fudenberg & Levine [START_REF] Fudenberg | Conditional universal consistency[END_REF], Hofbauer & Sandholm [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF] and references therein. This difference in terminology is owed to a different set of assumptions for h, which gives rise to interior-valued choice maps Q : R A → X .

Vanishingly regularized fictitious play. When the regularization weight in (RFP) decreases over time, we obtain the vanishingly regularized fictitious play (VRFP) dynamics of Benaïm & Faure [START_REF] Benaïm | Consistency of vanishingly smooth fictitious play[END_REF], viz.

X n+1 = BR εnh ( Xn ) = arg max x∈X V εnh ( Xn , x) (VRFP
) with ε n > 0 for all n and ε n → 0 as n → ∞. In terms of empirical frequencies, we then have

Xn+1 -Xn ∈ 1 n + 1 [BR εnh ( Xn ) -Xn ]. (16)
Because this process is non-autonomous (ε n depends explicitly on n), it is no longer meaningful to discuss its rest points.

Dual averaging. Dually to the above, instead of best-responding to the aggregate history of play (perfectly or approximately), we can also consider the case where agents play a "regularized best response to their aggregate payoff ". In our context, this gives rise to the dual averaging dynamics

X n+1 = Q h η n n k=1 F (X k ) , (17)
with Q h defined in (7a). Then, in iterative form, we get the update rule

S n = S n-1 + F (X n ) X n+1 = Q h (η n S n ) (DA)
where η n > 0 is a "learning rate" parameter in the spirit of Nesterov [START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF]. In the recursive formulation (DA) of the dynamics, the initialization S 0 = 0 is the most common one but, otherwise, it can be arbitrary.

Remark. In the literature on online learning and online optimization, the process (DA) is known as "follow the regularized leader" (FTRL) [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev | Convex repeated games and Fenchel duality[END_REF]. The terminology "dual averaging" is due to Nesterov [START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF] and is more common in the theory of variational inequalities and offline convex optimization. We adopt the latter to highlight the link of our work to variational inequalities.

Links between the dynamics: the case of random matching. To illustrate the relations between the various learning processes discussed above, it will be instructive to consider nonatomic games generated by random matching [START_REF] Weibull | Evolutionary Game Theory[END_REF][START_REF] William | Population Games and Evolutionary Dynamics[END_REF]. In such games, players are randomly matched to play a symmetric two-player game with payoff matrix A ∈ R A×A , so the population's mean payoff profile is F (x) = M x for all x ∈ X . As a result, the dynamics (DA) may be rewritten as

X n+1 = Q h η n n k=1 F (X k ) = Q h nη n F ( Xn ) = Q h/(nηn) (F ( Xn )), (18)
which immediately allows us to recover the variants of fictitious play as follows:

(1) For (VRFP):

η n = 1/(nε n ) for a sequence of weights ε n > 0, lim n→∞ ε n = 0.
(2) For (RFP): η n = 1/(nε) for some fixed ε > 0.

(3) For (FP): this corresponds to the limiting cases "nη n = ∞" or "h = 0". [Of course, these parameter choices are not formally allowed in (DA), so this limit is informal.]

Remark. The above is meaningful only when F (x) is linear in x; however, the relation between ε and η will be seen to underlie a large part of the sequel.

3.2. Continuous-time dynamics. We now proceed to define the corresponding continuous-time dynamics for each of the processes described above.

Best reply dynamics. The autonomous formulation [START_REF] Dafermos | Traffic equilibrium and variational inequalities[END_REF] of fictitious play can be seen as an Euler discretization of the best reply dynamics (BRD) of Gilboa & Matsui [START_REF] Gilboa | Social stability and equilibrium[END_REF], namely

μt ∈ BR(µ t ) -µ t . (BRD)
In the above, µ t ∈ X is the continuous-time analogue of the empirical mean process Xn in discrete time; we use the notation µ instead of x to highlight this link. Clearly, the rest points of (BRD) are again described by the fixed point equation ( 12), i.e., µ * is stationary under (BRD) if and only if it is an equilibrium of G.

Regularized best reply dynamics. Working as above, the regularized best reply dynamics (RBRD) are defined as μt = BR εh (µ t ) -µ t .

(RBRD) As in the case of (RFP), the rest points of (RBRD) are characterized by the fixed point equation [START_REF] Gilboa | Social stability and equilibrium[END_REF], i.e., µ * is stationary under (RBRD) if and only if it is an ε-regularized equilibrium of G.

Example 3.1 (The logit dynamics). Building on the logit choice map discussed in Section 2 (cf. Example 2.1), the associated regularized best reply dynamics are known as logit dynamics, and are given by

μt = Λ(F (µ t )/ε) -µ t . ( 19
)
Vanishing regularized best reply dynamics. If we allow the regularization weight ε to vary in (RBRD), we obtain the non-autonomous dynamics

μt = BR εth (µ t ) -µ t , (VBRD)
where the "V" indicates again that ε t → 0 as t → ∞.

The dual averaging dynamics. Finally, given a regularizer h on X as above, the dynamics of dual averaging in continuous time can be written as

ẏt = F (x t ) x t = Q h (η t y t ) (DAD)
where η t ≥ 0 is a time-varying learning parameter, which we assume throughout to be non-increasing. More compactly, the above can also be written as

ẏt = F (Q h (η t y t )) (20a)
or

x t = Q h η t t 0 F (x s ) ds , (20b)
depending on whether we take a differential-or integral-based viewpoint. Specifically, we note that (20a) is an autonomous ordinary differential equation evolving in the dual, payoff space of the game; by contrast, (20b) is an integral equation stated directly in the primal, strategy space of the game. We also note that, unlike (BRD), (RBRD) and (VBRD), the dynamics (DAD) are stated in terms of the actual population state x t at time t, not its empirical mean µ t (which is the driving variable of the previous dynamics).

Example 3.2. If η t ≡ 1 and h is the entropic regularizer on X (cf. Example 2.1), the dynamics (DAD) yield the replicator dynamics of Taylor & Jonker [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF], viz.

ẋα,t = x α,t [u α (x t ) -⟨F (x t ), x t ⟩]. (RD)
In words, (RD) indicates that the per capita growth rate of the population of α-strategists is proportional to the difference between the payoff that they experience and the mean population payoff. For a detailed presentation of this derivation in different contexts, see Rustichini [START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF], Sorin [START_REF] Sylvain Sorin | Exponential weight algorithm in continuous time[END_REF][START_REF] Sylvain Sorin | Replicator dynamics: Old and new[END_REF], Mertikopoulos & Moustakas [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF] and references therein. ♢ Example 3.3. If η t ≡ 1 and h(x) = (1/2) α∈A x 2 α , the integral form (20b) of (DAD) becomes

x t = Π t 0 F (x s ) ds (21)
where Π denotes the Euclidean projector on X . The differential form of ( 21) is more delicate to describe because x t may enter and exit different faces of X in perpetuity. However, if we focus on an open interval T ⊆ R over which the support of x t remains constant, it can be shown that [START_REF] Hofbauer | Evolutionary game dynamics[END_REF] follows the projection dynamics of Friedman [START_REF] Friedman | Evolutionary games in economics[END_REF], viz. for all t ∈ T we have

ẋα,t = u α (x) - 1 |supp(xt)| β∈supp(xt) u β (x) if α ∈ supp(x t ), 0 otherwise. (PD)
For the details of this derivation, see Mertikopoulos & Sandholm [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF].

♢

Remark. For posterity, we note that both regularizers used in the above examples satisfy (StrCvx), (Diff), and the technical condition (Rec) that we describe later in the paper.

Random matching in continuous time. Following Hofbauer et al. [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF], the various dynamics presented so far can be linked as follows when F is linear and µ t = 1 t t 0 x s ds for t > 0:

x t = arg max x∈X η t t 0 ⟨F (x s ), x⟩ ds -h(x) = arg max x∈X {η t t ⟨F (µ t ), x⟩ -h(x)} = BR [1/(tηt)]h (µ t ). (22)
It thus follows that the empirical distribution of play µ t under (DAD) follows the dynamics

μt = BR εth (µ t ) -µ t t (23)
with ε t = 1/(tη t ). Hence, after the change of time t ← log t, we get (RBRD) with a variable regularization parameter ε t = 1/(tη t ).

Analysis and results in continuous time

We now proceed to present our results for the class of dynamics under study. We begin with the continuous-time analysis which provides a template for the discrete-time analysis in the next section. We prove that under some assumptions depending on the dynamical system and the class of games under consideration (potential, monotone or strictly monotone), the dynamics converge to the set of equilibria or or -regularized equilibria -of the game. Then every solution orbit µ t of (BRD) converges to Eq(G).

Proof. Both cases rely on establishing a suitable Lyapunov function E(t) for (BRD):

(1) In the potential case, we simply take E(t) = P (µ t ).

(2) In the monotone case, E(t) = Gap(µ t ) where Gap denotes the function

Gap(x) := max x ′ ∈X ⟨F (x), x ′ -x⟩ = ⟨F (x), BR(x) -x⟩ (24)
Observe that Gap(x) ≥ 0 with equality if and only if x ∈ Eq(G).

We now proceed on a case-by-case basis:

Potential case. From (Pot) we obtain that

d dt P (µ t ) = lim δ→0 + [P (µ t + δ μt ) -P (µ t )]/δ = ⟨F (µ t ), μt ⟩ (25)
Since μt ∈ BR(µ t ) -µ t , it follows that d dt P (µ t ) = Gap(µ t ) ≥ 0 with equality if and only if μt = 0. Consequently, from Lyapunov's first method [see e.g., 20, Theorem 2.6.1] we deduce that µ t converges to the set of rest points of (BRD), which is Eq(G). 1 Recall that a family (xt) t≥0 (resp. a sequence (Xn), n = 1, 2, . . . ) converges to a set B if the set of

accumulation points A[xt] (resp. A[xn]), as t → ∞ (resp n → ∞), satisfies: A[xt] ⊂ B (resp. A[xn] ⊂ B).
Monotone case. Let JF denote the Jacobian of F . By the envelope theorem we get:

d dt Gap(µ t ) = ⟨F (µ t ), -μt ⟩ + μt JF (µ t )(BR(µ t ) -µ t ) = -Gap(µ t ) + μt JF (µ t ) μt ( 26
)
As G is monotone, (x ′ -x)JF (x)(x ′ -x) ≤ 0 for all x, x ′ ∈ X , so μt JF (µ t ) μt ≤ 0. Consequently:

d dt Gap(µ t ) ≤ -Gap(µ t ). (27)
Hence Gap(µ t ) decreases exponentially to 0, so µ t converges to Eq(G).

■ 4.2. Regularized best reply dynamics. In this section we will assume that the regularizer h satisfies (Diff). In a slight abuse of notation, we will skip the dependence on h and write F ε for F εh := F -ε ∇h, see [START_REF] Cesa | Prediction, Learning, and Games[END_REF], with ∇h defined as in (Diff). We also write BR ε (x) for BR εh (x) and so on. The reason is that the regularizer h will be fixed throughout while the weight ε will be allowed to vary in the next subsection.

Lemma 2. Under (Diff), we have ⟨F ε (x), BR ε (x) -x⟩ ≥ 0 for all x ∈ X , and equality holds if and only if x = BR ε (x).

Proof. Let ϕ(z) = ⟨F (x), z⟩ -εh(z). Then ϕ is strictly concave and so ∂ϕ defines a strictly monotone operator. Thus, x ′ = arg max z∈X ϕ(z) is a solution of the variational inequality (MVI) associated to ∂ϕ: for all d ∈ ∂ϕ(x): ⟨d, x ′ -x⟩ ≥ 0 with equality if and only if x = x ′ . As F ε (x) ∈ ∂ϕ(x) and x ′ = BR ε (x) the result follows.

■ Lemma 3. Suppose that (Diff) holds. If G with payoff field F is potential (resp. monotone) then the game G ε with payoff function F ε is potential (resp. strictly monotone).

Proof. If G has a potential P , a potential function of G ε is P -εh. If G is a monotone game, the game G ε is strictly monotone because we have ⟨ ∇h(x) -∇h(x ′ ), x -x ′ ⟩ ≥ 0 for every x, x ′ ∈ X , with equality if and only if x = x ′ .

■

We now turn to the asymptotic properties of regularized best reply dynamics.

Theorem 4.2. Suppose that (Diff) is satisfied and assume one of the following holds:

(a) G is potential.

(b) G is monotone and F is C 1 -smooth.
Then every solution orbit µ t of (RBRD) converges to Eq ε (G).

Remark. Observe that when G is monotone, G ε is strictly monotone, so Eq ε (G) is a singleton.

Proof. As above, both cases rely on establishing a suitable Lyapunov function E(t) for (RBRD):

(1) In the potential case: E(t) = P ε (µ t ) := P (µ t ) -εh(µ t ).

(2) In the monotone case:

E(t) = Gap ε (µ t ) = max x ′ ∈X ⟨F (µ t ), x ′ -µ t ⟩ -ε(h(x ′ ) -h(µ t )) = max x ′ ∈X V ε (µ t , x ′ ) -V ε (µ t , µ t ) (28)
Potential case. There is z(t) ∈ ∂h(µ t ) such that -similarly to (25) -we have:

d dt P ε (µ t ) = lim dt→0 + [P ε (µ t + μt dt) -P ε (µ t )]/dt = ⟨F (µ t ), μt ⟩ -ε⟨z(t), μt ⟩ (29)
As μt = BR ε (µ t ) -µ t , by Lemma A.1 in the appendix, we have ⟨z(t), μt ⟩ ≤ ⟨ ∇h(µ t ), μt ⟩.

Consequently d dt P ε (µ t ) ≥ ⟨F (µ t ), μt ⟩ -ε⟨ ∇h(µ t ), μt ⟩ = ⟨F ε (µ t ), μt ⟩ (30)
By Lemma 2 and the above, we deduce that d dt P ε (µ t ) ≥ 0 with equality if and only if μt = 0. Consequently, by a Lyapunov argument, µ t converges to Eq ε (G).

Monotone case. Using the envelope theorem as in [START_REF] Kwon | A continuous-time approach to online optimization[END_REF] and, just as above, there is z(t) ∈ ∂h(µ t ) such that:

d dt Gap ε (µ t ) = -⟨F (µ t ) -εz(t), μt ⟩ + μt JF (µ t ) μt ≤ -⟨F ε (µ t ), μt ⟩ + μt JF (µ t ) μt (31)
The inequality being a consequence of Lemma A. (a) G is potential.

(b) G is monotone, F is C 1 -smooth, and ∇h is bounded.

Then every solution orbit µ t of (VBRD) converges to Eq ε (G).

Remark.

The assumption that h takes value in [0, 1] is only made for notational convenience and does not incur any loss of generality.

Proof. As before, we treat the potential and monotone cases separately.

Potential case. Let P εt (µ t ) = P (µ t ) -ε t h(µ t ). Then, a calculation similar to the above implies that there exists z(t) ∈ ∂h(µ t ) such that

d dt P εt (µ t ) = ⟨F (µ t ) -ε t z(t), BR εt (µ t ) -µ t ⟩ -εt h(µ t ) ≥ ⟨F εt (µ t ), BR εt (µ t ) -µ t ⟩ -εt h(µ t ) (32)
The inequality being a consequence of Lemma A.1 as it implies that ⟨z(t), BR εt (µ t ) -µ t ⟩ ≤ ⟨ ∇h(µ t ), BR εt (µ t ) -µ t ⟩. By Lemma 2, ⟨F εt (x), BR εt (x) -x⟩ ≥ 0. Since -εt h(µ t ) ≥ 0 we deduce that d dt P εt (µ t ) ≥ 0 and consequently P εt (µ t ) converges. As ε t goes to zero and h(•) is bounded, P (µ t ) converges as well. We will deduce from this that µ t converges to Eq(G). By contradiction, if a limit point µ 0 = lim k µ t k is not in Eq(G) then:

Gap(µ 0 ) = max x ′ ∈X ⟨F (µ 0 ), x ′ -µ 0 ⟩ = ⟨F (µ 0 ), BR(µ 0 ) -µ 0 ⟩ = α > 0. (33)
Recall that, by definition, for all t and µ:

Gap εt (µ) = max x ′ ∈X ⟨F (µ), x ′ -µ⟩ -ε t (h(x ′ ) -h(µ)) = ⟨F (µ), BR εt (µ) -µ⟩ -ε t (h(BR εt (µ)) -h(µ)) = max x ′ ∈X V εt (µ, x ′ ) -V εt (µ, µ). (34)
Also, as h takes values in [0, 1],

|V ε (x, x ′ ) -V ε (x, x) -(V ε ′ (x, x ′ ) -V ε ′ (x, x))| ≤ |ε -ε ′ |. Thus: |Gap εt (µ) -Gap(µ)| ≤ ε t . (35)
As in [START_REF] Kwon | Stratégies de descente miroir pour la minimisation du regret et l'approchabilité[END_REF] one has for all k and s:

d dt P (µ s+t k ) = ⟨F (µ s+t k ), BR εs+t k (µ s+t k ) -µ s+t k ⟩ (36)
Thus, using [START_REF] Mertikopoulos | On the convergence of gradient-like flows with noisy gradient input[END_REF] then [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] we deduce that:

d dt P (µ s+t k ) ≥ Gap εs+t k (µ t k +s ) -ε s+t k ≥ Gap(µ t k +s ) -2ε s+t k . ( 37
)
As the function µ → Gap(µ) is uniformly continuous and t → µ t is Lipschitz, recalling that Gap(µ k ) → α > 0, we deduce that there is δ > 0 and K 1 such that for k ≥ K 1 and all 0 ≤ s ≤ δ one has:

Gap(µ t k +s ) ≥ Gap(µ t k ) -α/4 ≥ 3α/4 (38)
As ε t decreases to 0 there is K 2 such that for all k ≥ K 2 , ε s+t k ≤ α/4. From this, ( 35) and [START_REF] Semen | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF], we obtain that

d dt P (µ s+t k ) ≥ α/2 for all 0 ≤ s ≤ δ, for all k ≥ max(K 1 , K 2 ). Thus P (µ δ+t k ) -P (µ t k ) = δ 0 d dt P (µ s+t k )ds ≥ δα/2,
which contradicts the convergence of P (µ t ).

Monotone case. Using the envelope theorem, and a calculation similar to the above implies that there exists z(t) ∈ ∂h(µ t ) such that

d dt Gap εt (µ t ) = -⟨F (µ t ) -ε t z(t), μt ⟩ + μt JF (µ t ) μt + εt (h(µ t ) -h(BR εt (µ t )) (39a) ≤ -⟨F εt (µ t ), μt ⟩ + μt JF (µ t ) μt + εt (h(µ t ) -h(BR εt (µ t )) (39b) ≤ -⟨F εt (µ t ), μt ⟩ + εt (h(µ t ) -h(BR εt (µ t )) (39c) = -⟨F εt (µ t ), BR εt -µ t ⟩ + εt (h(µ t ) -h(BR εt (µ t )). (39d)
The first inequality is a consequence of Lemma A.1, which implies that ⟨z(t), μt ⟩ ≤ ⟨ ∇h(µ t ), μt ⟩. The second inequality is a consequence of μt JF (µ t ) μt ≤ 0 as G is monotone.

We now proceed to prove that d dt (Gap

εt (µ t ) + ε t ) < 0. Case 1: If Gap εt (µ t ) = 0 then µ t = BR εt (µ t ) = Eq εt (G) thus μt = 0. Then (39a) implies that d dt Gap εt (µ t ) = 0 and thus d dt (Gap εt (µ t ) + ε t ) < 0. Case 2: If Gap εt (µ t ) > 0 then since h(•) ∈ [0, 1]
and εt < 0 we have:

εt (h(µ t ) -h(BR εt (µ t )) ≤ -εt (40)
and from Lemma 2 and (39d) we deduce that d dt (Gap εt (µ t ) + ε t ) < 0. Consequently, Gap εt (µ t ) + ε t converges to δ ≥ 0 and since ε t decreases to zero we conclude that Gap εt (µ t ) → δ. If δ > 0, define:

∆ := -⟨F εt (µ t ), BR εt (µ t ) -µ t ⟩ = -⟨F (µ t ), BR εt (µ t ) -µ t ⟩ + ε t ⟨ ∇h(µ t ), BR εt (µ t ) -µ t ⟩. ( 41
)
We also need to assume the so called "reciprocity' condition which requires that for all x ∈ X and all sequences y n in R A :

Q h (y n ) → x =⇒ F h (x, y n ) → 0 (Rec)
Taken together, (StrCvx) and (Rec) imply that the sequence

x n = Q h (y n ) converges to x ∈ X if and only if F h (x, y n ) → 0.
The terminology "reciprocity" is justified by the fact that, under (Rec), the topology induced by the level sets of the Fenchel coupling becomes equivalent to the ordinary topology on X ; for a precise statement, see Lemma A.2 in Appendix A. This is a subtle -but important -requirement, which is fortunately satisfied by all the standard regularization choices on X , cf. [START_REF] Mertikopoulos | On the convergence of gradient-like flows with noisy gradient input[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF].

We can now state our convergence results for (DAD) when the learning rate is constant.

Theorem 4.4. Let x t be a solution trajectory of (DAD) with constant learning rate η t ≡ 1.

Assume further that one of the following holds:

(a) G is potential and h * is twice differentiable.

(b) G is strictly monotone, and h satisfies (StrCvx) and (Rec).

Then x t converges to Eq(G).

Proof. Again, we treat the potential and monotone cases separately.

Potential case. As y t = t 0 F (x s ) ds and

x t = Q h (y t ) = ∇h * (y t ) we obtain that: ẋt = ⟨F (x t ), ∇ 2 h * (y t )⟩. (51)
Since h * is convex, ∇ 2 h * is semidefinite positive and so:

d dt P (x t ) = ⟨F (x t ), ẋt ⟩ = F (x t )∇ 2 h * (y t )F (x t ) ≥ 0, (52)
the inequality being strict whenever ẋt ̸ = 0. As such, x t converges to Eq(G).

Monotone case.

As G is strictly monotone, Eq(G) is a singleton which coincides with x * the (necessarily unique) GESS of the game. The calculation in [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] gives:

d dt F h (x * , y t ) = ⟨F (x t ), x t -x * ⟩ ≤ 0 (53)
As x * is a GESS d dt F h (x * , y t ) ≤ 0, with equality if and only if

x t = Q h (y t ) = x * . Suppose there is δ > 0 such that ⟨F (x t ), x t -x * ⟩ < -δ < 0 for all t large enough. Then, F h (x * , y t ) goes to -∞ which is impossible because F h (•) ≥ 0. Thus there is t k → ∞ such that ⟨F (x t k ), x t k -x * ⟩ → 0 and so x t k = Q h (y t k ) → x * . By the reciprocity condition (Rec), we deduce that F h (x * , y t k ) → 0 since x * is a GESS. As d dt F h (x * , y t ) ≤ 0 and F h (•) ≥ 0, necessarily F h (x *
, y t ) converges and by the last argument, its limit is zero. Using the strong convexity of h, Lemma 6 implies that x t = Q h (y t ) converges to x * . ■ There are several things to note here. First, the proof of convergence to the unique equilibrium in strictly monotone games (part b of Theorem 4.4) extends to all games with a GESS. Second, the same proof implies that in all games, ESS (if exist) are asymptotically stable under (DAD) with constant learning rate (e.g., the dynamics converges to an ESS if it starts sufficiently close to it). Third, Theorem 4.4 concerns the "day-to-day" evolution of (DAD), not the corresponding empirical mean. Last, the theorem does not apply to monotone games which are not strict.

To complete the picture, the next proposition shows the convergence of the empirical mean to the set of Nash equilibria in all monotone games. Claim 1. η t y t ∈ F ε infinitely often.

Proof. If η t y t / ∈ F ε , then by (Rec), there exists a neighbourhood U(ε) of x * such that x t / ∈ U(ε). By definition of GESS, there is c(ε) > 0 such that ⟨F (x t ),

x t -x * ⟩ < -2c(ε). As ηt η 2 t → 0, there is T 1 (ε) such that for all t ≥ T 1 (ε) we have ηt η 2 t (max h -min h) < c(ε).
Consequently by contradiction to the claim, d dt F h (x * ,ηtyt) ηt < -c(ε) for all t large enough and so

F h (x * ,ηtyt) ηt goes to -∞. Since F h (x * , η t y t ) ≥ 0 this is impossible. § Claim 2. There exists T 2 (ε) ≥ T 1 (ε/2) such that if t ≥ T 2 (ε) and η t y t ∈ F ε then there exists τ > 0 such that η s y s ∈ F ε for all s ∈ [t, t + τ ].
Proof. We need to consider two cases separately:

Case a). If η t y t ∈ F ε/2 then obviously, there is τ > 0 such that η s y s ∈ F ε for all s ∈ [t, t + τ ]. Case b). If η t y t ∈ F ε but η t y t / ∈ F ε/2 then, from claim 1, d dt F h (x * ,ηtyt) ηt < -c(ε/2) < 0.
Thus there exists τ > 0 such that for all s ∈ [t, t + τ ]:

F h (x * ,ηsys) ηs ≤ F h (x * ,ηtyt) ηt . As η t y t ∈ F ε , F h (x * , η t y t ) ≤ ε and since η s ≤ η t , we deduce that F h (x * , η s y s ) ≤ ε. Thus η s y s ∈ F ε for all s ∈ [t, t + τ ]. §
From Claims 1 and 2, there exists t ≥ max(T 2 (ε), T (ε)), such that η t y t belongs to F ε and remains in it forever.

Analysis and results in discrete time

In this section, we continue with the analysis of the discrete-time dynamics presented in Section 3.1, starting with fictitious play and its variants in Section 5.1 before moving on to the dynamics of dual averaging in Section 5.2. 5.1. Fictitious play and regularized fictitious play. The convergence of (FP) and (RFP) can be obtained from the continuous-time analysis of Section 4 using the theory of stochastic approximation [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF][START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF][START_REF] Benaïm | Stochastic approximations and differential inclusions, part II: Applications[END_REF]. Informally, this theory links the asymptotic behavior of differential inclusions of the form ẋt ∈ M (x t ) (58) to the limit sets of discrete-time processes satisfying the basic recursion

X n+1 -X n ∈ γ n+1 M (X n ), (59)
where M : X ⇒ R A is an upper semicontinuous, compact-convex-valued correspondence on X , and γ n > 0 is a vanishing step-size sequence.

In our specific context, the role of M is to be played by the best-reply correspondence BR for (FP), and its regularized variant BR εh for (RFP). Concretely, we have:

Proposition 5.1. Let Xn = (1/n) n k=1 X k , n = 1,
2, . . . , be the empirical frequency of play under a sequence of population states X n ∈ X . Then:

(i ) If X n is generated by (FP), Xn is an asymptotic pseudotrajectory of (BRD). (ii) If X n is generated by (RFP), Xn is an asymptotic pseudotrajectory of (RBRD).

Informally, the notion of an asymptotic pseudotrajectory (APT) means that Xn asymptotically tracks the pseudo-flow of (BRD)/(RBRD) with arbitrary accuracy over windows of arbitrary length; for a precise definition, see Benaïm et In view of this "asymptotic approximation" property, it is plausible to expect that Xn exhibits the same asymptotic behavior as the corresponding continuous-time dynamics. Our next result makes this intuition precise in two classes of games:

(1) Monotone games, i.e., games that satisfy (Mon).

(2) Potential games for which the ε-regularized potential P ε = P -εh, ε ≥ 0, satisifies the Sard-type condition:

P ε (Eq ε (G)) has empty interior. (S ε )
Our main results for (FP) and (RFP) may then be stated as follows:

Theorem 5.1. Suppose that G satisfies (Mon) or (S ε ) for ε = 0. Then the empirical frequency of play Xn under (FP) converges to Eq(G).

Theorem 5.2. Suppose (Diff) holds and G satisfies (Mon) or (S ε ) for some ε > 0. Then the empirical frequency of play Xn under (RFP) converges to Eq ε (G).

Sketch of proof. The proof of Theorems 5.1 and 5.2 follows a similar technical path starting with the fact that Xn is an APT of (BRD) / (RBRD) respectively (cf. Proposition 5.1 above). In both cases, Theorem 4.3 of Benaïm et al. [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF] shows that the accumulation points of an APT lie in an internally chain transitive set of the underlying continuous-time dynamics. 2The claims of Theorem 5.1 may then be proved as follows:

( Finally, for ε > 0, the proof of Theorem 5.2 is entirely analogous, and simply invokes Theorem 4.2 in lieu of Theorem 4.1 in the above chain of implications.

■ 5.2. Dual averaging. We now proceed to state and prove our main convergence result for the recursion (DA). To do so, we will require the "reciprocity" condition (Rec) that was introduced for the study of the continuous-time dynamics (DAD), namely

Q h (y n ) → x =⇒ F h (x, y n ) → 0 (Rec)
for all x ∈ X and all sequences y n in R A . We then have:

Theorem 5.3. Suppose that (DA) is run with a regularizer satisfying (StrCvx) and (Rec), and a vanishing non-increasing learning rate η n ↘ 0 such that

lim n→∞ 1 η n - 1 η n-1 = 0. (60)
Then:

• If x * is a GESS of G, the sequence of population states X n converges to x * .

• If x * is an ESS of G, the same conclusion holds provided that max{η n , η -1 n -η -1 n-1 } is small enough and (DA) is initialized sufficiently close to x * . Corollary 5.1. Suppose that G is strictly monotone and (DA) is run with a regularizer satisfying (StrCvx) and (Rec), and a learning rate of the form η n ∝ 1/n p for p ∈ (0, 1). Then the sequence of population states induced by (DA) converges to the (necessarily unique) equilibrium of G.

Our proof relies on the use of a suitable "energy inequality", provided here by a deflated variant of the Fenchel coupling: Lemma 8. Fix a population state x ∈ X , and let

E n := 1 η n F h (x, η n S n ) = 1 η n [h(x) -h(X n+1 ) + η n ⟨S n , X n+1 -x⟩], (61)
with S n as in (DA). Then, for all n = 1, 2, . . . , we have:

E n ≤ E n-1 + ⟨F (X n ), X n -x⟩ + [h(x) -min h] δ n + F h (X n , η n-1 S n ) η n-1 , (62)
where δ n = 1/η n -1/η n-1 . If, in addition, h satisfies (StrCvx), we have

E n ≤ E n-1 + ⟨F (X n ), X n -x⟩ + [h(x) -min h] δ n + η n-1 2K ∥F (X n )∥ 2 * . ( 63
)
Energy inequalities of the form (62) are standard in the analysis of dual averaging schemes, and they go back at least as far as Nesterov [START_REF] Nesterov | Dual extrapolation and its applications to solving variational inequalities and related problems[END_REF][START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF] (who introduced the method). The specific formulation above follows Héliou et al. [START_REF] Héliou | Online non-convex optimization with imperfect feedback[END_REF]Lemma. C.1], so we omit the proof; for a range of similar computations, see Shalev-Shwartz [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF]Lemma 2.20], Kwon [25,p. 42] and Sorin [START_REF] Sylvain Sorin | No-regret algorithms in online learning, games and convex optimization[END_REF]. Now, to move forward with the proof of Theorem 5.3, we will require two complementary arguments. The first is a stability result: we show below that, if X n is sufficiently close to an evolutionarily stable state x * and the method's learning rate is "small enough", then X n+1 remains close to x * . To state this precisely, let F ε = {y ∈ R A : F h (x * , y) ≤ ε} denote the "Fenchel zone" of magnitude ε with respect to x * , and let

D ε = Q h (F ε ) = {x = Q h (y) : y ∈ F ε } denote the image of F ε under Q h .
We then have: Lemma 9. Let x * ∈ ESS(G) and assume that (StrCvx) and (Rec) hold. Then, for all sufficiently small ε > 0, we have the following implication (valid for all n = 1, 2, . . . ): if X n ∈ D ε and max{η n , δ n } is small enough, we also have X n+1 ∈ D ε .

The second component of the proof of Theorem 5.3 is a subsequence extraction argument: if the iterates of (DA) lie in a neighborhood of x * where (ESS) holds, there exists a subsequence of X n that converges to x * . Lemma 10. Let x * ∈ ESS(G), let U be the neighborhood of validity of (ESS), and assume further that (StrCvx) and (60) hold. If X n ∈ U for all sufficiently large n, we have lim inf n→∞ ∥X n -x * ∥ = 0.

We prove these two ancillary results below.

Proof of Lemma 9. Let U be the neighborhood whose existence is guaranteed by (ESS), i.e., ⟨F (x), x -x * ⟩ < 0 for all x ∈ U, x ̸ = x * . By the relation between the Fenchel coupling and the ordinary norm topology on X (cf. Lemma A.2 in Appendix A), it follows that D ε ⊆ U if ε is taken small enough; we will assume this to be the case throughout the rest of this proof. Moreover, by (Rec) and the continuity of u, there exists some c ≡ c(ε) such that

⟨F (x), x -x * ⟩ ≤ -c < 0 for all x ∈ D ε \ D ε/2 .
With all this in hand, assume that X n ∈ D ε ; we will show that X n+1 ∈ D ε provided that max{η n , δ n } is small enough. To do so, let F n = F h (x * , η n S n ); then, by substituting x ← x * in the template inequality (63) of Lemma 8, we obtain:

Case 1. If X n ∈ D ε \ D ε/2 , then F n ≤ F n-1 -η n c -δ n H -η n-1 G 2 2K , (64)
where H = max h -min h and G = max x∈X ∥F (x)∥ * . Hence, if δ n ≤ c/(2H) and η n-1 ≤ cK/G 2 , we conclude that F n ≤ F n-1 .

Case 2. If X n ∈ D ε/2 , then

F n ≤ ε 2 + δ n H + η n-1 G 2 2K , (65)
so F n ≤ ε provided that δ n < ε/(4H) and η n-1 ≤ εK/(2G 2 ).

In both cases, we conclude that

X n+1 = Q h (η n S n ) ∈ D ε , as claimed.
■ Proof of Lemma 10. Assume to the contrary that lim inf n→∞ ∥X n -x * ∥ > 0. Then, by assumption, there exist ε > 0 and n 0 ≡ n 0 (ε) such that X n ∈ U and ∥X n -x * ∥ ≥ ε for all n ≥ n 0 . Since x * ∈ ESS(G), there exists a positive constant c > 0 such that ⟨F (X n ), X n -x * ⟩ ≤ -c < 0 for all n ≥ n 0 . With this in mind, substituting x ← x * in the template inequality (63) and telescoping yields

E n ≤ E n0 -c(n -n 0 ) + 1 η n - 1 η n0 H + G 2 2K n k=n0 η k ≤ E n0 + cn 0 -H/n 0 -n c - 1 nη n - 1 n n k=n0 η k . (66)
To proceed, note that the first part of (60) gives

lim n→∞ (1/η n -1/η n-1 ) n -(n -1) = lim n→∞ 1 η n - 1 η n-1 = lim n→∞ δ n = 0, (67)
so lim n→∞ 1/(nη n ) = 0 by the Stolz-Cesàro theorem. By the second part of (60), we also have (1/n) n k=n0 η k = 0. Hence, by letting n → ∞ in (66), we get lim n→∞ E n = -∞, a contradiction which completes our proof.

■

The proof of our main convergence results follows by a tandem application of the above.

Proof of Theorem 5.3. We consider the two cases separately.

Case 1: x * ∈ GESS(G). Let ε > 0 be arbitrary. By (60), it follows that lim n→∞ η n = lim n→∞ δ n = 0, and, by Lemma 10, there exists a subsequence X n k of X n converging to x * . This means that, in the long run, η n and δ n become arbitrarily small, and X n comes arbitrarily close to x * . Hence, by applying Lemma 9 inductively, we conclude that X n ∈ D ε for all sufficiently large n. Since ε > 0 has been chosen arbitrarily, this implies that X n converges to x * , as claimed.

Case 2: x * ∈ ESS(G). Let U be the neighborhood whose existence is guaranteed by the evolutionary stability condition (3) for x * . Then, by Lemma 9, if (DA) is initialized sufficiently close to x * and max{η n , δ n } is sufficiently small, we will have X n ∈ U for all n. Hence, by Lemma 10, we conclude that lim inf n→∞ ∥X n -x * ∥ = 0. Our proof then follows by the same inductive application of Lemma 9 as in the case of a GESS above. ■ Time averages under dual averaging. We close this section with a result on the empirical frequency of play under (DA). Indeed, telescoping (62) trivially yields the bound:

n k=1 ⟨F (X k ), x -X k ⟩ ≤ max h -min h η n + 1 2K n k=1 η k-1 ∥F (X k )∥ 2 * . (68)
This regret-type bound echoes standard results in the literature -see e.g., Nesterov [40, Theorem 1] -and leads to the following time-average convergence result:

Proposition 5.2. Suppose that (DA) is run with a regularizer satisfying (StrCvx) and a learning rate of the form η n ∝ 1/ √ n. If G is monotone, the empirical frequency of play Xn under (DA) converges to Eq(G).

The proof of Proposition 5.2 mimics that of Proposition 4.1 so we omit it. We only note that, in contrast to Theorem 5.3, Proposition 5.2 does not require strict monotonicity or reciprocity; however, it concerns the cruder, average frequency of play, so it provides a considerably weaker guarantee in this regard.

Extensions and concluding remarks

In this concluding section, we provide a series of extensions and remarks that would have otherwise disrupted the flow of the rest of our paper. 6.1. Positive correlation. Sandholm [START_REF] William | Potential games with continuous player sets[END_REF] introduced the so-called "positive correlation" condition ẋt ̸ = 0 =⇒ ⟨F (x t ), ẋt ⟩ > 0.

(PC)

In the case of potential games, (PC) implies that

d dt P (x t ) = ⟨F (x t ), ẋt ⟩ > 0 (69)
whenever ẋt ̸ = 0. This in turn implies the convergence of the trajectories to the set of rest points of the dynamics [START_REF] William | Population Games and Evolutionary Dynamics[END_REF]Theorem 7.1.2]. Some of our results in Section 4 for potential games can also be obtained by establishing (PC) for the dynamics under study.

6.2.

No-regret dynamics. Our second remark concerns continuous-or discrete-time processes for which the average regret vanishes, i.e., for all x ∈ X we have:

lim sup t→∞ 1 t t 0 ⟨F (x s ), x -x s ⟩ ds = 0 in continuous time (70a) lim sup n→∞ 1 n n k=1 ⟨F (X k ), x -X k ⟩ = 0 in discrete time (70b)
As we saw in Propositions 4.1 and 5.2, the dynamics of dual averaging have the no-regret property (70) in both continuous and discrete time. Looking more closely at the proofs of Propositions 4.1 and 5.2, we conclude that, in monotone games, the empirical frequency of play under any dynamical process that satisfies (70) converges to the game's set of equilibria. This property forms the basis of many algorithms and dynamics designed to solve variational inequalities and equilibrium problems [START_REF] Semen | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF][START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF][START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF]; the above provides a game-theoretic interpretation of this property in the context of population games.

In this setting, F is monotone (dissipative) if

⟨F (x) -F (x ′ ), x -x ′ ⟩ ≤ 0 for all x, x ′ ∈ X (77)
As in the case of Section 2, we have SVI(X , F ) = MVI(X , F ) if F is monotone; furthermore, mutatis mutandis, all the properties presented in Section 2.3 extend to this general setup. The best-response map associated to F is defined again as

BR(x) = arg max x ′ ∈X ⟨F (x), x ′ ⟩. (78)
In addition to monotonicity, we will also now make the "unique best response" assumption BR(x) is a singleton for all x ∈ X . (U) Proposition 6.1. If F is monotone and (U) holds, the set E := MVI(X , F ) = SVI(X , F ) is a singleton.

Proof. If x, x ′ ∈ E, we have ⟨F (x), x ′ -x⟩ ≤ 0 and ⟨F (x ′ ), x -x ′ ⟩ ≤ 0, so

⟨F (x ′ ) -F (x), x ′ -x⟩ ≥ 0 (79)
implying first ⟨F (x ′ ) -F (x), x ′ -x⟩ = 0 by monotonicity and then ⟨F (x ′ ), x ′ -x⟩ = 0. Thus, x = x ′ by (U).

■

The regularized best response map is likewise defined as BR εh (x) = arg max

x ′ ∈X {⟨F (x), x ′ ⟩ -εh(x ′ )} (80)

where h : X → R satisfies the same axioms as Definition 2.1. Note that BR εh satisfies (U) by construction. Now, using these best-response maps, we may extend the definition of the dynamics (FP), (RFP) and (DA) to the more general setup considered here in the obvious way. We then have: Proposition 6.2. Suppose that (U) holds and let X n , n = 1, 2, . . . , be a sequence of states generated by (FP). If the accumulation points of Xn lie in SVI(X , F ), the same holds for the accumulation points of X n .

Proof. Let x * be an accumulation point of X n+1 = BR( Xn ), and let X n k +1 be a subsequence converging to x * . By descending to a further subsequence if necessary, we may assume without loss of generality that Xn k converges to some limit point x. Furthermore, by the definition of (FP), we have: ⟨F ( Xn k ), X n k +1 -x⟩ = ⟨F ( Xn k ), BR( Xn k ) -x⟩ ≥ 0 for all x ∈ X .

(81)

Hence, taking the limit k → ∞, we get ⟨F (x), x * -x⟩ ≥ 0 for all x ∈ X , (82) so x * ∈ BR(x). Since x ∈ SVI(X , F ) by assumption, we deduce further that x ∈ BR(x). Hence, by (U), we conclude that x = x * , and our assertion follows.

■

Obviously, under (U), a similar property holds for regularized fictitious play.

6.5. Preview for Part II. Part II of our paper [START_REF] Hadikhanloo | Learning in nonatomic games, Part II: Continuous action spaces and mean-field games[END_REF] deals with games with continuous action spaces, in the spirit of Example 6.1 (but with a continuous population of nonatomic players). The first step is to define the Stampacchia variational inequality when A is a compact metric space, Θ is an appropriate compact convex subset of ∆(A), F is a continuous map θ → F θ (•) from Θ to the space of continuous functions on A, and the duality mapping is given by ⟨F θ , ν⟩ = A F θ (α) dν(α) for all θ, ν ∈ Θ.

In this framework, we introduce potential and monotone maps, and we prove the convergence of the discrete-time dynamics of fictitious play.

We show that this study covers the case of nonatomic games with (player-dependent) compact action spaces. Finally, we introduce a class of first-order mean-field games and prove that solutions of the Stampacchia variational inequality correspond to the equilibria of the game in normal form where A is the set of paths generated by the players.

A. Properties of choice maps and the Fenchel coupling

Our aim in this appendix is to provide some useful background and properties for the regularized choice map h and the Fenchel coupling.

To recall the basic setup, we assume below that h is a regularizer on X in the sense of Definition 2.1. The convex conjugate h * : R A → R of h is then defined as where Q : R A → X is the choice map induced by h (cf. Definition 2.1). The lemma below establishes the inverse differentiability property for h, namely that ∂h = Q -1 : Lemma A.1. Let h be a regularizer on X . Then, for all x ∈ X and all y ∈ R A , we have:

x = Q(y) ⇐⇒ y ∈ ∂h(x).

(A.3)

If, in addition, h satisfies (Diff), we also have ⟨∇h(x), x -p⟩ ≤ ⟨y, x -p⟩ (A.4) for all p ∈ X and all y ∈ ∂h(x), x ∈ dom ∂h.

Proof of Lemma A.1. To prove (A.3), note that x solves (A.2) if and only if y -∂h(x) ∋ 0, i.e., if and only if y ∈ ∂h(x).

For the inequality (A.4), it suffices to show it holds for all p ∈ dom ∂h (by continuity). To do so, let ϕ(t) = h(x + t(p -x)) -[h(x) + ⟨y, x + t(p -x)⟩].

(A.5) Since h is strictly convex and y ∈ ∂h(x) by (A.3), it follows that ϕ(t) ≥ 0 with equality if and only if t = 0. Moreover, note that ψ(t) = ⟨∇h(x + t(p -x)) -y, p -x⟩ is a continuous subgradient selection of ϕ. Given that ϕ and ψ are both continuous on [0, 1], it follows a fortiori that ϕ is continuously differentiable and ϕ ′ = ψ on [0, 1]. Thus, with ϕ convex and ϕ(t) ≥ 0 = ϕ(0) for all t ∈ [0, 1], we conclude that ϕ ′ (0) = ⟨∇h(x) -y, p -x⟩ ≥ 0, from which our claim follows.

■

1

 1

4. 1 .Theorem 4 . 1 .

 141 Best reply dynamics. Our first result concerns the best reply dynamics (BRD). Albeit slightly more general, the results of this subsection and the next essentially follow Hofbauer & Sandholm[START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF][START_REF] Hofbauer | Stable games and their dynamics[END_REF]. Suppose that one of the following holds:(a) G is potential. (b) G is monotone and F is C 1 -smooth.

■

  al. [4, Definitions I and 4.1].The proof of Proposition 5.1 follows immediately from the general theory of Benaïm et al. [4, Propositions 1.3, 1.4, and Theorem 4.2], so we do not present it here.

  For games satisfying (Mon), invoke Theorem 4.1 from Section 4 and Theorem 3.23 and Proposition 3.25 of Benaïm et al. [4]. (2) For games satisfying (S ε ) with ε = 0, invoke Theorem 4.1 from Section 4 and Proposition 3.27 of Benaïm et al. [4].

h

  * (y) = max x∈X {⟨y, x⟩ -h(x)}. (A.1)Since X is compact and h is strictly convex and continuous on X , the maximum in (A.1) is attained at a unique point in X , so h * (y) is finite for all y ∈ R A [1]. Moreover, by standard results in convex analysis [42, Chap. 26], h * is differentiable on R A and its gradient satisfies the identity ∇h * (y) = arg max x∈X {⟨y, x⟩ -h(x)} = Q(y) (A.2)

An internally chain transitive set is a compact invariant set that contains no proper attractors[START_REF] Cameron | Isolated Invariant Set and the Morse Index[END_REF].

Acknowledgments

The authors acknowledge support by the COST Action CA16228 "European Network for Game Theory" (GAMENET), the FMJH Program PGMO under grant Damper, and the French National Research Agency (ANR) in the framework of the "Investissements d'avenir" program (ANR-15-IDEX-02), the LabEx PERSYVAL (ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and the grants ORACLESS (ANR-16-CE33-0004) and ALIAS (ANR-19-CE48-0018-01).

From [START_REF] Mertikopoulos | On the convergence of gradient-like flows with noisy gradient input[END_REF] we further get: ∆ = -Gap εt (µ t ) + ε t (h(µ t ) -h(BR εt (µ t )) + ε t ⟨ ∇h(µ t ), BR εt (µ t ) -µ t ⟩ [START_REF] Tyrrell | Convex Analysis[END_REF] As Gap εt (µ t ) → δ, and by the assumptions, h(•) and ∇h are bounded and ε t decreases to 0, we deduce that for t large enough:

Consequently, for t large enough we deduce from (39d), [START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF] and the last inequality that

which is impossible because Gap εt (µ t ) + ε t ≥ 0. Hence δ = 0 and so µ t converges to Eq(G). Dual averaging dynamics with a constant learning rate. Before stating our main result we establish some useful lemmas. Define the regret associated to a trajectory x t and a reference point x ∈ X as:

Lemma 4. Let x t be a solution trajectory of (DAD). Then:

This is a particular case of a more general bound due to Kwon & Mertikopoulos [START_REF] Kwon | A continuous-time approach to online optimization[END_REF] (see Lemma 7 below). The next more compact proof of this simpler bound follows Bravo & Mertikopoulos [START_REF] Bravo | On the robustness of learning in games with stochastically perturbed payoff observations[END_REF] and Sorin [START_REF] Sylvain Sorin | No-regret algorithms in online learning, games and convex optimization[END_REF].

Proof. Define for x ∈ X and y ∈ R A the Fenchel coupling

By the Fenchel-Young inequality, F h (x, y) ≥ 0. Recall that from ( 8) and (20b)

Consequently, following the reasoning of Sorin [START_REF] Sylvain Sorin | No-regret algorithms in online learning, games and convex optimization[END_REF], we get

Proof. From the previous lemma, for all t > 0 and x ∈ X one has

Letting t → ∞ implies x * ∈ Eq(G), as was to be shown.

■ Lemma 6. If h satisfies (StrCvx), then for all x ∈ X and all sequences y n in R A .

Proof. See Lemma A.2 in the appendix.

■ Proposition 4.1. Let x t = Q h (y t ) be a solution trajectory of (DAD) with constant learning rate η t ≡ 1. If the underlying game is monotone, then µ t = 1 t t 0 x s ds converges to Eq(G). Proof. By Lemma 4 and monotonicity of the game, for all x ∈ X :

and hence

Consequently, µ t converges to MVI(G) which coincides with Eq(G) as the game is monotone. Dual averaging dynamics with a variable learning rate. This subsection extends the results of the previous section on monotone games in two directions: we consider GESSs instead of (strictly) monotone games, and we treat dynamics with a variable learning rate.

Other extensions are also possible, but we do not treat them here. We begin with a technical lemma on the regret incurred by (DAD):

Lemma 7. If x t is a solution trajectory of (DAD) then the regret is bounded as follows:

Consequently, if tη t → ∞ and x t = x * for all t ≥ 0, then x * ∈ Eq(G).

Proof.

Let F ε = {y ∈ R A : F h (x * , y) ≤ ε} denote the "Fenchel zone" of magnitude ε with respect to x * . Then it suffices to show that For all ε > 0, there exists T (ε) > 0 such that η t y t ∈ F ε for all t ≥ T (ε).

(P)

Actually this means that F h (x * , η t y t ) → 0. By (StrCvx), (50) holds and thus x t converges to x * . The proof of (P) follows from the following two claims: 6.3. Extensions. We also note that our results can be extended to the following settings:

(1) If X is a convex compact subset of R A and F : X → R A is a vector field on X , we maintain the same results for convergence to solutions of (SVI) and (MVI); however, the population game interpretation disappears.

(2) This interpretation is recovered in multi-population games: if there are several player populations indexed by i = 1, . . . , N , and if A i denotes the set of pure strategies of the i-th population and u iα :

(3) Our theory can also be extended to normal form games with a finite number of players and smooth concave payoff functions g i , i = 1, . . . , N . In this case, the components of the corresponding vector field are G iα (x) = ∂gi ∂xiα , and the notion of evolutionary stability boils down to that of variational stability; for a detailed treatment, see Sorin & Wan [START_REF] Sorin | Finite composite games: Equilibria and dynamics[END_REF] and Mertikopoulos & Zhou [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF].

6.4. Links with variational inequalities and further extensions. Taking a more general point of view that focuses on the vector field F , we can also consider the following framework that brings to the forefront the associated variational inequalities. Let X i , i = 1, . . . , N be a convex compact subset of a topological vector space V i with dual V * i , write V = i V i and X = i X i , and let F i : X → V * i be a collection of continuous maps, i = 1, . . . , N . Finally, set F (x) = (F 1 (x), . . . , F N (x)) and, as usual, write

for the dual pairing between F (x) ∈ V * = i V * i and z = (z 1 , . . . , z N ) ∈ V := i V i . We may then define SVI(X , F ) as the set of x * ∈ X such that

and MVI(X , F ) as the set of x * ∈ X such that

The counterparts for ESS and GESS may also be defined similarly (though the link with population games is no longer present).

Example 6.1. Consider a strategic game with N players, compact metric strategy spaces A i ⊆ R d and continuous payoff functions u i : A → R, i = 1, . . . , N , with A := j A j .

Introduce the mixed extension of the game as usual: for a probability distribution (mixed strategy profile) χ = (χ 1 , . . . , χ N ) ∈ X with χ i ∈ X i := ∆(A i ), let u i be extended as

Then, introduce

for all χ ′ i ∈ X i = ∆(A i ). In this way, the equilibrium condition for χ * ∈ X becomes

which is again an instance of SVI(X , F ).

♢

Lemma A.2. Let h be a regularizer on X . Then, for all p ∈ X and all y ∈ R A , we have F h (p, y) ≥ 0 with equality if and only if p = Q(y).

(A.6)

If, in addition, if h satisfies (StrCvx), we also have:

Proof. Our first claim is a trivial consequence of the Fenchel-Young inequality and the strict convexity of h. For our second claim, let x = Q(y). Then, by the definition (A.1) of the convex conjugate of h, we have:

Now, since h is K-strongly convex, we also have: ■ By virtue of this lemma, we obtain the following convergence criterion in terms of the Fenchel coupling:

Corollary A.1. Let h be a regularizer on X satisfying (StrCvx), fix a base point p ∈ X , and let y n be a sequence in R A . Then, if F h (p, y n ) → 0, we also have Q(y n ) → p.

Proof. By Lemma A.2, we have ∥Q(y n ) -p∥ ≤ (2/K)F h (p, y n ), so our claim follows. ■