# Learning Correlated Equilibria in Mean-Field Games

Paul Muller111DeepMind Paris and London. Corresponding author:
<EMAIL_ADDRESS>Romuald Elie††footnotemark:  Mark Rowland††footnotemark:
Mathieu Lauriere222Google Research, Brain Team 333NYU Shanghai Julien
Perolat††footnotemark:  Sarah Perrin444Inria Scool Matthieu
Geist††footnotemark:  Georgios Piliouras††footnotemark:  Olivier
Pietquin††footnotemark:  Karl Tuyls††footnotemark:

###### Abstract

The designs of many large-scale systems today, from traffic routing
environments to smart grids, rely on game-theoretic equilibrium concepts.
However, as the size of an $N$-player game typically grows exponentially with
$N$, standard game theoretic analysis becomes effectively infeasible beyond a
low number of players. Recent approaches have gone around this limitation by
instead considering Mean-Field games, an approximation of anonymous $N$-player
games, where the number of players is infinite and the population’s state
distribution, instead of every individual player’s state, is the object of
interest. The practical computability of Mean-Field Nash equilibria, the most
studied Mean-Field equilibrium to date, however, typically depends on
beneficial non-generic structural properties such as monotonicity [61] or
contraction properties [43], which are required for known algorithms to
converge. In this work, we provide an alternative route for studying Mean-
Field games, by developing the concepts of Mean-Field correlated and coarse-
correlated equilibria. We show that they can be efficiently learnt in _all
games_ , without requiring any additional assumption on the structure of the
game, using three classical algorithms. Furthermore, we establish
correspondences between our notions and those already present in the
literature, derive optimality bounds for the Mean-Field - $N$-player
transition, and empirically demonstrate the convergence of these algorithms on
simple games.

Keywords— Mean Field Games, Correlated equilibrium, Coarse Correlated
equilibrium, Regret minimization

###### Contents

  1. 1 Introduction
  2. 2 A Small Detour Through $N$-Player Games
    1. 2.1 Notions and Intuitions of Equilibria in $N$-Player Games
    2. 2.2 The Special Case of Symmetric-Anonymous $N$-Player Games
  3. 3 Notions of Mean Field Equilibrium
    1. 3.1 Mean Field Nash Equilibrium
    2. 3.2 Intuition on Correlation Device and Correlated Equilibria
    3. 3.3 Mean-Field Correlation Device
    4. 3.4 Mean-Field Correlated Equilibrium
    5. 3.5 Mean-Field Coarse Correlated Equilibrium
    6. 3.6 Equilibrium Sets Visualization in a Toy Example
  4. 4 Properties of Mean Field (Coarse) Correlated Equilibria
    1. 4.1 Relationship Between (Coarse) Correlated Equilibria and Nash Equilibria
    2. 4.2 Existence of (Coarse) Correlated Equilibria
    3. 4.3 Uniqueness of (Coarse) Correlated Equilibria
    4. 4.4 Connection to the Notion of Correlated Equilibrium Derived by Campi and Fischer
    5. 4.5 Homogeneous Correlated Equilibrium Characterization
  5. 5 Connections Between $N$-Player and Mean-Field Equilibria
    1. 5.1 Mean-Field Games to $N$-Player Games
    2. 5.2 $N$-Player to Mean-Field Equilibria
    3. 5.3 Mean-Field Equilibria in $N$-Player Games
  6. 6 Regret Minimization and Empirical Play
    1. 6.1 Empirical Play
    2. 6.2 External Regret and Coarse Correlated Equilibria
    3. 6.3 Swap Regret and Correlated Equilibria
  7. 7 Learning Weak Equilibria in Mean Field Games
    1. 7.1 Mean-Field Joint Fictitious Play
    2. 7.2 Mean-Field Online Mirror Descent
    3. 7.3 Mean-Field PSRO and Derived Algorithms
  8. 8 Experimental Results
    1. 8.1 Games of Interest
    2. 8.2 Online Mirror Descent
    3. 8.3 Joint Fictitious Play
    4. 8.4 Mean-Field PSRO
  9. 9 Conclusion
  10. A Equilibrium equivalence in N-player games - Theorem 1
  11. B Proof of Existence of (Coarse) Correlated Equilibria
  12. C Proofs on N-player Optimality
    1. C.1 Useful lemmas
    2. C.2 Proof of Theorem 24
    3. C.3 Proof of Theorem 25
  13. D Online Mirror Descent No-regret Proof

##  1 Introduction

The complexity of describing and computing equilibria in games with a finite
number of players grows exponentially as the size of the population
increases555To see this, picture a M-action $N$-player game. The payoff tensor
of a such game is of size $N\,M^{N}$, a quantity exponential in $N$. Assuming
that this game is such that its Nash equilibrium is fully mixed, thus
computing the Nash equilibrium will require going through every payoff tensor
cell at least once, hence leading to an at least exponential relationship
between equilibrium computation time and number of players.. Such computations
are however extremely useful in many different fields: traffic routing [35,
95, 74], energy management [77, 90, 6, 97, 37, 64, 98], mechanism-design [75,
11], among many others. Computation is hampered by, among others, the need to
consider every individual player’s states and actions. The joint player state
space complexity thus grows combinatorially, the difficulty being akin to
producing an exact simulation of an $N$ particle system - easy for low $N$,
impossible for high $N$. In such context, taking insight from statistical
physics, we focus directly on the distribution of the population of particles
instead of simulating every one of them, and thus consider _Mean-Field games_.

Mean-Field games (MFGs) have been introduced to simplify the analysis of Nash
equilibria in games with a very large number of identical players interacting
in a symmetric fashion (i.e., through the distribution of all the players).
The key idea is to solely focus on the interactions between a representative
infinitesimal player and a (so-called Mean-Field) term capturing the effect of
the population of players. Understanding the behavior of one typical player is
enough, as the behavior of the whole population can be deduced from it, since
all players are assumed to be identical. This approach circumvents the
difficulties induced by representing an extremely large population of agents.
Since their introduction by Lasry and Lions [61], and Caines, Huang and
Malhamé [51], MFGs have been extensively studied both from a theoretical and a
numerical viewpoint [21, 10, 25, 26, 2]. Applications in various fields such
as energy management [73, 66, 32], financial markets [28, 24, 42],
macroeconomics [42, 40, 5], vehicle routing [92, 47, 32], mechanism design
[56, 52, 33] or epidemics dynamics [62, 83, 17, 9] have already been
considered. Most of the literature focuses on stochastic differential games
and characterize their solution via the consideration of partial differential
or stochastic differential equations [21, 10, 25, 26]. A forward equation
captures the full population dynamics, while a backward one represents the
evolution of the value function for a representative agent. With few
exceptions, such as in [58] which considers a class of closed-loop controls
with a common signal or in [30, 20] which considers correlated equilibria as
we explain below, only pure or mixed Nash equilibria have been considered so
far. This is in stark contrast with the panoply of alternative notions of
equilibria considered for games with a finite number of players [15, 69, 70,
8, 93, 94, 79, 3, 36, 84]. In the context of MFGs, mixed Nash equilibria with
relaxed controls have been studied in [57, 27]. For example, mixed controls
arise naturally in the context of MFG with optimal stopping where players
should avoid simultaneous actions, as studied by Bertuci [12] or Bouveret et
al. [16]. Moreover, mixed policies are commonly considered in the setting of
reinforcement learning for MFG, see for example [43, 82, 4]. More generally
the question of learning equilibria in MFGs has gained momentum in the past
few years [45, 22, 81, 2, 82, 44].

Studying and understanding learning behaviors in games has been a problem of
fundamental importance within traditional game theory. Shortly after Von
Neumann’s seminal work on the existence and effective uniqueness of equilibria
in zero-sum games via his minimax theorem [93, 94], Brown and Robinson [18,
85] developed the first learning procedures that converge successfully to
equilibrium in zero-sum games in a time-average sense. Unfortunately, this
initial glimmer of hope of general positive results connecting Nash equilibria
and learning took a step backwards when Shapley [89] established that, even in
the case of simple non-zero-sum games learning dynamics, one does not have to
converge to Nash equilibria (even in a time-average sense). This result was a
strong precursor of the evolution of the field with many, increasingly strong,
negative results establishing the lack of any meaningful correlation between
Nash equilibria and learning dynamics [38, 53, 88, 29, 55].

In the face of these persistent failures, a natural follow-up direction has
been to pursue connections between the time-average of learning dynamics and
other weaker game theoretic solutions concepts. The most well known approach
of this type has focused on the tightly coupled notions of correlated
equilibria (CE) [7] and coarse correlated equilibria (CCE) [71]. These
solutions concepts are inspired by the possibility for a mediator to provide
correlated advice to each player in regards to which action to pick from a
joint distribution that is common knowledge to all players. Extending such
concepts to MFGs somehow reduces the gap between Mean-Field Control, where a
central coordinator imposes their will on decentralized controllers with no
agency, and Mean-Field Games, where decentralized agents traditionally
manifest their own will with no coordination mechanism. This bridge also
entails the possibility of circumventing Price of Anarchy and Stability issues
[78], i.e., achieving performance guarantees better those possibly by Nash
equilibria, which is an known issue in Mean Field Games [23], by introducing a
way for agents to coordinate their actions. Besides, unlike Nash equilibria,
these solution concepts enjoy an inextricable connection to a wide class of
learning procedures known as no-regret or regret-minimizing dynamics [50, 48,
87]. Specifically, all regret-minimizing dynamics converge in a time-average
sense to coarse correlated equilibria and, vice versa, for any coarse
correlated equilibrium in any game, there exists a tuple of regret-minimizing
dynamics that converge to it [67]. Such notions of equilibria and related
learning mechanisms have surprisingly been so far neglected in the context of
Mean-Field games. Only DeglInnocenti [30] as well as Campi and Fischer [20]
considered the notion of Mean Field correlated equilibria in both static and
dynamic settings. They prove in particular, under suitable conditions and in
the fully discrete (State, Action and Time) setting, that $N$-player CEs
converge to Mean-Field CEs as N tends to infinity.

In contrast, our paper presents another vision of Mean-Field correlated
equilibria (and introduces coarse correlated ones), which we argue is closer
to the one considered in the traditional game theory literature [14, 8, 41],
as well as more intuitive and easier to manipulate. Yet, we are able to
provide equivalence results between our definition and the one in [20] and
focus our attention on relevant properties of these equilibria. In particular,
we draw connections with no-regret learning in a mean-field setting and show
that using a Mean Field Correlated Equilibrium policy in an $N$-player game
generates a $O(1/\sqrt{N})$ approximate Correlated Equilibrium under suitable
conditions. We study Correlated and Coarse Correlated Equilibria for a large
class of Mean Field Games, both in the static and the evolutive settings.
Importantly, this more flexible notion of equilibrium allows to capture the
efficiency of learning mechanisms in Mean Field Games with several Nash
equilibria. Building on the connection with no regret learning, we establish
the convergence of classical learning algorithms for Mean Field Games to
Coarse Correlated Equilibria in settings where no condition ensuring
uniqueness of Nash (monotonicity, contraction property) is available. The
three algorithms that we consider are Online Mirror Descent [81], a variant of
Fictitious Play [22, 82], and Policy Space Response Oracle (PSRO) [59]
(already introduced in [72] and reported here for the sake of completeness).
We summarize the main contributions of the paper as follows:

  * •

We provide the first formulation of coarse correlated equilibrium for Mean
Field Games together with a more convenient one for correlated equilibria in
this setting. Equivalence between our new formulation and the existing
literature [20] is provided.

  * •

We explore properties of our new equilibrium notions and in particular
demonstrate that using a Mean-Field (coarse) correlated equilibrium in
$N$-player games provides an $O(1/\sqrt{N})$ approximate Nash equilibrium.

  * •

We introduce Mean-Field regret minimization and establish the connection
between no-regret and (coarse) correlated equilibria properties.

  * •

For _all games_ in our framework (without requiring _e.g._ monotonicity
conditions), we show the convergence of several learning algorithms towards
approximate Mean-Field coarse-correlated equilibria. Numerical experiments
illustrate this property for Online Mirror Descent [81], a well-suited
modification of Fictitious Play [82] as well as Mean-Field PSRO [72].

The paper is organized as follows. Section 2 revisits the notion of
correlation device for Symmetric anonymous $N$-player games and paves the way
to the intuitive notion of Mean Field (Coarse) Correlated Equilibrium
presented in Section 3. Section 4 links this more intuitive notion to the
existing literature [20] and derives some of its relevant theoretical
properties, such as existence conditions and special cases characterization.
Section 5 deals with the relationship between $N$-player games and Mean-Field
games. It first establishes how to use a mean-field correlated equilibrium in
an $N$-player game and then proves that sequences of $N$-player (coarse)
correlated equilibria converge towards mean-field correlated equilibria with
N, a property adapted from Campi and Fischer [20]. Moreover, it provides
optimality bounds for using Mean-Field (coarse) correlated equilibria in
$N$-player games. The connections between Mean Field (Coarse) Correlated
equilibria and corresponding regret minimization is discussed in Section 6.
Finally, Section 7 establishes the convergence of learning algorithms to
coarse correlated equilibria for general Mean Field Games, which is
illustrated in Section 8.

## Notations

We introduce here the main notations of the paper.

Setting. Given a finite set $\mathcal{Y}$, we denote by $\Delta(\mathcal{Y})$
the set of distributions over $\mathcal{Y}$. To emphasize the difference
between the finite and non-finite cases, if $\mathcal{Y}$ is not finite, we
write $\mathcal{P}(\mathcal{Y})$ the set of distributions over $\mathcal{Y}$.
A game - be it Mean-Field or $N$-player symmetric-anonymous - is a set
$(\mathcal{X},\mathcal{A},r,P,\mu_{0})$ where $\mathcal{X}$ is the finite set
of states, $\mathcal{A}$ is the finite set of actions,
$r:\mathcal{X}\times\mathcal{A}\times\Delta(\mathcal{X})\rightarrow\mathbb{R}$
is a reward function,
$p:\mathcal{X}\times\mathcal{A}\times\Delta(\mathcal{X})\rightarrow\Delta(\mathcal{X})$
is a state transition function and $\mu_{0}\in\Delta(\mathcal{X})$ is an
initial state occupancy measure. The dependence of $r$ and $P$ on an element
of $\Delta(\mathcal{X})$ captures the interaction between the players. It
measures the influence of the full distribution of players over states on the
reward and dynamics of each identical player. This assumption considers that
all players are _anonymous_ , _i.e._ only their state distribution affects
others while their identity is irrelevant; and that the game is _symmetric_ ,
since all players share the same reward and dynamic functions. In an
$N$-player game, we denote by $\mathcal{N}$ the set of players. Note that we
only consider symmetric-anonymous $N$-player games, hence we deviate from the
traditional vision of considering all players’ individual states, to consider
that the other players affect one another only through their empirical
distribution. Finally, since we consider finite games, we name $\mathcal{T}$
the discrete set of times.

Policy. A policy is a mapping
$\bar{\pi}:\mathcal{X}\rightarrow\Delta(\mathcal{A})$, where $\bar{\pi}(x,a)$
represents the probability of playing action $a$ while at state $x$. The set
of such policies is denoted $\bar{\Pi}$. We also consider $\Pi$ the set of
deterministic policies, i.e. of the form: $\forall x\in\mathcal{X},\,\exists
a\in\mathcal{A},\,\pi(x)=\delta_{a}$, or
$\pi(x,a^{\prime})=\mathbf{1}_{\\{a^{\prime}=a\\}}$. The set $\Pi$ of
deterministic policies is _finite_ and its convex hull is the set $\bar{\Pi}$
of all (stochastic) policies. In an $N$-player game, we write $\Pi_{i}$ the
set of policies of player $i$. If the game is symmetric, we write
$\Pi=\Pi_{1}=...=\Pi_{N}$ the common set of policies available to all players.

Payoff. We name $J_{i}$ the expected payoff function for player $i$ :
$J(\pi_{i},\pi_{-i})$ is the expected return for player $i$ when they play
policy $\pi_{i}$ while the population of all other players play the joint
policy $\pi_{-i}$. If $\mu_{i,t}$ is the distribution of player $i$ over
states at time $t\in\mathcal{T}$, and $r^{\pi}_{i,t}$ is their expected reward
vector (One component per state and per time, averaged over actions given
their probability of occurrence following $\pi$) - both given the actions of
other players, then

$J(\pi_{i},\pi_{-i})\,=\;\sum_{t\in\mathcal{T}}\;\langle
r^{\pi}_{i,t},\,\mu_{i,t}\rangle\,.$

where the scalar product between two vectors $x,y\in\mathbb{R}^{N}$ is defined
as $\langle x,y\rangle=\sum\limits_{i=1}^{N}x_{i}y_{i}$.

Policy swap. Finally, we define the set of policy swap functions

$\mathcal{U}_{CE}:=\left\\{u:\Pi\rightarrow\Pi\right\\}\,,\;\mbox{ and
}\;\mathcal{U}_{CCE}:=\left\\{u:\Pi\rightarrow\Pi\mid u\text{ constant
}\right\\}$ (1)

the set of unilateral deviation functions, i.e. the restriction of
$\mathcal{U}_{CE}$ to constant functions. Intuitively, policy swaps which are
defined over deterministic policies, are functions that shift the probability
mass assigned on one policy to another - thereby swapping policies around in a
distribution of play. Note that swaps do not need to be bijective, and can for
example always return the same policy.

##  2 A Small Detour Through $N$-Player Games

By construction, Mean-Field Games identify to the limit of symmetric-anonymous
$N$-player games, when N tends to infinity. Correlated and coarse correlated
equilibria have been widely studied in games with finite number of players
[14, 15, 8, 65, 3, 36, 41]. Hence, we first ground our intuition and formalism
by focusing on the particular case of symmetric-anonymous games with a finite
number of players. We derive new expressions for correlated and coarse
correlated equilibria for these games, paving the way to their straightforward
extension in the Mean-Field setting in Section 3.

Considering (coarse) correlated equilibria removes this issue by letting the
correlation device choose which joint policy to recommend. Note that a
correlation device which only recommends one Nash equilibrium is a correlated
equilibrium. thus correlated equilibria may thus be used to solve the
equilibrium selection problem.

###  2.1 Notions and Intuitions of Equilibria in $N$-Player Games

For sake of completeness, we first briefly recall the classical notions of
Nash [76], correlated and coarse correlated [7] equilibria in $N$-player
games.

######  Definition 1 ($N$-Player Nash Equilibrium).

Given $\epsilon>0$, we define an $\epsilon$-Nash Equilibrium
$(\pi_{1},\ldots,\pi_{n})\in\bar{\Pi}_{1}\times\dots\times\bar{\Pi}_{N}$ as an
$n$-tuple of strategies such that

$\max_{\pi^{\prime}_{i}\in\Pi_{i}}J_{i}(\pi^{\prime}_{i},\pi_{-i})-J_{i}(\pi_{i},\pi_{-i})\leq\epsilon\,,\qquad\forall
i\in\mathcal{N}.$

We will call a Nash _pure_ if ever it is deterministic. Otherwise, we will
call it _mixed_.

Contrarily to Nash Equilibria, where players choose separately which policy to
follow, correlated and coarse correlated equilibria must be implemented with
an additional entity atop the game whose only purpose is to coordinate agents’
behaviors. It does so by selecting a joint strategy for the full population of
players, and then recommends each player their policy within the joint
strategy. Each player is aware of their own recommended policy together with
the joint distribution over the population, but does not know the
recommendation given to every other player: from a joint policy $\pi$, a
player $i$ only sees $\pi_{i}$.

The goal of the additional entity, termed a _correlation device_ , is to
render their recommendations stable in the presence of payoff maximizing
player. That is, given a policy recommendation, and given knowledge of the
probability distribution over the joint policies recommended by the
correlation device, does the player have an incentive to deviate and play
something else? If the answer is negative, the correlation device is a
correlated equilibrium:

######  Definition 2 ($N$-player $\epsilon$-Correlated Equilibrium).

Given $\epsilon>0$, we define an $\epsilon$-Correlated Equilibrium
$\rho\in\Delta(\Pi_{1}\times\dots\times\Pi_{N})$ as a distribution over joint
strategies such that

$\mathbb{E}_{\pi\sim\rho}\left[J_{i}(u(\pi_{i}),\pi_{-i})-J_{i}(\pi_{i},\pi_{-i})\right]\leq\epsilon\;,\qquad\forall
u\in\mathcal{U}_{CE},\,i\in\mathcal{N}.$

Another question, different from and less restrictive than the correlated
equilibria’s, concerns the player’s ability to _a priori_ find a fixed
deviating policy, independent of their received advice, so that they can
improve their payoff without even taking their own recommendation into
account. If this question’s answer is negative, the correlation device is a
coarse correlated equilibrium:

######  Definition 3 ($N$-player $\epsilon$-Coarse Correlated Equilibrium).

Given $\epsilon>0$, we define an $\epsilon$-Coarse Correlated Equilibrium
$\rho\in\Delta(\Pi_{1}\times\dots\times\Pi_{N})$ as a distribution over joint
strategies such that

$\mathbb{E}_{\pi\sim\rho}\left[J_{i}(u(\pi_{i}),\pi_{-i})-J_{i}(\pi_{i},\pi_{-i})\right]\leq\epsilon\;,\qquad\forall
u\in\mathcal{U}_{CCE},\,i\in\mathcal{N}.$

We see here that correlated and coarse correlated equilibria are very similar,
only differing by the collection of admissible deviation types
$\mathcal{U}_{CE}$ and $\mathcal{U}_{CCE}$ defined in (1). In particular, any
correlated equilibrium is obviously a coarse correlated equilibrium.

We note that the presence of the correlation device helps solving one issue
which plagues Nash equilibria in $N$-player games: the equilibrium selection
problem. Indeed, as mentioned above, Nash equilibria are characterized by all
players acting in a payoff maximizing manner but without coordination. When
several Nash equilibria exist in a game, players must all somehow choose the
same Nash equilibrium to receive any individual optimality guarantee.

This formulation is however too general to provide straightforward definitions
of these equilibria for Mean-Field games: there is no direct, general way to
define a joint strategy over an infinity of unique players, hence neither is
there one for distributions over this space. However, Mean-Field games are a
particular class of infinite player games, i.e. infinite-player symmetric-
anonymous games. In the following section, we provide an equivalent writing of
(coarse) correlated equilibria in this setting which naturally scales to the
Mean-Field limit.

###  2.2 The Special Case of Symmetric-Anonymous $N$-Player Games

We start this section with a remark: we will use interchangeably the terms
_symmetric-anonymous_ and _symmetric_ , because all symmetric games are
anonymous: indeed, take a symmetric game, a given player $i$, and the set of
permutations $\sigma_{i}$ composed of all permutations which do not permutate
$i$. Since the game is symmetric, $i$’s payoff remains identical whatever the
permutation, hence $i$’s payoff is only affected by the number of players
playing a given strategy, but not by their identity. Since this is true for
all players, the game is anonymous. This result is also derived in [46], along
with many other properties of symmetric and anonymous games.

In symmetric-anonymous games, on top of all individual policy sets $\Pi_{i}$
being identical and equal to $\Pi$, the payoff functions must not be impacted
by player identities. Namely, all payoff functions $J_{i}$ are such that, for
any permutation $\tau:[1,N]\rightarrow[1,N]$, we have

$J_{i}(\pi_{1},\dots,\pi_{N})=J_{\tau^{-1}(i)}(\pi_{\tau(1)},\dots,\pi_{\tau(N)})\,,\qquad\pi=(\pi_{1},\dots,\pi_{N})\in\Pi^{N}.$

In other words, the reward for a given player $i$ only depends on player $i$’s
own policy together with the distribution of policies over the population of
all the other players, without any impact from each player identity. This
rewrites analogously as follows: the payoff that player $i$ receives when
playing $\pi_{i}$ only depends on the proportion of other players playing
every policy in $\Pi$.

We therefore introduce the following concept:

######  Definition 4 ($N$-player Population Distribution).

The _Population Distribution_ of N players playing policies in $\Pi$ is
defined as $\nu_{N}=\frac{1}{N}\sum_{\pi}n_{\pi}\delta_{\pi}$, where $n_{\pi}$
is the number of players playing $\pi$, and $\delta_{\pi}$ is a dirac centered
on $\pi$. The set of $N$-player population distributions is written
$\Delta_{N}(\Pi)$.

We will analogously denote $\nu_{-i}\in\Delta_{N-1}(\Pi)$ the distribution
over policies in the population of all players except player $i$. By
construction, in symmetric-anonymous $N$-player games, we can express $J_{i}$
as a function that is independent of the specific identity of the current
player $i$, of $i$’s policy and other players’ policy distribution following

$J_{i}(\pi_{i},\pi_{-i})=\mathcal{J}(\pi_{i},\nu_{-i}).$ (2)

When N players sample their policies from $\Delta_{N}(\Pi)$, _i.e._ they
sample from $\nu_{N}\in\Delta(\Pi)\cap\Delta_{N}(\Pi)$ as a distribution, the
policy distribution obtained as an outcome of this sample may not match $\nu$
anymore. To guarantee that this remains the case, and that no asymmetry exists
between players when sampling from members of $\Delta_{N}(\Pi)$, we define a
new notion of sampling:

######  Definition 5 (Symmetric sampling from $\Delta_{N}(\Pi)$).

When $N$ players sample from $\nu_{N}\in\Delta_{N}(\Pi)$, they are
_symmetrically_ assigned a policy from $\nu_{N}$ such that their population
distribution is equal to $\nu_{N}$. The symmetrical assignment is such that
the sampling distribution is invariant to player permutation.

We remark that sampling from $\Delta_{N}(\Pi)$ is akin to an assignment. This
new sampling definition will guarantee that our new correlated equilibrium
concept is symmetric.

Finally, we need to define the concept of population recommenders, which
recommend different population distributions to the players:

######  Definition 6 (Population Recommenders).

A population recommender $\rho$ is a distribution over population
distributions, _i.e._ $\rho\in\Delta(\Delta_{N}(\Pi))$. A population
distribution sampled by a population recommender is also called a _population
recommendation_.

With these definitions introduced, we are in a position to rewrite both (C)CE
definitions 2 and 3 for a representative player $i$.

######  Definition 7 ($N$-player Symmetric-Anonymous
$\epsilon$-(Coarse)-Correlated Equilibrium).

We define a symmetric-anonymous $\epsilon$-(coarse)-correlated equilibrium
$\rho$ as a distribution in $\Delta(\Delta_{N}(\Pi))$ such that $\forall
i,\forall u\in\mathcal{U}_{(C)CE}$,

$\mathbb{E}_{\nu\sim\rho,\,\pi_{i}\sim\nu}\left[\mathcal{J}(u(\pi_{i}),\nu_{-i})-\mathcal{J}(\pi_{i},\nu_{-i})\right]\leq\epsilon\;.$

By construction, we observe that the correlating device $\rho$ defined above
only samples population distributions $\nu\in\Delta(\Pi)$. Individual players
then receive player-symmetric policy recommendations such that their marginal
policy distribution is equal to $\nu$ in a permutation-invariant way. Hereby,
all such correlated equilibria are symmetric and anonymous, hence their names:
symmetric-anonymous equilibria. Note here that $\nu_{-i}$ is computed
independently of the players’ policy assignments, it is the result of removing
from $\nu$ the policy assigned to player $i$.

We also see that being recommended a given policy does not necessarily imply
knowing which $\nu_{-i}$ was sampled by $\rho$: knowledge of $\rho$ only
allows one to make estimates about others’ expected behavior.

We see below that symmetric-anonymous equilibria are in fact equivalent to
standard equilibria (as in Def. 2 or Def. 3) that are symmetric, _i.e._ that
are in $\Delta_{sym}(\Pi^{N})=\\{\nu\in\Delta(\Pi^{N})\mid\forall\tau\text{
permutation },\,\nu\circ\tau=\nu\\}$ the set of distributions over $\Pi^{N}$
that are invariant to player permutations.

######  Theorem 1 (Equilibrium Equivalence).

In symmetric-anonymous $N$-player games, there is one to one correspondence
between symmetric-anonymous $\epsilon$-(C)CE and $\epsilon$-(C)CE with
symmetric correlating device, i.e. such that $\rho\in\Delta_{sym}(\Pi^{N})$.

The proof of Theorem 1 is located in Appendix A.

We have introduced the concept of Population Policy Distribution, and we
observed that Correlation Devices can be distributions over Population Policy
Distributions. Intuitively, the first concept can easily scale to the Mean-
Field limit by taking $N$ to infinity in $\Delta_{N}(\Pi)$, thus becoming
$\Delta(\Pi)$: intuitively, the ”granularity” of $\Delta_{N}(\Pi)$ is
$\frac{1}{N}$; as $N$ tends to infinity, this ”granularity” tends to 0 and
$\Delta_{N}(\Pi)$ is able to represent an increasing amount of members of
$\Delta(\Pi)$ \- when $N$ is infinite, both sets coincide. The second concept
can be transferred from $\Delta(\Delta_{N}(\Pi))$ to
$\mathcal{P}(\Delta(\Pi))$. In the next section, after initially defining the
Mean-Field setting of interest and recalling what Mean-Field Nash equilibria
are, we define Mean-Field correlated and coarse correlated equilibria in the
same spirit. Section 4 provides an analogue of Theorem 1 by proving that our
new notion of correlated equilibrium is equivalent to the pre-existing ones
established by Campi and Fischer [20].

##  3 Notions of Mean Field Equilibrium

We now describe a general setting, which is able to encompass the
consideration of both static and dynamic Mean-Field games. The state space is
denoted by $\mathcal{X}$. We denote by $\mathcal{T}$ the finite set of times
within the game, so that $\mathcal{T}$ simply reduces to a singleton for
static games. The set of distribution flows
$\Delta(\mathcal{X})^{\mathcal{T}}$ on the state space $\mathcal{X}$ over
times in $\mathcal{T}$ is denoted by $\mathcal{M}$.
Whenever every player in the population follows the policy $\pi\in\Pi$, the
game generates a Mean-Field flow over $\mathcal{X}$ denoted by
$\mu^{\pi}\in\mathcal{M}$. Formally, $\mu^{\pi}$ is defined by

$\mu^{\pi}_{t+1}(x)=\sum_{x_{t}\in\mathcal{X}}\sum_{a\in\mathcal{A}}p(x\mid
x_{t},a,\mu_{t}^{\pi})\,\pi(x_{t},a)\mu_{t}^{\pi}(x_{t})\qquad\forall
t\in\mathcal{T},x\in\mathcal{X}\,,$

with $\mu^{\pi}_{0}=\mu_{0}$ a predefined initial state distribution of the
population.

Given a Mean-Field flow $\mu\in\mathcal{M}$ of the population, the expected
reward of a representative player playing policy $\pi\in\Pi$ is given by

$\displaystyle J(\pi,\mu)$
$\displaystyle=\sum_{t\in\mathcal{T}}\sum_{x,a}r(x,a,\mu_{t})\mu_{t}^{\pi}(x)\pi(x,a)\;=\;\sum_{t\in\mathcal{T}}\langle
r^{\pi}(\cdot,\mu^{\pi}_{t}),\mu^{\pi}_{t}\rangle\;,$

where $\mu^{\pi}$ the expected state distribution of policy $\pi$ when the
population follows the Mean-Field flow $\mu$, and
$r^{\pi}(x,\mu)=\sum_{a}\pi(x,a)r(x,a,\mu)$.

Given a fixed mean-field flow $\mu\in\mathcal{M}$, an individual player can
maximise their expected return by solving the following Markov Decision
Process (MDP) policy optimisation problem

$\sup_{\pi\in\Pi}J(\pi,\mu)\;.$ (3)

Whenever the population of players plays a distribution of strategies
$\nu\in\Delta(\Pi)$, the induced Mean-Field flow over the state space
$\mathcal{X}$ is denoted by

$\mu(\nu)\in\mathcal{M}.$

In the case when the dynamics depend on $\mu$, it is difficult to express
$\mu(\nu)$ in closed form, since policies’ state distributions will interfere
with one another’s state distributions, leading to some potentially very
strong non-linearities. However, in the $\mu$-independent-dynamics case,
$\mu(\nu)$ can be expressed in closed form:

######  Lemma 2 (Closed-form $\mu(\nu)$).

In the $\mu$-independent-dynamics case,

$\mu(\nu)=\sum\limits_{\pi\in\Pi}\nu(\pi)\mu^{\pi}.$

By extension, for $\nu\in\Delta(\Pi)$, we write

$\pi(\nu)$

the stochastic policy defined by sampling, at every initial state of the game,
a policy $\pi\in\Pi$ with probability $\nu(\pi)$, and playing it until the end
of the game. This definition ensures that $\mu^{\pi(\nu)}=\mu(\nu)$ by
definition; however, we note that the set $\\{\pi\mid\mu^{\pi}=\mu(\nu)\\}$
may have more than one element; in degenerate cases where $p$ does not depend
on actions, for example, this set is equal to $\Pi$, as all policies have the
same state distributions. This definition of $\pi(\nu)$ yields a _unique_
policy.

Conversely, given a policy $\bar{\pi}\in\bar{\Pi}$, we write

$\nu_{\bar{\pi}}\in\Delta(\Pi)$

for the distribution such that

$\pi(\nu_{\bar{\pi}})=\bar{\pi}.$

ShopFashion A$r=-\mu(A)$Fashion B$r=-\mu(B)$$A$$B$ Figure 1: Two-Actions
Hipster game.

In the rest of this section, we will examine different types of game theoretic
equilibria. These incorporate a notion of deviation: an equilibrium is only
stable if no player has an incentive to deviate from its recommendations.
These deviations are considered from the point of view of _all_ players.
However, since all players are identical, it is enough to make sure that a
given, randomly chosen player never has an incentive to deviate. If that
player has no incentive to change behavior, then neither does the population.
We will refer to this player as the _representative player_.

###  3.1 Mean Field Nash Equilibrium

The literature on Mean Field Games mostly (and almost only) focused so far on
the notion of Nash equilibrium between the infinite number of agents within
the population. As a generalization of Definition 1, it is naturally defined
as follows:

######  Definition 8 (Mean Field Nash Equilibrium, MFE).

Given $\epsilon>0$, a policy $\bar{\pi}\in\bar{\Pi}$ is an $\epsilon$-Mean
Field Nash Equilibrium whenever

$\displaystyle\sup_{\pi^{\prime}\in\bar{\Pi}}J(\pi^{\prime},\mu^{\bar{\pi}})$
$\displaystyle\leq$ $\displaystyle J(\bar{\pi},\mu^{\bar{\pi}})+\epsilon.$

It is a _Mean Field Nash Equilibrium_ whenever the previous relation holds for
$\epsilon=0$. A Nash equilibrium is said to be _pure_ if it is deterministic.

######  Example 1 (Two-Actions Hipster game).

We give in Figure 1 an example of reward function in the Two-Actions Hipster
Game: the goal for each player is to stand out from their peers by choosing
the clothing item which is least frequent within the population. At a shop,
agents choose either item A or item B, and are penalized for the non-
uniqueness of their choice : if all agents choose Fashion A, Fashion B will
grant the highest reward, and conversely. In this simplistic game, there is no
pure Nash equilibrium, but only one mixed Nash (Agents choose Fashion A or B
with probability $\frac{1}{2}$).

One of the most prominent properties of Mean Field Nash equilibria relies on
their strong connection with equilibria in $N$ player games. We will later, in
Section 5, explain in detail how one can use Mean-Field equilibria in N-player
games. This process is at the core of the usefulness of Mean-Field games,
since plugging a Mean Field Nash equilibrium in an $N$-player game yields an
$\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$-approximate Nash equilibrium,
which is known in the continuous time and continuous space setting in e.g.
[51, 21], and which we prove in this paper for discrete games.

Nevertheless, while the existence of Nash equilibria is a very straightforward
property for MFGs to have, with clear and arguably non-restrictive conditions,
deriving the uniqueness of such equilibria in general is a difficult and
tedious task. One possible approach relies on additional strong Lipschitz
conditions leading to a contracting mapping operator [51]. Alternatively, the
so-called monotonicity condition introduced in [61] intuitively provides
players the incentive to behave differently than the full population and
ensures uniqueness of the Nash Equilibrium. Whenever this well established
condition is not satisfied, uniqueness of Mean Field Nash equilibrium can be
hard to enforce. A natural example for this is the converse of the Hipster
game (presented in Figure 1) as described below.

######  Example 2 (Suits Game).

In the Suit game, rewards are inverted compared to the Hipster game (players
are incentivized to act similarly to others). This game does not satisfy the
monotonicity condition [61] and has 3 Nash equilibria: all-in on Fashion A, B;
or 50% on each.

When the MFE is not unique, one possible option is to help the players
synchronize using an extraneous noise or signal. Restoring uniqueness of MFE
via the addition of vanishing common noise has been onserved in [31].
Alternatively, the addition of a common signal sent to the full population
naturally calls for notions of correlated or coarse correlated equilibria [7,
8]. With the exception of [30, 20], Nash equilibria are surprisingly the only
type of equilibrium considered in the MFG literature. This is in stark
contrast with the literature on $N$-player games, where weaker notions of
equilibria are well established and understood [15, 14, 70, 69, 8, 3, 36, 41].
Specifically, it is understood that there exists a tight correspondence
between no-regret dynamics and coarse correlated equilibria [67]. Moreover,
worst case analysis for Nash equilibria can sometimes automatically be
extended without any further degradation of performance to worst case (coarse)
correlated equilibria via what is known as robust Price of Anarchy analysis
[86].

###  3.2 Intuition on Correlation Device and Correlated Equilibria

We are now in position to generalize the concepts of correlation device and
(coarse) correlated equilibrium to the Mean-Field setting by building on new
formulations derived in Section 2. Before doing so, let first provide relevant
intuitions for these new concepts and facilitate their interpretation.

Correlation Device. A correlation device makes a single policy recommendation
to each player in the game. It coordinates the population’s actions. In the
well-known traffic lights example666In a hypothetical intersection where
traffic laws would not hold., the correlation device sets the lights’ colors,
and lets agents (cars) decide whether to follow or not the lights’ signals.

Coarse-Correlated Equilibrium - Agent’s perspective. From the perspective of
the agent, we can imagine that the correlation device is a mediator who is
partially aligned to the agent’s interests and has a bird’s eye view of what
the population is doing. In a coarse correlated equilibrium, the agent has two
choices: either delegate all decisions to the mediator - despite the partial
misalignment -, or take its own decisions, without the mediator’s knowledge of
what the rest of the population will be doing. If the agent has a larger
incentive to use the services of the mediator on average, then the mediator’s
recommendations may be said to be a coarse correlated equilibrium.

Correlated Equilibrium - Agent’s perspective. Keeping the mediator’s analogy,
in a correlated equilibrium situation, the agent has two choices: accept the
mediator’s suggested course of action, or refuse it and choose their own
course. This case differs from the coarse correlated case by the fact that
here, the agent sees which course of action the mediator has prepared, and,
from it, can estimate what the other agents may be recommended by the
mediator. Having more information - but not as much information as the
mediator -, the agent may therefore take better-informed decisions. However,
if despite this, the agent prefers to follow the mediator’s suggestion, then
the mediator’s recommendations may be said to be a correlated equilibrium777On
a philosophical note, a striking relationship between the concept of
Correlated Equilibrium and that of Manager Efficiency developed by MacIntyre
[63]. We hope to see such philosophical links developed more thoroughly in the
future..

Whenever correlation devices are discrete probability distributions, a
visualization of how correlation devices operate, for the homogeneous (only
one recommended policy to the population) and non-homogeneous (heterogeneous,
several deterministic policies may be recommended at once) cases, are
respectively available in Figures 3 and 2.

###  3.3 Mean-Field Correlation Device

Whenever several Nash equilibria exist, an equilibrium selection problem
arises: the population needs more guidance in order to be able to coordinate
and synchronize. As noted before, in $N$-player games, the notions of
correlated and coarse correlated equilibria bypass this issue through the use
of a correlation device, which provides a signal allowing the population to
synchronize; and so do they in Mean-Field games.

######  Definition 9 (Population distribution/recommendation).

We introduce the following.

  * •

A population distribution, or population recommendation $\nu\in\Delta(\Pi)$ is
a distribution over the set of policies $\Pi$;

  * •

Given a population distribution $\nu\in\Delta(\Pi)$, each player receives an
individual recommendation $\pi\in\Pi$ uniformly sampled from $\nu$, so that
the distribution of all individual recommendations over the population is
$\nu$.

As detailed in Section 3.4 below, correlated equilibria encompass an
information asymmetry component: while the recommender knows the full
population recommendation, the players - the recommendees - only have access
to their own recommendation, which can allow for complex cooperative behavior.
Nevertheless, all players are also aware of the possible population
distributions, together with their probability of occurrences. This
information is contained into what we call correlation devices, whose
definition in the Mean-Field setting is as follows.

$\rho$Correlation
Device…$\nu_{1}$$\rho(\nu_{1})$$\nu_{K}$$\rho(\nu_{K})$Population
Recommendation……$\pi_{1}$$\nu_{1}(\pi_{1})$$\pi_{M}$$\nu_{1}(\pi_{M})$Individual
Recommendation$\pi_{1}$$\nu_{K}(\pi_{1})$$\pi_{M}$$\nu_{K}(\pi_{M})$ Figure 2:
Structure of a discrete Mean-Field correlation device
$\rho\in\mathcal{P}(\Delta(\Pi))$.

######  Definition 10 (Correlation device).

A correlation device is a distribution $\rho$ over $\Delta(\Pi)$. It
encapsulates the possible population recommendations given to the population -
we denote $\mathcal{P}(\Delta(\Pi))$ the set of correlation devices.

A Mean-Field correlation device is a distribution over population
recommendations that synchronizes all individuals in the population. Its
structure is presented in Figure 2. The exogenous recommender picks a
realization of a random variable with distribution
$\rho\in\mathcal{P}(\Delta(\Pi))$ and gives each player its own individual
recommendation $\pi\in\Pi$ as a signal. All players know $\rho$ together with
their own individual recommendation $\pi\in\Pi$, but do not have access to the
population recommendation $\nu\in\Delta(\Pi)$ sampled by the recommender.
Whenever a player receives $\pi\in\Pi$ as recommendation, their belief about
the possible population distributions shifts to $\rho(\cdot\mid\pi)$ defined
by: for $\nu\in\Delta(\Pi)$,

$\displaystyle
d\rho(\nu\mid\pi)\;:=\;\frac{\nu(\pi)d\rho(\nu)}{\int_{\nu^{\prime}\in\Delta(\Pi)}\nu^{\prime}(\pi)d\rho(\nu^{\prime})}.$
(4)

This conditional distribution goes in pair with the distribution $\rho_{\Pi}$
over $\Pi$ induced by the correlation device $\rho\in\mathcal{P}(\Delta(\Pi))$
which is defined by

$\displaystyle\rho_{\Pi}(\pi)$
$\displaystyle:=\int_{\nu\in\Delta(\Pi)}\nu(\pi)d\rho(\nu)\;,$ (5)

so that

$d\rho(\nu)=\sum\limits_{\pi\in\Pi}\rho_{\Pi}(\pi)d\rho(\nu\mid\pi).$

By our definition, agents never observe $\nu$ : the whole stochasticity of the
process resides in the centralized instance, which samples both $\nu$ and a
policy from $\nu$ for each agent. However, we could also imagine that $\rho$
would send $\nu$ to each agent, and lets agents sample their policy from $\nu$
for the duration of an episode. In this case, agents all play the same policy
$\pi(\nu)\in\bar{\Pi}$, and all know what the other agents are playing. We
call such $\rho$, which communicate $\nu$ to the players, _homogeneous
correlation devices_. We note that $\rho$ samples $\nu$ and transfers it to
players, which then play $\pi(\nu)$. We can therefore view $\rho$ as a
distribution over the possible values of $\pi(\nu)$, _i.e._ over $\bar{\Pi}$.
We formalize this notion:

######  Definition 11 (Homogeneous correlation device).

A homogeneous correlation device $\rho_{h}\in\mathcal{P}(\bar{\Pi})$ is a
special type of correlation device that samples stochastic policies, and only
recommends one stochastic policy to all players in the population.

Here is an example of a homogeneous correlation device.

######  Example 3.

Let us consider again the Suits Game, defined in Example 2, in which each
player is incentivized to pick a fashion well represented in the population. A
correlation device alternatively recommending all players to choose Fashion A
and Fashion B (_i.e._ 50% of the time, it recommends Fashion A to all players;
50% of the time, Fashion B) is a homogeneous correlation device, that happens
to generate a Mean-Field correlated equilibrium, as discussed in the next
section.

Intuitively, since all players know what other players are playing, some
homogeneous equilibria should find themselves very restricted. We show that
this is indeed the case in Section 4.5.

$\rho$Correlation
Device…$\nu_{1}$$\rho(\nu_{1})$$\nu_{M}$$\rho(\nu_{M})$Population
Recommendation$\pi(\nu_{1})$Individual Recommendation$\pi(\nu_{M})$ Figure 3:
Structure of a discrete homogeneous Mean-Field correlation device
$\rho\in\mathcal{P}(\Delta(\Pi))$.

###  3.4 Mean-Field Correlated Equilibrium

We now turn to the definition of correlated equilibrium for Mean-Field games,
which is built as a natural extension to the one considered in $N$-player
games. We define Mean-Field correlated equilibria similarly to their anonymous
$N$-player version derived in Definition 7 above.

######  Definition 12 (Mean Field Correlated Equilibrium, MFCE).

Given $\epsilon>0$, a correlation device $\rho$ is an $\epsilon$\- Mean Field
Correlated Equilibrium if, $\forall u\in\mathcal{U}_{CE}$

$\displaystyle\mathbb{E}_{\nu\sim\rho,\,\pi\sim\nu}\left[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))\right]\leq\epsilon\;.$
(6)

It is called Mean Field Correlated Equilibrium whenever the previous relation
holds for $\epsilon=0$.

This definition of Mean Field Correlated equilibrium aligns naturally with the
one developed in the Game theory literature [8]. Besides, we will verify in
Section 4.4 below that it also connects in an elegant fashion to the one
introduced recently in [20].

The next result provides a geometric property of the set of Mean-Field
correlated equilibria.

######  Proposition 3.

For all $\epsilon\geq 0$, the set of $\epsilon$-MFCEs is convex.

###### Proof.

Let $\epsilon\geq 0$, $\rho_{0}$, $\rho_{1}$ be two $\epsilon$-MFCE. Let
$0\leq\alpha\leq 1$ and let $\rho_{\alpha}$ be the barycentric correlation
device $\alpha\rho_{0}+(1-\alpha)\rho_{1}\in\mathcal{P}(\Delta(\Pi))$.

Let $u\in\mathcal{U}_{CE}$.

$\displaystyle\mathbb{E}_{\nu\sim\rho_{\alpha},\,\pi\sim\nu}[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))]$
$\displaystyle=$
$\displaystyle\alpha\mathbb{E}_{\nu\sim\rho_{0},\,\pi\sim\nu}[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))]+(1-\alpha)\mathbb{E}_{\nu\sim\rho_{0},\,\pi\sim\nu}[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))]$
$\displaystyle\leq$ $\displaystyle\epsilon$

∎

The set of correlated equilibria is behaving as we expect. We now turn towards
the set of _homogeneous correlated equilibria_. There is a significant
information difference between correlated equilibria and homogeneous
correlated equilibria: while the former’s agents only observe their own
recommendation, the latter’s observe the full population recommendation. This
means that the deviations they consider will have more granularity than
$\mathcal{U}_{CE}$: each population recommendation will correspond to one
specific deviation, _i.e._ homogeneous correlated equilibria’s deviation
functions are $\mathcal{U}=\\{u\mid u:\bar{\Pi}\rightarrow\bar{\Pi}\\}$. This
concept can be linked with the notion of $\Phi$-regret introduced in Piliouras
et al. [84]. We formally define homogeneous correlated equilibria, given their
deviation set $\mathcal{U}^{h}_{CE}=\\{u\mid
u:\bar{\Pi}\rightarrow\bar{\Pi}\\}$,

######  Definition 13 (Homogeneous Mean Field Correlated Equilibrium, MFCE).

Given $\epsilon>0$, a homogeneous correlation device $\rho$ is an $\epsilon$\-
Homogeneous Mean Field Correlated Equilibrium if,

$\displaystyle\mathbb{E}_{\nu\sim\rho}\left[J(u(\pi(\nu)),\mu(\nu))-J(\pi(\nu),\mu(\nu))\right]\leq\epsilon\qquad\forall
u\in\mathcal{U}^{h}_{CE}.$ (7)

It is called Homogeneous Mean Field Correlated Equilibrium whenever the
previous relation holds for $\epsilon=0$.

###  3.5 Mean-Field Coarse Correlated Equilibrium

In $N$-player games, computing Correlated Equilibria can be very expensive
[70]. Hereby, another set of equilibria, wider and easier to compute, was
introduced in this setting: coarse correlated equilibria. Up to our knowledge,
such notion has never been studied in teh framework of mean Field Games. A
coarse correlated equilibrium is a weaker notion of equilibrium, where each
player may only choose to deviate from their recommendation before having
observed it - though players are still assumed to have knowledge of the
correlation device’s behavior $\rho\in\mathcal{P}(\Delta(\Pi))$. This larger
class of equilibria contains correlated equilibria and is more easily
reachable by classical learning algorithms, as will be discussed in Section 7.

######  Definition 14 (Mean Field Coarse Correlated equilibrium, MFCCE).

Given $\epsilon>0$, a correlation device $\rho$ is an $\epsilon$-Mean-Field
Coarse Correlated Equilibrium if

$\displaystyle\mathbb{E}_{\pi\sim\nu,\nu\sim\rho}\left[J\left(u(\pi),\mu(\nu)\right)-J\left(\pi,\mu(\nu)\right)\right]$
$\displaystyle\leq$ $\displaystyle\epsilon\;,\quad\forall
u\in\mathcal{U}_{CCE}\,.$ (8)

It is a _Mean-Field Coarse Correlated Equilibrium_ whenever the previous
equation holds for $\epsilon=0$.

Recall that $\mathcal{U}_{CCE}$ denotes the set constant deviations over
$\Pi$, i.e. the mappings from $\Pi$ to $\Pi$ which a fixed constant policy
$\pi\in\Pi$. MFCCEs can also be defined in an alternative way.

######  Proposition 4 (MFCCE characterization using best-responses).

A correlation device $\rho$ is an $\epsilon$-MFCCE if and only if,

$\displaystyle\sup_{\pi^{\prime}\in\Pi}\mathbb{E}_{\nu\sim\rho}[J(\pi^{\prime},\mu(\nu))]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\pi\sim\nu,\nu\sim\rho}\left[J(\pi,\mu(\nu))\right]+\epsilon$

###### Proof.

The proof follows from identifying $\Pi$ with
$\\{u(\pi),\,u\in\mathcal{U}_{CCE}\;\mbox{and}\;\pi\in\Pi\\}$. ∎

######  Proposition 5 (MFCEs are MFCCEs).

The set of $\epsilon$-MFCE is included in the set of $\epsilon$-MFCCE.

###### Proof.

This property is a direct implication from the definition of MFCEs and
Proposition 4, when it is noted that
$\mathcal{U}_{CCE}\subseteq\mathcal{U}_{CE}$. ∎

Inclusions between the sets of Nash, correlated and coarse correlated
equilibria are represented in Figure 4. Besides, MFCCEs being much less
restrictive than MFCEs, both sets rarely coincide. However, they can
consistently coincide in very small games.

######  Proposition 6.

In two-action one-state Mean-Field games, the set of MFCEs and MFCCEs are
equal.

###### Proof.

We already know that the set of MFCEs is included in the set of MFCCEs. The
reverse inclusion is proven by observing that in this particular setting,
unilateral deviation to either action is equivalent to deviating when being
recommended the other action - thus being optimal for unilateral deviations is
equivalent to being optimal for per-action deviations.

Note that this does not imply that $\mathcal{U}_{CE}=\mathcal{U}_{CCE}$ \-
indeed, members of $\mathcal{U}_{CE}$ which switch both policies at the same
time can not be members of $\mathcal{U}_{CCE}$. ∎

We note that this does not mean that $U_{CE}=U_{CCE}$ in these settings.
Indeed, a deviation function which switches both actions is a member of
$U_{CE}$ but not of $U_{CCE}$. However, if a payoff stands to be gained by
deviating from one action to another, then it means that the other action is
more profitable in general, and thus that only unilateral deviations towards
it matter.

Just like MFCEs, the set of MFCCEs is also convex:

######  Proposition 7.

For all $\epsilon\geq 0$, the set of $\epsilon$-MFCCE is convex.

###### Proof.

Similar to the one of Proposition 3. ∎

Nash Equilibria Correlated Equilibria Coarse Correlated Equilibria Figure 4:
Visualization of the typical inclusion relationships between equilibrium sets.

The definition of a homogeneous coarse correlated equilibrium is similar to
that of a correlated equilibrium: indeed, coarse correlated equilibrium
deviate before receiving any play information. More formally, with
$\mathcal{U}^{h}_{CCE}=\\{u\mid u:\bar{\Pi}\rightarrow\bar{\Pi},\;u\text{
constant.}\\}$ their deviation set,

######  Definition 15 (Mean Field Coarse Correlated equilibrium, MFCCE).

Given $\epsilon>0$, a homogeneous correlation device $\rho$ is an
$\epsilon$-Homogeneous Mean-Field Coarse Correlated Equilibrium if

$\displaystyle\mathbb{E}_{\pi\sim\nu,\nu\sim\rho}\left[J\left(u(\pi),\mu(\nu)\right)-J\left(\pi,\mu(\nu)\right)\right]$
$\displaystyle\leq$ $\displaystyle\epsilon\;,\quad\forall
u\in\mathcal{U}^{h}_{CCE}\,.$ (9)

It is a _Homogeneous Mean-Field Coarse Correlated Equilibrium_ whenever the
previous equation holds for $\epsilon=0$.

###  3.6 Equilibrium Sets Visualization in a Toy Example

This section ambitions to highlight how vast the set of correlated equilibria
can be in comparison to the set of Nash equilibria, and more strikingly how
vast the set of coarse correlated equilibria is compared to the set of
correlated equilibria. In a word, we illustrate the assertion depicted in
Figure 4:

$\text{ Nash Equilibria }\subseteq\text{ Correlated Equilibria
}\subseteq\text{ Coarse Correlated Equilibria. }$

and evaluate the size of these sets in a simple game.

######  Example 4.

Let consider the following 3-actions (A, B and C) static Mean-Field Dominated-
Action game:

$r(A,\mu)=\mu(A)+\mu(C)\,,\qquad r(B,\mu)=\mu(B)\,,\qquad
r(C,\mu)=\mu(A)+\mu(C)-0.05\,,$

where $\mu(X)$ abusively denotes the proportion of players picking action $X$
in the population (i.e. the state of a player reduces to their action). A
visualization of its Mean-Field Nash, correlated and coarse correlated
equilibria is provided in Figure 5.

In general, visualizing the sets of correlated equilibria is difficult.
Indeed, each correlated equilibrium is a distribution over distribution of
policies. Therefore, a correlated equilibrium is in general composed by
several different mixed policies at once. It is easy to see how to visualize
one such equilibrium, but less obvious how to visualize their set, especially
when the number of such mixed policies may be infinite. However, in our
example, one of the three available actions is dominated: whenever an agent is
recommended to play $C$, they know that they should play $A$ instead!
Correlated equilibria are therefore restricted to recommending either $A$ or
$B$. We know that any mixture between homogeneously recommending $A$ and $B$
to the population yields a CE, so that the set of CEs is the straight line
between $A$ and $B$ in Figure 5.

Visualizing the set of coarse correlated equilibria is much harder, even more
so in this simple game. Indeed, one can recommend action $C$ homogeneously and
still get many coarse correlated equilibria, so we can not use the simplifying
assumption used for CEs. We choose to restrict to the set of homogeneous CCEs,
more precisely, we represent $(\alpha,\,\beta,\gamma)$ such that
$\rho=\alpha\delta_{A}+\beta\delta_{B}+\gamma\delta_{C}$ is a CCE. We observe
in Figure 5 that the set of CCEs is represented by a very large triangle in
the simplex, so that the correlation device can recommend the dominated action
$C$. More strikingly, the set of CCEs reveals to be significantly larger than
the set of CEs and Nash equilibria.

Figure 5: Visualization of Mean-Field Equilibria on the Dominated-Action game.

##  4 Properties of Mean Field (Coarse) Correlated Equilibria

In this section, we investigate several properties of our (coarse) correlated
equilibrium framework. First, in Section 4.1, we detail relationships between
Nash equilibria and (coarse) correlated equilibria. Then, in Section 4.2, we
detail existence conditions for Mean-Field (coarse) correlated equilibria, and
find surprising situations where _no (coarse) correlated equilibrium exists_.
This is mitigated by the existence, for all $\epsilon>0$, of
$\epsilon$-(coarse) correlated equilibria. Then, in Section 4.4, we establish
equivalence between our notion of correlated equilibrium and the one presented
by Campi and Fischer [20], thereby inheriting all their asymptotic properties.
Finally, in Section 4.5, we characterize special properties of homogeneous
Mean-Field correlated equilibria.

###  4.1 Relationship Between (Coarse) Correlated Equilibria and Nash
Equilibria

In 2-player zero-sum games, correlated equilibria are strongly linked to Nash
equilibria: their marginalizations are Nash equilibria; a correlation device
recommending a Nash equilibrium is also a correlated equilibrium, and a
(coarse) correlated equilibrium which only recommends one (possibly
stochastic) joint policy actually recommends a Nash equilibrium !

Mirroring these statements, we first show how any $\epsilon$-Nash equilibrium
can be transformed into an $\epsilon$-correlated equilibrium; then that, given
any $\epsilon$-correlated equilibrium recommending only one $\nu$, $\pi(\nu)$
is an $\epsilon$-Nash equilibrium. Finally, we analyze the question of
(coarse) correlated equilibrium marginalizations, defining what they exactly
are, when they exist, and conditions for them to be Nash equilibria.

####  4.1.1 From Nash Equilibria to Correlated Equilibria

We first start by showing how one can derive Correlated equilibria from Nash
equilibria.

######  Proposition 8 (Nash-derived Correlated Equilibrium).

Every $\epsilon$-Nash equilibrium can be transformed into a Correlated
Equilibrium.

###### Proof.

Let $\pi^{*}\in\bar{\Pi}$ be a Nash equilibrium. We write
$\nu^{*}=\nu_{\pi^{*}}$ for conciseness, and take $\rho=\delta_{\nu^{*}}$.

$\rho$ is an $\epsilon$-correlated equilibrium: if there existed
$u\in\mathcal{U}_{CE}$ such that

$J(u(\pi(\nu^{*})),\mu(\nu^{*}))-J(\pi(\nu^{*}),\mu(\nu^{*}))>\epsilon$

then, since $\pi(\nu^{*})=\pi^{*}$ and $\mu(\nu^{*})=\mu^{\pi^{*}}$, this
would imply that $u(\pi^{*})$ is a policy which has higher value against the
Nash than the Nash policy $\pi^{*}$ plus $\epsilon$, which is strictly
impossible by definition.

Therefore every $\epsilon$-Nash equilibrium can be transformed into an
$\epsilon$-correlated equilibrium. ∎

####  4.1.2 From Coarse Correlated Equilibria to Nash Equilibria

We now examine the converse of the above property - when can we extract an
$\epsilon$-Nash equilibrium from an $\epsilon$-correlated equilibrium ? We
show that this is at least possible when the correlated equilibrium is a
single Dirac:

######  Proposition 9 (Coarse correlated equilibrium-derived Nash
equilibrium).

Assume $\rho=\delta_{\nu}$, with $\nu\in\Delta(\Pi)$, is an $\epsilon$-coarse
correlated equilibrium. Then $\pi(\nu)$ is an $\epsilon$-Nash equilibrium.

###### Proof.

We write the optimality condition of $\rho$ for all $u\in\mathcal{U}_{CCE}$:

$\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))]\leq\epsilon,$

$\mathbb{E}_{\pi\sim\nu}[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))]\leq\epsilon,$

_i.e._ , $\forall\pi^{\prime}\in\Pi$,

$J(\pi^{\prime},\mu(\nu))-\mathbb{E}_{\pi\sim\nu}[J(\pi,\mu(\nu))]\leq\epsilon.$

Finally, we note that
$\mathbb{E}_{\pi\sim\nu}[J(\pi,\mu(\nu))]=J(\pi(\nu),\mu(\nu))$, which
concludes the proof:

$J(\pi^{\prime},\mu(\nu))-J(\pi(\nu),\mu(\nu))\leq\epsilon,$

_i.e._ $\pi(\nu)$ is an $\epsilon$-Nash equilibrium. ∎

We also show that, in certain classes of games, the marginalization - defined
in Definition 16 \- of an $\epsilon$-Mean-Field coarse-correlated equilibrium
yields an $\epsilon$-Nash equilibrium

We first define properly what the marginalization of a correlation device is:

######  Definition 16 (Correlation Device Marginalization).

The marginalization $\hat{\pi}$ of a correlation device $\rho$ is defined as
the policy whose distribution is equal to $\int_{\nu}\mu(\nu)d\rho(\nu)$.

Note that it always exists when the dynamics do not depend on the
distribution:

######  Proposition 10 (Existence of the marginalization).

In games where the dynamics do not depend on the mean field flow, the
marginalization of a correlation device always exists, and is equal to

$\hat{\pi}_{t}(s,a)=\sum_{\pi\in\Pi}\frac{\int_{\nu}\nu(\pi)\mu_{t}^{\pi}(s)d\rho(\nu)}{\sum_{\pi^{\prime}\in\Pi}\int_{\nu^{\prime}}\nu^{\prime}(\pi^{\prime})\mu_{t}^{\pi^{\prime}}(s)d\rho(\nu^{\prime})}\pi(s,a).$

###### Proof.

Let first write the distribution evolution equation for $\hat{\pi}$:

$\mu_{t+1}^{\hat{\pi}}(x)=\sum_{x_{t},a}p(x\mid
x_{t},a)\hat{\pi}(x_{t},a)\mu_{t}^{\hat{\pi}}(x_{t})\,.$

We prove by induction that
$\mu_{t}^{\hat{\pi}}=\int_{\nu}\mu_{t}(\nu)d\rho(\nu)$ for all $t$.

The result holds for $t=0$ since $\mu_{0}$ is fixed. If this is true for $t$,
then

$\displaystyle\mu_{t+1}^{\hat{\pi}}(x)$ $\displaystyle=\sum_{x_{t},a}p(x\mid
x_{t},a)\hat{\pi}(x_{t},a)\mu_{t}^{\hat{\pi}}(x_{t})$
$\displaystyle=\sum_{x_{t},a}p(x\mid
x_{t},a)\int_{\nu^{\prime}}\int_{\nu}\sum_{\pi}\frac{\nu(\pi)\mu_{t}^{\pi}(x_{t})d\rho(\nu)}{\int_{\nu^{\prime}}\mu_{t}(\nu^{\prime})d\rho(\nu^{\prime})}\mu_{t}(\nu^{\prime})\pi(x_{t},a)d\rho(\nu^{\prime})$
$\displaystyle=\int_{\nu}\sum_{\pi}\nu(\pi)\underbrace{\sum_{x_{t},a}p(x\mid
x_{t},a)\mu_{t}^{\pi}(x_{t})\pi(x_{t},a)}_{=\mu_{t+1}^{\pi}(x)}d\rho(\nu)$
$\displaystyle=\int_{\nu}\mu_{t+1}(\nu)(x)d\rho(\nu)\,,$

which concludes the induction argument. ∎

Finally, we will need to define what monotonicity, introduced by Lasry and
Lions [61] is:

######  Definition 17 (Monotonicity).

A mean field game is said to be monotonic if

$\langle\mu-\mu^{\prime},r(\cdot,\mu)-r(\cdot,\mu^{\prime})\rangle\leq
0\,,\forall\mu,\mu^{\prime}\in\mathcal{M}\;.$

We can now present cases where we can link the marginalization of a coarse
correlated equilibrium with its optimality as a Nash equilibrium:

######  Proposition 11.

In monotonic games where the reward function is affine with respect to $\mu$,
the marginalization of an $\epsilon$-Mean-Field-coarse correlated equilibrium,
if it exists, is a $2\epsilon$-Mean-Field-Nash-equilibrium.

###### Proof.

Let $\rho$ be an $\epsilon$-MFCCE, and $\hat{\pi}$ its marginalization. Let
first observe that the monotonicity property implies:

$\langle\mu-\mu^{\prime},r(\cdot,\mu)\rangle\leq\langle\mu-\mu^{\prime},r(\cdot,\mu^{\prime})\rangle\,,\forall\mu,\mu^{\prime}\in\mathcal{M}\;.$
(10)

From there, we compute

$\displaystyle J(\pi,\mu^{\hat{\pi}})-J(\hat{\pi},\mu^{\hat{\pi}})$
$\displaystyle=\langle\mu^{\pi}-\mu^{\hat{\pi}},r(\cdot,\mu^{\hat{\pi}})\rangle$
$\displaystyle=\sum_{\nu}\sum_{\nu^{\prime}}\rho(\nu)\rho(\nu^{\prime})\langle\mu^{\pi}-\mu(\nu),r\left(\cdot,\mu(\nu^{\prime})\right)\rangle$
$\displaystyle=\sum_{\nu}\sum_{\nu^{\prime}}\rho(\nu)\rho(\nu^{\prime})\left(\langle\mu^{\pi}-\mu(\nu^{\prime}),r\left(\cdot,\mu(\nu^{\prime})\right)\rangle+\langle\mu(\nu^{\prime})-\mu(\nu),r\left(\cdot,\mu(\nu^{\prime})\right)\rangle\right)$
$\displaystyle\leq\sum_{\nu}\sum_{\nu^{\prime}}\rho(\nu)\rho(\nu^{\prime})\left(\epsilon+\langle\mu(\nu^{\prime})-\mu(\nu),r\left(\cdot,\mu(\nu^{\prime})\right)\rangle\right)$
$\displaystyle\leq\sum_{\nu}\sum_{\nu^{\prime}}\rho(\nu)\rho(\nu^{\prime})\left(\epsilon+\langle\mu(\nu^{\prime})-\mu(\nu),r\left(\cdot,\mu(\nu)\right)\rangle\right)$
$\displaystyle\leq 2\epsilon$

where the second line comes from the affine character of $r$ with respect to
$\mu$, and $\hat{\pi}$ being the marginalization of $\rho$; the third and
fifth lines come from $\rho$ being $\epsilon$-optimal, and the fourth line
comes from Equation 10. ∎

######  Remark 1 (Translation-invariance).

We note that the above property also holds if a state-independent dependency
on $\mu$ is added to the reward function.

######  Remark 2 (Extension to $\epsilon$-monotonicity).

If the game is $\epsilon^{\prime}$-quasi-monotonic, i.e.

$\langle\mu-\mu^{\prime},r(\cdot,\mu)-r(\cdot,\mu^{\prime})\rangle\leq\epsilon^{\prime}\,,\forall\mu,\mu^{\prime}\in\mathcal{M}\;,$

then the marginalization of an $\epsilon$-MFCCE, if it exists, is a
$(2\epsilon+\epsilon^{\prime})$-MFE.

######  Remark 3 (On the non existence of marginalization in distribution-
dependent settings).

Consider the hole-trap game depicted in Figure 6. In this game, one initially
chooses between going left or right. Once in the Left or Right node, the next
state does not depend on the players’ actions anymore: if every player is in
the current node, then it transitions to its $+$ version (Left+ or Right+),
otherwise all players are sent to the hole.

Taking a reward structure which makes Left+ and Right+ equivalent, and the
Hole node very penalizing, we can take a Mean-Field Coarse Correlated
Equilibrium which alternatively selects between Left and Right 50% of the
time.

Its marginalized policy is a policy for which 50% of players ends up in Left+
and 50% of players ends up in Right+. However, this is strictly impossible, as
this requires that 50% of players be on the Left and Right nodes, which would
automatically send all players to the hole, and none to Right+ and Left+. The
marginalization of this correlated equilibrium is therefore impossible.

StartLeftRightLeft+HoleRight+$L$$R$$\mu=1$$\mu<1$$\mu=1$$\mu<1$ Figure 6:
Hole-trap game

###  4.2 Existence of (Coarse) Correlated Equilibria

We have not yet established conditions for correlated equilibria to exist. A
set of conditions can be derived immediately from the fact that Nash
equilibria can be used as correlated equilibria, as we proved in Proposition
8. Existence conditions for Nash equilibria, namely, continuity of the reward
and dynamics functions with respect to $\mu$, hence also imply existence of
correlated equilibria. Perhaps surprisingly, we find that the famous result
derived by Hart and Schmeidler [49] that correlated equilibria (and therefore
coarse correlated equilibria) exist in _all finite $N$-player games_ (_i.e._
$N$-player games with finite $\mathcal{S}$, $\mathcal{A}$ and $\mathcal{T}$
but not necessarily with continuous reward and or dynamic functions) does not
hold in Mean-Field games: Example 5 shows a game where no exact correlated
equilibrium exists. We summarize the existence relationships between different
Mean-Field equilibria in Figure 7, and visually represent them in Figure 4.

MF-Nash
$\overset{\text{\normalsize$\overset{*}{\implies}$}}{\underset{\dagger}{\centernot\impliedby}}$
MF-CE
$\overset{\text{\normalsize$\overset{**}{\implies}$}}{\underset{\dagger\dagger}{\centernot\impliedby}}$
MF-CCE

$*$ : Proposition 8. $**$ : Proposition 5. $\dagger$ : Example 6.
$\dagger\dagger$ : Example 7
---

Figure 7: Existence relationship between equilibrium concepts. $A\implies B$
means that the existence of $A$ implies the existence of $B$; whereas
$A\centernot\impliedby B$ means that the existence of $B$ does not imply the
existence of $A$.

######  Remark 4.

Note that deriving a Mean-Field version of Hart and Schmeidler [49]’s proof of
existence in the case of infinite players remains an open problem, due in part
to the Mean-Field assumption that any finite set of players changing their
policies would have no impact at all on the Mean-Field reward function - but
Hart and Schmeidler [49]’s proof relies precisely on the fact that this isn’t
the case in their framework.

We begin by the following proposition, which will be the core argument for the
existence proof.

With Proposition 8 proven, we know that if the game admits a Nash equilibrium,
then it admits a correlated equilibrium. Therefore, for correlated equilibria
to exist, it suffices that Nash equilibria exist. A sufficient condition for
their existence is the continuity of $r$ with respect to $\mu$. This has been
proven in a very similar setting by [72], for what they call a _restricted
game_. We straightforwardly adapt here their argument to our setting to prove
Theorem 12, whose proof is postponed to Appendix B.

######  Theorem 12 ((Coarse) Correlated equilibrium existence).

If the reward function $r$ and the dynamics kernel function $p$ are continuous
with respect to $\mu$, then the game admits at least one (coarse) correlated
equilibrium.

Finally, we address the question of whether (coarse) correlated equilibria are
always guaranteed to exist for Mean-Field games with finite state and action
spaces. Theorem 12 has already established the existence of such equilibria
when the reward function $r$ is continuous in the population distribution
$\mu$. The following example illustrates that equilibria do not necessarily
exist when this continuity assumption does not hold, by highlighting a game
where neither correlated nor coarse correlated equilibria exist !

######  Example 5 (Reward for the few).

We consider a stateless Mean-Field game with two actions, $a$ and $b$. The
reward function is set up so as to reward the players who select the least
popular action. More precisely, letting $\mu\in\mathscr{P}(\\{a,b\\})$ denote
the population distribution over actions, we define

$\displaystyle r(a,\mu)=\begin{cases}1&\text{ if
}\mu(a)<\nicefrac{{1}}{{2}}\\\ 0&\text{ if }\mu(a)=\nicefrac{{1}}{{2}}\\\
0&\text{ if }\mu(a)>\nicefrac{{1}}{{2}}\end{cases}\,,\quad
r(b,\mu)=\begin{cases}0&\text{ if }\mu(a)<\nicefrac{{1}}{{2}}\\\ 1&\text{ if
}\mu(a)=\nicefrac{{1}}{{2}}\\\ 1&\text{ if
}\mu(a)>\nicefrac{{1}}{{2}}\end{cases}\,,$

noting that in the case where the population is evenly split between actions
$a$ and $b$, the players taking action $b$ are the one who are rewarded. Note
that this payoff function is not continuous at
$\mu=\nicefrac{{1}}{{2}}\delta_{a}+\nicefrac{{1}}{{2}}\delta_{b}$. Now,
suppose $\rho$ is the correlation device of a coarse correlated equilibrium.
The expected return of a representative player accepting the recommendation
generated by this correlation device is

$\displaystyle\int\left(\nu(a)\mathbbm{1}_{\\{\nu(a)<\nicefrac{{1}}{{2}}\\}}+\nu(b)\mathbbm{1}_{\\{\nu(a)>\nicefrac{{1}}{{2}}\\}}+\frac{1}{2}\mathbbm{1}_{\\{\nu(a)=\nicefrac{{1}}{{2}}\\}}\right)\rho(\mathrm{d}\nu)=\int\min(\nu(a),\nu(b))\rho(\mathrm{d}\nu)\,.$

Now, the expected reward of a player that decides to deviate to action $a$
before seeing the recommendation generated by the correlation device is
$\int\mathbbm{1}\\{\nu(a)<\nicefrac{{1}}{{2}}\\}\rho(\mathrm{d}\nu)$ , and
similarly the expected reward for deviating to $b$ is
$\int\mathbbm{1}\\{\nu(a)\geq\nicefrac{{1}}{{2}}\\}\rho(\mathrm{d}\nu)$.

In order for $\rho$ to encode a coarse correlated equilibrium, it must be the
case that these expected rewards under deviation from the recommended play are
no greater than the expected reward when following the recommendation:

$\displaystyle\int\mathbbm{1}\\{\nu(a)<\nicefrac{{1}}{{2}}\\}\rho(\mathrm{d}\nu)\,,\int\mathbbm{1}\\{\nu(a)\geq\nicefrac{{1}}{{2}}\\}\rho(\mathrm{d}\nu)\leq\int\min(\nu(a),\nu(b))\rho(\mathrm{d}\nu)\,.$

However, adding these two inequalities yields

$\displaystyle 1\leq\int 2\min(\nu(a),\nu(b))\rho(\mathrm{d}\nu)\,.$

Since $2\min(\nu(a),\nu(b))\leq 1$, this inequality can only hold if
$\nu(a)=\nu(b)$ $\rho$-almost surely, meaning that
$\rho(\nicefrac{{1}}{{2}}\delta_{a}+\nicefrac{{1}}{{2}}\delta_{b})=1$.
However, this is clearly not a coarse correlated equilibrium, since an
individual player benefits from deviating to $b$ in this case.

We conclude no coarse correlated equilibrium (and hence no correlated
equilibrium nor Nash equilibrium) exist for this Mean-Field game.

However, the following example below mitigates the previous one, by showing a
game where, despite the lack of existence of Nash equilibria, correlated and
coarse correlated equilibria do exist.

######  Example 6 (Existence of Mean-Field games with a CE and a CCE but no
Nash equilibrium.).

Consider a Mean-Field variant of rock-paper-scissors. If there are at least
two distinct actions in the population distribution, then rock wins, and
scissor loses most. If there is only a single action taken in the population,
then the payoffs to each individual player are as in the standard game. More
precisely, when $\mu\in\mathscr{P}(\\{\text{R},\text{P},\text{S}\\})$ is not a
Dirac, we have

$\displaystyle r(\text{R},\mu)=1\,,r(\text{P},\mu)=-1,\,r(\text{S},\mu)=-3\,.$

Moreover, when $\mu$ is a Dirac, say $\delta_{\text{R}}$, we have the usual
payoffs presented to the individual agent:

$\displaystyle
r(\text{R},\delta_{\text{R}})=0\,,r(\text{S},\delta_{\text{R}})=-1\,,r(\text{P},\delta_{\text{R}})=1\,.$

Note that this reward function is not continuous at $\mu$ when $\mu$ is a
Dirac. There is no Nash equilibrium in this game: a mixed policy $\pi$ cannot
be a Nash equilibrium, since there is benefit in deviating to Rock, and a
Dirac $\pi$ cannot be a Nash equilibrium, since there is benefit to an
individual agent in deviating to the superior action.

Now, we argue that the correlation device $\rho\in\mathcal{P}(\Delta(\Pi))$
given informally by first selecting one of rock, paper, scissors uniformly at
random, and then recommending this action to all players, is a coarse
correlated equilibrium; mathematically, this is given by

$\displaystyle\rho=\nicefrac{{1}}{{3}}\delta_{\delta_{\text{R}}}+\nicefrac{{1}}{{3}}\delta_{\delta_{\text{P}}}+\nicefrac{{1}}{{3}}\delta_{\delta_{\text{S}}}\,.$

The payoff when accepting this recommendation is $0$. The average payoff when
deviating to a fixed action prior to seeing the recommendation is also $0$,
hence we have a CCE. Note this is not a CE, since one can clearly deviate to a
better action after seeing the recommendation.

However, the correlating device which alternates between everyone playing
paper, and half the population playing paper while the other half plays rock
is a mean field correlated equilibrium. More formally,

$\rho=\nicefrac{{1}}{{2}}\delta_{\nicefrac{{1}}{{2}}\delta_{\text{P}}+\nicefrac{{1}}{{2}}\delta_{\text{R}}}+\nicefrac{{1}}{{2}}\delta_{\delta_{\text{P}}}$

is a Mean Field CE. To see this, let us consider each action’s deviation
incentive. When players are recommended to play rock, they always have an
incentive to follow this recommendation. Players are never recommended to play
scissors. Therefore, we must only examine the deviation payoffs from paper to
rock on the one hand, and from paper to scissors on the other hand.

$\displaystyle Payoff(S\mid P)$
$\displaystyle=1\,\mathbb{P}(\nu=\delta_{\text{P}}\mid
P)-3\,\mathbb{P}(\nu=\nicefrac{{1}}{{2}}\delta_{\text{P}}+\nicefrac{{1}}{{2}}\delta_{\text{R}}\mid
P)=1\,\frac{2}{3}-3\,\frac{1}{3}=-\frac{1}{3}$

Similarly, we find that the expected deviation payoff when switching from
paper to rock is $-\frac{1}{3}$. Finally, we see that the expected payoff when
being recommended paper is $-\frac{1}{3}$. Players therefore never have an
incentive to deviate from paper, and $\rho$ is thus a correlated equilibrium.

We have thereby provided an instance of a game where correlated and coarse
correlated equilibria exist, but Nash equilibria do not. Hence, the set of
correlated equilibria of all games is strictly larger than the set of Nash
equilibria.

We also need to nuance the non-existence result: as we will see in Section 6,
although (coarse) correlated equilibria do not always exist as we have just
shown, we can always find $\epsilon$-(coarse) correlated equilibria, with
$\epsilon>0$ as small as we like. We provide here a theorem stating this
property, though its proof will be the entirety of Section 6.

######  Theorem 13 (Existence of $\epsilon>0$-(coarse) correlated equilibria).

For all $\epsilon>0$ small enough, there exists $\epsilon$-(coarse) correlated
equilibria in _all games_.

###### Proof.

All algorithms of Section 6 provably converge towards $\epsilon>0$ (coarse)
correlated equilibria, with $\epsilon\rightarrow 0$. ∎

To illustrate Theorem 13, we remark that in Example 5, although no exact
equilibrium exists, one can easily design _e.g._ an $\epsilon$-Nash
equilibrium for all $\nicefrac{{1}}{{2}}>\epsilon>0$. Indeed, taking
$\nu_{a}=(\nicefrac{{1}}{{2}}+\epsilon)\delta_{a}+(\nicefrac{{1}}{{2}}-\epsilon)\delta_{b}$
and
$\nu_{b}=(\nicefrac{{1}}{{2}}-\epsilon)\delta_{a}+(\nicefrac{{1}}{{2}}+\epsilon)\delta_{b}$,
$\rho=\nicefrac{{1}}{{2}}\delta_{\nu_{a}}+\nicefrac{{1}}{{2}}\delta_{\nu_{b}}$
is a $4\epsilon$-Nash equilibrium. However, a single policy will always be
$>\nicefrac{{1}}{{2}}$-exploitable, thereby showing that $\epsilon$-Nash
equilibria do not always exist for $\epsilon$ small enough.

At last, we exhibite a game where the existence of Mean Field CCE does not
imply the existence of Mean Field CE.

######  Example 7.

Let consider the following (stateless) mean-field variant of rock-paper-
scissors. Each member of the population selects an action from
$\\{\text{R},\text{P},\text{S}\\}$, and the payoff structure is specified as:

  * •

If $\mu(\text{P})>0$ (that is, a non-zero proportion of the population play
paper), then $r(\text{S},\mu)=1$, $r(\text{P},\mu)=0$, $r(\text{R},\mu)=-1$.

  * •

If $\mu(\text{P})=0$ but $\mu(\text{S})>0$ (that is, almost no one plays
paper, but a non-zero proportion play scissors), then $r(\text{R},\mu)=1$,
$r(\text{S},\mu)=0$, $r(\text{P},\mu)=-1$.

  * •

Finally, if $\mu=\delta_{\text{R}}$, then $r(\text{P},\mu)=1$,
$r(\text{R},\mu)=0$, $r(\text{S},\mu)=-1$.

Is there a correlated equilibrium in this game? No: if a player is ever
recommended P, they realise that the sampled recommendation distribution puts
mass on P, so they would benefit from deviating to S. So no MFCE can ever
recommend P. But now similarly, any player recommended S could similarly
benefit from deviating to R, so S cannot be recommended in a MFCE. This leaves
only one possibility: that the MFCE always recommends R, but this is clearly
also not an MFCE.

We now claim that
$\rho=\nicefrac{{1}}{{3}}\delta_{\delta_{\text{S}}}+\nicefrac{{1}}{{3}}\delta_{\delta_{\text{P}}}+\nicefrac{{1}}{{3}}\delta_{\delta_{\text{R}}}$
is an MFCCE for this game. Following the recommendation leads to a payoff of
$0$. However, playing a fixed action also clearly leads to an expected payoff
of $0$, hence we have an MFCCE.

###  4.3 Uniqueness of (Coarse) Correlated Equilibria

The uniqueness of correlated and coarse correlated equilibria is less crucial
than it is for Nash equilibria: indeed, when a game has a unique Nash, there
can be no equilibrium selection problem, which is why Nash unicity is of
interest for us. In counterpart, correlated equilibria do not suffer from
equilibrium selection problems due to the correlation device’s role in
coordinating agents. However, we identified an important situation where
correlated and coarse correlated equilibria are unique: the presence of a
dominant strategy, which we define as follows:

######  Definition 18 (Strictly-dominant strategy).

A strategy $\pi^{*}\in\bar{\Pi}$ is said to be strictly dominant if

$J(\pi^{*},\mu)>J(\pi,\mu)\,,\qquad\forall\pi\in\Pi,\,\mu\in\Delta(\mathcal{X})^{\mathcal{T}}\,.$

Indeed, if a correlated or coarse-correlated equilibrium were to recommend any
other action than the dominant one, the players would all have an incentive to
play that dominant strategy instead, as we show here:

######  Proposition 14 ((Coarse) Correlated equilibria uniqueness).

If there exists a strictly dominant strategy in the game, then the game only
admits a unique coarse correlated equilibrium, and therefore a unique
correlated equilibrium, which only recommends $\nu^{*}\in\Delta(\Pi)$ such
that $\pi(\nu^{*})=\pi^{*}$.

###### Proof.

Let $\rho$ be a coarse correlated equilibrium of a game with strictly dominant
strategy $\pi^{*}$.

Then $\forall\nu\in\Delta(\Pi)$ such that $\pi(\nu)\neq\pi^{*}$,

$J(\pi^{*},\mu(\nu))>J(\pi(\nu),\mu(\nu))$

since $\pi^{*}$ is a strictly dominant strategy.

Therefore, unless $\rho$ only recommends $\nu\in\Delta(\Pi)$ such that
$\pi(\nu)=\pi^{*}$, $\pi^{*}$ is always a strictly-value-increasing deviation.
For $\rho$ to be a coarse correlated equilibrium, it must therefore only
recommend $\nu^{*}\in\Delta(\Pi)$ such that $\pi(\nu^{*})=\pi^{*}$. Since
there only exists one such $\nu^{*}$ (Otherwise two different deterministic
policies would have equal state-action distribution, which is impossible),
equilibrium uniqueness follows. Of course, equilibrium properties derive
directly from the optimality of $\pi^{*}$. ∎

We provide an example of such a situation in the Mean-Field Prisoner’s
Dilemma:

######  Example 8 (Mean-Field Prisoner’s Dilemma).

Consider the two-action normal-form mean-field game with actions C(ooperate)
and D(efect), and reward function

$\displaystyle r(C,\mu)$ $\displaystyle=3\mu(C)-\mu(D)\;,$ $\displaystyle
r(D,\mu)$ $\displaystyle=4\mu(C)-0\mu(D)$

This game has a strictly dominating action, D.

###  4.4 Connection to the Notion of Correlated Equilibrium Derived by Campi
and Fischer

A notion of correlated solution in Mean-Field games has already been
introduced by Campi and Fischer [20]. The main difference between their
framework and ours is that they chose to work with (policy, distribution flow)
pairs $(\pi,\mu)$ instead of population recommendations, which led to
difficulties in adapting their equilibrium concept from Mean-Field settings to
$N$-player settings. In counterpart, the concept of population distribution
adapted seamlessly to $N$-player games and allows us to provide deeper
theoretical properties such as optimality bounds in the next sections of this
work.

we investigate how our definition of MFCE coincides with their notion of
correlated solution. Following our notations, $\mathcal{T}:=\\{0,\ldots,T\\}$
with $T\in\mathbb{N}$ in their framework, while the state space $\mathcal{X}$
and the action space $\mathcal{A}$ are finite. The set $\Pi$ is the finite set
of deterministic strategies, that is

$\Pi=\\{\pi:\\{0,\ldots,T-1\\}\times\mathcal{X}\rightarrow\mathcal{A}\\}\;.$

In our approach, the correlation device $\rho\in\mathcal{P}(\Delta(\Pi))$ is
introduced in order to generate different distributions of policies over the
full population and synchronise hereby the players actions. In the approach
detailed in [20], the synchronisation between the representative player and
the population is viewed as a constraint to which their correlation device
must conform. In more details, their correlation device analogue recommends
directly the representative individual policy $\pi\in\Pi$ together with the
population Mean-Field flow
$\mu\in\mathcal{M}=\Delta(\mathcal{X})^{\mathcal{T}}$. This gives rise to the
notion of correlation flow $\bar{\rho}$, a distribution over
$\Pi\times\mathcal{M}$. The main drawback of this approach is that, written as
such, there is no guarantee that the policies generated by a correlating flow
$\bar{\rho}$ induces a Mean-Field flow consistent with the one sampled by
$\bar{\rho}$. This additional property in [20] identifies to a consistency
condition on the correlating flow $\bar{\rho}$, which can be adapted from the
one described in Definition 4.1 in [20] and rewritten as follows.

######  Definition 19 (Consistent correlating flow [20]).

A consistent correlating flow is a distribution $\bar{\rho}$ over
$\Pi\times\mathcal{M}$ that satisfies the following consistency condition:

$\displaystyle\mu\left(\frac{\bar{\rho}(\cdot,\mu)}{\sum\limits_{\pi\in\Pi}\bar{\rho}(\pi,\mu)}\right)=\mu\,,\quad\mbox{
for any $\mu$ in the support of $\bar{\rho}$\;.}$ (11)

The consistency condition indicates that, for a potentially recommended Mean-
Field flow $\mu\in\mathcal{M}$, the population recommendation induced by the
correlation flow $\bar{\rho}$ conditioned by $\mu$, that is

$\bar{\rho}_{p}(\cdot\mid\mu):=\frac{\bar{\rho}(\cdot,\mu)}{\sum_{\pi\in\Pi}\bar{\rho}(\pi,\mu)},$
(12)

generates its own Mean-Field flow $\mu(\bar{\rho}_{p}(\cdot\mid\mu))$ that
coincides with $\mu$. This condition is naturally inspired by the structure of
Nash equilibria definition in MFGs and is required in order to properly define
the notion of correlated solution of Mean Field Games in [20]. Nevertheless,
directly providing recommendations to the population when manipulating (C)CEs
allows to automatically satisfy this condition. This is the approach naturally
followed by our notion of correlation device.

We are now in position to establish a one to one correspondence between
consistent correlation flows $\bar{\rho}$ considered in [20] and correlation
devices $\rho\in\mathcal{P}(\Delta(\Pi))$ as introduced in Definition 10.

######  Theorem 15.

For any consistent correlating flow $\bar{\rho}$ on $\Pi\times\mathcal{M}$,
there exists a correlation device $\rho\in\mathcal{P}(\Delta(\Pi))$ that
generates the same distribution over $\Pi\times\mathcal{M}$. The opposite
result holds similarly.

The derivation of this property first requires the following result.

######  Lemma 16.

For any $\mu\in\mathcal{M}$, the set
$\mathcal{D}_{\mu}=\\{\nu\in\Delta(\Pi)\mid\mu(\nu)=\mu\\}$ is convex.

###### Proof.

Define $\mu^{\pi}(\nu)$ the state distribution flow of agents playing $\pi$
when the population distribution is $\nu\in\mathcal{V}$, and
$p^{\pi}(x^{\prime}\mid
x,\mu)=\sum\limits_{a\in\mathcal{A}}\pi(x^{\prime},a)p(x^{\prime}\mid
a,x,\mu)$ the proportion of agents going from $x^{\prime}$ to $x$ when playing
$\pi$, under population distribution $\mu$.

The state distribution of an agent playing $\pi$ in a population playing
$\pi(\nu)$, is by definition

$\mu_{t+1}^{\pi}(\nu)(x)=\sum_{x^{\prime}}\mu_{t}^{\pi}(\nu)(x^{\prime})p^{\pi}(x^{\prime}\mid
x,\mu_{t}(\nu)).$

Fix $\mu\in\mathcal{M}$, $\nu_{1},\,\nu_{2}\in\mathcal{D}_{\mu}$ and define
$\nu=\alpha\nu_{1}+(1-\alpha)\nu_{2}$ with $\alpha\in[0,1]$.

We will prove by induction on $t\in\mathcal{T}$ that, for each $\pi\in\Pi$,
$\mu_{t}^{\pi}(\nu)=\mu_{t}^{\pi}(\nu_{1})=\mu_{t}^{\pi}(\nu_{2})$ and
$\mu_{t}(\nu)=\alpha\mu_{t}(\nu_{1})+(1-\alpha)\mu_{t}(\nu_{2})$ so that
$\mu_{t}(\nu)=\mu_{t}$. We first observe that this is satisfied for $t=0$,
since the initial distribution is fixed.

Suppose that the result holds at time $t$. Then

$\displaystyle\mu_{t+1}^{\pi}(\nu)(x)$
$\displaystyle=\sum_{x^{\prime}}\mu_{t}^{\pi}(\nu)(x^{\prime})p^{\pi}(x^{\prime}\mid
x,\mu_{t}(\nu))$
$\displaystyle=\sum_{x^{\prime}}\mu_{t}^{\pi}(\nu_{1})(x^{\prime})p^{\pi}(x^{\prime}\mid
x,\mu_{t})$
$\displaystyle=\sum_{x^{\prime}}\mu_{t}^{\pi}(\nu_{1})(x^{\prime})p^{\pi}(x^{\prime}\mid
x,\mu_{t}(\nu_{1}))$ $\displaystyle=\mu_{t+1}^{\pi}(\nu_{1})(x)$ and similarly
$\displaystyle=\sum_{x^{\prime}}\mu_{t}^{\pi}(\nu_{2})(x^{\prime})p^{\pi}(x^{\prime}\mid
x,\mu_{t}(\nu_{2}))$ $\displaystyle=\mu_{t+1}^{\pi}(\nu_{2})(x)\;.$

Besides, we observe that

$\displaystyle\mu_{t+1}(\nu)(x)$
$\displaystyle=\sum_{\pi}\mu_{t+1}^{\pi}(\nu)(x)\nu(\pi)$
$\displaystyle=\alpha\sum_{\pi}\mu_{t+1}^{\pi}(\nu)(x)\nu_{1}(\pi)+(1-\alpha)\sum_{\pi}\mu_{t+1}^{\pi}(\nu)(x)\nu_{2}(\pi)$
$\displaystyle=\alpha\sum_{\pi}\mu_{t+1}^{\pi}(\nu_{1})(x)\nu_{1}(\pi)+(1-\alpha)\sum_{\pi}\mu_{t+1}^{\pi}(\nu_{2})(x)\nu_{2}(\pi)$
$\displaystyle=\alpha\mu_{t+1}(\nu_{1})(x)+(1-\alpha)\mu_{t+1}(\nu_{2})(x)$
$\displaystyle=\mu_{t+1}(x)\;.$

The property is initialized and hereditary, which concludes the proof:
$\mathcal{D}_{\mu}$ is convex. ∎

With Lemma 16 available, we are now in position to prove Theorem 15, i.e. the
equivalence between our correlated equilibrium representation and the one
presented in [20].

###### Proof of Theorem 15.

Take any consistent correlation flow $\bar{\rho}$ in the sense of Campi and
Fischer [20]. It can be decomposed as a distribution $\bar{\rho}_{m}$ over
$\mathcal{M}$ combined with a conditional distribution $\bar{\rho}_{p}$ over
$\Pi$:

$\bar{\rho}(\pi,\mu)=\bar{\rho}_{p}(\pi\mid\mu)\bar{\rho}_{m}(\mu)\,.$

To any $\mu\in\mathcal{M}$, we associate the induced population distribution
$\nu(\mu):=\bar{\rho}_{p}(.\mid\mu)$. Because the correlating flow is
consistent, the Mean-Field flow induced by $\nu(\mu)$ coincides with $\mu$ \-
i.e. $\mu(\nu(\mu))=\mu$. Therefore the distribution over
$\Pi\times\mathcal{M}$ induced by $\bar{\rho}$ is similar to the one generated
by the following correlation device

$\displaystyle d\rho(\nu)$ $\displaystyle=$
$\displaystyle\int_{\mu\in\mathcal{M}}\mathbf{1}_{\bar{\rho}_{p}(.\mid\mu)=\nu}\;d\bar{\rho}_{m}(\mu)\,.$

Indeed, the distribution over $\Pi\times\mathcal{M}$ generated by $\rho$ is
given for $(\pi,\mu)\in\Pi\times\mathcal{M}$ by

$\displaystyle\int_{\nu\in\mathcal{V}}\mathbf{1}_{\mu(\nu)=\mu}\nu(\pi)d\rho(\nu)$
$\displaystyle=$
$\displaystyle\int_{\nu\in\mathcal{V}}\int_{\mu^{\prime}\in\mathcal{M}}\mathbf{1}_{\bar{\rho}_{p}(.\mid\mu^{\prime})=\nu}\mathbf{1}_{\mu(\nu)=\mu}\nu(\pi)d\bar{\rho}_{m}(\mu^{\prime})$
$\displaystyle=$
$\displaystyle\int_{\nu\in\mathcal{V}}\mathbf{1}_{\bar{\rho}_{p}(.\mid\mu)=\nu}\nu(\pi)d\bar{\rho}_{m}(\mu)$
$\displaystyle=$ $\displaystyle
d\bar{\rho}_{p}(\pi\mid\mu)d\bar{\rho}_{m}(\mu)$ $\displaystyle=$
$\displaystyle d\bar{\rho}(\pi,\mu)\;,$

where we used the consistency condition in the second equality.

On the other hand, take now a correlation device
$\rho\in\mathcal{P}(\Delta(\Pi))$. It induces on $\Pi\times\mathcal{M}$ the
following correlation flow:

$\displaystyle d\bar{\rho}(\pi,\mu)$ $\displaystyle=$
$\displaystyle\int_{\nu\in\mathcal{V}}\mathbf{1}_{\mu(\nu)=\mu}\;\nu(\pi)d\rho(\nu)\;.$

It remains to verify that the induced correlation flow is indeed consistent.
By construction, we have that $d\bar{\rho}(\pi,\mu)\neq
0\iff\exists\nu,\,\mu(\nu)=\mu,\,\nu(\pi)\neq 0,\,d\rho(\nu)\neq 0$.

Whenever there exists a unique $\nu\in\mathcal{D}$ such that
$\mu(\nu)=\mu,\,d\rho(\nu)\neq 0$, then directly
$\bar{\rho}_{p}(.\mid\mu)=\nu$ and the consistency condition holds.

Otherwise, $\bar{\rho}_{p}(.\mid\mu)$ is a mixture of several population
recommendations $\nu\in\mathcal{V}$ such that $\mu(\nu)=\mu$. But Lemma 16
ensures that the set
$\mathcal{D}_{\mu}=\\{\nu\in\Delta(\Pi)\mid\mu(\nu)=\mu\\}$ is convex, so that
$\mu(\bar{\rho}_{p}(.\mid\mu))=\mu$ and the correlation flow induced by $\rho$
is also consistent.

∎

As our notion of correlating device connects now naturally to the notion of
correlation flow considered in Campi and Fischer [20], we are now in position
to draw connections between our notion of Correlated equilibria and the notion
of correlated solution described in [20]. Before doing so, let’s turn to the
definition of correlated solution introduced by Campi and Fischer [20] which
requires the following notion of expected return when using a deviation
mapping $u\in\mathcal{U}_{CE}$ in the presence of a correlating flow
$\bar{\rho}$.

######  Definition 20 (Correlated solution, Definition 4.1 in [20]).

A consistent correlation flow $\bar{\rho}$ is a correlated solution to the
Mean Field Game whenever the following optimality condition holds:

$\displaystyle\mathbb{E}_{(\pi,\mu)\sim\bar{\rho}}\left[J(u(\pi),\mu)-J(\pi,\mu)\right]\leq
0\;,\mbox{ for any }u\in\mathcal{U}_{CE}\;.$

######  Proposition 17.

A correlating flow $\bar{\rho}$ is a correlated solution in the Campi-Fischer
[20] sense if and only if a corresponding correlation device $\rho$ \- which
exists by Proposition 15 \- is a Mean Field Correlated Equilibrium according
to our definition.

###### Proof.

Let $\bar{\rho}$ be a consistent correlation flow generating the same
distribution over $\Pi\times\mathcal{M}$ than the correlation device
$\rho\in\mathcal{C}$, see Proposition 15. The consistent correlation flow
$\bar{\rho}$ is a correlated solution of the MFG if and only if

$\displaystyle\mathbb{E}_{(\pi,\mu)\sim\bar{\rho}}\left[J(u(\pi),\mu)-J(\pi,\mu)\right]\leq
0\;,\qquad u\in\mathcal{U}_{CE}\;.$

On the other hand, the correlation device is a correlated equilibrium if and
only if

$\displaystyle\mathbb{E}_{\pi\sim\nu,\nu\sim\rho}\left[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))\right]\leq
0\;,\qquad u\in\mathcal{U}_{CE}\;.$

The proof is complete, recalling that $\bar{\rho}$ and $\rho$ induce the same
distribution on $\Pi\times\mathcal{M}$. ∎

###  4.5 Homogeneous Correlated Equilibrium Characterization

Homogeneous correlation device presented in Definition 11 are such that any
agent knows what any other agent is playing, since everyone is playing the
same policy. Therefore, a homogeneous $\epsilon$-correlated equilibrium should
intuitively only recommend $\epsilon^{\prime}$-Nash equilibria, with some
$\epsilon^{\prime}\geq 0$ to be specified. In this section, we clarify the
relationship between Nash equilibria and homogeneous correlated equilibria.

We first start with linking the components of a homogeneous $\epsilon$-Mean-
Field correlated equilibrium to $\epsilon$-nash-equilibria.

######  Proposition 18.

Let $\epsilon\geq 0$ and $\rho$ be a homogeneous $\epsilon$-MFCE. Then all
$\pi\in\Pi$ atoms of $\rho$ are $\frac{\epsilon}{\rho(\pi)}$-MFE.

###### Proof.

Let $\epsilon\geq 0$, $\rho$ be a homogeneous $\epsilon$-MFCE and
$\pi^{*}\in\Pi$ such that $\rho(\pi^{*})>0$.

Since $\rho$ is an $\epsilon$-homogeneous Mean-Field correlated equilibrium,
we have

$\displaystyle\int_{\pi\in\bar{\Pi}}(J(u(\pi),\mu^{\pi})-J(\pi,\mu^{\pi}))\rho(d\pi)\leq\epsilon\qquad\forall\pi^{\prime}\in\Pi,\,u:\bar{\Pi}\rightarrow\bar{\Pi}.$

Given $\pi^{*}\in\bar{\Pi}$ an atom of $\rho$ and $\pi^{\prime}\in\bar{\Pi}$
any policy, we select $u$ such that
$\forall\pi\in\bar{\Pi},\,\pi\neq\pi^{*},\,u(\pi)=\pi$ and
$u(\pi^{*})=\pi^{\prime}$. Plugging this in the above equation, we get

$\displaystyle\rho(\pi^{*})(J(\pi^{\prime},\mu^{\pi^{*}})-J(\pi^{*},\mu^{\pi^{*}}))$
$\displaystyle\leq\epsilon$ $\displaystyle
J(\pi^{\prime},\mu^{\pi^{*}})-J(\pi^{*},\mu^{\pi^{*}})$
$\displaystyle\leq\frac{\epsilon}{\rho(\pi^{*})}\;.$

Which means that $\pi^{*}$ is an $\frac{\epsilon}{\rho(\pi^{*})}$-MFE. ∎

We now know that the components of homogeneous $\epsilon$-correlated
equilibria are necessarily $\epsilon^{\prime}$-Nash equilibria. This shows
that, at least in Mean-Field games, only homogeneous correlation devices
recommending solely Nash equilibria can have no $\Phi$-regret.

Finally, we answer the converse question - if a homogeneous correlated
equilibrium only recommends $\epsilon$-Mean-Field Nash equilibria, is it an
$\epsilon$-Mean-Field correlated equilibrium?

######  Proposition 19.

Any homogeneous correlation device recommending only $\epsilon$-Mean-Field
Nash equilibria is an $\epsilon$-MFCE.

###### Proof.

Let $\rho$ be a homogeneous correlation device with support only over
$\epsilon$-Nash equilibria.

For all $u\in\mathcal{U}^{h}_{CE}$, we compute

$\displaystyle\mathbb{E}_{\pi\sim\rho}[J(u(\pi),\mu^{\pi})-J(\pi,\mu^{\pi})]$
$\displaystyle\,=\,\int\limits_{\pi\in\bar{\Pi}}\rho(d\pi)\left(J(u(\pi),\mu^{\pi})-J(\pi,\mu^{\pi})\right)$
$\displaystyle=\int\limits_{\pi\in\epsilon\text{-Nash}}\rho(d\pi)\underbrace{\left(J(u(\pi),\mu^{\pi})-J(\pi,\mu^{\pi})\right)}_{\leq\epsilon}$
$\displaystyle\leq\epsilon,$

hence $\rho$ is an $\epsilon$-MFCE. ∎

##  5 Connections Between $N$-Player and Mean-Field Equilibria

In this section, we explore the connections between $N$-player and Mean-Field
equilibria. We first properly define how to use mean-field equilibria in
$N$-player games in section 5.1. We then build in section 5.2 on the
correspondence between our approach and the one in Campi and Fischer [20] to
investigate the behavior of $N$-player equilibria as N tends to infinity. We
show that they converge towards Mean-Field equilibria. Finally, in Section
5.3, we derive a key practical property by computing optimality bounds
whenever using a mean-field equilibrium in an $N$-player game.

###  5.1 Mean-Field Games to $N$-Player Games

Before we use Mean-Field correlation devices in $N$-player games, we must
first define how we can do so.

The population recommendation framework is very straightforward to use in
$N$-player games : just like in Mean-Field games, we first sample a population
recommendation $\nu\sim\rho$, and then, for each player, sample a policy from
$\nu$. Since there are now only N players, sampling N policies from $\nu$
yields $\nu_{N}\in\Delta_{N}(\Pi)$, a random variable with a law determined by
$\nu$ and N. This means that we can view $\rho$ as a distribution over
$\Delta_{N}(\Pi)$, _i.e._ $\rho\in\mathcal{P}(\Delta_{N}(\Pi))$: $\rho$ is an
$N$-player correlation device !

When sampling an $N$-player population recommendation $\nu_{N}$ from a Mean-
Field population recommendation $\nu\in\Delta(\Pi)$, we will use the abusive
notation $\nu_{N}\sim\nu$. The discussions above yield the following property:

######  Proposition 20 (Mean-Field to $N$-player equilibria).

Taking $\rho$ a Mean-Field correlation device, and $\rho_{N}$ its $N$-player
version, we have that

$\mathbb{E}_{\nu\sim\rho,\,\nu_{N}\sim\nu,\,\pi\sim\nu_{N}}\left[\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(u(\pi),\mu_{N})\right]\right]=\mathbb{E}_{\nu_{N}\sim\rho_{N},\,\pi\sim\nu_{N}}\left[J(u(\pi),\mu_{N})\right]\quad\forall
u:\Pi\rightarrow\Pi.$

However, a Mean-Field correlation device can only be used in an $N$-player
game if it makes sense to do so, _i.e._ if the $N$-player game corresponds to
the Mean-Field game. We define this notion more precisely:

######  Definition 21 (Corresponding $N$-player game).

Given a Mean-Field game with payoff function $J$ and deterministic policies
$\Pi$, its corresponding $N$-player game is the $N$-player game where all N
players play the Mean-Field game as independent agents, and the Mean-Field
population distribution is replaced by the $N$-players’ distribution.

In other words, taking $\mu_{N}$ the state distribution of all N players,
replace $r(x,a,\mu)$ by $r(x,a,\mu_{N})$ and $p(x^{\prime}\mid x,a,\mu)$ by
$p(x^{\prime}\mid x,a,\mu_{N})$.

To rephrase the definition, players play a modified version of the Mean-Field
game where their distribution flow is considered to be the game’s Mean-Field
flow as far as rewards and dynamics are concerned.

###  5.2 $N$-Player to Mean-Field Equilibria

Given the equilibrium equivalence shown in section 4.4 between Campi and
Fischer [20]’s concepts and ours, we inherit their convergence proofs going
from $N$-player games to the Mean-Field case: any sequence of $N$-player
(coarse) correlated equilibria converges towards a Mean-Field (coarse)
correlated equilibrium as N increases, given some conditions.

######  Theorem 21 ($N$-player CEs to Mean-Field CEs).

Let $(\rho_{N})_{N}$ be a sequence of $\epsilon_{N}$-correlated equilibria in
the corresponding $N$-player game. If the reward function and state transition
functions are continuous in $\mu$, and if $\epsilon_{N}\rightarrow 0$, then
the limit of the sequence $(\rho_{N})_{N}$ is a Mean-Field correlated
equilibrium.

###### Proof.

The result follows from a direct application of Theorem 6.1 in [20] and we
only need to verify that the 5 required assumptions (A1)-(A5) [20] in are
satisfied. Assumption (A1) holds since the state transition function is
continuous in $\mu$. Assumption (A2) follows from the continuity of the reward
function with respect to $\mu$. Assumption (A3) and (A4) are valid as
$(\rho_{N})_{N}$ is a sequence of $\epsilon_{N}$-correlated equilibria and
$\epsilon_{N}\rightarrow 0$. Finally, Assumption (A5) holds by virtue of
$(\rho_{N})_{N}$ being correlated equilibria of the corresponding $N$-player
game, so that $\mu^{N}_{0}=\mu_{0}$ for all N. ∎

######  Theorem 22 ($N$-player CCEs to Mean-Field CCEs).

A similar statement holds for coarse correlated equilibria.

###### Proof.

The proof follows the line of argument of the one of Theorem 6.1 in [20] and
simply requires to restrict the set of deviations $\mathcal{U}_{CE}$ to the
more restrictive $\mathcal{U}_{CCE}$. ∎

We now explore the converse of these properties: which population behavior is
induced by plugging Mean-Field equilibria policy in $N$-player games?

###  5.3 Mean-Field Equilibria in $N$-Player Games

Spending resources computing Mean-Field equilibria can be reasonably justified
whenever we can use these equilibria in real-world situations, where,
typically, agents aren’t infinite, but present in very large numbers. It is
therefore useful to be sure that our Mean-Field-generated equilibria work
reasonably well in the large-$N$ $N$-player games of interest. The purpose of
this section is to provide conditions for which using a Mean-Field
$\epsilon$-(coarse) correlated equilibrium in $N$-player games provides an
$N$-player $\mathcal{O}\left(\epsilon+\frac{1}{\sqrt{N}}\right)$-(coarse)
correlated equilibrium !

We first consider in Theorem 23 the simple situation, where transitions do not
depend on $\mu$, then ramp up to transition functions that are Lipschitz with
respect to $\mu$, first with $\rho$ as sums of diracs in Theorem 24, then for
all correlating devices in Theorem 25.

######  Theorem 23.

Let $\rho$ be an $\epsilon\geq 0$-Mean-Field (coarse) correlated equilibrium.
If

  * •

the reward function is $\gamma_{r}$-lipschitz in $\mu$ for the $L_{2}$ norm,
and

  * •

the transition function does not depend on $\mu$,

then $\rho$ is an
$\epsilon+\frac{2\gamma_{r}T\left(1+\sqrt{\frac{1}{2N}}\right)}{\sqrt{N}}$-(coarse)
correlated equilibrium of the corresponding $N$-player game.

###### Proof.

We consider correlated equilibria, but dealing with coarse correlated ones
simply requires to replace the set of deviations $\mathcal{U}_{CE}$ by
$\mathcal{U}_{CCE}$. An $\epsilon$-Mean-Field correlated equilibrium $\rho$ in
the Mean-Field’s corresponding $N$-player game is characterized by, according
to Proposition 20,

$\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}\left[\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(u(\pi),\mu^{N}_{-\pi,u(\pi)})-J(\pi,\mu^{N})\right]\right]\leq\epsilon\,,\quad\forall
u\in\mathcal{U}_{CE}\,.$

Fix $u\in\mathcal{U}_{CE}$. The outline of the proof is the following: We
first control the difference between $J(u(\pi),\mu^{N}_{-\pi,u(\pi)})$ and
$J(u(\pi),\mu^{N})$, and then bound the difference between $J(u(\pi),\mu^{N})$
and $J(u(\pi),\mu(\nu))$, both using the Lipschitz property of $r$, and
therefore of $J$.

We write $\delta_{\mu}$ the indicator function of a player’s position and
time: if a given player $i$ is in state $x$ at time $t$, then
$\delta^{i}_{\mu}(x,t)=1$, and it is 0 for all other states at time $t$.
Directly, we have that $\mu^{N}=\frac{1}{N}\sum_{i}\delta^{i}_{\mu}$. We
overload the notation to write $\delta^{\pi}_{\mu}$ the indicator function of
the location of a given player playing $\pi$. Observe that, since
$\mu^{N}=\sum_{i}\delta^{i}_{\mu}$, we can separate this sum following

$\mu^{N}=\frac{1}{N}\sum_{i\neq
j}\delta^{i}_{\mu}+\frac{1}{N}\delta^{j}_{\mu}$

_i.e._

$\mu^{N}=\mu^{N}_{-j}+\frac{1}{N}\delta^{j}_{\mu}.$

Since this is true for all $j$, we can exclude the player which deviated from
playing $\pi$ to $u(\pi)$ from the sum:

$\mu^{N}_{-\pi,u(\pi)}=\frac{N-1}{N}\mu^{N-1}_{-\pi}+\frac{1}{N}\delta^{u(\pi)}_{\mu}\quad\mbox{and}\quad\mu^{N}=\frac{N-1}{N}\mu^{N-1}_{-\pi}+\frac{1}{N}\delta^{\pi}_{\mu}\,.$

Therefore

$\mu^{N}_{-\pi,u(\pi)}-\mu^{N}=\frac{1}{N}\left(\delta^{u(\pi)}_{\mu}-\delta^{\pi}_{\mu}\right)\,.$

We will now prove that $J$ is $T\gamma_{r}$-Lipschitz w.r.t. $\mu$. Take
$\mu_{1}$, $\mu_{2}\in\mathcal{M}$ and $\pi\in\Pi$.

$\displaystyle J(\pi,\mu_{1})-J(\pi,\mu_{2})$
$\displaystyle=\sum\limits_{t\in\mathcal{T}}\sum\limits_{x\in\mathcal{X}}\mu^{\pi}_{t}(x)\left(r^{\pi}(x,\mu_{1,t})-r^{\pi}(x,\mu_{2,t})\right)$
$\displaystyle\leq\sum\limits_{t\in\mathcal{T}}\sum\limits_{x\in\mathcal{X}}\mu^{\pi}_{t}(x)\gamma_{r}\|\mu_{1,t}-\mu_{2,t}\|_{2}$
$\displaystyle\leq\gamma_{r}\sum\limits_{t\in\mathcal{T}}\|\mu_{1,t}-\mu_{2,t}\|_{2}$
$\displaystyle\leq\gamma_{r}\sum\limits_{t\in\mathcal{T}}1\sqrt{\sum_{x}(\mu_{1,t}(x)-\mu_{2,t}(x))^{2}}$
$\displaystyle\leq\gamma_{r}\sqrt{\sum\limits_{t\in\mathcal{T}}\sum_{x}(\mu_{1,t}(x)-\mu_{2,t}(x))^{2}}\sqrt{\sum\limits_{t\in\mathcal{T}}1^{2}}$
$\displaystyle\leq\sqrt{T}\gamma_{r}\|\mu_{1}-\mu_{2}\|_{2}$

where the first line is true because $\mu^{\pi}$ doesn’t depend on $\mu_{1}$
or $\mu_{2}$, since dynamics are independent of distribution.

Since $J$ is $\sqrt{T}\gamma_{r}$-Lipschitz w.r.t. $\mu$, we deduce

$\lvert
J(u(\pi),\mu^{N}_{-\pi,u(\pi)})-J(u(\pi),\mu^{N})\rvert\leq\frac{\sqrt{T}\gamma_{r}}{N}\|\delta^{u(\pi)}_{\mu}-\delta^{\pi}_{\mu}\|_{2}\,.$

Because the number of states in the game is finite,
$\|\delta^{u(\pi)}_{\mu}-\delta^{\pi}_{\mu}\|_{2}$ is bounded. The maximum
value of this difference is reached in the hypothetical situation where $\pi$
and $u(\pi)$ never reach the same state at the same time. Hence, we have

$\displaystyle\|\delta^{u(\pi)}_{\mu}-\delta^{\pi}_{\mu}\|_{2}$
$\displaystyle=\sqrt{\sum_{t}\underbrace{\sum_{s}\left(\delta^{u(\pi)}_{\mu}(s,t)-\delta^{\pi}_{\mu}(s,t)\right)^{2}}_{\leq
2}}\;\leq\;\sqrt{2T}\,,$

so that

$\lvert
J(u(\pi),\mu^{N}_{-\pi,u(\pi)})-J(u(\pi),\mu^{N})\rvert\leq\frac{T\gamma_{r}\sqrt{2}}{N}.$
(13)

Note that the above is true for any realization of the random variables
$\delta^{\pi}_{\mu}$.

We have bounded the difference between $J(u(\pi),\mu^{N}_{-\pi,u(\pi)})$ and
$J(u(\pi),\mu^{N})$; now let us bound the difference between $J(\pi,\mu^{N})$
and $J(\pi,\mu(\nu))$ for all $\pi$, as we will use the following equality
later on:

$\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(\pi,\mu^{N})\right]=\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(\pi,\mu^{N})-J(\pi,\mu(\nu))\right]+J(\pi,\mu(\nu)).$
(14)

We start with the Lipschitz property of J:

$\lvert J(\pi,\mu^{N})-J(\pi,\mu(\nu))\rvert\leq
T\gamma_{r}\|\mu^{N}-\mu(\nu)\|_{2}.$

By the Jensen inequality, we have

$\mathbb{E}[\|\mu^{N}-\mu(\nu)\|_{2}]=\mathbb{E}\left[\sqrt{\sum_{x,t}\left|\mu^{N}(x,t)-\mu(\nu)(x,t)\right|^{2}}\right]\leq\sqrt{\sum_{x,t}\mathbb{E}\left[\left|\mu^{N}(x,t)-\mu(\nu)(x,t)\right|^{2}\right]}\,.$

Recall that $\mu^{N}$ is the Mean-Field flow resulting from an N players
independently sampling _and_ playing their policies from $\nu$. Since the
policy sampling _and_ the state sampling via policy playing are independent of
other players, the _expected_ distribution of all players is the Mean-Field
distribution of a population playing $\nu$, _i.e._
$\mathbb{E}[\mu^{N}]=\mu(\nu)$ (Though their _actual_ state distribution will
of course typically differ from their expected state distribution).

Therefore $\forall
x\in\mathcal{X},\,t\in\mathcal{T},\;\mathbb{E}[\mu^{N}(x,t)]=\mu(\nu)(x,t)$
and therefore, $\forall x\in\mathcal{X},\,t\in\mathcal{T}$,

$\mathbb{E}\left[\left|\mu^{N}(x,t)-\mu(\nu)(x,t)\right|^{2}\right]=\text{Var}(\mu^{N}(x,t))$

The term $\mu^{N}(x,t)=\frac{1}{N}\sum\limits_{i=1}^{N}\delta^{i}_{\mu}(x,t)$
is the empirical mean of N independent Bernoulli random variables with mean
$\mu(\nu)(x,t)$, and therefore has variance
$\frac{1}{N}\mu(\nu)(x,t)(1-\mu(\nu)(x,t))$.

We notice that whatever the value of $\mu$, $\mu(1-\mu)\leq\mu$ since
$1-\mu\leq 1$. Therefore $\forall t\leq T,\,\forall\mu\in\mathcal{M}$,

$\sum_{x}\mu(x,t)(1-\mu(x,t))\leq\sum_{x}\mu(x,t)=1$

Which yields

$\mathbb{E}\left[\|\mu^{N}-\mu(\nu)\|_{2}\right]\leq\sqrt{\frac{T}{N}},$

and finally gives us

$\mathbb{E}\left[\lvert
J(u(\pi),\mu^{N})-J(u(\pi),\mu(\nu))\rvert\right]\leq\frac{T\gamma_{r}}{\sqrt{N}}.$
(15)

Plugging this property into Equation 14, we obtain

$\displaystyle\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(\pi,\mu^{N})\right]=\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(\pi,\mu^{N})-J(\pi,\mu(\nu))\right]+J(\pi,\mu(\nu))$
$\displaystyle
J(\pi,\mu(\nu))-\frac{T\gamma_{r}}{\sqrt{N}}\leq\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(\pi,\mu^{N})\right]\leq
J(\pi,\mu(\nu))+\frac{T\gamma_{r}}{\sqrt{N}},$

where the second line comes from Equation 15 and the fact that
$-\mathbb{E}[\lvert X\rvert]\leq\mathbb{E}[X]\leq\mathbb{E}[\lvert X\rvert]$.

We recall Equation 13:

$\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}\left[\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(u(\pi),\mu^{N}_{-\pi,u(\pi)})\right]\right]\leq\frac{T\gamma_{r}\sqrt{2}}{N}+\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}\left[\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(u(\pi),\mu^{N})\right]\right]\quad\forall
u:\Pi\rightarrow\Pi.$

Combining all these equations, we have

$\displaystyle\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}\Big{[}\mathbb{E}_{\mu^{N}\sim\mu(\nu)}$
$\displaystyle\left[J(u(\pi),\mu^{N}_{-\pi,u(\pi)})-J(\pi,\mu^{N})\right]\Big{]}$
$\displaystyle\leq\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}\Big{[}\mathbb{E}_{\nu_{N}\sim\nu}\left[J(u(\pi),\mu(\nu_{N}))-J(\pi,\mu(\nu_{N}))\right]\Big{]}+\frac{T\gamma_{r}\sqrt{2}}{N}$
$\displaystyle\leq\mathbb{E}_{\nu\sim\rho,\pi\sim\nu}\left[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))\right]+\frac{T\gamma_{r}\sqrt{2}}{N}+2\frac{\gamma_{r}T}{\sqrt{N}}$
$\displaystyle\leq\epsilon+\frac{2\gamma_{r}T\left(1+\sqrt{\frac{1}{2N}}\right)}{\sqrt{N}}\,.$

where the last inequality comes from the fact that $\rho$ is an
$\epsilon$-Mean-Field (coarse) correlated equilibrium. ∎

######  Remark 5.

We see that in this case, equilibrium approximation accuracy decreases with
the time horizon, however, it does so at speed $\mathcal{O}(T)$ \-
surprisingly, the inaccuracy is not just not exponential in the time horizon,
but it is linear ! It also linearly depends on $\gamma_{r}$: the lower the
Lipschitz coefficient, the more accurate the approximation. There is no
dependency on state space size $\lvert\mathcal{X}\rvert$, however we infer
that it is hidden within the $L_{2}$-Lipschitz condition.

We now tackle the more complex case of $\mu$-dependent transitions. In
$N$-player games, sampling recommendations from a Mean-Field correlation
device $\rho$ induces a sampling noise: when $\rho$ has sampled population
distribution $\nu$, although the N players sample their distributions from
$\nu$, their population distribution will not be equal to $\nu$.

Moreover, the $N$-players’ action choices, and the game’s intrinsic
stochasticity will also render players’ trajectories different from their
expected values.

This adds a third expectation in the computation of a (coarse) correlated
equilibrium’s payoff, which we abusively write $\mu^{N}\sim\mu(\nu)$ as the
distribution of N players who sampled their policies from $\nu$.

Finally, we write $\mu^{N}_{\pi}$ the distribution flow associated with all
$N_{\pi}$ players playing policy $\pi\in\Pi$. Similarly, we write
$\mu_{\pi}(\nu)$ the Mean-Field flow associated with players playing policy
$\pi$ when the population distribution is $\nu$.

We first tackle the distribution-dependent dynamics in the particular case
where $\rho$ is a finite sum of diracs.

######  Theorem 24.

Let $\rho$ be an $\epsilon\geq 0$-Mean-Field (coarse) correlated equilibrium.
If

  * •

the reward and transition functions are lipschitz in $\mu$ for the $L_{2}$
norm, and

  * •

$\rho$ is a finite sum of diracs,

then $\rho$ is an $\epsilon+O\left(\frac{1}{\sqrt{N}}\right)$ (coarse)
correlated equilibrium of the corresponding $N$-player game.

###### Proof.

We provide here a proof outline to introduce the reader to the main arguments
in the full proof, which can be found in Appendix C.2.

Using Lipschitz arguments, we bound the (coarse) correlated equilibrium
equation in the $N$-player game by the same equation in the mean-field game,
with the addition of a distance term between the mean-field distribution and
the $N$-player distribution, _e.g._

$\displaystyle\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[J(u(\pi),\mu^{N}_{-\pi,u(\pi)})-J(\pi,\mu^{N})\right]$
$\displaystyle\leq J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))$
$\displaystyle+\gamma_{r}\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[\|\mu(\nu)-\mu^{N}\|_{2}+\|\mu(\nu)-\mu^{N}_{-\pi,u(\pi)}\|_{2}\right].$

The rest of the proof is focused on finding bounds for the
$\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[\|\mu(\nu)-\mu^{N}\|_{2}\right]$ term,
which can be straightforwardly extended to the
$\mathbb{E}_{\mu^{N}\sim\mu(\nu)}\left[\|\mu(\nu)-\mu^{N}_{-\pi,u(\pi)}\|_{2}\right]$
term.

The dependence of $p$ on $\mu$ forces us to consider every sampled policy’s
state distributions separately, as they influence one another: it is difficult
otherwise to know policy state distributions, and thus which mixed policy is
being played at which state and time.

To bound the difference between $\mu^{N}$ and $\mu(\nu)$, we proceed by
induction over game time using a lemma which reconciles per-policy correctness
(Closeness to $\mu_{\pi}$ for every $\pi$) with global correctness (Closeness
to $\mu$ for every $\mu^{N}$).

Finally, we conclude the proof by summing over the finite number of atoms of
$\rho$ to recover the first expectation. ∎

We see that we still keep a bound in
$\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$ for this more complex case,
though deriving it was much more difficult. Unfortunately, allowing $\rho$ to
be any type of distribution degrades the bounds, given our proof technique, to
$\mathcal{O}\left(\frac{1}{N^{\frac{1}{4}}}\right)$, the square root of the
former one, as we see in the following theorem.

######  Theorem 25.

Let $\rho$ be an $\epsilon\geq 0$-Mean-Field (coarse) correlated equilibrium.
If

  * •

the reward and transition functions are lipschitz in $\mu$ for the $L_{2}$
norm

then $\rho$ is an $\epsilon+O\left(\frac{1}{N^{\frac{1}{4}}}\right)$ (coarse)
correlated equilibrium of the corresponding $N$-player game.

###### Proof.

The line of arguments is similar to that of Theorem 24, with a few alterations
to the end, that are developed in Appendix C.3.

Indeed, the end of the proof of Theorem 24 requires summing over a finite
number of values of $\frac{\rho(\nu)}{\sqrt{\nu_{m}N}}$, which is always
finite and is indeed $\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$. However,
when $\rho$ is not finite, it could well be that it puts mass on a sequence
for which $\nu_{m}$ tends to 0, and this bound therefore diverges.

To counter this, we introduce a new scalar, $\alpha$,that we use to filter out
policies with selection probabilities $\leq\alpha$. We prove that, while
$\alpha\leq\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$, the policies that
weren’t filtered out will still have their state distribution
$\mu_{\pi}\leq\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$, and so will the
global state distribution. Once this is proven, we search for the best value
of $\alpha$ leading to the best bound on $N$. We find that
$\alpha=\frac{1}{\sqrt{N}}$ yields the bound of
$\mathcal{O}\left(\frac{1}{N^{\frac{1}{4}}}\right)$. ∎

######  Remark 6.

We note that these proofs are much more difficult than for Nash equilibria
because of Mean-Field correlated equilibria’s induced stochasticities: they
provide deterministic policy recommendations, and in $N$-player games, the
number of players playing a given policy _is a random variable_. What this
means is that we cannot consider that the whole population plays a policy
$\pi(\nu)$, which greatly complexifies the proof.

It is unclear whether the bound
$\mathcal{O}\left(\frac{1}{N^{\frac{1}{4}}}\right)$ is ever reached, or if
non-discrete MF(C)CEs have tighter bounds; we leave this question for future
work.

However, before closing this section, we would like to make the remark that,
since Nash equilibria can be cast as correlated equilibria, the above bounds
also apply to Nash equilibria. Surprisingly, this is the first result of the
sort of which we are aware in the fully discrete setting:

######  Remark 7 (Mean-Field Nash Equilibrium $N$-player
$\epsilon$-optimality).

This development, since it applies to coarse correlated and correlated
equilibria, also straightforwardly applies to Nash equilibria by Proposition
8, which, given the conditions of the above theorem, are thus
$\epsilon=\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$-Nash equilibria in their
corresponding $N$-player games since Proposition 9 can be adapted to
$N$-player games).

To the best of our knowledge, this is the first time that optimality bounds
have been provided for Mean-Field Nash equilibria’s optimality in $N$-player
games for the fully discrete setting.

##  6 Regret Minimization and Empirical Play

There are strong connections between game-theoretic equilibria and regret
minimisation in online learning. A core result [14] states that if all players
follow a regret-minimizing algorithm to select their strategy, then the
(learning-)time average of their joint behaviour converges to the set of
coarse correlated equilibria. This connection provides a means of computing
approximate equilibria which has been fundamental to recent advances in the
state-of-the-art of games such as heads-up no-limit poker [19, 68].

Regret minimization has surprisingly been understudied in the Mean Field Games
literature. In this section, we describe a corresponding connection between
regret-minimizing algorithms and Mean-Field coarse correlated equilibria,
which serve as the basis for deriving convergence results of learning
equilibria in Section 7.

###  6.1 Empirical Play

A continuous-time learning algorithm generates a continuous-time, measurable
sequence of policies $(\pi_{s})_{0\leq s\leq t}$. A correlation device is
extracted from this sequence by recommending a policy from a uniformly-
selected moment of play: it is the _empirical play_.

######  Definition 22 (Empirical Play).

The empirical play $\hat{\rho}\in\mathcal{P}(\Delta(\Pi))$ of the sequence of
policies $(\pi_{s})_{0\leq s\leq t}$ is the correlation device resulting from
uniformly recommending each deterministic component of one stochastic policy
selected at random among $(\pi_{s})_{0\leq s\leq t}$.

More formally, in the continuous case, this yields

$\displaystyle\hat{\rho}(A)=\frac{1}{t}\int_{0}^{t}\mathbbm{1}\\{\nu\in
A\mid\pi_{s}=\pi(\nu)\\}\mathrm{d}s\,.$

In the discrete case, this yields

$\displaystyle\hat{\rho}(\nu)=\frac{1}{t}\sum_{s=1}^{t}\delta_{\pi_{s}=\pi(\nu)}\,,$

The motivation for introducing the notion of empirical play is that several
key results in this section establish that if each member of a population that
played the sequence of policies $(\pi_{s})_{0\leq s\leq t}$ is relatively
happy with their choice of policies in hindsight, in a sense made precise
below, then the corresponding empirical play correlation device is an
approximate equilibrium for the Mean-Field game under consideration.

To evaluate how close to optimal the empirical play is, we define policy
alterations which characterize the expected deviation payoffs when one follows
it.

######  Definition 23 (Policy Alterations).

The set of Policy Alterations $\mathcal{U}_{A}$ is the set of functions
$\bar{\Pi}\rightarrow\bar{\Pi}$ such that $u\in\mathcal{U}_{A}$ is a policy
alteration if there exists a function $u^{\prime}\in\mathcal{U}_{CE}$ such
that for all $\bar{\pi}=\sum\limits_{\pi\in\Pi}\alpha_{\pi}\pi$,
$u(\bar{\pi})=\sum\limits_{\pi\in\Pi}\alpha_{\pi}u^{\prime}(\pi)$

Informally, a policy alteration of $\bar{\pi}\in\bar{\Pi}$ is a function that
swaps around deterministic policies’ mass in the composition of $\bar{\pi}$.

The set of Coarse Policy Alterations $\mathcal{U}_{CA}$ is the subset of
$\mathcal{U}_{A}$ composed only of constant functions.

The remainder of this section is devoted to formalising the relationship
between regret minimization and both correlated equilibria and coarse
correlated equilibria, and the question of how such sequences of policies can
be generated algorithmically is addressed in Section 7.

###  6.2 External Regret and Coarse Correlated Equilibria

Consider a representative agent in a Mean-Field game, using policy $\pi_{s}$
at time $s$, against a population distribution $\mu_{s}$. The cumulative
return of the agent over a time interval $[0,t]$ is given by

$\displaystyle\int_{0}^{t}J(\pi_{s},\mu^{s})\mathrm{d}s\,.$

A natural question to consider is how better the agent could have done in
hindsight by sticking with a fixed policy $\pi$ throughout the interval
$[0,t]$, in contrast to using the sequence $(\pi_{s})_{0\leq s\leq t}$. The
increase in payoff that the agent could have received is referred to as the
_regret_ of not having played $\pi$. The _external regret_ of a policy
sequence codifies the worst-case regret against a fixed policy.

######  Definition 24 (External regret).

Given a sequence of population distributions $(\mu_{s})_{0\leq s\leq t}$, the
_external regret_ of a policy sequence $(\pi_{s})_{0\leq s\leq t}$ is given by

$\displaystyle\operatorname*{ExtReg}((\pi_{s})_{0\leq s\leq
t},(\mu_{s})_{0\leq s\leq
t})=\sup_{\pi\in\Pi}\int_{0}^{t}J(\pi,\mu^{s})\mathrm{d}s-\int_{0}^{t}J(\pi_{s},\mu^{s})\mathrm{d}s\,.$

Alternatively, an equivalent definition is

$\displaystyle\operatorname*{ExtReg}((\pi_{s})_{0\leq s\leq
t},(\mu_{s})_{0\leq s\leq
t})=\sup_{u\in\mathcal{U}_{CA}}\int_{0}^{t}J(u(\pi_{s}),\mu^{s})\mathrm{d}s-\int_{0}^{t}J(\pi_{s},\mu^{s})\mathrm{d}s\,,$

where the equivalence is immediate when equating $\mathcal{U}_{CA}$ to $\Pi$.

For a bounded reward function $J$, an immediate upper bound on the external
regret of a policy sequence $(\pi_{s})_{0\leq s\leq t}$ given a population
sequence $(\mu_{s})_{0\leq s\leq t}$ is $O(t)$. Of particular interest are
methods for selecting policy sequences $(\pi_{s})_{s\geq 0}$ in the presence
of a population sequence $(\mu_{s})_{s\geq 0}$ such that the external regret
grows as $o(t)$; such a policy sequence is said to be _no-regret_ , or
_regret-minimising_. This interest, in the context of game theory, stems from
the close connection between external regret and coarse correlated equilibria;
both notions encode the value of deviation to a fixed policy in certain
circumstances.

This connection is well-known in non-Mean-Field game theory, and forms the
basis for many algorithms for computing equilibria. The following result makes
this connection precise in the case of Mean-Field games, and serves as a key
motivation for the use of regret-minimisation algorithms for computing coarse
correlated equilibria in Mean-Field games, following similar results in non-
Mean-Field game theory.

######  Proposition 26.

Let $\epsilon>0$ and $(\pi_{s})_{0\leq s\leq t}$ be a sequence of policies.
Then the following two propositions are equivalent.

  1. 1.

$\frac{1}{t}\operatorname*{ExtReg}((\pi_{s})_{0\leq s\leq
t},(\mu^{\pi_{s}})_{0\leq s\leq t})\leq\epsilon$

  2. 2.

The Empirical Play of $(\pi_{s})_{0\leq s\leq t}$ is an $\epsilon$-Mean Field
Coarse Correlated Equilibrium.

###### Proof.

Let select $\epsilon>0$ and $(\pi_{s})_{0\leq s\leq t}$, and name $\hat{\rho}$
the correlation device recommending the empirical play of $(\pi_{s})_{0\leq
s\leq t}$. Observe that

$\displaystyle\frac{1}{t}\operatorname*{ExtReg}((\pi_{s})_{0\leq s\leq
t},(\mu^{\pi_{s}})_{0\leq s\leq t})$
$\displaystyle=\sup_{\pi^{\prime}\in\Pi}\mathbb{E}_{\nu\sim\hat{\rho},\pi\sim\nu}[J(\pi^{\prime},\mu(\nu))-J(\pi,\mu(\nu))]\,,$

following the definition of $\hat{\rho}$ as recommending the empirical play
uniformly: each $\nu$ recommended by $\rho$ is derived from uniformly
recommending $\nu_{\pi_{s}}$ over $s$. We deduce that

$\displaystyle\frac{1}{t}\operatorname*{ExtReg}((\pi_{s})_{0\leq s\leq
t},(\mu^{\pi_{s}})_{0\leq s\leq t})$
$\displaystyle=\sup_{u\in\mathcal{U}_{CCE}}\mathbb{E}_{\nu\sim\hat{\rho},\pi\sim\nu}[J(u(\pi),\mu(\nu))-J(\pi,\mu(\nu))]\,,$

hence providing the connection with the coarse correlated equilibrium
characterization stated in Definition 14.

Hence, $\hat{\rho}$ is an $\epsilon$-Mean-Field Coarse Correlated Equilibrium
if and only if the Average External Regret of $(\pi_{s})_{0\leq s\leq t}$ is
smaller than $\epsilon$. ∎

The correspondence between $\epsilon$-external regret and $\epsilon$-coarse
correlated equilibria is now established. However, in general, algorithms
never really reach $0$ regret, and we now wonder: Does an asymptotically no-
regret algorithm indeed get closer to the set of coarse correlated equilibria
as it minimizes regrets, or could it actually remain “away” from this set? The
following proposition proves that no-external-regret learners do approach the
set of CCEs!

######  Proposition 27.

Let $(\pi_{s})_{0\leq s\leq t}$ be such that
$\lim_{t\rightarrow\infty}\frac{1}{t}\operatorname*{ExtReg}((\pi_{s})_{0\leq
s\leq t},(\mu^{\pi_{s}})_{0\leq s\leq t})=0$, and assume the reward function
$r$ is bounded and the set of coarse correlated equilibria is non-empty. Then
the empirical play of $\pi$, $\hat{\rho}_{\pi}^{t}$, converges to the set of
coarse correlated equilibria $\mathcal{C}$, _i.e._
$\inf\limits_{\rho_{0}\in\mathcal{C}}d_{\mathcal{W}_{2}}(\hat{\rho}_{\pi}^{t},\rho_{0})\rightarrow
0$, where $d_{\mathcal{W}_{2}}$ is the Wasserstein-2 distance.

###### Proof.

First, notice that, since we are in a finite-time, finite-state setting, $r$
being bounded implies directly that $J$ is bounded. Let denote by
$\mathcal{C}_{\epsilon}$ is the set of $\epsilon$-CCE, while $\mathcal{C}$ is
the set of CCE.

We will prove by contradiction that

$\forall\alpha>0,\,\exists\epsilon>0,\forall\rho\in\mathcal{C}_{\epsilon},\;\inf\limits_{\rho_{0}\in\mathcal{C}}d_{\mathcal{W}_{2}}(\rho,\rho_{0})<\alpha\,.$
(16)

Let us suppose that

$\exists\alpha>0,\,\forall\epsilon>0,\exists\rho\in\mathcal{C}_{\epsilon},\;\inf\limits_{\rho_{0}\in\mathcal{C}}d_{\mathcal{W}_{2}}(\rho,\rho_{0})\geq\alpha\,.$
(17)

We take a sequence $(\rho_{n})_{n}$ such that

$\forall
n,\,\rho_{n}\in\mathcal{C}_{\frac{1}{2^{n}}},\,d_{\mathcal{W}_{2}}(\rho_{n},\rho_{0})\geq\alpha\,.$

Correlation devices are distributions over distributions over
$\lvert\Pi\rvert$ elements. The set of distributions over $\lvert\Pi\rvert$
elements is the set of vectors in $\mathbb{R}_{+}^{\lvert\Pi\rvert}$ which sum
to 1. It is compact as a closed and bounded subset of
$\mathbb{R}^{\lvert\Pi\rvert}$. All measures over the set of population
distributions are therefore, by definition, tight. Since their set is tight,
Theorem 5.1 in Billingsley [13] indicates that the set of correlation devices
is relatively compact.

Hence, there exists a subsequence of $(\rho_{n})_{n}$, denoted
$(\rho^{\prime}_{n})_{n}$ converging weakly towards a point $\bar{\rho}$.
Since $\mathbb{R}^{\lvert\Pi\rvert}$ is Polish, $(\rho^{\prime}_{n})_{n}$