# Graphon Mean Field Games with a Representative Player: Analysis and Learning
Algorithm

Fuzhong Zhou  Chenyu Zhang  Xu Chen  Xuan Di

###### Abstract

We propose a discrete-time graphon game formulation on continuous state and
action spaces using a representative player to study stochastic games with
heterogeneous interaction among agents. This formulation admits both
philosophical and mathematical advantages, compared to a widely adopted
formulation using a continuum of players. We prove the existence and
uniqueness of the graphon equilibrium with mild assumptions, and show that
this equilibrium can be used to construct an approximate solution for finite
player game on networks, which is challenging to analyze and solve due to
curse of dimensionality. An online oracle-free learning algorithm is developed
to solve the equilibrium numerically, and sample complexity analysis is
provided for its convergence.

Machine Learning, ICML

##  1 Introduction

Many real-world applications, such as flocking (Perrin et al., 2021),
epidemiology (Cui et al., 2022), and autonomous driving (Huang et al., 2020)
involve multiagent systems, where agents optimize individual cumulative
rewards by selecting sequential actions in an (in)finite horizon, while
interacting strategically among one another. In discrete-time, such finite
player games form Markov games (Littman, 1994; Solan & Vieille, 2015; Yang et
al., 2018b). At a Nash equilibrium (NE), nobody can improve her payoff by
unilaterally switching her individual action policies. The NE is challenging
to solve when the population size grows due to curse of dimensionality (Wang
et al., 2020). To address such a challenge, mean-field formulations are
proposed to model players interacting with others only via an aggregate
population, usually a population measure, instead of individual states or
actions directly.

Mean fields game (MFG) (Lasry & Lions, 2007; Huang et al., 2006) is a type of
mean-field model which describes the limiting behavior of its corresponding
finite player game as the number of players is large, and their analytical
properties are now well-studied (Carmona & Delarue, 2018). The model is build
upon the assumption that the interaction among players are homogeneous, in the
sense that all players follow a same state distribution. As one interacts with
the population only through the measure, all players react in a same manner
and considering one representative is straightforward and appropriate.

As a generalization to MFGs, graphon mean field games (GMFG or graphon games)
are developed (Caines & Huang, 2021; Gao et al., 2021; Aurell et al., 2022;
Tangpi & Zhou, 2023; Cui & Koeppl, 2022) to tackle the limiting behavior of
finite player games with heterogeneous agents who interact asymmetrically,
deemed as games on networks. In such network games, the interactions are given
by a weighted graph (network), where each player is represented by a vertex
and the interaction intensities among players are depicted by edge weights.
Each player reacts to an interaction-weighted average of other individuals’
empirical state measure, which is made precise in Section 3. As the limiting
model, GMFGs models a continuum of players whos interaction intensities are
given by a graphon $W\in L_{1}[0,1]^{2}$, which is a natural limit of finite
graphs and can be deemed as a weighted graph on infinitely many vertices
labeled by the continuum $[0,1]$. Rather than depending on states of some
specific individual, a player in the game reacts only to an average of the
population state distribution, which is weighted as individuals of different
types (different vertices in the graphon) exert heterogeneous influence on the
current player.

GMFGs cover a wider range of real-world applications than MFGs, as it allows
more flexibility with heterogeneous interaction. They are applicable to
problems in finance, economics, engineering, including for instance high-
frequency trading, social opinion dynamics and autonomous vehicle driving.
Because the equilibrium of GMFGs may not be solved explicitly in general,
recent years have seen a growing trend of using learning methods for
equilibria. Compared to abundant studies on learning MFG (Yang et al., 2018a;
Guo et al., 2019b; Cardaliaguet & Hadikhanloo, 2015; Elie et al., 2020; Perrin
et al., 2020, 2021, 2022; Lauriere et al., 2022; Chen et al., 2023b, c, a),
learning on graphon games (Cui & Koeppl, 2022; Zhang et al., 2023) is
relatively understudied.

A major roadblock in learning GMFG lies in the fact that there is no consensus
on what a mathematically tractable formulation of GMFG should be, since it is
not straightforward to describe the the limiting behavior (or a common
population measure) of large number of heterogeneous players. There are mainly
two types of formulations so far. The first type, also the widely adopted one,
models a game for a continuum (uncountably infinite) of players with distinct
types (Caines & Huang, 2021), so-called “continuum-player” games (Carmona et
al., 2021). In this formulation, each player is assigned a controlled state
process, which evolves independently of other individuals’ state processes and
optimize her own reward function.

Unfortunately, this formulation suffers from limitations. Theoretically, the
joint measurability of state dynamics with respect to the player types and
randomness under the usual product space $\sigma$-algebra is not compatible
with the independence of their evolution, which potentially pose challenges in
analytical investigation of solution properties (Appendix C.2); And
practically, it is difficult to develop an algorithm that directly solves a
system of optimal control problems for a continuum of players. Moreover, these
studies could lack consistency between the formulations (that model infinitely
many players) and the algorithms (that only sample a single representative
agent).

To tackle the aforementioned challenges, a second kind of formulation (Lacker
& Soret, 2022) refers to a generic representative player who represents all
types of players while interacting with the aggregate population. While the
state distribution for players of different type are different, it is possible
to fit their label-state pairs into a common law on the product space of
labels and state paths. This formulation is amenable to theoretical guarantees
and ease the algorithmic design and implementation.

In this paper, we study discrete-time graphon games of the second formulation
with rigorous analysis and learning methods. We start from finite player games
to motivate graphon games, which in turn provide approximate equilibra to
finite games in dense interaction networks. Subsequently, GMFG and graphon
games always refer to representative-player formulation, unless otherwise
specified.

##### Related work.

A detailed comparison with the most relevant studies on learning GMFGs is
demonstrated in Appendix B. Continuum-player formulation: In discrete time
regime, Cui & Koeppl (2022) showed existence and approximate equilibrium under
Lipschitz transition kernel and graphon, and Zhang et al. (2023) only showed
the existence of GMFGs with entropic regularization. Both studies assumed
access to an oracle that returns the population dynamics, and the latter
further assumes access to an action-value function oracle that returns the
optimal policies. Under these assumptions, Zhang et al. (2023) provides a
convergence rate of their algorithm, while Cui & Koeppl (2022) only shows the
asymptotic convergence. In continuous time regime, Caines & Huang (2021)
focused on finite networks where each vertex represents a population. Gao et
al. (2021); Aurell et al. (2022); Tangpi & Zhou (2023) studied linear
quadratic games, and the latter two adopted rich Fubini extension to address
the measurability issue. Representative-player formulation: As the establisher
and the only work to the best of our knowledge, Lacker & Soret (2022)
rigorously studied the equilibrium existence uniqueness and approximate
equilibrium in continuous-time, with no discussion in algorithm
implementation.

##### Contributions.

Our major contributions are:

  * •

We propose a general-purpose graphon game framework on continuous state and
action space with one representative player that admits great technical and
philosophical advantages over the continuum-player formulation in most prior
works.

  * •

We present an extensive self-contained analysis on the equilibrium including
existence, uniqueness, and approximate equilibrium to network games with
weaker assumptions and novel proof techniques.

  * •

We give a comprehensive discussion and clarification on various aspects of the
graphon game, including but not limited to MFG reformulation, overview on
measurability issue, convergence of graph sequence, and fixed point iteration.

  * •

We provide the first fully oracle-free online algorithm that numerically
solves the equilibrium, and showed a sample complexity analysis for the ready-
to-implement algorithm with assumptions equivalent to or weaker than prior
works.

  * •

We conduct abundant numerical experiments with assessments that demonstrate
the validity of our algorithm design.

##  2 Preliminaries

###  2.1 Notations

Let $E$ be any Polish space (complete separable metric topological space). We
use ${\mathcal{P}}(E)$ to represent all the probability measures on $E$
equipped with the weak topology, with $\Rightarrow$ being the weak
convergence. Let ${\mathcal{M}}_{+}(E)$ denote the space of nonnegative Borel
measures of finite variation. Denote $\|\cdot\|_{\mathrm{TV}}$ the total
variation norm. Given a random element $X$ valued in $E$, let
${\mathcal{L}}(X)\in{\mathcal{P}}(E)$ be the probabilistic law (distribution)
of $X$. For any $\mu\in{\mathcal{P}}(E)$, we write $X\sim\mu$ if
${\mathcal{L}}(X)=\mu$. For simplicity, we represent the integral with
$\langle\mu,\phi\rangle=\int_{E}\phi d\mu$ for $\mu\in{\mathcal{M}}_{+}(E)$
and measurable $\phi$.

Let ${\mathcal{P}}_{\mathrm{unif}}([0,1]\times E)$ denote a measure on product
space $[0,1]\times E$ with uniform first marginal. We always consider $E$ to
be a regular space, and thus each element $\mu$ admits a disintegration
$du\mu^{u}(dx)$ where $\mu^{u}(dx)$ is a Lebesgue almost every uniquely
defined kernel $[0,1]\to E$.

###  2.2 Graphon

####  2.2.1 Definition

A graphon $W$ is an $L_{1}$ integrable function
$:[0,1]^{2}\to{\mathbb{R}}_{+}$. It represents a graph with infinitely many
vertices taking labels in $[0,1]$, and the edge weight connecting vertex $u$
and $v$ is given by $W(u,v)$. It is a natural notion for the limit of a
sequence of graphs as the size of vertices grows.

Any finite graph can be expressed equivalently as a graphon: given any graph
on $n\geq 1$ vertices with non-negative edge weights, it can be equivalently
expressed as a matrix $\xi\in{\mathbb{R}}_{+}^{n\times n}$, where $\xi_{ij}$
is the edge weight between vertex $i$ and $j$. We define a step graphon
associated with $\xi$, denoted as $W_{\xi}$ on $[0,1]^{2}$ below:

$\displaystyle W_{\xi}(u,v):=\sum_{i,j=1}^{n}\xi_{ij}1_{\\{u\in I^{n}_{i},v\in
I^{n}_{j}\\}}$

where the interval of $[0,1]$ is divided into $n$ bins with the $i^{th}$ bin
as $I^{n}_{i}:=[(i-1)/n,i/n),\forall i=1,\dots,n-1$; $I^{n}_{n}:=[(n-1)/n,1]$.

####  2.2.2 Graphon Operator

Given a Polish space $E$ and any graphon $W$, the graphon operator W, which
maps a measure on ${\mathcal{P}}_{\mathrm{unif}}([0,1]\times E)$ to a function
$[0,1]\to{\mathcal{M}}_{+}(E)$, is defined as follows (Lacker & Soret, 2022):
for any $m\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times E)$,

$\displaystyle\textsf{W}m(u):=\int_{[0,1]\times E}W(u,v)\delta_{x}m(dv,dx)$
(1)

where $\delta_{x}$ is Dirac delta measure at $x$. Intuitively, assume $m$
admits disintegration $m(du,dx)=dvm_{u}(dx)$, and $W$ represents a graph with
infinitely many vertices where each vertex $u\in[0,1]$ bears a random value on
$E$ with distribution $m_{u}$. Then $\textsf{W}m(u)=\int_{[0,1]\times
E}W(u,v)\delta_{x}m_{v}(dx)dv$ is an average of the distribution of the random
value over all vertices, weighted by edges with $u$ as one end. Note that
$\textsf{W}m(u)\in{\mathcal{M}}_{+}(E)$ since the weighted average may no
longer be a probability measure.

####  2.2.3 Strong Operator Topology

Now we define convergence of graphons in strong operator topology. We abuse
the notation by denoting the usual integral operator
$\textsf{W}:L_{\infty}[0,1]\to L_{1}[0,1]$,

$\displaystyle\textsf{W}\phi(u):=\int_{[0,1]}W(u,v)\phi(v)dv\quad\forall\phi\in
L_{\infty}[0,1]$ (2)

and it should lead to no ambiguity as graphon operators and integral operators
have different domains. We say a sequence of graphons $W^{n}$ converges to a
limit graphon $W$ in the strong operator topology if for any $\phi\in
L_{\infty}[0,1]$, $\|\textsf{W}^{n}\phi-\textsf{W}\phi\|_{1}\to 0$, denoted as
$W^{n}\to W$. Convergence in strong operator topology is usually weaker than
converge in cut norm, see appendix A.5.

##  3 Finite Player Games

Consider a game with $n\in{\mathbb{N}}_{+}$ players. Let
$\xi\in{\mathbb{R}}_{+}^{n\times n}$ be an interaction matrix with nonnegative
entries, where $\xi_{ij}$ is the interaction influence of player $j$ onto
player $i$ for $i,j\in[n]$. Let $T\in\mathbb{N}_{+}$ be terminal time of the
game, and ${\mathbb{T}}:=\\{0,1,2,\dots,T-1\\}$. At each time $t$, denote
$\mathbf{X}_{t}=(X^{1}_{t},\dots,X^{n}_{t})\in({\mathbb{R}}^{d})^{n}$ the
state dynamics of all the players, i.e. each player’s state takes value in
${\mathbb{R}}^{d}$ for some fixed $d\geq 1$, and let
${\mathcal{C}}:=({\mathbb{R}}^{d})^{T+1}$ be the space of state paths. For any
$x\in{\mathcal{C}}$, write $x_{t}$ the value of path at time $t$. The initial
states $\mathbf{X}_{0}$ follow a vector of initial measures
$\mathbf{\lambda}=(\lambda^{1},\dots,\lambda^{n})\in({\mathcal{P}}({\mathbb{R}}^{d}))^{n}$.
At each time every player may choose an action from the action space $A$, and
we assume that $A\subset{\mathbb{R}}^{d}$ is compact. Let ${\mathcal{A}}_{n}$
be the collection of all feedback policies
${\mathbb{T}}\times({\mathbb{R}}^{d})^{n}\to{\mathcal{P}}(A)$, and each
player’s action follows a policy from this collection. For any policy
$\pi^{i}\in{\mathcal{A}}_{n}$ chosen by player $i$, the state process of
player $i$ evolves by a transition kernel
$P:{\mathbb{T}}\times{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\times
A\to{\mathcal{P}}({\mathbb{R}}^{d})$ as follows

$\displaystyle X^{i}_{0}\sim\lambda^{i}$ $\displaystyle
a^{i}_{t}\sim\pi^{i}_{t}(\mathbf{X}_{t})\qquad X^{i}_{t+1}\sim
P_{t}(X^{i}_{t},M^{i}_{t},a^{i}_{t})$

for $i=1,\dots,n$, where

$\displaystyle
M^{i}:=\frac{1}{n}\sum_{j=1}^{n}\xi_{ij}\delta_{X^{j}}\in{\mathcal{M}}_{+}({\mathcal{C}})$

is the empirical weighted neighborhood measure of player $i$, and $M^{i}_{t}$
is the time $t$ marginal of $M^{i}$. The measure is emperical as it is an
average of the Dirac measures at the realizations, in particular, $M^{i}$ is a
random measure. For general matrix $\xi$, $M^{i}$ depicts heterogeneous
interaction: for a player $i$, the influence $\xi_{ij}$ from player $j$ is
different from the influence $\xi_{ir}$ from player $r$ for $r\neq j$. In the
special case that $\xi$ is the adjacency matrix of an unweighted complete
graph, i.e. $\xi$ has $0$ on the diagonal and $1$ off diagonal, the
interactions become homogeneous, and $M^{i}$ becomes the simple empirical
measure of the states of all other players.

At a given time step, each player chooses an action according to her policy,
and her state process $X$ is Markov decision process (MDP), which now depends
not only on her current state and action, but also the empirical weighted
neighborhood measure. Note that at each time $t$, the policy $\pi^{i}$ of
player $i$ may depend on each of other players’ state, while the transition
law $P$ should only depend on other players by an aggregation of their states,
i.e. the empirical weighted neighborhood measure.

At each time all players receive running reward according to some
$f:{\mathbb{T}}\times{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\times
A\to{\mathbb{R}}$ and they receive a terminal reward at the terminal time $T$
according to some function
$g:{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\to{\mathbb{R}}$.
The objective of player $i$ is to maximize her expected accumulated reward

$\displaystyle
J^{i}(\bm{\pi}):={\mathbb{E}}\left[\sum_{t\in{\mathbb{T}}}f_{t}(X^{\bm{\pi},i}_{t},M^{\bm{\pi},i}_{t},a^{\bm{\pi},i}_{t})+g(X^{\bm{\pi},i}_{T},M^{\bm{\pi},i}_{T})\right]$

which is a function of the policy of all players
$\bm{\pi}=(\pi^{1},\dots,\pi^{n})\in({\mathcal{A}}_{n})^{n}$. We write
$X^{\bm{\pi},i}$, $M^{\bm{\pi},i}$ and $a^{\bm{\pi},i}$ to emphasize that the
state dynamic of player $i$ depends on $\bm{\pi}$.

######  Definition 3.1.

For any nonnegative vector
$\bm{\epsilon}=(\epsilon^{1},\dots,\epsilon^{n})\in{\mathbb{R}}^{n}_{+}$, an
$\bm{\epsilon}$-equilibrium of the $n$-player game is defined as
$\widehat{\bm{\pi}}=(\widehat{\pi}^{1},\dots,\widehat{\pi}^{n})\in({\mathcal{A}}_{n})^{n}$
such that for any $i$,

$\displaystyle
J^{i}(\widehat{\bm{\pi}})\geq\sup_{\pi\in{\mathcal{A}}_{n}}J^{i}(\widehat{\bm{\pi}}^{-i},\pi)-\epsilon_{i}$
(3)

where $(\widehat{\bm{\pi}}^{-i},\pi)$ denotes the vector $\widehat{\bm{\pi}}$
with $i^{\mathrm{th}}$ coordinate replaced by $\pi$.

##### Mapping $n$-player indices onto a continuous label space.

This part serves as a transition from finite player game defined above, to its
limiting system in the next section. In the finite $n$-player game, we map the
index of agent $i\in\\{1,\cdots,n\\}$ onto a continuous label space $[0,1]$,
by assigning player $i$ a label $u_{i}\in I^{n}_{i}:=[(i-1)/n,i/n),\forall
i=1,\dots,n-1$ and $u_{n}\in I^{n}_{n}:=[(n-1)/n,1]$.

We demonstrate that the empirical weighted neighborhood measure $M^{i}$ can be
expressed in terms of the graphon operator. Let $W_{\xi}$ be the step graphon
associated with interaction matrix $\xi$, then the interaction between player
$i$ and $j$ can be expressed by $\xi_{ij}=W_{\xi}(u_{i},u_{j})$. Define the
empirical label-state joint measure

$\displaystyle
S:=\frac{1}{n}\sum_{i=1}^{n}\delta_{(u_{i},X^{i})}\in{\mathcal{P}}([0,1]\times{\mathcal{C}})$
(4)

which is an empirical measure of the label-state pairs of all players. Then we
have for $i=1,\dots,n$,

(5)

This demonstrates that the graphon operator is a generalization of the
weighted neighborhood measure when there are infinitely many players: with $W$
being the interaction among a continuum of players, and $\mu$ being their
population label-state joint measure, $\textsf{W}\mu(u)$ is the weighted
neighborhood measure for player of label $u\in[0,1]$.

##  4 Representative-player Graphon Game

###  4.1 Game formulation

Given a graphon $W\in L^{1}_{+}[0,1]^{2}$ representing the interaction
intensity among a continuum types of players labeled in $[0,1]$, with $W(u,v)$
being the interaction intensity between player $u$ and player $v$, we define
the graphon game associated with $W$ for a single representative player as
follows. Let the state and action space be defined as in Section 3. Let
$(\Omega,{\mathcal{F}},\mathbb{F},{\mathbb{P}})$ be a filtered probability
space that supports an ${\mathcal{F}}_{0}$-measurable random variable $U$
uniform on $[0,1]$, and an adapted Markov process $X$ valued in
${\mathbb{R}}^{d}$. We understand $U$ as the label for the representative
player, and $X$ as her state dynamic. The initial label-state law of the
representative player is given by
$\lambda:={\mathcal{L}}(U,X_{0})\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathbb{R}}^{d})$.
The term “label-state” always refer to the joint measure of a player’s label
and state pair $(U,X)$. As in mean-field games, we abstract all other players
into a measure $\mu\in{\mathcal{P}}_{\text{unif}}([0,1]\times{\mathcal{C}})$,
i.e. each non-representative player should admits $\mu$ as her label-state
joint measure, and the representative player only reacts to the population via
this measure. Let $\mu$ be fixed. Let
$\mu_{t}\in{\mathcal{P}}_{\text{unif}}([0,1]\times{\mathbb{R}}^{d})$ be the
marginal of $\mu$ under image $(u,x)\mapsto(u,x_{t})$.

Let ${\mathcal{V}}_{U}$ be the collections of all the open-loop policies, i.e.
all the adapted process valued in ${\mathcal{P}}(A)$. Let ${\mathcal{A}}_{U}$
denotes the collection of all the closed-loop (Markovian) policies, i.e.
measurable functions
${\mathbb{T}}\times[0,1]\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$.
${\mathcal{A}}_{U}$ is usually a proper subset of ${\mathcal{V}}_{U}$, unless
the filtration is generated by $U$ and $X$. For any $\pi\in{\mathcal{V}}_{U}$,
the label-state pair $(U,X)$ follows the transition dynamic
$(U,X_{0})\sim\lambda$ and at each $t\in{\mathbb{T}}$,

$\displaystyle a_{t}\sim\pi_{t}\qquad X_{t+1}\sim
P_{t}(X_{t},\textsf{W}\mu_{t}(U),a_{t})$

for the same $\\{P_{t}\\}_{t\in{\mathbb{T}}}$ as in the finite player game
introduced in section 3. In words, the representative player is uniformly
assigned a label $U$ at time $0$, and her later state transition depends on
her current state, action and weighted neighborhood measure
$\textsf{W}\mu_{t}(U)\in{\mathcal{P}}({\mathbb{R}}^{d})$. Recall (5) in the
finite-player case, $\mu$ is now a generalization of $S$ defined in (4) when
there are infinitely many types of players. We may consider the disintegration
$\mu(du,dx)=du\mu^{u}(dx)$, where $du$ is the Lebesgue measure and $[0,1]\ni
u\mapsto\mu^{u}\in\mathcal{P}(\mathcal{C})$ is a probabilistic kernel. Then
$\textsf{W}\mu(u)=\int_{[0,1]}W(u,v)\int_{\mathcal{C}}\delta_{x}\mu^{v}(dx)dv$.
The inner integral is the path measure of player $v$, and the outer integral
depicts an average of state distributions over all labels $v$, weighted by
their interaction with the representative player when her label is
$u\in[0,1]$.

Let
$f:{\mathbb{T}}\times{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\times
A\to{\mathbb{R}}$ be the running reward and
$g:{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\to{\mathbb{R}}$
be the terminal reward. The objective of the representative player is to
choose a policy $\pi\in{\mathcal{V}}_{U}$ to maximize

$\displaystyle J_{W}(\mu,\pi)$
$\displaystyle:={\mathbb{E}}\bigg{[}\sum_{t\in{\mathbb{T}}}f_{t}(X^{\pi}_{t},\textsf{W}\mu_{t}(U),a^{\pi}_{t})+g(X_{T}^{\pi},\textsf{W}\mu_{T}(U))\bigg{]}$

Note that the expectation is w.r.t. all random elements on ${\mathcal{F}}$,
i.e. $(U,X)$ and $\pi$, and we use $X^{\pi}$, $a^{\pi}$ to emphasize that they
depends on the policy $\pi$.

######  Definition 4.1.

We say that the measure-policy pair
$(\widehat{\mu},\widehat{\pi})\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})\times{\mathcal{V}}_{U}$
is a $W$-equilibrium if

$\displaystyle J_{W}(\widehat{\mu},\widehat{\pi})$
$\displaystyle=\sup_{\pi\in{\mathcal{V}}_{U}}J_{W}(\widehat{\mu},\pi)$ (6)
$\displaystyle\widehat{\mu}$
$\displaystyle={\mathcal{L}}(U,X^{\widehat{\pi}})\quad$ (7)

$\widehat{\mu}$, $\widehat{\pi}$ are called equilibrium population measure and
equilibrium optimal policy respectively.

Intuitively, the game is formulated for a representative player, while all
other players are abstracted into a label-state joint measure $\mu$. The
representative player interacts with the population only through the weighted
neighborhood measure $\textsf{W}\mu(U)$, according to which she takes action
to optimize her reward. The proposed graphon game is a strict generalization
of MFGs, and it degenerates to an MFG when the graphon $W\equiv 1$. This is
made precise in Section A.3. We will give a comprehensive comparison between
our formulation with the continuum-player graphon game in Appendix C.

######  Remark 4.2.

We define an infinite horizon version of graphon game with time-invariant
dynamics and rewards in Section A.1. The analysis in the rest of this section
could be easily adpated to the infinite horizon formulation by eliminating the
time dependency of functions.

##### GMFG as MFG with augmented state space.

The graphon games defined here could be transformed into classical MFGs with
an augmented state space, by imposing the label space $[0,1]$ as an additional
dimension to the state space. However, this does not simplify the analysis or
proof, and it is not appropriate to adapt existing results from MFG directly
(See Section A.2).

###  4.2 Existence of Equilibrium

######  Assumption 4.3.

  1. nosep

The action space $A$ is a compact subspace of ${\mathbb{R}}^{d}$.

  2. nosep

The running rewards $f_{t}$, $\forall t\in{\mathbb{T}}$ and terminal reward
$g$ are bounded and jointly continuous.

  3. nosep

The intial distribution
$\lambda\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathbb{R}}^{d})$ admits
disintegration $\lambda(du,dx)=du\lambda_{u}(dx)$, and the following
collection of measures is tight 111Recall the definition of tightness: for
arbitrary index set $I$ and Polish space $E$, a collection of probability
measures $\\{P_{i}\\}_{i\in I}\subset{\mathcal{P}}(E)$ is tight if for any
$\epsilon>0$, there exists some compact measurable subset $K\subset E$ such
that $\inf_{i\in I}P_{i}(K)>1-\epsilon$. :

$\displaystyle\\{\lambda_{u}\\}_{u\in[0,1]}\subset{\mathcal{P}}({\mathbb{R}}^{d})$

  4. nosep

For each $t\in{\mathbb{T}}$, the following collection of measures is tight:

$\displaystyle\zeta_{t}:=\\{P_{t}$
$\displaystyle(x,m,a)\\}_{(x,m,a)\in{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\times
A}\subset{\mathcal{P}}({\mathbb{R}}^{d})$

  5. nosep

For each $t\in{\mathbb{T}}$, $P_{t}(x,m,\cdot)$ is continuous in $A$ for every
$(x,m)\in{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})$.

An example case where 4.3(3, 4) are trivially satisfied is that there exists
some compact subspace ${\mathcal{X}}\subset{\mathbb{R}}^{d}$ such that the
collection $\zeta_{t}$ are uniformly supported on ${\mathcal{X}}$, i.e. the
Markov process $X$ takes values in the state space ${\mathcal{X}}$. Also note
that we do not assume the graphon $W$ to be continuous.

######  Theorem 4.4.

Suppose assumption 4.3 holds. Then there exists a $W$-equilibrium
$(\widehat{\mu},\widehat{\pi})$. Moreover, the equilibrium optimal policy
$\widehat{\pi}$ can be chosen to be a closed-loop policy.

The theorem is proved with probabilistic compactification and Kakutani-Fan-
Glicksberg fixed point theorem in Appendix E.

###  4.3 Uniqueness of Equilibrium

######  Assumption 4.5.

  1. nosep

The state transition law $P$ does not depend on the measure argument. Then it
reads $P_{t}:{\mathbb{R}}^{d}\times A\to{\mathcal{P}}({\mathbb{R}}^{d})$ for
$t\in{\mathbb{T}}$.

  2. nosep

For each $t\in{\mathbb{T}}$, the running reward $f_{t}$ is separable in the
measure and action argument: there exists $f^{1}_{t}:{\mathbb{R}}^{d}\times
M_{+}({\mathbb{R}}^{d})\to{\mathbb{R}}$ and $f^{2}_{t}:{\mathbb{R}}^{d}\times
A\to{\mathbb{R}}$ such that $f_{t}(x,m,a)=f^{1}_{t}(x,m)+f^{2}_{t}(x,a)$.

  3. nosep

The optimal policy is unique. More specifically, for each
$\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$, the supremum
$\sup_{\pi\in{\mathcal{V}}_{U}}J_{W}(\mu,\pi)$ is attained uniquely.

  4. nosep

The functions $f^{1}_{t}$ and $g$ satisfy the Larsy-Lions Monotonicity
condition, in the following sense: for any
$m_{1},m_{2}\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathbb{R}}^{d})$,
and $t\in{\mathbb{T}}$,

$\displaystyle\int_{[0,1]\times{\mathbb{R}}^{d}}\big{(}g(x,$
$\displaystyle\textsf{W}m_{1}(u))-g(x,\textsf{W}m_{2}(u))\big{)}$
$\displaystyle(m_{1}-m_{2})(du,dx)\leq 0$
$\displaystyle\int_{[0,1]\times{\mathbb{R}}^{d}}\big{(}f^{1}_{t}(x,$
$\displaystyle\textsf{W}m_{1}(u))-f^{1}_{t}(x,\textsf{W}m_{2}(u))\big{)}$
$\displaystyle(m_{1}-m_{2})(du,dx)\leq 0$

Assumption 4.5 are the graphon game analogies to classic uniqueness
assumptions in mean-field games, see for example Carmona & Delarue (2018,
Section 3.4) and Lacker (2018, section 8.6).

######  Theorem 4.6.

Suppose assumption 4.3 and assumption 4.5 holds. Then the graphon game admits
a unique $W$-equilibrium.

The proof follows a standard argument in MFG, see Appendix F.

###  4.4 Approximate Equilibrium for Finite Player Game

Let
$\widehat{\pi}:{\mathbb{T}}\times[0,1]\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$
be the equilibrium optimal closed-loop policy of the graphon game associated
with graphon $W$, and we construct an $n$-player game policy from
$\widehat{\pi}$ as follows. Assign player $i$ the policy

$\displaystyle\pi^{n,\textbf{u}^{n},i}(t,x_{1},\dots,x_{n}):=\widehat{\pi}(t,u^{n}_{i},x_{i})$
(8)

and
$\bm{\pi}^{n,\textbf{u}^{n}}:=(\pi^{n,\textbf{u}^{n},1},\dots,\pi^{n,\textbf{u}^{n},n})\in({\mathcal{A}}_{n})^{n}$.
Define

$\displaystyle\epsilon^{n}_{i}(\textbf{u}^{n}):=\sup_{\beta\in{\mathcal{A}}_{n}}J_{i}(\bm{\pi}^{n,\textbf{u}^{n},-i},\beta)-J_{i}(\bm{\pi}^{n,\textbf{u}^{n}})$
(9)

and
$\bm{\epsilon}^{n}(\textbf{u}^{n}):=(\epsilon^{n}_{1}(\textbf{u}^{n}),\dots,\epsilon^{n}_{n}(\textbf{u}^{n}))$.
$\epsilon^{n}_{i}(\textbf{u}^{n})$ is the largest reward improvement player
$i$ could achieve by changing her own policy, when all other players follow
policies $\bm{\pi}^{n,\textbf{u}^{n}}$. By definition 3.1,
$\bm{\pi}^{n,\textbf{u}^{n}}$ is an
$\bm{\epsilon}^{n}(\textbf{u}^{n})$-equilibrium of the $n$-player game. We
need the following additional assumptions.

######  Assumption 4.7.

  1. nosep

$\xi^{n}\in{\mathbb{R}}_{+}^{n\times n}$ is a sequence of matrix with 0
diagonals such that $W_{\xi^{n}}\to W$ in strong operator topology, and

$\displaystyle\lim_{n\to\infty}\frac{1}{n^{3}}\sum_{i,j=1}^{n}(\xi^{n}_{ij})^{2}=0$
(10)

  2. nosep

For each $t\in{\mathbb{T}}$, the transition dynamic
$P_{t}:{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\times
A\rightarrow{\mathcal{P}}({\mathbb{R}}^{d})$ is jointly continuous for all
$t\in{\mathbb{T}}$.

The next main result demonstrates that the $n$-player game policy
$\bm{\pi}^{n,\bm{u}^{n}}$ constructed from the graphon game equilibrium
optimal policy $\widehat{\pi}$ forms an approximate equilibrium, and it
converges to the true equilibrium in an average sense as the number of players
$n\to\infty$.

######  Theorem 4.8.

Suppose assumption 4.3 and assumption 4.7 holds. For each
$n\in{\mathbb{N}}_{+}$, let $\mathbf{U}^{n}:=(U^{n}_{1},\dots,U^{n}_{n})$
where $U^{n}_{i}\sim\mathrm{unif}(I^{n}_{i})$ and $U^{n}_{i}$ is independent
of $U^{n}_{j}$ for $i\neq j$. Then we have

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}[\epsilon^{n}_{i}(\mathbf{U}^{n})]=0$
(11)

The proof is in Appendix G. Equation (11) can be equivalently written as
$\epsilon^{n}_{I^{n}}(\mathbf{U}^{n})\to 0$ in probability, where
$I^{n}\sim\mathrm{unif}([n])$. Intuitively, for randomly assigned label
$\mathbf{U}^{n}$, and a player $I^{n}$ uniformly chosen on $[n]$, the error is
small. As the number of player $n\to\infty$, the collection of
$\mathbf{U}^{n}$ and player label $I^{n}$ such that the error cannot be
controlled becomes a measure 0 set.

######  Remark 4.9.

Equation (10) is a very mild graph denseness condition and is satisfied by
many commonly-encountered finite graphs. The assumption $W_{\xi^{n}}\to W$
also poses denseness restrictions on the underlying graphs of interaction
matrix $\xi^{n}$, as the existence of a graphon limit implicitly implies that
the sequence of finite graphs are dense enough. We give some examples and a
detailed discussion on dense graph sequence in Section A.5.

##  5 Learning Scheme and Sample Complexity

We now develop a scheme for learning the stationary equilibrium of infinite-
horizon graphon games (Section A.1). Throughout the section we assume finite
state space ${\mathcal{X}}$ and action space $A$.

###  5.1 Finite Classes of Label Space

To handle the continuous label space algorithmically, one generally needs
function approximation techniques such as linear function approximation or
neural networks, which is beyond the scope of this work. For the development
and analysis of our algorithms, we discretize the label space $[0,1]$ into $D$
classes of types of players $\mathcal{U}\subset[0,1]$ such that
$|\mathcal{U}|=D<\infty$. We denote
$\mathcal{U}\coloneqq\\{u_{1},\ldots,u_{D}\\}$, and define projection mapping
$\Pi_{D}:[0,1]\to\mathcal{U}$. Denote the inverse image
$I_{u_{d}}\coloneqq\Pi_{D}^{-1}(u_{d})\subset[0,1]$. A simple example is the
uniform quantization: $[0,1]$ is divided into $D$ bins
$\\{I^{D}_{d}\\}_{d=1}^{D}$, and $\Pi_{D}$ maps each bin to its midpoint:

$\displaystyle\Pi_{D}(u)=\sum_{i=1}^{D}\frac{2i-1}{2D}{1}_{\\{u\in
I_{i}^{D}\\}}$ (12)

As we are only able to learn measures on the finite discretization
$\mathcal{U}$, we define
$\bm{\Pi}_{D}:{\mathcal{P}}({\mathcal{X}})^{\mathcal{U}}\to{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{X}})$
as follows: for any $M=\\{M^{u_{d}}\\}_{d=1}^{D}$, $\bm{\Pi}_{D}M$ is the
measure $\mathrm{Leb}\otimes\nu$, where $\nu$ is a probabilistic kernel given
by $\nu(u)\coloneqq\sum_{d=1}^{D}M^{u_{d}}1_{\\{u\in I_{u_{d}}\\}}$.

###  5.2 Approximate Fixed-Point Iteration

Our learning scheme follows fixed-point iteration (FPI), which is widely used
for learning (G)MFGs (Guo et al., 2019b; Cui & Koeppl, 2022; Zhang et al.,
2023). An FPI represents an update of the game: given the population measure,
the representative player first finds the optimal policy in reaction to this
population, i.e.
$\Gamma_{1}:{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{X}})\to{\mathcal{A}}_{U}$,
$\Gamma_{1}(\mu)\coloneqq\mathrm{argmax}_{\pi\in{\mathcal{A}}_{U}}J_{W}(\mu,\pi)$.
As everyone in the population reacts similarly, the population is then updated
to the induced state distribution of the acquired policy, i.e.
$\Gamma_{2}:{\mathcal{A}}_{U}\times
P_{\mathrm{unif}}([0,1]\times{\mathcal{X}})\to{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{X}})$,
$\Gamma_{2}(\pi,\mu):={\mathcal{L}}(U,X^{\pi})$. Then, the FPI is given by
$\Gamma(\mu)\coloneqq\Gamma_{2}(\Gamma_{1}(\mu),\mu)$, and the equilibrium
population measure $\widehat{\mu}$ satisfies
$\widehat{\mu}=\Gamma(\widehat{\mu})$. However, the FPI operators can be hard
to implement. As the environment ($P$ and $f$) is unknown, $\Gamma_{1}$ and
$\Gamma_{2}$ are not directly accessible and need to be approximated. The
general approximate FPI scheme is presented in Algorithm 1.

Algorithm 1 provides a general framework that can incorporate various learning
algorithms for the two evaluation steps as subroutines, with (i) and (ii)
approximating $\Gamma_{1}$ and $\Gamma_{2}$ respectively. If the access to a
state process generator (called an oracle) is assumed, we may generate the
state variable under any control and population measure for arbitrary times,
and Algorithm 1 recovers the algorithms used in prior work (Cui & Koeppl,
2022; Zhang et al., 2023).

Algorithm 1 Approximate FPI for GMFGs

Initialize policy estimate $\\{\pi^{0}_{d}\\}_{d=1}^{D}$ and population
estimate $\\{M^{0}_{d}\\}_{d=1}^{D}$ for all label classes $d\in[D]$

for $k\leftarrow 0$ to $K-1$ do

for $d\leftarrow 1$ to $D$ do

(i) Evaluate approximate optimal policy $\pi^{k+1}_{d}$ in reaction to $M^{k}$
(ii) Evaluate approximate population measure $M^{k+1}_{d}$ induced by
$\pi^{k+1}_{d}$

end for

end for

Return $\left\\{\pi_{d}^{K}\right\\}$ and $\\{M^{K}_{d}\\}$

We next provide the first non-asymptotic analysis for $D$-class FPI scheme
given the following assumptions.

######  Assumption 5.1.

  1. nosep

The transition kernel and reward function are uniformly $L_{P},L_{f}$
Lipschitz w.r.t. the measure argument respectively: 222Finite signed measures
on finite space can be equivalently expressed as a vector, and the total
variation norm is equivalent to the $\ell_{1}$ norm.

$\displaystyle\sup_{x,a}\left|f(x,m_{1},a)-f(x,m_{2},a)\right|\leq
L_{f}\|m_{1}-m_{2}\|_{\mathrm{TV}},$
$\displaystyle\sup_{x,a}\|P(x,m_{1},a)-P(x,m_{2},a)\|_{\mathrm{TV}}\leq
L_{P}\|m_{1}-m_{2}\|_{\mathrm{TV}}$

  2. nosep

There exists $L_{d}$ such that

$\displaystyle\sup_{u,v\in[0,1]}|W(u,v)-W(\Pi_{D}(u),v)|\leq L_{d}/D.$

  3. nosep

The FPI operator $\Gamma$ is a contraction mapping: there exists
$\kappa\in(0,1)$ such that
$\|\Gamma(\mu_{1})-\Gamma(\mu_{2})\|_{\mathrm{TV}}\leq(1-\kappa)\|\mu_{1}-\mu_{2}\|_{\mathrm{TV}}$
for any $\mu_{1},\mu_{2}\in{\mathcal{P}}([0,1]\times{\mathcal{X}})$.

5.1(2) ensures label classes $\mathcal{U}$ are a good approximation of the
label space $[0,1]$. An example that satisfies this is the uniform
quantization $\Pi_{D}$ in equation (12) if the graphon is Lipschitz continuous
in the first argument. The contraction mapping along with the Lipschitzness
assumptions are limited but unfortunately necessary in complexity analysis
proofs. We give a brief discussion on this assumption and different types of
fixed-point theorems in Section A.6.

Suppose Assumptions 5.1 hold, Algorithm 1 with exact evaluation steps needs at
most $D=O(\kappa^{-1}\epsilon^{-1})$ classes and
$K=O(\kappa^{-1}\log\epsilon^{-1})$ iterations to achieve an
$\epsilon$-approximate equilibrium. This claim is formalized in Theorem 5.4.

###  5.3 Online Oracle-Free Learning

An oracle is defined to be a state process generator that could repeatedly
sample a player’s next state, or a device that could collect the next state
for a number of players at the same time regardless of communication costs and
asynchronous delays. An oracle-free algorithm (Angiuli et al., 2022b, a) is
one that does not involve an oracle. In the following We present an online
oracle-free subroutine for the approximate evaluation steps in Algorithm 1 by
specifying a concrete implementation of the two evaluation steps (i) and (ii).
Specifically, we use SARSA (Sutton & Barto, 2018), a value-based reinforcement
learning method, for policy estimation, and Markov chain Monte Carlo (MCMC)
for population estimation.

For policy estimation, we maintain a Q-function:
$\mathcal{U}\times\mathcal{X}\times A\to{\mathbb{R}}$, with entry $Q_{d}(x,a)$
estimating the expected return starting with the state-action pair $(x,a)$
conditional on label being $u_{d}$. Let ${\mathcal{Q}}$ be the collection of
all Q-functions. To obtain the policy from a Q-function, we assume access to a
Lipschitz continuous policy operator
$\Gamma_{\pi}:{\mathcal{Q}}\to{\mathcal{A}}_{U}$, i.e., for any
$Q_{1},Q_{2}\in{\mathcal{Q}}$, there exists a constant $L_{\pi}$ such that

$\displaystyle\sup_{u,x}\\!\left\|\left(\Gamma_{\pi}(Q_{1})\\!-\\!\Gamma_{\pi}(Q_{2})\right)\\!(u,x)\right\|_{\mathrm{TV}}\\!\leq\\!L_{\pi}\\!\left\|Q_{1}\\!-\\!Q_{2}\right\|_{2}$

(13)

An example policy operator satisfying (13) is the softmax function, with its
temperature parameter controlling the constant $L_{\pi}$ (Gao & Pavel, 2017).
Given $\Gamma_{\pi}$, SARSA converges to the Q-function corresponding to the
optimal policy in $\Gamma_{\pi}({\mathcal{Q}})\subset{\mathcal{A}}_{U}$ (Zou
et al., 2019).

######  Remark 5.2.

Utilizing a Lipschitz continuous policy operator, $\Gamma_{1}$ returns the
optimal Q-function instead of a policy; and 5.1(3) can be relaxed to only
requiring $\Gamma_{1}$ and $\Gamma_{2}$ to be Lipschitz continuous with
constants $L_{1}$ and $L_{2}$. Then, we can choose a sufficiently smooth
policy operator such that $L_{\pi}L_{1}L_{2}<1$, making the FPI operator
$\Gamma(\mu)\coloneqq\Gamma_{2}(\Gamma_{\pi}(\Gamma_{1}(\mu)),\mu)$
contractive.

For population estimation, we maintain a M-function:
$\mathcal{U}\to{\mathcal{P}}(\mathcal{X})$, with entry $M_{d}$ estimating the
population measure of the representative player conditional on label $u_{d}$.
Since $\mathcal{U}\times\mathcal{X}\times A$ is a finite space, both Q- and
M-functions can be represented by tables. Being fully online, SARSA and MCMC
can update the Q- and M-functions using the same online samples without the
need of any oracle. Specifically, we execute $H$ updates for the evaluation
subroutine of Algorithm 1. At each step $\tau=0,\dots,H-1$, the representative
agent with label $u_{d}$ at $x_{\tau}$ samples its action
$a_{\tau}\sim\Gamma_{\pi}(Q^{k,\tau}_{d})$, reward
$r_{\tau}=f(x_{\tau},\textsf{W}\bm{\Pi}_{D}M^{k,0}(u_{d}),a_{\tau})$, next
state $x_{\tau+1}\sim
P(x_{\tau},\textsf{W}\bm{\Pi}_{D}M^{k,0}(u_{d}),a_{\tau})$, and next action
$a_{\tau+1}\sim\Gamma_{\pi}(Q^{k,\tau}_{d})$. Using these sample, the Q- and
M-functions are updated simultaneously as follows:

$\displaystyle Q^{k,\tau+1}_{d}(x_{\tau},a_{\tau})\leftarrow$
$\displaystyle(1-\alpha_{\tau})Q^{k,\tau}_{d}(x_{\tau},a_{\tau})$ (14)
$\displaystyle+\alpha_{\tau}\left(r_{\tau}+\gamma
Q^{k,\tau}_{d}(x_{\tau+1},a_{\tau+1})\right),$ $\displaystyle
M^{k,\tau+1}_{d}\leftarrow$
$\displaystyle(1-\beta_{\tau})M^{k,\tau}_{d}+\beta_{\tau}\delta_{x_{\tau+1}},$

where the Q- and M-functions are indexed by the outer iteration $k$ and the
inner evaluation step $t$, and $\alpha_{\tau}$ and $\beta_{\tau}$ are step
sizes. Substituting the Q-function $Q^{k,\tau}_{d}$ with the optimal
Q-function $Q^{\mu^{k,\tau}}$ associated with the population measure
$\mu^{k,\tau}=\bm{\Pi}_{D}M^{k,\tau}$, we recover the FPI scheme in Algorithm
1. Substituting (i) and (ii) in Algorithm 1 with $H$ updates using Equation
14, we obtain the first fully online algorithm for learning GMFGs. Notably,
our method is oracle-free in the sense that we do not assume access to an
optimal policy calculator or a state process generator. Additionally, in
contrast to FPI-like methods in prior work where (i) and (ii) in Algorithm 1
are executed sequentially, Equation 14 updates both policy and population
concurrently using the same samples, enhancing the sample efficiency.
Algorithm 2 in Appendix H is an example of concrete realization of the
aformentioned ideas.

As our method is fully online, we need the following ergodicity assumption
(Zou et al., 2019).

######  Assumption 5.3.

For any $\pi\in\Gamma_{\pi}({\mathcal{Q}})$ and
$M\in{\mathcal{P}}(\mathcal{X})^{\mathcal{U}}$, the Markovian state dynamic is
ergodic: there exists
$\nu\in{\mathcal{P}}_{\mathrm{unif}}(\mathcal{U}\times{\mathcal{X}})$ and
$c_{1}>0$, $c_{2}\in(0,1)$ such that

$\sup_{x}\|{\mathcal{L}}(X_{\tau}\,|\,X_{0}=x)-\nu\|_{\mathrm{TV}}\leq
c_{1}c_{2}^{\tau},$

where the dynamic of $X$ is determined by policy $\pi$ and neighborhood
measure $\textsf{W}\bm{\Pi}_{D}M$.

Finally, we give the sample complexity of our algorithm.

######  Theorem 5.4.

Let $\widehat{\mu}$ be the stationary equilibrium measure of the infinite
horizon GMFG. Suppose Assumptions 5.1 and 5.3 hold. For any initial estimate
$M^{0,0}\in{\mathcal{P}}({\mathcal{X}})^{\mathcal{U}}$, Algorithm 1, combined
with Equation 14 and step sizes $\alpha_{\tau},\beta_{\tau}\asymp 1/\tau$,
finds an $\epsilon$-approximate equilibrium distribution $M^{K,H}$ such that
${\mathbb{E}}\|\bm{\Pi}_{D}M^{K,H}-\widehat{\mu}\|_{\mathrm{TV}}\leq\epsilon$,
with the number of iteration being at most

$\displaystyle K=O\left(\kappa^{-1}\log\epsilon^{-1}\right),\quad
D=O\left(\kappa^{-1}\epsilon^{-1}\right),\quad$ $\displaystyle
H=O\left(\kappa^{-3}\epsilon^{-3}\log\epsilon^{-1}\right),$

giving a total sample complexity of
$O\left(\kappa^{-5}\epsilon^{-4}\log^{2}\epsilon^{-1}\right)$.

We present a rephrase of Theorem 5.4 in Theorem H.3 that incorporates the
dependence on constants in Assumptions 5.1 and 5.3. The proof as well as more
details of our method are deferred to Appendix H.

##  6 Numerical Experiments

In this section, we apply our learning algorithm to three graphon game
examples, namely, Flocking-, SIS- and Invest-Graphon. We first briefly
introduce each game scenario, and present only the algorithm performance and
graphon mean-field equilibrium (GMFE) for Flocking-Graphon due to space limit.
The problem formulation of each game is in Appendix I. The detailed numerical
results are in J, including algorithm performance (e.g., exploitability,
convergence) and visualizations for GMFE. All numerical experiments are
conducted on Mac Air M2.

##### Flocking-Graphon

The flocking-graphon game (Lacker & Soret, 2022) studies the flocking behavior
in a system where each agent makes decisions on its velocity, which in turn
determines its position. We consider the game with ${\mathcal{X}}=[0,1]$, and
a time horizon $\mathbb{T}=[0,1]$, under proper discretization. An agent with
label $u$ and position $x$ randomly picks its velocity at time $t$ according
to the policy $\pi_{t}(u,x)\in{\mathcal{P}}(A)$ for action space $A=[0,1]$.
Each agent aims to minimize its own running cost determined by the velocity
control and the agent’s deviation from the population.

##### SIS-Graphon

The SIS-Graphon game (Cui & Koeppl, 2022) models an epidemic scenario where
agents can choose taking precautions to avoid being infected. The infected
probability is determined by the agents’ action (i.e., take precaution or not)
and the number of infected neighbors.

##### Invest-Graphon

In the Invest-Graphon game model (Cui & Koeppl, 2022), each firm aims to
maximize its own profit, which is determined by the firm’s investment
strategies and other firms’ product quality.

Figure 1: Algorithm performance (Flocking-Graphon)

We test four types of graphons: uniform attachment graphon
($W_{\mathrm{unif}}(u,v)=1-\max(u,v)$), ranked attachment graphon
($W_{\mathrm{rank}}(u,v)=1-uv$), Erdös-Rényi graphon
($W_{\mathrm{er}}(u,v)=p$) and threshold graphon
($W_{\mathrm{thresh}}(u,v)=\mathbf{1}_{u+v<1}$). Figure 1 demonstrates the
algorithm performance to solve the Flocking-Graphon. The x-axis denotes the
epoch index $k$. We visualize the convergence gaps
$|\mu^{(k)}-\mu^{(k-1)}|,|\pi^{(k)}-\pi^{(k-1)}|$, and the W1-distances
$|\mu^{(k)}-\mu^{*}|,|\pi^{(k)}-\pi^{*}|$, which measures the closeness
between the benchmark solution $(\pi^{*},\mu^{*})$ and results at each epoch.
The benchmark solution is obtained by the equivalent class method in (Cui &
Koeppl, 2022). The results show that it takes around 50 epochs for our
algorithm to converge. The convergence performance remains consistent for all
four graphons.

Figure 2: GMFE (Flocking-Graphon)

Figure 2 shows the obtained GMFE for Flocking-Graphon. We visualize the policy
and state density of agent with label $U=1$ at equilibrium in a 3D plot. The
x-axis denotes the space domain $\mathcal{X}$, and the y-axis is the time
horizon $\mathbb{T}$. Agent with each label is intialized at $t=0$ uniformly
over ${\mathcal{X}}$. Note that the GMFE is time-dependent, which is obtained
by adapting our learning algorithm to solve graphon games with finite horizons
(See Algo 3 in Appendix H). The z-axis is the spatial-temporal velocity
control $\alpha_{t}(1,x)$ and population density $\mu_{t}(1,x)$ of the agent
with label $1$. The numerical results show that GMFEs associated with
$W_{\mathrm{unif}}$ and $W_{\mathrm{thresh}}$ are similar. The flock behavior,
i.e. the phenomenon that players gather together without central planning at
some location as time goes by, occurs at position $x=0.6$ and the population
density $\mu$ reaches a red peak around $0.35$ with velocity around $0.2$.
When the agent’s velocity reaches the maximum velocity $\alpha_{max}=1$ (dark
red), the population quickly dissipates (dark blue) and no flock behavior
occurs.

##  7 Conclusion

We offer a new general formulation of graphon games with one representative
player in continuous state and action space. A comprehensive analysis on the
equilibrium properties is proved with assumptions milder than previous works.
We present a general approximate fixed-point iteration framework, and design
an oracle-free algorithm along with the sample complexity analysis.

## Broader Impact

This work is motivated by the theoretical challenges in the analysis of
graphon games. As a generalization to mean-field games, graphon games is
capable of modeling heterogeneous interactions among gaming participants, and
this flexibility allows it to cover a broader range of applications in
finance, economics, engineering, including for example high-frequency trading,
social opinion dynamics and autonomous vehicle driving. By addressing
rigorously the technical issues faced by games on networks, this work proposes
a conceptually and mathematically concise formulation. The analysis provides
concrete theoretical foundation for the mathematical properties, on top of
which the algorithms empower the solvability of the system. With the
comprehensive and self-consistent technical analysis, this work is capable of
modeling system with large amount of agents and remain computationally
efficient.

## References

  * Aliprantis & Border (2006) Aliprantis, C. D. and Border, K. C.  _Infinite Dimensional Analysis_.  Springer, 3rd edition, 2006.
  * Angiuli et al. (2022a) Angiuli, A., Fouque, J.-P., and Laurière, M.  Unified reinforcement q-learning for mean field game and control problems.  _Mathematics of Control, Signals, and Systems_ , pp. 1–55, 2022a.
  * Angiuli et al. (2022b) Angiuli, A., Fouque, J.-P., and Laurière, M.  Unified reinforcement q-learning for mean field game and control problems.  _Mathematics of Control, Signals, and Systems_ , pp. 1–55, 2022b.
  * Aurell et al. (2022) Aurell, A., Carmona, R., and Lauriere, M.  Stochastic graphon games: II. the linear-quadratic case.  _Applied Mathematics and Optimization_ , 85, 06 2022.
  * Billingsley (1995) Billingsley, P.  _Probability and Measure_.  John Wiley and Sons, 3rd edition, 1995.
  * Bris & Poquet (2023) Bris, P. L. and Poquet, C.  A note on uniform in time mean-field limit in graphs, 2023.
  * Brunick & Shreve (2013) Brunick, G. and Shreve, S.  Mimicking an ito process by a solution of a stochastic differential equiation.  _The Annals of Applied Probability_ , pp. 1584–1628, 2013.
  * Caines & Huang (2021) Caines, P. E. and Huang, M.  Graphon mean field games and their equations.  _SIAM Journal on Control and Optimization_ , 59(6):4373–4399, 2021.
  * Cardaliaguet & Hadikhanloo (2015) Cardaliaguet, P. and Hadikhanloo, S.  Learning in mean field games: the fictitious play.  _ESAIM: Control, Optimisation and Calculus of Variations_ , 23, 07 2015.  doi: 10.1051/cocv/2016004.
  * Carmona & Delarue (2018) Carmona, R. and Delarue, F.  _Probabilistic Theory of Mean Field Games with Applications I_.  Springer, 2018.
  * Carmona et al. (2021) Carmona, R., Cooney, D. B., Graves, C. V., and Laurière, M.  Stochastic graphon games: I. the static case.  _Mathematics of Operations Research_ , 47(1):750–778, 2021.
  * Chen et al. (2023a) Chen, X., FU, Y., Liu, S., and Di, X.  Physics-informed neural operator for coupled forward-backward partial differential equations.  In _ICML Workshop on the Synergy of Scientific and Machine Learning Modeling_ , 2023a.
  * Chen et al. (2023b) Chen, X., Liu, S., and Di, X.  A hybrid framework of reinforcement learning and physics-informed deep learning for spatiotemporal mean field games.  In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ , pp. 1079–1087, 2023b.
  * Chen et al. (2023c) Chen, X., Liu, S., and Di, X.  Learning dual mean field games on graphs.  In _Proceedings of the 26th European Conference on Artificial Intelligence, ECAI_ , 2023c.
  * Cui & Koeppl (2021) Cui, K. and Koeppl, H.  Approximately solving mean field games via entropy-regularized deep reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , 2021.
  * Cui & Koeppl (2022) Cui, K. and Koeppl, H.  Learning graphon mean field games and approximate nash equilibria.  In _International Conference on Learning Representations_ , 2022.
  * Cui et al. (2022) Cui, K., KhudaBukhsh, W. R., and Koeppl, H.  Hypergraphon mean field games.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , 32(11), 2022.
  * Delattre et al. (2016) Delattre, S., Giacomin, G., and Luçon, E.  A note on dynamical models on random graphs and fokker–planck equations.  _Publications of the Mathematical Institute of the Hungarian Academy of Sciences_ , 165:785–798, 2016.
  * Elie et al. (2020) Elie, R., P’erolat, J., Laurière, M., Geist, M., and Pietquin, O.  On the convergence of model free learning in mean field games.  In _AAAI_ , 2020.
  * Erdős & Rényi (1959) Erdős, P. and Rényi, A.  On random graphs. i.  _Publicationes Mathematicae_ , 6(3–4):290–297, 1959.
  * Erdős & Rényi (1960) Erdős, P. and Rényi, A.  On the evolution of random graphs.  _Publications of the Mathematical Institute of the Hungarian Academy of Sciences_ , 5:17–61, 1960.
  * Fabian et al. (2023) Fabian, C., Cui, K., and Koeppl, H.  Learning sparse graphon mean field games.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 4486–4514. PMLR, 2023.
  * Gao & Pavel (2017) Gao, B. and Pavel, L.  On the properties of the softmax function with application in game theory and reinforcement learning.  _arXiv preprint arXiv:1704.00805_ , 2017.
  * Gao et al. (2021) Gao, S., Tchuendom, R. F., and Caines, P. E.  Linear quadratic graphon field games.  _Communications in Information and Systems_ , 21(3):341–369, 06 2021.
  * Guo et al. (2019a) Guo, X., Hu, A., Xu, R., and Zhang, J.  Learning mean-field games.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019a.
  * Guo et al. (2019b) Guo, X., Hu, A., Xu, R., and Zhang, J.  Learning mean-field games.  _Advances in Neural Information Processing Systems_ , 32, 2019b.
  * Huang et al. (2020) Huang, K., Di, X., Du, Q., and Chen, X.  A game-theoretic framework for autonomous vehicles velocity control: Bridging microscopic differential games and macroscopic mean field games.  _Discrete and Continuous Dynamical Systems - Series B_ , 25(12):4869–4903, 2020.
  * Huang et al. (2006) Huang, M., Malhamé, R. P., and Caines, P. E.  Large population stochastic dynamic games: closed-loop Mckean-Vlasov systems and the Nash certainty equivalence principle.  _Communications in Information & Systems_, 6(3):221–252, 2006.
  * Jabin et al. (2022) Jabin, P.-E., Poyato, D., and Soler, J.  Mean-field limit of non-exchangeable systems, 2022.
  * Lacker (2015) Lacker, D.  Mean field games via controlled martingale problems: Existence of markovian equilibria.  _Stochastic Processes and their Applications_ , 23(4):2856–2894, 2015.
  * Lacker (2018) Lacker, D.  Mean field games and interacting particle systems.  _preprint_ , 2018.
  * Lacker & Soret (2022) Lacker, D. and Soret, A.  A label-state formulation of stochastic graphon games and approximate equilibria on large networks.  _Mathematics of Operations Research_ , 2022.
  * Lacker et al. (2023) Lacker, D., Ramanan, K., and Wu, R.  Local weak convergence for sparse networks of interacting processes.  _The Annals of Applied Probability_ , 33(2):843 – 888, 2023.
  * Lasry & Lions (2007) Lasry, J.-M. and Lions, P.-L.  Mean field games.  _Japanese Journal of Mathematics_ , 2(1):229–260, 2007.
  * Lauriere et al. (2022) Lauriere, M., Perrin, S., Girgin, S., Muller, P., Jain, A., Cabannes, T., Piliouras, G., Perolat, J., Elie, R., Pietquin, O., and Geist, M.  Scalable deep reinforcement learning algorithms for mean field games.  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 12078–12095. PMLR, 2022.
  * Littman (1994) Littman, M. L.  Markov Games As a Framework for Multi-agent Reinforcement Learning.  In _Proceedings of the Eleventh International Conference on International Conference on Machine Learning_ , ICML’94, pp. 157–163, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc.  ISBN 978-1-55860-335-6.  event-place: New Brunswick, NJ, USA.
  * Lovász (2012) Lovász, L.  _Large networks and graph limits_ , volume 60.  American Mathematical Soc., 2012.
  * Mitrophanov (2005) Mitrophanov, A. Y.  Sensitivity and convergence of uniformly ergodic markov chains.  _Journal of Applied Probability_ , 42(4):1003–1014, 2005.
  * Perrin et al. (2020) Perrin, S., Perolat, J., Laurière, M., Geist, M., Elie, R., and Pietquin, O.  Fictitious play for mean field games: Continuous time analysis and applications.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20, 2020.
  * Perrin et al. (2021) Perrin, S., Laurière, M., Pérolat, J., Geist, M., Élie, R., and Pietquin, O.  Mean field games flock! the reinforcement learning way.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pp. 356–362, 2021.
  * Perrin et al. (2022) Perrin, S., Laurière, M., Pérolat, J., Élie, R., Geist, M., and Pietquin, O.  Generalization in mean field games by learning master policies.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 9413–9421, 2022.
  * Solan & Vieille (2015) Solan, E. and Vieille, N.  Stochastic games.  _Proceedings of the National Academy of Sciences_ , 112(45):13743–13746, 2015.
  * Sun (2006) Sun, Y.  The exact law of large numbers via fubini extension and characterization of insurable risks.  _Journal of Economic Theory_ , 126:31–69, 2006.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tangpi & Zhou (2023) Tangpi, L. and Zhou, X.  Optimal investment in a large population of competitive and heterogeneous agents, 2023.
  * Tuzel et al. (2017) Tuzel, O., Fleming, C., and Marcon, G.  Learning flocking control in an artificial swarm.  _Neural Information Processing Systems_ , 2017.
  * Wang et al. (2020) Wang, L., Yang, Z., and Wang, Z.  Breaking the curse of many agents: Provable mean embedding q-iteration for mean-field reinforcement learning.  In _International conference on machine learning_ , pp. 10092–10103. PMLR, 2020.
  * Yang et al. (2018a) Yang, J., Ye, X., Trivedi, R., Xu, H., and Zha, H.  Deep mean field games for learning optimal behavior policy of large populations.  In _International Conference on Learning Representations_ , 2018a.
  * Yang et al. (2018b) Yang, Y., Luo, R., Li, M., Zhou, M., Zhang, W., and Wang, J.  Mean Field Multi-Agent Reinforcement Learning.  In _International Conference on Machine Learning_ , pp. 5571–5580, July 2018b.
  * Zhang et al. (2024) Zhang, C., Chen, X., and Di, X.  A single online agent can efficiently learn mean field games.  _arXiv preprint arXiv:2405.03718_ , 2024.
  * Zhang et al. (2023) Zhang, F., Tan, V. Y., Wang, Z., and Yang, Z.  Learning regularized monotone graphon mean-field games.  _Neural Information Processing Systems_ , 2023.
  * Zou et al. (2019) Zou, S., Xu, T., and Liang, Y.  Finite-sample analysis for sarsa with linear function approximation.  _Advances in neural information processing systems_ , 32, 2019.

## Organization of Appendix

The appendix is outlined as follows.

Appendix A is a discussion section serving as a supplement to the concepts in
the main paper. The topics include: the infinite horizon version of graphon
game formulation (Section A.1), formulating the graphon game into a mean-field
game with augmented state space (Section A.2), the degeneration of graphon
game to mean-field games with trivial graphon (Section A.3), time-variant
interaction intensities (Section A.4), dense graph sequence and examples
(Section A.5), fixed point theorems and the contraction mapping assumption
(Section A.6).

Appendix B provides a list of tables where we compare our novelty and
improvement to prior works.

In Appendix C, we define the continuum-player formulation (Section C.1) and
discuss in detail the aforementioned measurability issue residing in
continuum-player formulation in Section C.2. We then give a toy example in
Appendix D to demonstrate the difference on the two formulations.

The following three appendix are dedicated to the proof of analysis
properties. The existence of equilibrium (Theorem 4.4) is proved in Appendix
E. The uniqueness of equilibrium (Theorem 4.6) is proved in Appendix F. The
approximate equilibrium (Theorem 4.8) is proved in Appendix G.

In Section H.1 we give a concrete realization of algorithm discussed in
Section 5.3, and the rest of Appendix H is dedicated to the proof of the
sample complexity of learning algorithms (Theorem 5.4). Finally, we give the
detailed problem setups for the numerical examples in Appendix I, and show the
numerical results in Appendix J.

##  Appendix A Additional Discussion

###  A.1 Infinite horizon formulation

In this section we define the infinite horizon version of the representative-
player graphon game, as appose the the finite horizon version defined in
section 4.1. All analysis results in section 4 regarding existence, uniqueness
and approximate equilibrium holds by adjusting the assumptions accordingly.

Let the graphon $W\in L^{1}_{+}[0,1]^{2}$ be given and fixed. Let
$(\Omega,{\mathcal{F}},\mathbb{F},{\mathbb{P}})$ be a filtered probability
space that support an ${\mathcal{F}}_{0}$-measurable random variable $U$
uniform on $[0,1]$, and a Markov process $X$ valued in ${\mathbb{R}}^{d}$. We
understand $U$ as the label for the representative player, and $X$ as her
state dynamic. Let the flow of label-state joint measures be
$\mu\in{\mathcal{P}}_{\text{unif}}([0,1]\times{\mathcal{C}})$, where the path
space ${\mathcal{C}}=\prod_{i=0}^{\infty}{\mathbb{R}}^{d}$ is now a countable
product of ${\mathbb{R}}^{d}$.
$\mu_{t}\in{\mathcal{P}}_{\text{unif}}([0,1]\times{\mathbb{R}}^{d})$ is the
marginal under image $(u,x)\mapsto(u,x_{t})$. Let the initial joint law
$\lambda:={\mathcal{L}}(U,X_{0})\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathbb{R}}^{d})$
be given.

We still let ${\mathcal{A}}_{U}$ denotes the collection of time-variant
closed-loop (Markovian) policies
${\mathbb{N}}_{+}\times[0,1]\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$. For
any $\pi\in{\mathcal{A}}_{U}$, $(U,X)$ follows the transition dynamic

$\displaystyle(U,X_{0})\sim\lambda$ $\displaystyle
a_{t}\sim\pi_{t}(U,X_{t})\qquad X_{t+1}\sim
P(X_{t},\textsf{W}\mu_{t}(U),a_{t})$

at any time $t\in{\mathbb{N}}_{+}$. Note that the transition law $P$ is time-
invariant. Let
$f:{\mathbb{R}}^{d}\times{\mathcal{M}}_{+}({\mathbb{R}}^{d})\times
A\to{\mathbb{R}}$ be the running reward and $\gamma\in(0,1)$ be a known
discount factor. The objective of the representative player is to choose
$\pi\in{\mathcal{A}}_{U}$ to maximize

$\displaystyle J_{W}(\mu,\pi)$
$\displaystyle={\mathbb{E}}\bigg{[}\sum_{t=0}^{\infty}\gamma^{t}f(X^{\pi}_{t},\textsf{W}\mu_{t}(U),a_{t})\bigg{]}$

######  Definition A.1.

We say that
$(\widehat{\mu},\widehat{\pi})\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})\times{\mathcal{A}}_{U}$
is a $W$-equilibrium if

$\displaystyle J_{W}(\widehat{\mu},\widehat{\pi})$
$\displaystyle=\sup_{\pi\in{\mathcal{V}}_{U}}J_{W}(\widehat{\mu},\pi)$
$\displaystyle\widehat{\mu}$
$\displaystyle={\mathcal{L}}(U,X^{\widehat{\pi}})\quad$

If we do not fix an initial distribution $\lambda$, we may define a stationary
equilibrium which is time independent:

######  Definition A.2.

We say that
$(\widehat{\mu},\widehat{\pi})\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathbb{R}}^{d})\times{\mathcal{A}}_{U}$
is a stationary $W$-equilibrium if

$\displaystyle J_{W}(\widehat{\mu},\widehat{\pi})$
$\displaystyle=\sup_{\pi\in{\mathcal{A}}_{U}}J_{W}(\widehat{\mu},\pi)$
$\displaystyle\widehat{\mu}$
$\displaystyle={\mathcal{L}}(U,X^{\widehat{\pi}}_{t})\qquad\forall t\geq 0$

where ${\mathcal{A}}_{U}$ now denotes the collection of time-invariant closed-
loop policies $[0,1]\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$.

Note that we need an additional ergodicity assumption of the Markov chain to
show the existence of stationary $W$-equilibrium with the same proof argument
in Appendix E, i.e. the Markov chain admits a stationary distribution under
any policy. A sufficient condition for ergodicity is given in 5.3.

###  A.2 Game with Augmented State Space

We give another view of graphon game by reformulating it into a mean-field
game with augmented state space. We view the label $U$ as a coordinate of the
state, and it remains at the same value a.s. Let
$\overline{X}_{t}=\binom{U}{X_{t}}\in{\mathbb{R}}^{d+1}$, where the state
process space is augmented by one more dimension. Any fixed
$\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$ can now be
equivalently regarded as an element in ${\mathcal{P}}({\mathcal{C}}^{d+1})$
where ${\mathcal{C}}^{d+1}=({\mathbb{R}}^{d+1})^{T+1}$ is the augmented path
space. More specifically, we denote
$\mu_{t}:=\mu\circ(U,X_{t})^{-1}\in{\mathcal{P}}({\mathbb{R}}^{d+1})$, where
$\circ$ is the pushforward. Given any graphon closed-loop policy
$\pi\in{\mathcal{A}}_{U}$, define a mean-field closed-loop policy
$\overline{\pi}$ and a mean-field Markovian transition law $\overline{P}$ as
follows. For every $\overline{x}=\binom{u}{x}\in{\mathbb{R}}^{d+1}$,

$\displaystyle\overline{\pi}_{t}(\overline{x})(da):=\pi_{t}(u,x)(da)$
$\displaystyle\overline{P}_{t}(\overline{x},m,a)(d\overline{y}):=\delta_{u}(dv)P_{t}(x,\textsf{W}m(u),a)(dy)\quad\forall\overline{y}=\binom{v}{y}$

respectively and let $\overline{\lambda}(d\overline{y}):=\lambda(dv,dy)$ for
any $\overline{y}=\binom{v}{y}$ be the mean-field intial condition. Then
$\overline{X}$ satisfies the dynamic

$\displaystyle\overline{X}_{0}\sim\overline{\lambda}$ $\displaystyle
a_{t}\sim\overline{\pi}_{t}(\overline{X}_{t})\qquad\overline{X}_{t+1}\sim\overline{P}_{t}(\overline{x},\mu_{t},a_{t})$

Define similarly for every $\overline{x}=\binom{u}{x}\in{\mathbb{R}}^{d+1}$
the reward functions

$\displaystyle\overline{f}_{t}(\overline{x},m,a):=f_{t}(x,\textsf{W}m(u),a)$
$\displaystyle\overline{g}(\overline{x},m):=g(x,\textsf{W}m(u))$

for all $t\in{\mathbb{T}}$. The objective is recast into

$\displaystyle
J(\overline{\pi}):={\mathbb{E}}\left[\sum_{t\in{\mathbb{T}}}\overline{f}_{t}(\overline{X}^{\overline{\pi}}_{t},\mu_{t},a_{t})+\overline{g}(\overline{X}^{\overline{\pi}}_{T},\mu_{T})\right]$

thus we have obtained a classic mean-field game problem associated with the
new coefficients
$\overline{\lambda},\overline{P}_{t},\overline{f}_{t},\overline{g}$. Note that
their implicit dependence on $W$.

However, it is worth noticing that in most of the proofs for graphon game,
this translation into mean-field game with augmented state space does not
simplify the mathematical analysis, and it is not appropriate to adapt the
mean field game results directly. There are two main reasons (Lacker & Soret,
2022):

Firstly, it requires the graphon $W\in L^{1}_{+}[0,1]^{2}$ to be continuous.
To see this, recall that most of the results for classic mean-field games
assume the joint continuity of reward function, see e.g. (Carmona & Delarue,
2018; Lacker, 2018). In particular,
$\overline{f}_{t}(\overline{x},m,a):=f_{t}(x,\textsf{W}m(u),a)$ is assumed to
be continuous in the augmented state variable $\overline{x}=(u,x)^{\top}$.
This requires the graphon operator $\textsf{W}\mu$ viewed as a function

$\displaystyle[0,1]\ni u\mapsto\textsf{W}\mu(u)\in{\mathcal{M}}_{+}(E)$

should be continuous, for any $\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times
E)$, which is satisfied by a continuous graphon. However, the graphon is in
general not a continuous function. Indeed many commonly encountered convergent
graph sequence tends to a discontinuous graphon limit, see for instance
examples in (Lovász, 2012) section 11.4.

Second, in the analysis of approximate equilibrium, the model setting for the
finite-player game does not fit into this augmented state space framework.
Consider an $n$-player game associated with interaction matrix
$\xi\in{\mathbb{R}}_{+}^{n\times n}$, and assign player $i$ the label
$u_{i}\in I^{n}_{i}$. Recall the setting for finite player games in section 3,
the running reward can be written as
$f_{t}(X^{i}_{t},\textsf{W}_{\xi}S_{t}(u_{i}),a^{i}_{t})$, where $S$ is the
empirical label-state measure defined in (4). On the other hand, let
$\overline{X}^{i}_{t}=\binom{u_{i}}{X^{i}_{t}}$, and the running cost of
player $i$ in the aformentioned augmented state space framework is

$\displaystyle\overline{f}_{t}(\overline{X}^{i},S_{t},a^{i}_{t}):=f_{t}(X^{i},\textsf{W}S_{t}(u_{i}),a^{i}_{t})$

which is different from the originial problem, as in the finite player game
the graphon $W$ needs to be replaced with the step graphon $W_{\xi}$. However,
it is not possible to incorperate this change in the augmented state space
framework. As a result the augmented state space transformation fails to
provide an approximate equilibrium result, which is a strong justification of
the reasonableness of graphon game formulation.

In continuous time setting (Lacker & Soret, 2022), the augmented state space
formulation provides an equivalent forward-backward PDE system for the graphon
game, and thus provides another perspective to the problem formulation.

Actually the continuum-player graphon games may be transformed to a mean-field
game with augmented state space in a similar way, and many previous works on
continuum-player formulation relied on this (Cui & Koeppl, 2022; Zhang et al.,
2023) to show existence of equilibrium. However, they not only suffer from the
two limitations mentioned above, but also encounter a critical measurability
issue that representative-player formulation does not have, and this leads to
difficulties in the proof. We will discuss this point in detail in Appendix C.

###  A.3 Degeneration to mean-field games under trivial graphon

When the graphon $W\equiv 1$, the interactions among players are symmetric,
and we illustrate that our graphon game formulation degenerates to the classic
mean-field game.

let the initial distribution $\lambda$, which is a product measure with the
path space marginal $\lambda^{\circ}$, be given. Fix a population measure
$\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$ and assume it
takes the product measure form: $\mu(du,dx)=du\times\nu(dx)$ for some
$\nu\in{\mathcal{P}}({\mathcal{C}})$. The graphon operator applied on $\mu$
degenerates to $\nu$:

$\displaystyle\textsf{W}\mu(u)=\int_{[0,1]\times{\mathcal{C}}}\delta_{x}\mu(dv,dx)=\int_{{\mathcal{C}}}\delta_{x}\nu(dx)\qquad\forall
u\in[0,1]$

For any closed-loop policy $\pi\in{\mathcal{A}}_{U}$ that depends only on the
state variable, i.e. $\pi$ is a function
${\mathbb{T}}\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$, $(U,X)$ follows the
transition dynamic: $U\sim\mathrm{unif}[0,1]$, $X_{0}\sim\lambda^{\circ}$ and

$\displaystyle a_{t}\sim\pi_{t}\qquad X_{t+1}\sim P_{t}(X_{t},\nu_{t},a_{t})$

note that $U$ and $X$ are now independent. The objective of the representative
player becomes

$\displaystyle J_{W}(\nu,\pi)$
$\displaystyle={\mathbb{E}}\bigg{[}\sum_{t\in{\mathbb{T}}}f_{t}(X^{\pi}_{t},\nu_{t},a_{t})+g(X_{T}^{\pi},\nu_{T})\bigg{]}$

where the expectation is w.r.t $X$ only, thanks to the independence between
$U$ and $X$. In this way our label-state graphon game formulation degenerates
to a classic mean-field game problem. The equilibrium measure and controls
indeed does not depend on the label, and thus it is safe to restrict to $\mu$
being a product measure and policies not depending on label at the beginning.

###  A.4 Time-variant interaction intensity

It is possible to consider time-variant interaction intensity in our framework
when the time horizon is finite. In definition of finite player games (section
3), we may replace $\xi$ with a sequence of matrix $\\{\xi^{t}\\}_{t=0}^{T}$,
where $\xi^{t}$ is the interaction intensity of the $n$ players at time $t$.
The empirical weighted neighborhood measure of player $i$ then becomes
$M^{i}_{t}=\frac{1}{n}\sum_{i=1}^{n}\xi^{t}_{ij}\delta_{X^{j}_{t}}$, and it
can be equivalently written as $W_{\xi^{t}}S_{t}(u_{i})$, in the notation of
section 3.

In the graphon game setting (section 4.1), we may work on a sequence of
graphon $\\{W_{t}\\}_{t=0}^{T}$, where $W_{t}$ is the interaction among a
continuum types of players at time $t$. Note that the sequence
$\\{W_{t}\\}_{t=0}^{T}$ should be non-random. By replacing every
$\textsf{W}\mu_{t}$ with $\textsf{W}_{t}\mu_{t}$, it is ready to check that
the existence (section 4.2) and uniqueness (section 4.3) results still holds.
As for the approximate equilibrium result (section 4.4), we may change
assumption 4.7(1) into the following: $W_{\xi^{n,t}}\rightarrow W_{t}$, and

$\displaystyle\lim_{n\to\infty}\sup_{t\in{\mathbb{T}}}\frac{1}{n^{3}}\sum_{i,j=1}^{n}(\xi^{n,t}_{ij})^{2}=0.$

Then the approximate equilibrium result still holds. We present the main paper
in terms of a time-invariant graphon $W$ to avoid distraction from the main
point we want to address.

###  A.5 Graph sequence and the convergence assumption 4.7

Conceptually, a graph is dense if nearly every pair of vertices are connected
by an edge. However rigorously, the denseness of graph is ill-defined, and
different results require different denseness conditions.

We first demonstrate that assumption equation (10) is indeed very mild. We may
write ${\mathrm{Tr}}((\xi^{n})^{2})=\sum_{i,j=1}(\xi^{n}_{ij})^{2}$ where
${\mathrm{Tr}}(\cdot)$ is the trace, and this is referred as second moment of
square matrix. Here are several examples on commonly-encountered interaction
matrix on networks.

Complete graph. Let $\xi^{n}_{ij}=1$ for each $i\neq j$, and thus $\xi^{n}$ is
the adjacency matrix of a complete graph, and this recovers the mean-field
case where the players interacts symmetrically. We have $W_{\xi^{n}}\equiv 1$
for all $n$, and thus $W_{\xi^{n}}\to W$ for $W\equiv 1$. We have

$\displaystyle\frac{1}{n^{3}}\sum_{i,j=1}^{n}(\xi^{n}_{ij})^{2}\leq\frac{1}{n}\to
0$

Threshold graph. Consider a threshold graph on $n$ vertices where vertex $i$
and $j$ are connected by an edge if $i+j<n$, and let $\xi^{n}_{ij}=1_{i+j<n}$.
It is easy to see that $W_{\xi^{n}}$ converges in cut norm to a limit defined
by $W(u,v):=1_{u+v<1}$. It is ready to check that assumption equiation (10) is
satisfied.

Random walk on graph. Consider a graph on $n$ vertices where vetex $i$ has
degree $d^{n}_{i}$. Let $\xi^{n}_{ij}=\frac{n}{d^{n}_{i}}1_{i\sim j}$, where
$1_{i\sim j}$ is 1 if $i$ and $j$ are connected by an edge and 0 otherwise.
Then $\xi/n$ is a Markovian transition matrix of the random walk on the graph.
We have

$\displaystyle\frac{1}{n^{3}}\sum_{i,j=1}^{n}(\xi^{n}_{ij})^{2}=\frac{1}{n}\sum_{i,j=1}^{n}\frac{1}{(d^{n}_{i})^{2}}1_{i\sim
j}=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{d^{n}_{i}}$

and the assumption holds if $\sum_{i=1}^{n}\frac{1}{d^{n}_{i}}\to 0$.
Intuitively this means the average of degrees diverges. In particular, if
$d^{n}_{1}=\dots=d^{n}_{n}=d^{n}$, $\xi^{n}$ becomes an interaction matrix on
a $d^{n}$-regular graph, and we just need $\frac{1}{d_{n}}\to 0$, i.e. the
degree $d^{n}$ diverges to satisfies equation (10). However, not even every
sequence of regular graphs has a graphon limit, and we will discuss this
below.

Erdös-Rényi graph. Consider an Erdös-Rényi graph $G^{n}(p_{n})$ (Erdős &
Rényi, 1959) on $n$ vertices, where every edge is connected with
Bernoulli$(p_{n})$. Let $\xi^{n}_{ij}=\frac{1}{p_{n}}1_{i\sim j}$, it is not
hard to show that equation (10) holds in probability as long as
$np_{n}\to\infty$. We understand $np_{n}$ as the expected degree of any
vertex, and this is an important quantity of Erdös-Rényi graphs that also
implies connectivity (Erdős & Rényi, 1960). Moreover, when $p_{n}\to p$ for
some $p\in(0,1)$, $W_{\xi^{n}}\rightarrow W$ for $W\equiv 1$ in probability.

All examples mentioned above merely requires a diverging-average-degree type
condition to be considered dense enough for our results to hold. These
denseness conditions are attracting more and more awareness in the stochastic
community and particularly in the studies of stochastic differential equation
dynamics and heterogenous propogation of chaos on networks (Delattre et al.,
2016; Bris & Poquet, 2023; Jabin et al., 2022).

The assumption $W_{\xi^{n}}\to W$ is also a denseness condition as the
existence of a graphon limit implicitly implies that the converging graph
sequence is generally dense. Actually in the sparse setting, vertices in a
local neighborhood interact strongly with each other and do not become
negligible as the number of vertices goes to infinity (Lacker et al., 2023).
The propogation of chaos results also fail in this regime. Nevertheless, not
every dense graph sequence necessarily admits a graphon limit, since the
sequence is also required to preserve similar network structures. This can be
formalized by graph homomorphism [(Lovász, 2012) chapter 5].

It is worth noticing that a sequence of sparse graphs may converge if they are
sampled from the limiting graphon. There are works (Fabian et al., 2023)
adopting this setting. However conceptually this means the finite player games
are constructed from the graphon game, which is different from the view we
take, that graphon games are motivated by finite player games.

Finally, we demonstrate that the convergence of graphon in strong operator
topology is weaker than converging in other norm. Recall the definition of
integral operator in equation (2):

$\displaystyle\textsf{W}\phi(u):=\int_{[0,1]}W(u,v)\phi(v)dv\quad\forall\phi\in
L_{\infty}[0,1]$

which maps $L_{\infty}[0,1]$ to $L_{1}[0,1]$. The integral operator norm is
given by $\|\textsf{W}\|_{\infty\to 1}:=\sup_{\|\phi\|_{\infty}\leq
1}\|\textsf{W}\phi\|_{1}$, where $\|\cdot\|_{p}$ is the $L_{p}$ norm. It is
known to be equivalent to the cut norm [(Lovász, 2012) lemma 8.11] by

$\displaystyle\|W\|_{\mathord{\scalerel*{\Box}{gX}}}\leq\|\textsf{W}\|_{\infty\to
1}\leq 4\|W\|_{\mathord{\scalerel*{\Box}{gX}}}$ (15)

where the cut norm of a graphon is defined by

$\displaystyle\|W\|_{\mathord{\scalerel*{\Box}{gX}}}:=\sup_{S,T\subset[0,1]}\left|\int_{S\times
T}W(u,v)dudv\right|$

for measurable subsets $S,T$. It is immediate from (15) that the convergence
in strong operator topology is weaker than converging in the cut norm. Indeed
$W^{n}$ converging to $W$ in $L_{1}$ also implies $W^{n}\to W$, see Lemma E.3.

###  A.6 Fixed point theorems and strong assumptions for sample complexity
analysis

There are two main stream fixed point theorems. The first type is based on
contraction mapping, that if an operator is contraction in norm, then it
admits a fixed point. An example of this catagory is the well-known Banach
fixed point theorem. The second type, on the other hand, is usually based on
the compact properties of the range space and operator, this includes
Brouwer’s fixed point theorem (compact, covex range space and continuous
operators), Schauder’s fixed point theorem (closed, bounded, convex range
space and compact operators), and Kakutani-Fan-Glicksberg fixed point theorem
for set-value functions, which is the one we will use in the proof of
equilibrium existence (Appendix E). Compact-based fixed point theorems require
weaker assumptions, but they fail to indicate how to find a fixed point rather
than telling its theoretical existence.

Contraction based fixed point theorems usually have stronger assumptions, and
the contraction in norm property is hard to verify practically. However, it
provides clear approaches to find the fixed point when one exists: starting
from an appropriate initial point, we may iteratively apply the operator and
the result is guaranteed to converge to a fixed point. This iteration comes
naturally from the forward-backward structure of games: players give their
best response, and the population changes according to everyone’s best
response.

Many algorithms on mean-field type games are based on the contraction fixed
point theorem and iteration (Guo et al., 2019a; Cui & Koeppl, 2022), including
our work. These algorithms usually try to approximate the contraction mapping
with estimations (since the environment is usually unknown) in order to
demonstrates the convergences of algorithm. Thus the contraction mapping
Lipschitzness assumptions are unfortunately necessary in complexity analysis
proofs (see 5.1(3)), even though we do not make such assumptions in pure
mathematical analysis in section 4.

There is a trade-off between the nice properties of the algorithm and a
relatively weaker assumption. In our work, we focus on an algorithm that is
online and oracle-free with convergence guarantees, which is proved based on
existing reinforcement learning complexity results that require stronger
assumptions (see for example Lemma H.5 and Lemma H.6). On the other end of the
trade-off, we may consider algorithms that require weaker assumption, but do
not enjoy theoretical convergence guarantees. Designing sharper quantitative
convergence result for reinforcement learning algorithms is beyond the scope
of this work.

##  Appendix B Comparison with Related Works

In this section we give a comparison with related prior works in discrete-time
graphon games, and representative-player graphon games. The comparison is
facilitated from four aspects, in terms of the difference on problem
formulation (Table 1), the analysis results showed (Table 2), the assumptions
needed for existence and approximate equilibrium (Table 3), and the properties
of the proposed learning algorithms (Table 4).

Table 1: Comparison of formulation

Reference | Player-type | Time domain | State space | Action space | Entropic regularization
---|---|---|---|---|---
(Cui & Koeppl, 2022) | Continuum | Discrete | Finite | Finite | ✗
(Fabian et al., 2023) 333We note that (Fabian et al., 2023) considers a sparse type of graphon convergence with a factor that mitigates the sparseness, and adopts a sampling regime where the finite player interactions are sampled from a graphon. This is different from the other works where the graphon games are considered to be the limit model of finite player network games. | Continuum | Discrete | Finite | Finite | ✗
(Zhang et al., 2023) | Continuum | Discrete | Compact | Finite | ✓
(Lacker & Soret, 2022) | Representative | Continuous | ${\mathbb{R}}^{d}$ | Compact | ✗
This paper | Representative | Discrete | ${\mathbb{R}}^{d}$ | Compact | ✗

Table 2: Comparison of analysis results

Reference | Existence | Uniqueness | Approximate Equilibrium
---|---|---|---
(Cui & Koeppl, 2022) | ✓ | ✗ | ✓
(Fabian et al., 2023) | ✓ | ✗ | ✓
(Zhang et al., 2023) | ✓ | ✓ | ✗
(Lacker & Soret, 2022) | ✓ | ✓ | ✓
This paper | ✓ | ✓ | ✓

Table 3: Comparison of analysis assumptions

Reference |  | Existence assumptions |  | Approx. eqbm. assumptions |
---|---|---|---|---|---
Perspective | Graphon | Transition kernel | Reward function | Transition kernel | Graphon convergence
(Cui & Koeppl, 2022) | Jointly Lipschitz | Jointly Lipschitz | Jointly Lipschitz | Jointly Lipschitz | In cut norm
(Fabian et al., 2023) | Jointly Lipschitz | Jointly Lipschitz | Jointly Lipschitz | Jointly Lipschitz | In cut norm
(Zhang et al., 2023) | Jointly cont. | Jointly cont. | Jointly cont. | NA | NA
This paper |  $L_{1}$-integrable | Cont. in action | Jointly cont. | Jointly cont. | In strong operator norm

Table 4: Comparison of Algorithm Analysis

Reference | Oracle-free | MFG criterion | Graphon |  | Complexity
---
analysis
(Cui & Koeppl, 2022) | ✓ | Contractive | Block-wise jointly Lipschitz | ✗ |
(Fabian et al., 2023) | ✗ | Monotone | Block-wise jointly Lipschitz | ✗ |
(Zhang et al., 2023) | ✗ | Monotone | Jointly Lipschitz | ✓ – 444 The sample complexity in (Zhang et al., 2023) is partially stated for the backward part, i.e. the best response of players to a fixed population distribution, without discussing the complexity of obtaining an estimate of the induced population measure in the forward step. |
This paper | ✓ | Contractive | Asymptotic cont. | ✓ |

As a comparison with the pioneering work in representative graphon game
(Lacker & Soret, 2022), the discrete-time game model proposed in this paper is
more realistic and strongly associated with the applications and lends itself
well to RL algorithm design as existing algorithms and analytical results for
RL are mostly given on a discrete time domain.

In addition, the discrete-time formulation, defined with transition kernels
directly, covers a broader range of state dynamics. Consider a partition of
the continuous-time domain $[0,S]$ into $N+1$ time slices with a time step
$\Delta:=S/N$, and $s_{k}:=k\Delta$, then the SDE can be discretized on the
time slices $\\{s_{k}\\}_{k=0}^{N}$, resulting in a discrete-time Markov
process. In other words, every state Ito’s process of the form
$dX_{s}=b(s,X_{s},\alpha_{s})ds+\sigma(s,X_{s})dB_{s}$ can be discretized into
the form $X_{t+1}\sim P_{t}(X_{t},\textsf{W}\mu_{t}(U),\alpha_{t})$ for some
Markovian transition kernel $P_{t}$. On the other hand, not every discrete
time Markov process (with a general transition kernel $P_{t}$) has a
continuous time analog in the form of an Ito’s process. It is actually a
trade-off: we sacrifice information on time domain by evaluating the state
process only on discrete time slices rather than a complete path on $[0,T]$,
but may cover a broader range of possible state dynamics in our framework.

##  Appendix C Comparing Representative-player Games and Continuum-player
Games

###  C.1 Continuum-Player Graphon Game

In this section we give a review on continuum-player graphon games in previous
works. Consider a game with a continuum of players, labeled with $u\in[0,1]$,
and we assume the label space $[0,1]$ is equipped with Borel-$\sigma$-algebra
and Lebesgue measure. Each player $u$ admits a state process $X^{u}$ valued in
${\mathbb{R}}^{d}$. Fix a population measure, which is a collection
$\mu=\\{\mu^{u}\\}_{u\in[0,1]}$, and it is usually an assumption that
$u\mapsto\mu^{u}$ is a probabilistic kernel, i.e. $u\mapsto\mu^{u}(B)$ is a
measureable function for any Borel subset $B\subset{\mathcal{C}}$. Let
${\mathcal{A}}$ be the collection of all the feedback (closed-loop) policies
${\mathbb{T}}\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$, and assume player $u$
adopts a policy $\pi^{u}\in{\mathcal{A}}$, the state process follows

$\displaystyle X^{u}_{0}\sim\lambda^{u}$ $\displaystyle
a^{u}_{t}\sim\pi^{u}_{t}(X^{u}_{t})\qquad X^{u}_{t+1}\sim
P_{t}(X^{u}_{t},\textsf{W}\mu_{t}(u),a_{t})$

for some initial condition $\lambda^{u}\in{\mathcal{P}}({\mathbb{R}}^{d})$.
Here we regard $\mu$ as a measure constructed by $du\times\mu^{u}(dx)$, where
the assumption $\mu$ being a kernel come into place. It is also common to
write $\int_{[0,1]}W(u,v)\mu^{v}_{t}dv$.

Note that all the players’ state dynamics are independent, in the following
sense: for every $u\in[0,1]$, $X^{u}$ is independent of $X^{v}$ for every
$v\in[0,1]$. Indeed this independence leads to a significant measurability
issue that many proofs ignore, and we will give a detailed discussion in
Section C.2.

Each player $u$ aims to maximize an objective function

$\displaystyle J^{u}(\mu,\pi^{u}):={\mathbb{E}}\bigg{[}$
$\displaystyle\sum_{t\in{\mathbb{T}}}f_{t}(X^{u,\pi^{u}}_{t},\textsf{W}\mu_{t}(u),a^{u}_{t})+g(X_{T}^{u,\pi^{u}},\textsf{W}\mu_{T}(u))\bigg{]}$

where we denote $X^{u,\pi^{u}}$ to emphasize the process $X^{u}$ is controlled
by policy $\pi^{u}$. The equilibrium is defined as a pair
$(\widehat{\boldsymbol{\mu}},\widehat{\boldsymbol{\pi}}):=(\\{\widehat{\mu}^{u}\\}_{u\in[0,1]},\\{\widehat{\pi}^{u}\\}_{u\in[0,1]})\in{\mathcal{P}}({\mathcal{C}})^{[0,1]}\times{\mathcal{A}}^{[0,1]}$
such that

$\displaystyle J^{u}(\widehat{\bm{\mu}},\widehat{\pi}^{u})$
$\displaystyle=\sup_{\pi\in{\mathcal{A}}}J^{u}(\widehat{\boldsymbol{\mu}},\pi)$
$\displaystyle\widehat{\mu}^{u}$
$\displaystyle={\mathcal{L}}(X^{u,\widehat{\pi}^{u}})$

for almost every $u\in[0,1]$. This is called ”continuum-player formulation”
since it involves a continuum of players.

###  C.2 Technical: the non-measurability issue

Mathematically, the continuum-player formulation suffers from significant
measurability difficulties. For completeness, we first cite proposition 2.1
from (Sun, 2006) as follows:

######  Proposition C.1.

Consider index space $(I,{\mathcal{I}},\lambda)$ and probability space
$(\Omega,{\mathcal{F}},P)$. Consider function $f:I\times\Omega\to E$ for some
Polish space $E$. If $f$ is measurable on the product space
$(I\times\Omega,{\mathcal{I}}\otimes{\mathcal{F}},\lambda\otimes P)$, equipped
with the usual product $\sigma$-algebra, and for $\lambda$-almost every $j\in
I$, $f_{j}$ is independent of $f_{i}$ for $\lambda$-almost every $i\in I$.
Then, for $\lambda$-almost every $i\in I$, $f_{i}$ is a constant random
variable.

Intuitively, the product $\sigma$-algebra ${\mathcal{I}}\otimes\mathcal{E}$
fails to support the large amount of information when we require both the
joint measurability of $f$, and the independence between $f_{i}$ and $f_{j}$.
This would lead to a problem when we consider a continuum of players, even if
the state space is a finite space rather than ${\mathbb{R}}^{d}$, and even for
a static game.

More precisely, let $(\Omega,{\mathcal{F}},\mathbb{F},{\mathbb{P}})$ be a
probability space that supports a collection of stochastic processes
$\\{X^{u}:u\in[0,1]\\}$, where $X^{u}$ is a process on $\\{0,1,\dots,T\\}$
valued in ${\mathcal{X}}$ (which could be ${\mathbb{R}}^{d}$ or a finite state
space). $X^{u}$ represents the state process of player with label $u$. From
time $t-1$ to $t$, $X^{u}_{t}$ are generated independently for every
$u\in[0,1]$, and thus the mapping $(u,\omega)\to X^{u}(\omega)$ is not
measurable on the typical product $\sigma$-algebra, similarly
$(u,\omega)\mapsto a^{u}_{t}(X^{u}_{t}(\omega))$ is not measurable. This
measurability issue leads to significant difficulties in the proof, as the
objective reward function may involve these mappings. For instance, as one
attempts to transform the continuum-player graphon game into a mean-field game
with augmented state space, the objective becomes

$\displaystyle{\mathbb{E}}\int_{[0,1]}\Big{[}\sum_{t\in{\mathbb{T}}}\overline{f}_{t}(\binom{u}{X^{u,\pi^{u}}_{t}},\mu_{t},a_{t})+\overline{g}(\binom{u}{X^{u,\pi^{u}}_{T}},\mu_{T})\Big{]}du$

where the integral with respect to $(u,\omega)$ over $[0,1]\times\Omega$ is
not well-defined since the integrand is not measureable. A similar argument
demonstrates why we cannot aggregate the objective of all the players in a
continuum-player graphon game, where the integral
$\int_{[0,1]}J^{u}(\bm{\mu},\pi^{u})du$ is not well-defined. Thus the
continuum-player graphon game is not mathematically equivalent to our
representative-player formulation.

This technical issue can be addressed by carefully enlarging the
$\sigma$-algebra with rich Fubini extension [(Sun, 2006), section 2], allowing
it to hold more information while ensuring the joint measurability and
independence (Aurell et al., 2022; Tangpi & Zhou, 2023). However this approach
is restricted to linear-quadratic problems.

On the contrary, our graphon game formulation considers only one
representative player. Recall that for any
$\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$, the
conditional law of $X$ given $U$ yielded by disintegration is uniquely defined
Lebesgue almost surely. Thus it encodes less information by only considering
almost every label $u$, but this provides great technical convenience and
allow us to consider the game for one player (Lacker & Soret, 2022).

###  C.3 Philosophical: Clarification on representative player

As demonstrated above, the representative-player graphon game we present in
section 4.1 and the continuum-player graphon game in section C.1 are not
mathematically equivalent.

Conceptually, our representative-player formulation inherits the spirit of
mean-field game. We recall that there is only one representative player in the
mean-field game, and all other players are abstracted into a population
measure in ${\mathcal{P}}({\mathcal{C}})$. Similarly, our game formulation is
for one representative player, and the difference is that now the
representative player is in addition assigned a random label, while all other
players are abstracted into a label-state joint population measure on
${\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$.

In other words, our graphon game formulation is defined directly for a
representative player as in classic mean-field games. This should be
distinguished from reformulating a continuum-player graphon game into an MFG
with augmented state space (in a smilar way of Section A.2), which is a proof
technique to adapt existing MFG results into a graphon game setting, and it is
possible to avoid this technique as in our proofs. Using this technique does
not change the fact that the problems are still defined for a continuum of
players: the theorems are stated for the proposed continuum-player graphon
game, and the measurability issue is not avoided. Thus we do not regard this
concept as ”representative-player”.

As a comparison, using one representative to define a graphon game directly at
the beginning, as in (Lacker & Soret, 2022) and this paper, brings novelty
compared with prior works. This is similar to the concept that classic MFG
literature defines a game for a representative player from the start, rather
than models a game for a continuum of players and use techniques to
reformulate it in the proofs.

##  Appendix D A Toy Example on the Difference between the Two Formulations

In this section we compare two types of graphon games formulations on a toy
example, inspired by the motivating example in (Cui & Koeppl, 2021). The two
types of formulations of graphon games lead to the same equilibrium in this
particular one-shot game, while the representative-player graphon game is
simpler in formulation. When a finite player game contains larger and
continuous state and action spaces with more complex settings, our formulation
would demonstrate more advantage in both analysis and computation. Note that
this toy example focus on demonstrating the difference in formulation, and the
measurability issue mentioned in Section C.2 is not the main point here as the
example is simple enough to be solved explicitly, and no technical proofs are
involved.

The interaction is defined by a threshold graph, where
$\xi^{n}_{ij}=1_{i+j<n}$. It is easy to see that $W_{\xi^{n}}$ converges in
cut norm to a limit defined by $W(u,v):=1_{u+v<1}$. Note that this graphon is
discountinuous.

###  D.1 N-player Game

Consider a one-shot (single-stage) game for $n$ players, and let the state and
action space be ${\mathcal{X}}=A=\\{-1,1\\}$, understood as left and right.
Each player simultaneously chooses either left or right, and is punished by
the weighted average of proportion of players that chose the same action.
Precisely,

$\displaystyle a^{i}=\left\\{\begin{matrix}1\quad\text{w.p. }p^{i}\\\
-1\quad\text{w.p. }1-p^{i}\\\ \end{matrix}\right.\qquad X^{i}=a^{i}$

where $p^{i}$ is the probability player $i$ choose right (state 1), and this
characterizes the policy. Let $\bm{p}=(p^{1},\dots,p^{n})$ and let the
terminal reward be $g(x,m)=-\langle m,1_{x}\rangle$, where $1_{x}$ is the
indicator function. Player $i$ aims to maximize

$\displaystyle J^{i}(\bm{p})$
$\displaystyle=-{\mathbb{E}}\bigg{(}\sum_{j=1}^{n}\xi^{n}_{ij}1_{X^{i}=X^{j}}\bigg{)}$
$\displaystyle=-\sum_{j=1}^{n-i}\Big{(}p^{i}p^{j}+(1-p^{i})(1-p^{j})\Big{)}$

It can be verified that one equilibrium is given by
$p^{1}=\dots=p^{n}=\frac{1}{2}$.

###  D.2 Representative-player formulation

Consider a one-shot game for a single player, and let the state and action
space be ${\mathcal{X}}=A=\\{-1,1\\}$. Any population measure
$\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{X}})$ can be
characterized by a function $q(u):=\mu(u,\\{1\\})$, $\forall u\in[0,1]$. Let
this population measure be fixed. The graphon operator is given by

$\displaystyle\textsf{W}\mu(u)=\int_{[0,1]}W(u,v)(q(v)\delta_{1}+(1-q(v))\delta_{-1})dv\,\in\,{\mathcal{M}}_{+}(\\{-1,1\\})$

where $\delta$ is Dirac delta measure. The player is randomly assigned a label
$U\sim\mathrm{unif}[0,1]$, and let $\pi$ be her policy. Equivalently the
policy can be characterized by $p(u):=\pi(u)(\\{1\\})$. Then she follows the
dynamic

$\displaystyle a=\left\\{\begin{matrix}1\quad\text{w.p. }p(U)\\\
-1\quad\text{w.p. }1-p(U)\\\ \end{matrix}\right.\qquad X=a$

The objective is

$\displaystyle J(q,p)$
$\displaystyle=-{\mathbb{E}}\bigg{(}\langle\textsf{W}\mu(U),1_{X}\rangle\bigg{)}$
$\displaystyle=-{\mathbb{E}}\bigg{(}\int_{[0,1]}W(U,v)(q(v)1_{X=1}+(1-q(v))1_{X=-1})dv\bigg{)}$
$\displaystyle=-\int_{u+v<1}(q(v)p(u)+(1-q(v))(1-p(u)))dvdu$

Solving this as a calculus of variation problem provides a necessary condition
$\int_{0}^{u}q(v)dv=\frac{1}{2},\,\forall u\in[0,1]$, and thus the equilibrium
is given by $p(u)=\frac{1}{2}$ for a.e. $u$, and $q(v)=\frac{1}{2}$ for a.e.
$v$.

###  D.3 Continuum-player formulation

Consider a static game for a continuum of players with the same setting, and
let the population measure be $\bm{q}:=\\{q^{u}\\}_{u\in[0,1]}$ for
$q^{u}=\mu^{u}(\\{1\\})$. Each player $u\sim[0,1]$ admits a policy $\pi^{u}$
as the probability choosing $1$, so we may write $p^{u}:=\pi^{u}(\\{1\\})$ and
denote $\bm{p}:=\\{p^{u}\\}_{u\in[0,1]}$. Then the player $u$ chooses the
action

$\displaystyle a^{u}=\left\\{\begin{matrix}1\quad\text{w.p. }p^{u}\\\
-1\quad\text{w.p. }1-p^{u}\\\ \end{matrix}\right.\qquad X^{u}=a^{u}$

and optimize the objective

$\displaystyle J^{u}(\bm{q},p^{u})$
$\displaystyle=-{\mathbb{E}}\bigg{(}\langle\textsf{W}\mu(u),1_{X}\rangle\bigg{)}$
$\displaystyle=-{\mathbb{E}}\bigg{(}\int_{[0,1]}W(u,v)(q^{v}1_{X=1}+(1-q^{v})1_{X=-1})dv\bigg{)}$
$\displaystyle=-\int_{0}^{1-u}(q^{v}p^{u}+(1-q^{v})(1-p^{u}))dv$

It is immediate that the equilibrium is given by $p^{u}=\frac{1}{2}$, and
$q^{v}=\frac{1}{2}$ for almost every $u,v$. Note that the measurability issue
is not a concern for this specific example, since it can be solved directly
and thus doesn’t involve technical analysis.

##  Appendix E Proof for Existence

###  E.1 Preliminary Lemmas

######  Lemma E.1.

[Lemma A.2 of (Lacker, 2015)] Let $X_{1}$ and $X_{2}$ be Polish spaces.
Defined the coordinate projections
$\Pi_{i}:{\mathcal{X}}_{1}\times{\mathcal{X}}_{2}\to{\mathcal{X}}_{i}$ for
$i=1,2$. Then a set
$S\subset{\mathcal{P}}({\mathcal{X}}_{1}\times{\mathcal{X}}_{2})$ is tight if
and only if the sets $S_{1}=\\{\mu\circ\Pi_{1}^{-1}:\mu\in S\\}$ and
$S_{2}=\\{\mu\circ\Pi_{2}^{-1}:\mu\in S\\}$ are tight in
${\mathcal{P}}(X_{1})$ and ${\mathcal{P}}(X_{2})$ respectively.

######  Lemma E.2.

[Corollary A.5 of (Lacker, 2015)] Let $E,F,G$ be complete, separable metric
spaces. $\phi:E\times F\times G\to{\mathbb{R}}$ is a bounded measurable
function, with $\phi(x,\cdot,\cdot)$ being jointly continuous for any $x\in
E$. Then the following mapping is continuous:

$\displaystyle G\times{\mathcal{P}}(E\times F)\ni(z,P)\mapsto\int_{E\times
F}\phi(x,y,z)P(dx,dy)$

######  Lemma E.3.

Let $W^{n},W$ be graphons. If $W^{n}\stackrel{{\scriptstyle
L_{1}}}{{\longrightarrow}}W$, then, $W^{n}\longrightarrow W$.

###### Proof.

Fiven any $\psi\in L_{\infty}[0,1]$,

$\displaystyle\|\textsf{W}^{n}\psi-\textsf{W}\psi\|_{1}$
$\displaystyle=\int_{[0,1]}\Big{|}\textsf{W}^{n}\psi(u)-\textsf{W}\psi(u)\Big{|}du$
$\displaystyle=\int_{[0,1]}\Big{|}\int_{[0,1]}W^{n}(u,v)\psi(v)-W(u,v)\psi(v)dv\Big{|}du$
$\displaystyle\leq\|\psi\|_{\infty}\int_{[0,1]^{2}}\Big{|}W^{n}(u,v)-W(u,v)\Big{|}dvdu$
$\displaystyle=\|\psi\|_{\infty}\|W^{n}-W\|_{1}\longrightarrow 0$

∎

######  Lemma E.4.

[Lemma 4.2 of (Lacker & Soret, 2022)] Let $E$ be any Polish space, and $W$ be
any graphon.

  1. 1.

For a.e. $u\in[0,1]$, the following map is continuous:

$\displaystyle{\mathcal{P}}_{\mathrm{unif}}([0,1]\times
E)\ni\mu\mapsto\textsf{W}\mu(u)\in{\mathcal{M}}_{+}(E)$

  2. 2.

Suppose the map $[0,1]\ni
u\mapsto\textsf{W}(u,v)dv\in{\mathcal{M}}_{+}([0,1])$ is continuous, then for
any $\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times E)$,

$\displaystyle[0,1]\ni u\mapsto\textsf{W}\mu(u)\in{\mathcal{M}}_{+}(E)$

is continuous.

######  Lemma E.5.

Let $E,F$ be complete, separable metric space, and $F$ is a regular measurable
space. Consider a sequence of probability measures on the product space
$\\{\nu_{n}\\}\subset{\mathcal{P}}(E\times F)$. Suppose that $\nu_{n}$ admits
disintegration

$\displaystyle\nu_{n}(dx,dy)=\mu_{n}(dx)K(x,dy)$

for some common kernel $K$, which is continuous as a mapping
$E\to{\mathcal{P}}(F)$, i.e. any sequence $x_{n}\to x$ implies
$K_{x_{n}}\Rightarrow K_{x}$. Then if $\nu_{n}\Rightarrow\nu$, $\nu$ admits a
disintegration $\nu(dx,dy)=\mu(dx)K(x,dy)$ for some $\mu\in{\mathcal{P}}(E)$.

###### Proof.

Let $\Pi_{1}$ be the projection to first coordinate, which is a continuous
mapping. By continuous mapping theorem, the pushforward of a weak convergence
measure seqnece under continuous mapping converge weakly:

$\displaystyle\nu_{n}\circ\Pi_{1}^{-1}\Rightarrow\nu\circ\Pi_{1}^{-1}=:\mu$

Suppose $\nu$ admits disintegration $\nu(dx,dy)=\mu(dx)\bar{K}(x,dy)$ for some
$\bar{K}$. Given $\forall\phi:E\times F\to{\mathbb{R}}$ bounded, jointly
continuous, the mapping $E\ni x\mapsto\int_{F}\phi(x,y)K(x,dy)\in{\mathbb{R}}$
is bounded and continuous since for any $x_{n}\to x$,

$\displaystyle\left|\int_{F}\phi(x_{n},y)K(x_{n},dy)-\int_{F}\phi(x,y)K(x,dy)\right|$
$\displaystyle\leq\left|\int_{F}\phi(x_{n},y)K(x_{n},dy)-\int_{F}\phi(x,y)K(x_{n},dy)\right|+\left|\int_{F}\phi(x,y)K(x_{n},dy)-\int_{F}\phi(x,y)K(x,dy)\right|$

which converges to 0. Finally,
$\langle\nu_{n},\phi\rangle\to\langle\nu,\phi\rangle$, and on the other hand,

$\displaystyle\langle\nu_{n},\phi\rangle=\int_{E\times
F}\phi(x,y)K(x,dy)\mu_{n}(dx)\longrightarrow\int_{E\times
F}\phi(x,y)K(x,dy)\mu(dx)$

which holds for any $\phi$ bounded continuous, and we conclude that $K$ is a
version of $\bar{K}$. ∎

###  E.2 Existence of Equilibrium

Given any function $\phi:E\times A\to F$ for Polish space $E,F$ and a measure
$\pi\in{\mathcal{P}}(A)$, we may also abuse the notation by writing $\phi$ as
a function $E\times{\mathcal{P}}(A)\to F$, defined by
$\phi(x,\pi)=\langle\pi,\phi(x,\cdot)\rangle$ for each $x\in E$.

Throughout the proof we fix a graphon $W$, and denote
${\mathcal{V}}={\mathcal{P}}(A)^{T}$ the space of all policies. We fix any
policy $\pi\in{\mathcal{V}}$, and construct the label-state joint measure of
the representative player controlled by $\pi$ as follows. Recall that at time
$t$ given $U=u,X_{t}=x,\alpha_{t}=a$, the law of next state $X_{t+1}$ follows
the probabilistic kernel $[0,1]\times{\mathbb{R}}^{d}\times
A\to{\mathbb{R}}^{d}$

$\displaystyle{\mathcal{L}}(X_{t+1}|X_{t}=x,U_{t}=u,\alpha_{t}=a)(dy)=P_{t}(dy|x,\textsf{W}\mu_{t}(u),a)\qquad\forall
y\in{\mathbb{R}}^{d}$

and the control process $\alpha_{t}$ follows

$\displaystyle{\mathcal{L}}(\alpha_{t})(da)=\pi_{t}(da)\qquad\forall a\in A$

We may thus consider

$\displaystyle\widehat{P}^{\pi,\mu}_{t}(dy|u,x):={\mathcal{L}}(X_{t+1}|X_{t}=x,U_{t}=u)(dy)=\int_{A}P_{t}(dy|x,\textsf{W}\mu_{t}(u),a)\pi_{t}(da)\qquad\forall
y\in{\mathbb{R}}^{d}$

and we use the superscript to emphasize that the law is controlled by the
policy $\pi$. Note that
${\mathcal{V}}_{U}\ni\pi\mapsto\widehat{P}^{\pi,\mu}_{t}(u,x)\in{\mathcal{P}}({\mathbb{R}}^{d})$
is measurable. The collection of kernels
$\\{\widehat{P}^{\pi}_{t}\\}_{t\in{\mathbb{T}}}$ (recall
${\mathbb{T}}=\\{0,1,\dots,T-1\\}$) along with the initial law $\lambda$
implies a label-state joint law in
${\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$

$\displaystyle\widehat{P}^{\pi,\mu}(du,dx):={\mathcal{L}}(U,X)(du,dx)=\lambda(du,dx_{0})\prod_{t\in{\mathbb{T}}}\widehat{P}^{\pi,\mu}_{t}(dx_{t+1}|u,x_{t})\qquad\forall(u,x)\in[0,1]\times{\mathcal{C}}$

which is the label-state joint measure of the representative player, when her
state dynamic is controlled by $\pi$. Since the space
$[0,1]\times{\mathcal{C}}$ is a standard measurable space, this is understood
as a regular version of the kernel from ${\mathcal{V}}$ to
$[0,1]\times{\mathcal{C}}$.

######  Lemma E.6.

Under assumption 4.3(5), for any
$\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$,
$\pi\mapsto\widehat{P}^{\pi,\mu}$ is continuous. In particular,
$\pi_{t}\mapsto\widehat{P}^{\pi,\mu}_{t}(u,x)$ is continuous for every
$(u,x)\in[0,1]\times{\mathbb{R}}^{d}$.

###### Proof.

Let $\\{\pi^{n}\\}\subset{\mathcal{V}}$ be any sequence of policies such that
$\pi^{n}\Rightarrow\pi$ for some $\pi\in{\mathcal{V}}$. For any
$\phi:[0,1]\times{\mathcal{C}}\to{\mathbb{R}}$ bounded continuous,

$\displaystyle\int_{[0,1]\times{\mathcal{C}}}\phi(u,x)\widehat{P}^{\pi^{n},\mu}(du,dx)$
$\displaystyle=\int_{[0,1]\times{\mathbb{R}}^{d}}\Big{[}\int_{A^{T}}\int_{({\mathbb{R}}^{d})^{T}}\phi(u,x_{0},\dots,x_{T})\prod_{t\in{\mathbb{T}}}P_{t}(dx_{t+1}|x_{t},\textsf{W}\mu_{t}(u),a_{t})\pi^{n}(da_{0},\dots,da_{T-1})\Big{]}\lambda(du,dx_{0})$
$\displaystyle=:\int_{[0,1]\times{\mathbb{R}}^{d}}\Big{[}\int_{A^{T}}\psi(a_{0},\dots,a_{T-1})\pi^{n}(da_{0},\dots,da_{T-1})\Big{]}\lambda(du,dx_{0})$

where

$\displaystyle\psi(a_{0},\dots,a_{T-1}):=\int_{({\mathbb{R}}^{d})^{T}}\phi(u,x_{0},\dots,x_{T})\prod_{t\in{\mathbb{T}}}P_{t}(dx_{t+1}|x_{t},\textsf{W}\mu_{t}(u),a_{t})$

We know that $a_{t}\mapsto P_{t}(dx_{t+1}|x_{t},\textsf{W}\mu_{t}(u),a_{t})$
is continuous for each $t\in{\mathbb{T}}$ by assumption 4.3(5), and since
$({\mathbb{R}}^{d})^{T}$ is separable, with standard measure theory argument
for weak convergence on product space, for instance chapter 2 of (Billingsley,
1995), the map $\psi$ is continuous. Thus
$\langle\pi^{n},\psi\rangle\to\langle\pi,\psi\rangle$, and

$\displaystyle\int_{[0,1]\times{\mathcal{C}}}\phi(u,x)\widehat{P}^{\pi^{n},\mu}(du,dx)$
$\displaystyle\longrightarrow$
$\displaystyle\int_{[0,1]\times{\mathbb{R}}^{d}}\Big{[}\int_{A^{T}}\psi(a_{0},\dots,a_{T-1})\pi(da_{0},\dots,da_{T-1})\Big{]}\lambda(du,dx_{0})$
$\displaystyle=\int_{[0,1]\times{\mathcal{C}}}\phi(u,x)\widehat{P}^{\pi,\mu}(du,dx)$

∎

Define the probability space
$\Omega:=\mathcal{V}\times[0,1]\times\mathcal{C}$, equipped with the product
$\sigma$-algebra. A typical element of $\Omega$ is $(\pi,u,x)$, where we
understood them as a policy, a label of the representative player and the
player’s path, respectively. Let the coordinate maps be $\Lambda,U,X$
respectively. The filtration is given by
${\mathcal{F}}_{t}=\sigma\\{\Lambda|_{[t]\times A},U,\\{X_{s}\\}_{0\leq s\leq
t}\\}$.

The collection of admissible laws ${\mathcal{R}}(\mu)$ is defined as the set

$\displaystyle{\mathcal{R}}(\mu):=\\{R\in{\mathcal{P}}(\Omega):R\text{ admits
disintegration
}R(d\pi,du,dx)=R_{\Lambda}(d\pi)\widehat{P}^{\pi,\mu}(du,dx)\text{ for some
}R_{\Lambda}\in{\mathcal{P}}({\mathcal{V}})\\}$

Define a random variable $\Xi^{\mu}:\Omega\to{\mathbb{R}}$ by

$\displaystyle\Xi^{\mu}(\pi,u,x):=\sum_{t\in{\mathbb{T}}}\int_{A}f_{t}(\textsf{W}\mu_{t}(u),x_{t},a)\pi_{t}(da)+g(x_{T},\textsf{W}\mu_{T}(u))$
(16)

where $\mu_{t}$ is the marginal obtained as the image by
$(u,x)\mapsto(u,x_{t})$. In particular, given a policy $\pi\in{\mathcal{V}}$,
let
$R^{(\pi)}(d\tilde{\pi},du,dx):=\delta_{\pi}(d\tilde{\pi})\widehat{P}^{\tilde{\pi},\mu}(du,dx)$
be an element of ${\mathcal{R}}(\mu)$, where $\delta$ is the Dirac measure. It
holds that the objective can be rewritten as

$\displaystyle J_{W}(\mu,\pi)=\langle R^{(\pi)},\Xi^{\mu}\rangle$

thus the expectation $\langle R,\Xi^{\mu}\rangle$ is a reformulation of the
objective, and a single player’s objective is to find the collection of
measures that maximize this expectation:

$\displaystyle{\mathcal{R}}^{*}(\mu):=\\{R^{*}\in{\mathcal{R}}(\mu):\langle
R^{*},\Xi^{\mu}\rangle\geq\langle R,\Xi^{\mu}\rangle,\,\forall
R\in{\mathcal{R}}(\mu)\\}$ (17)

Define the correspondence (i.e. set valued function, see (Aliprantis & Border,
2006) for an overview) $\Phi:{\mathcal{P}}([0,1]\times{\mathcal{C}})\to
2^{{\mathcal{P}}([0,1]\times{\mathcal{C}})}$, given by

$\displaystyle\Phi(\mu):=\\{R\circ(U,X)^{-1}:R\in{\mathcal{R}}^{*}(\mu)\\}$

The existence of $W-$equilibrium is divided into two steps: we first show the
existence of optimizer to the optimization problem (17) over the probability
measures, i.e. ${\mathcal{R}}^{*}(\mu)$ is non-empty for any $\mu$; Next, to
obtain a $W-$equilibrium, we aim to find a fixed point for the correspondence
$\Phi$.

######  Proposition E.7.

For $\forall\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$,
the following optimization problem admits optimizer.

$\displaystyle\sup_{R\in{\mathcal{R}}(\mu)}\langle R,\Xi^{\mu}\rangle$

###### Proof.

We want to show that $R\mapsto\langle R,\Xi^{\mu}\rangle$ is a continuous
mapping on compact space, and thus the maximum of this mapping is attained.
With a direct application of lemma E.2, we immediately conclude that the
following map is jointly continuous:

$\displaystyle\text{Gr}({\mathcal{R}})\ni(\mu,R)\longmapsto\langle
R,\Xi^{\mu}\rangle\in{\mathbb{R}}$ (18)

where Gr denotes the graph of an operator.

It remains to prove that ${\mathcal{R}}(\mu)$ is compact. First we want to
show ${\mathcal{R}}(\mu)$ is tight for any $\mu$. By lemma E.1, it suffices to
show that the following sets are tight: $\\{R\circ
X^{-1}:R\in{\mathcal{R}}(\mu)\\}$, $\\{R\circ
U^{-1}:R\in{\mathcal{R}}(\mu)\\}$,
$\\{R\circ\Lambda^{-1}:R\in{\mathcal{R}}(\mu)\\}$. The last two follows
immediately from the fact that $[0,1]$ and $A$ are compact spaces.

Fix any $\epsilon^{\prime}>0$, we could always find some $\epsilon$ such that
$(1-\epsilon)^{T+1}>1-\epsilon^{\prime}$. By assumption 4.3(3) and 4.3(4), let
$\\{K_{t}\\}_{t\in{\mathbb{T}}}$ be compact subsets of ${\mathbb{R}}^{d}$ such
that

$\displaystyle\inf_{u\in[0,1]}\lambda^{u}({K_{0}})>1-\epsilon\qquad\inf_{\widetilde{P}_{t}\in\zeta_{t}}\widetilde{P}_{t}(K_{t+1})>1-\epsilon\quad\forall
t\in{\mathbb{T}}$

Define $K=\prod_{t=0}^{T}K_{t}$, which is a compact subset of ${\mathcal{C}}$.
Then for every $R\in{\mathcal{R}}(\mu)$, let
$\widehat{P}^{\pi,\mu}(du,dx)R_{\Lambda}(d\pi)$ be its disintegration,

$\displaystyle(R\circ X^{-1})(K)$
$\displaystyle=R({\mathcal{V}}\times[0,1]\times K)$
$\displaystyle=\int_{{\mathcal{V}}\times[0,1]\times{\mathcal{C}}}1_{K}(x)\widehat{P}^{\pi,\mu}(du,dx)R_{\Lambda}(d\pi)$
$\displaystyle=\int_{{\mathcal{V}}}\int_{[0,1]\times{\mathbb{R}}^{d}}\Big{[}\prod_{t=0}^{T-1}\int_{A}\int_{{\mathbb{R}}^{d}}1_{K_{t+1}}(x_{t+1})P_{t}(dx_{t+1}|x_{t},\textsf{W}\mu_{t}(u),a)\pi_{t}(da)\Big{]}1_{K_{0}}(x_{0})\lambda(du,dx_{0})R_{\Lambda}(d\pi)$
$\displaystyle\geq\int_{{\mathcal{V}}}\int_{[0,1]}\Big{[}\prod_{t=0}^{T-1}\int_{A}(1-\epsilon)\pi_{t}(da)\Big{]}\int_{{\mathbb{R}}^{d}}1_{K_{0}}(x_{0})\lambda^{u}(dx_{0})duR_{\Lambda}(d\pi)$
$\displaystyle\geq\int_{{\mathcal{V}}}\int_{[0,1]}(1-\epsilon)^{T+1}duR_{\Lambda}(d\pi)$
$\displaystyle=(1-\epsilon)^{T+1}>1-\epsilon^{\prime}$

and thus we have $\inf_{R\in{\mathcal{R}}(\mu)}(R\circ
X^{-1})(K)>1-\epsilon^{\prime}$, which implies the tightness of $\\{R\circ
X^{-1}:R\in{\mathcal{R}}(\mu)\\}$. Note that if the state space
${\mathcal{X}}$ of dynamic $X$ is compact, then $\\{R\circ
X^{-1}:R\in{\mathcal{R}}(\mu)\\}$ being tight is immediate. By Prokhorov’s
theorem, ${\mathcal{R}}(\mu)$ is precompact.

We conclude by showing that ${\mathcal{R}}(\mu)$ is closed. Let
$\\{R_{n}\\}\subset{\mathcal{R}}(\mu)$, and $R_{n}\Rightarrow R$. Indeed each
$R_{n}$ admits disintegration
$R_{\Lambda}^{n}(d\pi)\widehat{P}^{\pi,\mu}(du,dx)$ for some
$R_{\Lambda}^{n}\in{\mathcal{P}}({\mathcal{V}})$, and the kernel
$\pi\mapsto\widehat{P}^{\pi,\mu}$ is continuous by lemma E.6. Then lemma E.5
implies that $R$ admits disintegration
$R_{\Lambda}(d\pi)\widehat{P}^{\pi,\mu}(du,dx)$ and thus
$R\in{\mathcal{R}}(\mu)$. ∎

Next we show that the correspondence $\Phi$ admits a fixed point, and thus the
graphon game admits a $W$-equilibrium.

######  Proposition E.8.

There exists a fixed point $\widehat{\mu}$ for the correspondence $\Phi$.

###### Proof.

We aim to apply the Kakutani-Fan-Glicksberg fixed point theorem, which is a
classic fixed point theorem for correspondences, see for instance theorem
17.55 of (Aliprantis & Border, 2006). We need to show the following
conditions: $\exists K\subset{\mathcal{P}}([0,1]\times{\mathcal{C}})$
nonempty, convex and compact, such that

  1. 1.

$\Phi(\mu)\subset K$ for each $\mu\in K$.

  2. 2.

$\Phi(\mu)$ is nonempty and convex for each $\mu\in K$.

  3. 3.

The graph $\mathrm{Gr}(\Phi)=\\{(\mu,\mu^{\prime}):\mu\in
K,\mu^{\prime}\in\Phi(\mu)\\}$ is closed.

We start from defining $K$, note that $\lambda$ is a fixed initial measure.

$\displaystyle
K:=\\{\lambda\otimes\prod_{t=0}^{T-1}\widehat{P}_{t}:\widehat{P}_{t}\in\overline{\mathrm{conv}}(\zeta_{t})\\}$

where $\overline{\mathrm{conv}}(\cdot)$ denotes the closed convex hull of a
set, and $\otimes$ is the combinations of probabilistic kernels on product
space. $K$ is obviously non-empty. By construction, $K$ is the finite
cartesian product of convex sets, thus $K$ is convex. To show $K$ is compact,
it suffices to show $\overline{\mathrm{conv}}(\zeta_{t})$ is compact for each
$t\in{\mathbb{T}}$, since Tychonoff’s theorem asserts that an arbitrary
product of compact spaces is again compact. Indeed, since $\zeta_{t}$ is
tight, and thus precompact by Prokhorov’s theorem, and the closed convex hull
of a precompact set is compact in a locally convex Hausdorff space. Again, if
the value space ${\mathcal{X}}$ of $X$ is compact, let
$K={\mathcal{P}}([0,1]\times{\mathcal{C}})$ and $K$ is compact automatically.

For each $R\in{\mathcal{R}}(\mu)$, let it admit the disintegration
$R=R_{\Lambda}\otimes\widehat{P}$:

$\displaystyle
R_{\Lambda}(d\pi)\widehat{P}^{\pi,\mu}(du,dx)=\Big{[}\lambda(du,dx_{0})\prod_{t=0}^{T-1}\int_{A}P_{t}(dx_{t+1}|x_{t},\textsf{W}\mu_{t}(u),a)\pi_{t}(da)\Big{]}R_{\Lambda}(d\pi)$

We claim that for any $t\in{\mathbb{T}}$,

$\displaystyle\widehat{P}^{\pi,\mu}_{t}(dx_{t+1}|u,x_{t})=\int_{A}P_{t}(dx_{t+1}|x_{t},\textsf{W}\mu_{t}(u),a)\pi_{t}(da)\in\overline{\mathrm{conv}}(\zeta_{t})$

since it is the limit of convex combinations of
$P_{t}(\cdot|x_{t},\textsf{W}\mu_{t}(u),a)\in\zeta_{t}$. and thus for any
$(\pi,\mu)\in{\mathcal{V}}\times{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$,
the measure
$\widehat{P}^{\pi,\mu}\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$
belongs to $K$. The pushforward of $R$ onto $(U,X)$ coordinate is

$\displaystyle(R\circ(U,X)^{-1})(du,dx)=\int_{{\mathcal{V}}}\widehat{P}^{\pi,\mu}(du,dx)R_{\Lambda}(d\pi)$

which is also the limit of a sequence of convex combinations of
$\widehat{P}^{\pi,\mu}(du,dx)$, indexed by $\pi$. Thus by closedness and
compactness of $K$, $R\circ(U,X)^{-1}\in K$, and thus $\Phi(\mu)\subset K$.

To show the convexity of $\Phi(\mu)$, we start with showing
${\mathcal{R}}(\mu)$ is convex since for any
$R^{1}=R^{1}_{\Lambda}\otimes\widehat{P}$ and
$R^{2}=R^{2}_{\Lambda}\otimes\widehat{P}$ and $\lambda\in[0,1]$, $\lambda
R^{1}+(1-\lambda)R^{2}=(\lambda
R^{1}_{\Lambda}+(1-\lambda)R^{2}_{\Lambda})\otimes\widehat{P}\in{\mathcal{R}}(\mu)$.
Convexity of ${\mathcal{R}}^{*}(\mu)$ follows from the linearity of
$R\mapsto\langle P,\Xi^{\mu}\rangle$ and the convexity of
${\mathcal{R}}(\mu)$, and thus the convexity of $\Phi(\mu)$ follows from the
linearity of map $R\mapsto R\circ(U,X)^{-1}$ and the convexity of
${\mathcal{R}}^{*}(\mu)$.

It remains to show the closedness of the graph of $\Phi$, and we first show
the closedness of the following set:

$\displaystyle\\{(\mu,R):\mu\in K,R\in{\mathcal{R}}^{*}(\mu)\\}$

Let $\mu_{n}\Rightarrow\mu$ and $R_{n}\Rightarrow R$ with $\mu_{n},\mu\in K$,
$R_{n}\in{\mathcal{R}}^{*}(\mu_{n})$, and $R\in{\mathcal{R}}$. To show that
$R\in{\mathcal{R}}^{*}(\mu)$, we use the continuity (18), and for any
$R^{\prime}\in{\mathcal{R}}$,

$\displaystyle\langle R,\Xi^{\mu}\rangle=\lim_{n\to\infty}\langle
R_{n},\Gamma^{\mu_{n}}\rangle\geq\lim_{n\to\infty}\langle
R^{\prime},\Gamma^{\mu_{n}}\rangle=\langle R^{\prime},\Xi^{\mu}\rangle$

and thus $\langle R,\Xi^{\mu}\rangle\geq\langle R^{\prime},\Xi^{\mu}\rangle$
for any $R^{\prime}\in{\mathcal{R}}$. The by the continuity of $R\mapsto
R\circ(U,X)^{-1}$ and compactness of $K$, we have the closedness of
Gr($\Phi$). ∎

###  E.3 Closed-loop equilibrium optimal policy

In this section we show the second part of theorem 4.4, that the equilibrium
optimal open-loop policy can be made closed-loop.

######  Proposition E.9.

Let $\mu\in{\mathcal{P}}_{\mathrm{unif}}([0,1]\times{\mathcal{C}})$, and
$R\in{\mathcal{R}}(\mu)$. Then, there exists a closed-loop optimal policy, in
the following sense: $\exists$ a measurable function
$\pi:{\mathbb{T}}\times[0,1]\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$, and
$R^{0}\in{\mathcal{R}}(\mu)$, such that

  1. 1.

$R^{0}(\Lambda_{t}(da)=\pi_{t}(U,X_{t})(da)\,\,\forall t\in{\mathbb{T}})=1$

  2. 2.

$\int_{\Omega}\Xi^{\mu}dR^{0}\geq\int_{\Omega}\Xi^{\mu}dR$

  3. 3.

$R^{0}\circ(U,X_{t})^{-1}=R\circ(U,X_{t})^{-1}\quad\forall t\in{\mathbb{T}}$

######  Corollary E.10.

There exists a closed-loop equilibrium optimal policy to the graphon game.

###### Proof.

We first find a space $(\Omega^{1},{\mathcal{F}}^{1},R^{1})$ supporting a
random variable $U^{1}$, an adapted process $X^{1}$ valued in
${\mathbb{R}}^{d}$, and a ${\mathcal{P}}(A)$-valued adpated process
$\Lambda_{t}$ s.t.

$\displaystyle(U^{1},X_{0}^{1})\sim\lambda\quad X^{1}_{t+1}\sim
P_{t}(X^{1}_{t},\textsf{W}\mu_{t}(U^{1}),\Lambda_{t})$ $\displaystyle
R^{1}\circ\left(U,X^{1}\right)^{-1}=\mu$

The existence of such space is guarenteed by reasoning in Section E.2. We
claim that there exists a measurable
$\pi:{\mathbb{T}}\times[0,1]\times{\mathbb{R}}^{d}\to{\mathcal{P}}(A)$ such
that

$\displaystyle\pi_{t}(U^{1},X^{1}_{t})={\mathbb{E}}^{R^{1}}(\Lambda_{t}\,|\,U^{1},X^{1}_{t})\qquad
R^{1}-a.s.\,\,\forall t\in{\mathbb{T}}$

More precisely, for every bounded measurable
$\phi:[0,1]\times{\mathbb{R}}^{d}\times A\to{\mathbb{R}}$,

$\displaystyle\int_{A}\phi(U^{1},X^{1}_{t},a)\pi_{t}(U^{1},X^{1}_{t})(da)={\mathbb{E}}^{R^{1}}\left(\int_{A}\phi(U^{1},X^{1}_{t},a)\Lambda_{t}(da)\,\Big{|}\,U^{1},X^{1}_{t}\right)\qquad
R^{1}-a.s.,\forall t\in{\mathbb{T}}$

Define a collection of measures, $\\{\eta_{t}\\}_{t\in{\mathbb{T}}}$,
$\eta_{t}\in{\mathcal{P}}([0,1]\times{\mathbb{R}}^{d}\times A)$ by

$\displaystyle\eta_{t}(C):={\mathbb{E}}^{R^{1}}\left[\int_{A}1_{C}(t,U^{1}_{t},X^{1}_{t},a)\Lambda_{t}(da)\right]$

and let $\eta_{t}$ adimits disintegration
$\eta_{t}(du,dx,da)=\eta^{\prime}_{t}(du,dx)\pi_{t}(u,x)(da)$, where
$\eta^{\prime}_{t}$ is the marginal of $\eta_{t}$ onto
$[0,1]\times{\mathbb{R}}^{d}$. Note that actually
$\eta^{\prime}_{t}(du,dx)=\mu_{t}$, since for any measurable
$F\subset[0,1]\times{\mathbb{R}}^{d}$,

$\displaystyle\eta^{\prime}_{t}(F)=\eta_{t}(F\times A)$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[\int_{A}1_{F}(U^{1}_{t},X^{1}_{t})1_{A}(a)\Lambda_{t}(da)\right]$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[1_{F}(U^{1}_{t},X^{1}_{t})\right]=\langle
R^{1}\circ(U,X^{1})^{-1},1_{F}\rangle$

Fix $\forall t$, for any bounded measurable
$h:\times[0,1]\times{\mathbb{R}}^{d}\to{\mathbb{R}}$,

$\displaystyle{\mathbb{E}}^{R^{1}}\left[h(U^{1},X^{1}_{t})\int_{A}\phi(U^{1},X^{1}_{t},a)\pi_{t}(U^{1},X^{1}_{t})(da)\right]$
$\displaystyle=\int_{[0,1]\times{\mathbb{R}}^{d}}h(u,x)\int_{A}\phi(u,x,a)\pi_{t}(u,x)(da)\eta^{\prime}_{t}(du,dx)$
$\displaystyle=\int_{[0,1]\times{\mathbb{R}}^{d}\times
A}h(u,x)\phi(u,x,a)\eta_{t}(du,dx,da)$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[h(U^{1},X^{1}_{t})\int_{A}\phi(U^{1},X^{1}_{t},a)\Lambda_{t}(da)\right]$

By definition of conditional expectation, the claim follows.

Construct another probability space $(\Omega^{2},{\mathcal{F}}^{2},R^{2})$ as
follows: Let $\Omega^{2}=[0,1]\times{\mathcal{C}}$, $U^{2}$ and $X^{2}$ are
the coordinate maps, and

$\displaystyle R^{2}:=R^{1}\circ\left(U^{1},X^{1}\right)^{-1}=\mu$

In the rest of the proof, we aim to show that $U^{2},X^{2}$ follows the
dynamic

$\displaystyle(U^{2},X_{0}^{2})\sim\lambda\quad X^{2}_{t+1}\sim
P_{t}(X^{2}_{t},\textsf{W}\mu_{t}(U^{2}),\pi_{t}(U^{2},X^{2}_{t}))$

Fix any bounded continuous $\psi:{\mathbb{R}}^{d}\to{\mathbb{R}}$. For any
measurable $h:[0,1]\times{\mathbb{R}}^{d}\to{\mathbb{R}}_{+}$,

$\displaystyle{\mathbb{E}}^{R^{2}}\left[h(U^{2},X^{2}_{t})\psi(X^{2}_{t+1})\right]$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[h(U^{1},X^{1}_{t})\psi(X^{1}_{t+1})\right]$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[h(U^{1},X^{1}_{t}){\mathbb{E}}^{R^{1}}\left(\int_{A}\int_{{\mathbb{R}}^{d}}\psi(y)P_{t}(\textsf{W}\mu_{t}(U^{1}),X^{1}_{t},a)(dy)\Lambda_{t}(da)\,\Big{|}\,U^{1},X^{1}_{t}\right)\right]$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[h(U^{1},X^{1}_{t})\int_{A}\int_{{\mathbb{R}}^{d}}\psi(y)P_{t}(\textsf{W}\mu_{t}(U^{1}),X^{1}_{t},a)(dy)\pi_{t}(U^{1},X^{1}_{t})(da)\right]$
$\displaystyle={\mathbb{E}}^{R^{2}}\left[h(U^{2},X^{2}_{t})\int_{A}\int_{{\mathbb{R}}^{d}}\psi(y)P_{t}(\textsf{W}\mu_{t}(U^{2}),X^{2}_{t},a)(dy)\pi_{t}(U^{2},X^{2}_{t})(da)\right]$

By definition of conditional expectation, we claim that

$\displaystyle{\mathbb{E}}^{R^{2}}\left[\psi(X^{2}_{t+1})\,|\,U^{2},X^{2}_{t}\right]=\int_{A}\int_{{\mathbb{R}}^{d}}\psi(y)P(t,U^{2},\textsf{W}\mu_{t}(U^{2}),X^{2}_{t},a)(dy)\pi_{t}(U^{2},X^{2}_{t})(da)$

and note that this holds for any $\psi$ bounded continuous. Finally, let
$R^{0}:=R^{2}\circ(\\{\pi_{t}(U^{2},X^{2}_{t})\\}_{t\in T},U^{2},X^{2})^{-1}$,
then $R^{0}\in{\mathcal{R}}(\mu)$, and the objective value is preserved:

$\displaystyle\int_{\Omega}\Xi^{\mu}dR^{0}$
$\displaystyle={\mathbb{E}}^{R^{2}}\left[\sum_{t\in
T}\int_{A}f(t,U^{2},X^{2}_{t},\textsf{W}\mu_{t}(U^{2}),a)\pi(t,U^{2},X^{2}_{t})(da)+g(X^{2}_{T},\textsf{W}\mu_{T}(U^{2}))\right]$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[\sum_{t\in
T}\int_{A}f(t,U^{1},X^{1}_{t},\textsf{W}\mu_{t}(U^{1}),a)\pi_{t}(U^{1},X^{1}_{t})(da)+g(X^{1}_{T},\textsf{W}\mu_{T}(U^{1}))\right]$
$\displaystyle={\mathbb{E}}^{R^{1}}\left[\sum_{t\in
T}\int_{A}f(t,U^{1},X^{1}_{t},\textsf{W}\mu_{t}(U^{1}),a)\Lambda_{t}(da)+g(X^{1}_{T},\textsf{W}\mu_{T}(U^{1}))\right]$
$\displaystyle=\int_{\Omega}\Xi^{\mu}dR$

∎

######  Remark E.11.

The proof is closely based on (Lacker, 2015), whick utilized a remarkable
result called Markovian projection theorem (or Mimicking theorem), originated
from (Brunick & Shreve, 2013). However, the discrete time setting greatly
simplifies the proof and just the definition of conditional expectation would
work.

##  Appendix F Proof for Uniqueness

Let $(\mu,\pi)$ and $(\nu,\rho)$ be two different $W$-equilibrium, and the
Markovian state dynamic being $X^{\pi}$ and $X^{\rho}$ respectively. By
construction the processes $\pi$ and $\rho$ must be different, since otherwise
$X^{\pi}$ and $X^{\nu}$ would be the same, and then $\mu$ and $\nu$ will be
the same as well. Therefore, by uniqueness of optimal policy, we have

$\displaystyle J_{W}(\mu,\pi)-J_{W}(\mu,\rho)>0\quad\textrm{and}\quad
J_{W}(\nu,\rho)-J_{W}(\nu,\pi)>0$

note that the inequalities are strict. Adding them result in

$\displaystyle
J_{W}(\mu,\pi)-J_{W}(\nu,\pi)-(J_{W}(\mu,\rho)-J_{W}(\nu,\rho))>0$ (19)

Since the Markovian dynamic does not depend on the measure argument, when the
population meausre is $\mu$, the dynamic controlled by policy $\rho$ is the
same pathwise as $X^{\rho}$. This is not true if the assumption is not
satisfied, since

$\displaystyle X^{\pi}_{t+1}\sim
P_{t}(X^{\pi}_{t},\textsf{W}\mu_{t}(U),\pi_{t})\qquad X^{\rho}_{t+1}\sim
P_{t}(X^{\rho}_{t},\textsf{W}\nu_{t}(U),\rho_{t})$

and under population measure $\mu$, the process controlled by $\rho$ follows
the dynamic $X^{{}^{\prime}}_{t+1}\sim
P_{t}(X^{{}^{\prime}}_{t},\textsf{W}\mu_{t}(U),\rho_{t})$, which is not the
same as $X^{\rho}$. Continue with the proof,

$\displaystyle J_{W}(\mu,\pi)-J_{W}(\nu,\pi)={\mathbb{E}}\bigg{[}$
$\displaystyle\sum_{t\in{\mathbb{T}}}\left(f^{1}_{t}(X^{\pi}_{t},\textsf{W}\mu_{t}(U))-f^{1}_{t}(X^{\pi}_{t},\textsf{W}\nu_{t}(U))\right)$
$\displaystyle+\sum_{t\in{\mathbb{T}}}\left(f^{2}_{t}(X^{\pi}_{t},\pi)-f^{2}_{t}(X^{\pi}_{t},\pi)\right)+g(X^{\pi}_{T},\textsf{W}\mu_{T}(U))-g(X^{\pi}_{T},\textsf{W}\nu_{T}(U))\bigg{]}$
$\displaystyle=$
$\displaystyle\sum_{t\in{\mathbb{T}}}\int_{[0,1]\times{\mathbb{R}}^{d}}\big{[}f^{1}_{t}(x,\textsf{W}\mu_{t}(u))-f^{1}_{t}(x,\textsf{W}\nu_{t}(u))\big{]}\mu_{t}(du,dx)$
$\displaystyle+\int_{[0,1]\times{\mathbb{R}}^{d}}\big{[}g(x,\textsf{W}\mu_{T}(u))-g(x,\textsf{W}\nu_{T}(u)\big{]}\mu_{T}(du,dx)$

Similarly,

$\displaystyle J_{W}(\mu,\rho)-J_{W}(\nu,\rho)=$
$\displaystyle\sum_{t\in{\mathbb{T}}}\int_{[0,1]\times{\mathbb{R}}^{d}}\big{[}f^{1}_{t}(x,\textsf{W}\mu_{t}(u))-f^{1}_{t}(x,\textsf{W}\nu_{t}(u))\big{]}\nu_{t}(du,dx)$
$\displaystyle+\int_{[0,1]\times{\mathbb{R}}^{d}}\big{[}g(x,\textsf{W}\mu_{T}(u))-g(x,\textsf{W}\nu_{T}(u)\big{]}\nu_{T}(du,dx)$

Taking difference,

$\displaystyle
J_{W}(\mu,\pi)-J_{W}(\nu,\pi)-(J_{W}(\mu,\rho)-J_{W}(\nu,\rho))$
$\displaystyle=\sum_{t\in{\mathbb{T}}}\int_{[0,1]\times{\mathbb{R}}^{d}}\big{[}f^{1}_{t}(x,\textsf{W}\mu_{t}(u))-f^{1}_{t}(x,\textsf{W}\nu_{t}(u))\big{]}(\mu_{t}-\nu_{t})(du,dx)$
$\displaystyle\quad+\int_{[0,1]\times{\mathbb{R}}^{d}}\big{[}g(x,\textsf{W}\mu_{T}(u))-g(x,\textsf{W}\nu_{T}(u)\big{]}(\mu_{T}-\nu_{T})(du,dx)$
$\displaystyle\leq 0$

by the assumed Larsy-Lions monotonicity. However this contradicts (19), and we
conclude that $\mu$ and $\nu$ should be the same.

##  Appendix G Proof for Approximate Equilibrium

###  G.1 Comparable dynamics

Define $I^{n}_{i}:=[(i-1)/n,i/n)$ for $i=1,\dots,n-1$,
$I^{n}_{n}:=[(n-1)/n,1]$, and $\mathbf{I}^{n}:=I^{n}_{1}\times\dots\times
I^{n}_{n}$. Let $(\mu,\pi)$ be a $W$-equilibrium, and $X$ is the Markov chain
controlled by policy $\pi$. Let $X^{u}$ denote the state process conditional
on $U=u$.

Fix $\forall n\in{\mathbb{N}}$, and any
$\textbf{u}^{n}=(u^{n}_{1},\dots,u^{n}_{n})\in[0,1]^{n}$. Assign player $i$
the policy

$\displaystyle\widehat{\pi}^{n,\textbf{u}^{n},i}(t,x_{1},\dots,x_{n}):=\pi(t,u^{n}_{i},x_{i})$

and let
$\mathbf{\widehat{X}}^{n,\textbf{u}^{n}}=(\widehat{X}^{n,\textbf{u}^{n},1},\dots,\widehat{X}^{n,\textbf{u}^{n},n})$
be the state dynamic of all the players

$\displaystyle\widehat{X}^{n,\textbf{u}^{n},i}_{t+1}\sim
P_{t}(\widehat{X}^{n,\textbf{u}^{n},i}_{t},\widehat{M}^{n,\textbf{u}^{n},i}_{t},\widehat{\pi}^{n,\textbf{u}^{n},i}_{t}(\mathbf{\widehat{X}}^{n,\textbf{u}^{n}}_{t}))\qquad\widehat{X}^{n,\textbf{u}^{n},i}_{0}\sim\lambda_{u^{n}_{i}}$

where

$\displaystyle\widehat{M}^{n,\textbf{u}^{n},i}:=\frac{1}{n}\sum_{r=1}^{n}\xi^{n}_{ir}\delta_{\widehat{X}^{n,\textbf{u}^{n},r}}$

and $\widehat{M}^{n,\textbf{u}^{n},i}_{t}$ is the time $t$ marginal. Let
$\widehat{X}^{n,\textbf{u}^{n},\beta,j}$ denote the dynamic of player $j$ when
she change her policy from $\widehat{\pi}^{n,\textbf{u}^{n},j}$ to $\beta$.
More specifically, player $j$ follows

$\displaystyle\widehat{X}^{n,\textbf{u}^{n},\beta,j}_{t+1}\sim
P_{t}(\widehat{X}^{n,\textbf{u}^{n},j}_{t},\widehat{M}^{n,\textbf{u}^{n},(\beta,j),j}_{t},\beta_{t})\qquad\widehat{X}^{n,\textbf{u}^{n},\beta,j}_{0}\sim\lambda_{u^{n}_{j}}$

and all other player $i\neq j$ follows

$\displaystyle\widehat{X}^{n,\textbf{u}^{n},i}_{t+1}\sim
P_{t}(\widehat{X}^{n,\textbf{u}^{n},i}_{t},\widehat{M}^{n,\textbf{u}^{n},(\beta,j),i}_{t},\widehat{\pi}^{n,\textbf{u}^{n},i}_{t}(\textbf{X}^{n,\textbf{u}^{n},\beta,j}_{t}))\qquad\widehat{X}^{n,\textbf{u}^{n},i}_{0}\sim\lambda_{u^{n}_{i}}$

where the empirical neighborhood measure is

$\displaystyle\widehat{M}^{n,\textbf{u}^{n},(\beta,j),i}:=\frac{1}{n}\left(\sum_{r\neq
j}\xi^{n}_{ir}\delta_{\widehat{X}^{n,\textbf{u}^{n},r}}+\xi_{ij}\delta_{\widehat{X}^{n,\textbf{u}^{n},\beta,j}}\right)$

and $\textbf{X}^{n,\textbf{u}^{n},\beta,j}$ denotes the vector
$\textbf{X}^{n,\textbf{u}^{n}}$ with the $j^{\text{th}}$ element replaced by
$\widehat{X}^{n,\textbf{u}^{n},\beta,j}$.

For $\forall u\in[0,1],$we define $X^{\pi,u}$ to be the process with marginal