Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach
Authors: Christian Fabian
Kai Cui
Heinz Koeppl
Venue: ICLR 2024 poster (2024)
Keywords: Mean Field Games
Equilibrium Learning
Networks
Large Graphs
Multi Agent Systems
Primary area: general machine learning (i.e., none of the above)
TL;DR: We develop a novel graphex mean field game framework that enables us to learn otherwise intractable equilibria on sparse realistic networks via a hybrid graphex learning approach.

Abstract: Learning the behavior of large agent populations is an important task for numerous research areas. Although the field of multi-agent reinforcement learning (MARL) has made significant progress towards solving these systems, solutions for many agents often remain computationally infeasible and lack theoretical guarantees. Mean Field Games (MFGs) address both of these issues and can be extended to Graphon MFGs (GMFGs) to include network structures between agents. Despite their merits, the real world applicability of GMFGs is limited by the fact that graphons only capture dense graphs. Since most empirically observed networks show some degree of sparsity, such as power law graphs, the GMFG framework is insufficient for capturing these network topologies. Thus, we introduce the novel concept of Graphex MFGs (GXMFGs) which builds on the graph theoretical concept of graphexes. Graphexes are the limiting objects to sparse graph sequences that also have other desirable features such as the small world property. Learning equilibria in these games is challenging due to the rich and sparse structure of the underlying graphs. To tackle these challenges, we design a new learning algorithm tailored to the GXMFG setup. This hybrid graphex learning approach leverages that the system mainly consists of a highly connected core and a sparse periphery. After defining the system and providing a theoretical analysis, we state our learning approach and demonstrate its learning capabilities on both synthetic graphs and real-world networks. This comparison shows that our GXMFG learning algorithm successfully extends MFGs to a highly relevant class of hard, realistic learning problems that are not accurately addressed by current MARL and MFG methods.

Published as a conference paper at ICLR 2024
LEARNING MEAN FIELD GAMES ON SPARSE GRAPHS: A HYBRID GRAPHEX APPROACH
Christian Fabian, Kai Cui & Heinz Koeppl
Dept. of Electrical Engineering and Information Technology, Technische Universität Darmstadt (christ ian. fabian, heinz. koeppl @tu-da rmstadt.
ABSTRACT
Learning the behavior of large agent populations is an important task for numerous research areas. Although the field of multi- aallt--geettenn reinforcement learning (MARL) has made significant progress towards solving these systems, solutions for many agents often remain computationally infeasible and lack theoretical guarantees. Mean Field Games (MFGs) address both of these issues and can be extended to Graphon MFGs (GMFGs) to include network structures between agents. Despite their merits, the real world applicability of GMFGs is limited by the fact that graphons only capture dense graphs. Since most empirically observed networks show some degree of sparsity, such power law graphs, the GMFG framework is insufficient for capturing these network topologies. Thus, we introduce the novel concept of Graphex MFGs (GXMFGs) which builds on the graph theoretical concept of graphexes. Graphexes are the limiting objects to sparse graph sequences that also have other desirable features such as the small world property. Learning equilibria in these games is challenging due to the rich and sparse structure of the underlying graphs. To tackle these challenges, we design a new learning algorithm tailored to the GXMFG setup. This hybrid graphex learning approach leverages that the system mainly consists of a highly connected core and a sparse periphery. After defining the system and providing theoretical analysis, state our learning approach and demonstrate its learning capabilities on both synthetic graphs and real-world networks. This comparison shows that our GXMFG learning algorithm successfully extends MFGs to a highly relevant class of hard, realistic learning problems that not accurately addressed by current MARL and MFG methods.
INTRODUCTION
In various research fields, scientists are confronted with situations where many agents or particles interact with each other. Examples range from energy optimization (González-Briones et al. 2018)
or financial loan markets (Corbae & D Erasmo 2021 to the dynamics of public opinions (You et al.)
2022). To predict the behavior in these setups of great practical interest, one can employ numerous algorithms from the field of multi-agent reinforcement learning (MARL), see /Zhang al. (2021) or
Gronauer & Diepold (2022) for overviews. Although there is a rapidly growing interest in MARL methods, many approaches are hardly scalable in the number of agents and often lack a rigorous theoretical foundation. One way to address these issues is the concept of mean field games (MFGs) introduced by Huang et al. (2066) and Lasry & Lions (007). The basic assumption of MIGS and their corresponding learning methods is that there is a large number of indistinguishable agents where each individual has an almost negligible influence on the entire system. Then, it is possible focus on a representative agent and infer the group behavior from the representative individual. Approaches to learning MFGs include entropy regularization (Cui & Koeppl 2021a Guo et al. 2022; Anahtarci et al. (202). fictitious play (Cardaliaguet& & Hadikhanloo 2017 Perrin et al. 2020 Elie et al. 2020 Xie et al. [2021] Min & Hul 2021), normalizing flows (Perrin et al.) 2021 and online mirror descent (OMD) (Pérolat et al. 2022 Laurière et al. 2022b), see Laurière et al. 2022a) for survey.
Despite their benefits, standard MFGs also have some strong limitations. Especially, basic MFGs assume that each agent interacts with all of the other agents. For real-world applications such as financial markets, pandemics, or social networks it appears to be more realistic that agents are connected by some sort of network and only interact with their network neighbors. To incorporate

---

Published as a conference paper at ICLR 2024
such network structures into MFGs, Graphon MFGs (GMFGs) have been proposed and learned in
the literature (Caines & Huang 2019 Gao et al. 2021 Cui & Koeppl 2021b) Vasal et al.) (021). The graph theoretical concept of graphons gives a limiting object for growing sequences of random dense graphs, see Lovász (2012). However, their applicability to real-world networks is limited by the rather strong assumptions the networks necessary to use graphon theory.
GMFG algorithms can only learn equilibria for dense graph sequences where each agent is connected to an infinite number of neighbors in the limit. This excludes erucial sparse networks such as power laws graphs observed in many real world networks (Newman 2018). Even somewhat sparse extensions of GMFGs. namely LPGMFGs (Fabian et al., 2023), can only model networks with low power law coefficients between zero and one where the number of neighbors per agent still diverges to infinity. Besides the degree distribution, researchers are frequently interested in other important graph features such as the so-called small world property. This property states that if persons A and are friends and B and C are friends, A and are likely to be friends as well (the friend of my friend is my friend) and is characteristic for many real world networks (Watts 1999 Amaral et al. 2000).
To obtain an expressive model and corresponding learning algorithm, we employ a different, both more flexible and more involved concept, called a graphex (Caron & Fox 2017; Veitch & Roy 2015 Borgs et al. 2018b) which generalizes the graphon idea and builds on the representation theorem by K>KKlleeebrg (1990). While point to later sections for details, a graphex intuitively enables the modelling of graph sequences with features such as the small world property and sparse graph sequences where almost all nodes have finite degree in the limit. Furthermore, their flexibility enables the combination of different graph features, e.g., having a block structure with power law degree distribution, see Caron et al. (022).. Building on graphexes, we propose graphex mean field games (GXMFGs) which bring the above mentioned network features into an MFG setup and thereby closer to reality. This expressiveness adds substantial new challenges for the design of a learning algorithm as well as the respective theory which we address with novel hybrid graphex approach.
The aim of this paper provide a theoretical analysis of the model. Thus, we propose the hybrid graphex learning approach, which consists of two subsystems, a highly connected core and sparsely connected periphery. This allows us to depict the large fraction of finite degree agents, who would be insufficiently modelled by standard MFG techniques. Our method contains a novel learning scheme specifically designed for the hybrid character of the system. Finally, we demonstrate the predictive power of our learning algorithm on both synthetic and real world networks. These empirical observations show that GXMFGs can formalize agent interactions in many complex real world networks and provide learning mechanism to determine equilibria in these systems. Our contributions can be summarized as follows:
design a learning algorithm for this challenging and realistic setup and
1. We define the novel concept of graphex mean field games extend MFGs to important class of problems;
2. We provide theoretical guarantees to show that GXMFGs are an increasingly accurate approximation of the finite system;
3. We develop a learning algorithm tailored to the challenging class of GXMFGs, where we exploit the hybrid structure caused by the sparse nature of the underlying graphs;
4. We demonstrate the accuracy of our GXMFG approximation on different examples on both synthetic and empirical networks.
THE GRAPHEX CONCEPT
This section provides brief introduction graphex theory. It is based the existing literature to which we refer to for more details, e.g. Caron et al.) (2022) and Janson (2022). Intuitively, the crucial benefit of graphexes is that they can capture the structure of many real world networks where both graphons and Lp graphons provide insufficient results, see Figure for an illustrative example. In our context, a graphex W 00) + [0, 1] is symmetric, measurable function with 0 < J2g W(a, B) dad,3 < co and f&, W(a, a) do co. For technical reasons, we also assume
that lima-+00 Wa,, a) and lima- W (a. a) both exist. For convenience, we often write
Ew(a) = =/{ W(a, d3 and Ěw == / 32
d) dad3.
2

---

Published as a conference paper at ICLR 2024
gragoph
LO GFAP vn Brach
GONpee grash
degree
100
Figure I: Four networks, each with around 15k nodes and 50k edges. The Erdös-Rényl graph (left) generated by a standard graphon does not have any high degree nodes. The Lp graphon graph (middle left) has few high degree nodes expressed by the flat degree distribution tail. The graphex (middle right) and real subsampled Flickr network (right) (data from Mislove et al. (2007); Kunegis (2013) showa a very similar degree distribution with rather broad tails and core-periphery like structure.
Now, we associate each finite graph G with graphex WO, Therefore, assume that G is some finite graph with vertex set V(G) and edge set E(G) and that without loss of R the vertices ordered in some way 01y.--; UN- One associate G with graphex WG follows. First, partition the unit interval into N subintervals I1.... ......; IN of equal length with I
N N for all S j S N. Then, (C (a, B) 1 for E I and 3 I& if and only if (wy, v%) E EG) and W (a, B) otherwise. To obtain expressive associated graphexes for sparse graphs, we stretch them by defining the stretched canonical graphon W. 3) WG (IW"11/2 a, ||
f0 a, B = || with ||W*|| 2E(G)/N² and zero otherwise.
Conversely, to sample almost surely finite graphs from a graphex, we start with a unit-rate Poisson process (0,, ity) )aN on IR3 where each tuple (0;, ) is a potential node for the sampled graph. Then, any pair of candidate nodes (0,, 0z). (0): ,,,) connected by an edge independent of all other edges with probability W 02). To obtain an almost surely finite sampled graph, we stop the process at an arbitrary but fixed time v > 0 by only keeping candidate nodes with 0; S и and edges (w, v,) with 0g, Oj S v. In the remaining graph, we discard all isolated vertices with degree 0 which yields an almost surely finite graph G, = (V,, Ev) (Veitch & Roy, 2015 Theorem 4.9). A random sequence of such sampled graphs (Gu)o>o converges almost surely the generating graphex in the stretched cut metric (Borgs et al. 2018b Theorem 28). This motivates our first assumption.
Assumption 1.
a) The sequence of stretched empirical graphexes (Wv) converges to the limiting graphex W in the cut norm, i.e.
| - Wo = sup | W(a, 3) - Wo (1, 9) dadB +0 as v w U.V
Juxv
where the supremum is over measurable subsets U, V C R24. Also, assume that
b) Ew is non non-increasing with Ey' (a) = inf 0 Ew (8) S at = (1+o(1))((1/))) a as a + 0 with a E [0, 1] and slowly varying function (Vc > 0: lime- ((cr)/{(x) = 1):
c) and there exist C, and oo 2 0 with (wo) such that So W(a, =) (B, < CEw (w (8)a for all o., 2 on with a > max ( o) if E (0, 1) and
if 1.
Parts b) and c) of Assumption] D are standard, see Caron et al. (2022) for details. Assumption bb) focuses on the behavior of Ew at infinity and states for E (0, 1) that (w(a) (a) roughly follows a power function a a- for large Assumption [c)) is of technical nature and especially holds for the rich class of separable graphexes which satisfy (a. 3) = (w (3))/E/ Combining these insights, Assumption[] especially fulfilled by the separable power-law graphex used in our learning algorithm. We choose the separable power-law graphex for its conceptual simplicity and ability to capture the topology of many real world networks (Naulet al. (021) and leave the use of different graphexes to future work. Graphexes are the limit of very different sparse graph sequences than those depicted by Lp graphons (Borgs et al. 2018a 2019) see Borgs et al. (2018b) Proposition 20).
3

---

Published as a conference paper at ICLR 2024
3 GRAPHEX MEAN FIELD GAMES
In this section we introduce the finite and limiting game. The proof's corresponding to the thcoretical results can be found in the appendix. Throughout the paper, assume the state space X' and action space to be finite and work with a discrete, finite time horizon T = {O...., the set of probability distributions
T ......T arbitrary finite set A. We start with the finite game.
1}. Let P(A) be
3.1 THE FINITE GAME
Consider a finite set Ve of agents who are connected by a graph Gy = (Vr, sampled from graphex by stopping v. For an individual V, define the neighborhood state distribution by
Σ jeV,
((jEE,)
degv, (i)
Each agent i chooses a policy n. == =1 P(4) x competitively maximize the objective
Txx
Mv)) =
Σ r (Xi,s ULe G.,,) LIT
where r X x P(X) R is some arbitrary reward function. The dynamics of the finite system are for all i E V, given by the initialization Xi,0 Po and for all t E T by
US ~ Tie (. (x,)) and X1,+1 ~ P((1 Xi,s, Use, GY,,
Here, P:A' x u x P(x) + P(X) is arbitrary transition kernel that formalizes the transition probabilities from the current state to the next one given the action and neighborhood. To complete the model, we adopt suitable equilibrium concept from the literature (Carmona 2004: Elie et al.) 2020) that allows for the occurrence of small local deviations from the limiting graphex structure.
Definition 1. An (e, (.r)))Mrrro--ass equilibrium (MNE) with e,p >> 0 is tuple of policies (m1,.... (V2) ITlv such that there exists some set V V. with [V]] (1 Vvl and
mV.)) 2 sup JT T , (vo) - 8 for all i V,
R;Ell
3.2 THE LIMITING GXMFG SYSTEM
Due to the underlying graphex structure, our limiting system with infinitely many agents differs significantly from existing MFG models which based graphons, for example. It consists of two subsystems we call the high degree core and the low degree periphery which both have very different characteristics. While the core consists of relatively few agents with high number of connections between themselves, low degree individuals in the periphery almost exclusively connect to agents in the core. Analyzing this novel hybrid system is challenging and allows us to develop new learning algorithm for approximating equilibria in these sparse and often rather realistic systems, see e.g. Figure To obtain meaningful theoretical results, we make a standard Lipschitz assumption. Assumption 2. P, W, and are Lipschitz.
The high degree core. Nodes are part of the core their latent parameter a fulfills 0 S a ax. Here, 0 < a* < is arbitrary but fixed cutoff parameter that marks the border of the core. With an increasing stopping time v the expected degrees in the core also increase and become infinite in the limit. Therefore, highly connected agents characterized by their low parameters The neighborhood distribution Go c E P(2') for every 0 S a S a" and f E T is defined by
a².
1 (H.(())= Ew.a- (a)
with Ew (oyaa-aa==0 and just write Go0, when μ is clear from the context. Then, for all core agents a E [0, a²) the model dynamics are
(a) = J0d W(a, 3)33. For notational convenience, we often drop the dependence on μ
Un n (:) Xa.)
and Xa P(: X Un,t, G2.)
4

---

Published as a conference paper at ICLR 2024
for all E T and initial Xa.0 Mo- Each agent chooses policy aa to maximize J E EIET (Xa,t, La,, [2,t)] ]. The corresponding core MF forward equation is given by
Mas+1 == P t.," = Iua (x)
Σ
C (u | x) P (- u, (4))
DER
MEN
with M4.00 = Mo- Furthermore, define the space of measurable core mean field ensembles M P(X)Tx(000") with a + Ha,t being measurable for all (H,t, t, x)) E M x T x X. Analogously, the space - ".,a"" contains all measurable policy ensembles with a + (u,((u)z) being measurable for all t, u) E II T X' x xu. We write μ v (T)) for a tuple (H, π E -M x I1 μ is generated by π according to the above MF forward equation. Conversely, define (()) as the set of optimal policy ensembles π with Ta E arg = J/'(zt (अt) for every a [0, a"] under the given MF For the limiting system we define mean field core equilibrium (MFCE).
Definition 2. A MFCE is a tuple (1,,T) M I with μ (T) and E P(1)).
Under a standard Lipschitz assumption, a mean field core equilibrium is guaranteed to exist. Lemma 1. Under Assumption 2 there exists a mean field core equilibrium (μ, π E M
x x II.
For measurable, bounded functions f: X x I + IR we define a mean field core operator by
Pe (F,00' = a² / Σ I(e, (())
NEX
The low degree periphery. Let ge = E k G NC) be the set of possible neighborhoods for agents with a finite number latent parameter a and finite degree &o the model dynamics
of neighbors. For agents in the periphery with
k Gha, ~ Pr (G&, = =- 1 Xa,a), Ua, ~ aa, (-1 Xa,), Xa.+1 ~ P (- Xa,t: Ua G&,))
for all t T and Xa.0 μo. The probability distribution Pr (Gh,, = Xo.t) / can be calculated analytically, see Appendix Oppendix[forr [or details. A key difference to the core dynamics with deterministic neighborhoods in the limit is that in the periphery, the neighborhoods remain stochastic. This is caused by the finite number neighbors of periphery agent, which is finite even in the limit. An extension to degree specific transition kemels (P* for each k) is straightforward but neglected for expositional sim- plicity. Each agent a chooses policy Ta to maximize JHh (Ta)
|EEET' (Xa,t- Ua,1 G G-
The corresponding MF evolves according to
12, == Mo,t P b.
Σ Evae(t) ZEX
Σ PT (G. (v))= = G Faat = GEG
Σ (u x) P( Ix, u, G) well The periphery empirical MF operator for finite degree i and measurable, bounded f: X I R is pK*(() =
E
[deg(())=k)
VaLE.
Sa, (x)
V.
V
VIIETT
ZEX
which intuitively is the average over evaluating the function of over all agents with degree k. For the k-degree mean field in the limiting system stopped at we analogously define the MF operator
VEW
/
p (f.))
Poi
Σ ((.aa)) a)) da DE
J P. (k)dda
where Poi. (k) is the probability for in a Poisson distribution with parameter v&w (a). Stopping As shown in the next
is necessary ensure the existence of the integral via the factor subsection, these two operators are closely related for sufficiently large a* and v. For our learning algorithm, choose kinez < co the maximal degree contained in the periphery.
Remark 1. The union of the core and periphery does not contain some intermediate degree nodes. These intermediate nodes are negligible for the limiting system and our learning algorithm for two reasons. Due to the integrability of the graphex W, intermediate nodes have a vanishing influence on the neighborhoods of all other agents for sufficiently large a². Similarly, the maximal degree kmax for nodes contained in the periphery increases, the fraction of intermediate nodes becomes arbitrarily Corollary 5) and makes them negligible for the MF of the whole system.
small CCron al. 2022
5

---

Published as a conference paper at ICLR 2024
3.3 GXMFG APPROXIMATION FOR FINITE SYSTEMS
To compare the finite and limiting GXMFG system, we give some definitions that connect both systems. For an empirical graph G2 sampled up to time v, the corresponding empirical MF is iaa
Eien. 1 LaE( 1-1 ValeoT ValkoT
0x; and the empirical policies are A². = =iiev. A Vai Valsel
Furthermore, define the map (TT) == ( (F1,..., AvV1) 1 with n; Ta(i)
dog(()) if deg(u.) S
kmax and n. [a(i) otherwise, where a(i) = for notational simplicity, If one agents deviates by playing policy म; instead of тú denote this by ( mi) == (T.....,,,.....TTT))) provide the MF convergence result for the high degree core.
First,
Theorem (Core MF convergence). Lei ग E II be Lipschitz up to a finite number of discontinuities with μ = (T). Under Assumptions all measurable functions f: X x I
and the policy I (T āg) II with R, II, t T, for uniformly bounded by some M, >> 0 and for each & > 0
there exist some v' v(("), of such that
E holds for all v v/ (a') and a* a' uniformly over all possible deviations n. i V..
1z (J, a²)l] S
similar result holds for the low degree periphery and connects the two operators defined previously. Theorem (Periphery MF convergence). In the situation as in Theorem 7 for each & > 0 and finite k E N there exist a', v' (a') > 0 such that
E
( p ( SE
holds for all a" o' and 2 v' uniformly over all possible deviations म. I11 V..
Finally, we establish approximate optimality of the GXMFG policies both the core and periphery. Theorem 3 (Core approximate optimality). Consider MFCE (1,, T) under Assumptions and 2 with π Lipschitz up to finite number of discontinuities. Then, for any E,p >> 0 there exist d'v''aa) (ca)² > 0 such that for all a* > a', V 2 v'(a') the policy (T) is an (E.N)-MNE for the core. Theorem 4 (Periphery approximate optimality). Under Assumptions 7 annd consider an optimal policy ensemble π Lipschitz up to a finite number of discontinuities for a MF ensemble μ,, i.e. Ta E arg max Jr, for all a E R., Then, for any E.p > 0 there exist a', v/ v/a()) 0 such that for all a" > a. (a') the policy (TT) is a periphery (E.P)-MNE.
LEARNING ALGORITHM
The hybrid graphex approach and the corresponding learning algorithm, see Algorithm I consist of two parts. Intuitively, the first step of the algorithm is to learn an approximate equilibrium for the high degree core agents. In second step, this approximate core equilibrium is leveraged also learn the optimal behavior of the many periphery agents. For approximating the core equilibrium, we utilize the well-established online mirror descent (OMD) algorithm (Pérolat al. (022) and emphasize that the theoretical algorithmic guarantees provided by Pérolat et al. (2022) also hold in our case. Therefore, we partition the core parameter interval [0, a") into M subintervals of equal length and approximate all agents in each group by the agent at the centre of the respective subinterval. Thus, we obtain a game with A equivalence classes of agents for which an equilibrium learned via OMD. Here, we choose OMD for its state-of-the-art performance but other learning methods could be incorporated into our framework just as well. In Algorithm| [ the Q function is
T (x, u) == r(x, u. G..) + Σ |x, x. Gi,)) arg max QT. (a', w'eu
Z'EX
where Gi, is the discretized neighborhood. In the second step, remains to learn the approximately optimal behavior of the periphery agents. We interpret the dynamics in the periphery as a standard
Markov decision process (MDP) with reward r (2s, u) == E [r(,, U, Gk) X, = x, U. = u] and transition kernel P/ (=.11x, [x, u) = E [P(x' Y,, U. G/) X, - 2, U. = u. Here, Qu Tmax is defined
as above with r/ and PK instead of r and P. Recall that in the limiting model the periphery does not influence the core agents. Therefore, its neighborhood. The reformulation as a standard MDP then allows us to apply the theoretically well-founded calculation of the Q function via backward induction (dynamic programming).
action by periphery agent has effect on

---

Published as a conference paper at ICLR 2024
Algorithm 1 Hybrid Online Mirror Descent (HOMD)
First step: solve for the core equilibrium
2: Input: update weight 7, number of iterations Tmax, number of equivalence classes M, a
3: Initialization: vi, = for all T
4: for r -- 1....... Tmax do
5: Forward update for all via equation ①I for given nf: P
6: Backward update for all i: Q,,,"
7: Update for all i, 2T, u
v (Ir, u) V.,( u) + Qi. see (z
8:
9: T (-1ar) = softmax (v1,)+1(x,.))
end for
11: Second step: determine the optimal strategies in the periphery
Input: maximal degree in the periphery kmax
13: for ll kmax do
14: Backward update for k: Qhi
15: end for
5 EXAMPLES
In this work, we consider three numerical examples inspired by the existing literature. In each example, a crucial modification that the agents are now connected by topology generated by power law graphex. For more detailed descriptions and problem parameters, see Appendix G
Susceptible-Infeetee Susceppiblee (SIS). The SIS epidemics model a well-known benchmark problem for learning MFGs (Laurière et al. 2022b Becherer al. 2023) and of practical relevance to epidemics control without immunity. Here, agents in the susceptible state (a = S) can choose a costly action that prevents costly infection (æ: 7), and the probability be infected scales both with the number of connections and the fraction of infected neighbors, while the probability of recovery remains constant. Additionally, we consider the Susceptible-Infeeter RecevveedRecooeeed (SIR) model (Laguzet & Turinici 2015 Lee et al. 2020 Aurell et al. (2022) as an extension of the SIS epidemics model allow for modelling epidemics with immunity using third, terminal state R.
Rumor Spreading (RS). Lastly, in rumor spreading problem as in Cui et al. 2022) agents (e.g.. on a social network) randomly contact neighbors and try to spread a rumor to neighbors unaware (U) of the rumor for reputation gain, while avoiding to spread the rumor to aware neighbors (U).
Simulation on synthetic networks. We assume the underlying graphex to be of separable power law form W (a, 3) (1 -1/01(11 3) 11/a with a 0.5. In Figure 2 we show the convergence of Algorithm I contrast to naive fixed point iteration (FPI), i.e. the core exploitability
E = max max
Σ DE
(o(x)) max QTT (a, u) well
Σ ma(x)) Σ TEX
TTo( x)) (z. u)
wEll
Exploitability 3
10
10a
10
10a
10
10a
100
FPI HOMD
10
10
(a)
(b)
(c)
100
100
10
102
10a
100
10
102
10
100
10
102
10a
Iterations n
Iterations n
Iterations n
Figure 2: The core exploitability & is optimized with respect the iterations of Algorithm
(a):
SIS; (b): SIR; (c): RS.
7

---

Published as a conference paper at ICLR 2024
o
k ==
(a)
(b)
(c)
0.4
0.3
0.2
Av An
0.2
0.2
0.1
0.1
0.0
0.0
0.0
250
500
750
250
500
750
250
500
750
Graph size /
Graph size
Graph size v
Figure 3: Difference Apt +
El 14 [1 and Aμ
E pi [I]] of the
27
periphery k-degree and core MFs against the empirical k-degree and k > kmax MFs with respect to for sampled graphs (# 95% confidence interval, 20 trials). The parameters
10 and 750 corresponds to approximately N = 40 and N 26750 nodes. (a): SIS; (b): SIR; (c): RS.
is optimized which quantifies the limiting MFCE quality. The resulting MFCE is then applied in randomly sampled graphs for fixed y by computing the periphery optimal strategies as in the second step of Algorithm[]
[ As result of applying the obtained equilibrium in the preceding examples, in Figure 3 we observe the convergence of empirical periphery k-degree MFs and core MFs k kmax for degree cutoff kmax to the limiting MFs predicted by the GXMFG equations in Section as + 00, validating the derived theoretical framework. For qualitative results, see also the next section and the following Figure 4
SIMULATION ON REAL NETWORKS
Beyond synthetic data, we find that our framework is capable of producing good equilibria in real world networks. Under the separable power law form, for each empirical data estimate with the procedure proposed by Naulet et al. (202T). Although this simple estimation yields reasonable evaluation results, we believe that developing more complex estimators would also further increase the accuracy of our GXMFG learning method. If data sets contain multiple directed edges, we substitute them by one undirected edge obtain simple, undirected graphs. We consider the following real world networks from the KONECT database (Kunegis) (011)): Prosper loans (Redmond Cunningham| 2013), Dogster (Kunegis) 2013), Pokec (Takac & Zabovsky 2012). Livemocha (Zafarani & Liu 2009). Flickr (Mislove al. 2007). Brightkite (Cho et al.
2011
> Kmax
k =
MF core
MF 3
k 2
k
MF A
MF k 4
1.0
(a)
(b)
(c)
(d)
0.5
0.0
0
250
500 0
250 Time t
500
250 Time t
500
25
50
Time t
Time t
Figure 4: Comparison of the empirically observed MF on a real network with the predicted equilibrium for (a) SIS: x on Prosper; (b-c) SIR: r = and r = R on Dogster; and (d) RS: æ = on Pokec.
8

---

Published as a conference paper at ICLR 2024
Table 1: Expected average total variation Aμ
E 12 jt -Melli E [0, between the overall
2T
GXMFG MF prediction br and the empirical MF dr Σ,
Ox; (#: standard deviation, 5 trials).
Expected total variation Ap in %
network
# nodes
# edges
SIS (%)
SIR (%)
RS (%)
Prosper 0.058
89269
3.3 MM
0.53 0.21
2.06 + 0.25
1.58 + 0.31
Dogster
0.071
426820
8.5 MM
2.78 = 0.44
4.93 + 0.98
1.89 + 0.66
Pokec
0.108
1.6 MM
22.3 MM
2.14 = 0.05
4.93 + 0.12
2.19 + 0.08
Livemocha
0.075
104103
2.2 MM
2.57 0.20
4.40 + 1.08
2.51 = 0.54
Flickr 0.506
2.3 MM
22.8 MM
3.57 0.08
8.58 + 0.24
2.24 + 0.11
Brightkite 0.376
58228
214078
1,37 = 0.11
10.92 = 0.77
3.37 + 0.25
Facebook 0.252
46952
188453
2.90 = 0.09
13.57 + 0.37
5.01 + 0.27
Hyves
0.585
1.4 MM
2.8 MM
5.07 0.24
10.06 + 0.81
2.62 + 0.44
Facebook (Viswanath et al. 2009), and Hyves Zafarani & Liu 2009). See the respective papers for detailed network descriptions.
The plots in Figure give give qualitative impression of the algorithmic performance of our approach on real world networks and show that the estimated equilibrium is close to the empirical MF on the real networks. The quantitative empirical results can be found in Table I where the overall predicted GXMFG mean field is = Ex pk,4* + (1 - Σn Ph) with p oT f (I!I - ))), see Caron et al. (2022, Section 6.3) for the choice of Pę- Similar results are shown for the periphery mean fields, see Table in Appendix G Furthermore, our GXMFG learning approach clearly outperforms LPGMFGs (Fabian et al. 2023) (and thereby also the subset of GMFGs) on all of the considered tasks and real world networks, see Table Appendix G for details. These results indicate that the ability of GXMFGs to depict sparse networks with finite degree agents is crucial advantage over existing GMFG and LPGMFG models, both conceptually and empirically.
In Table I each row shows the estimated graphex parameter & and the number of nodes and edges for each real world network. The last three columns contain the (normalized) expected total variation Ap which measures how close the empirical mean field fa is the predicted mean field μ of the graphex learning approach for each of the three examplary models SIS, SIR and RS. One can see that the accuracy of the hybrid graphex learning algorithm is somewhere between a deviation of 1.5% up to 5% for most of the real world networks and examples. While the MFs for SIS and RS are learned accurately (Δμ < 5.1%) on all networks, the SIR approximation performs well on the Prosper, Dogster, Pokec, and Livemotcha networks. A possible explanation for the under average performance on the Brightkite and Facebook data sets could be their rather small number of nodes which decreases the accuracy of our asymptotic approximation. Additionally, some networks such as Hyves might not be represented optimally by a separable power law graphex. We think that proposing more evolved approximation schemes and thereby allowing for more diverse graphexes would improve the performance of our algorithm on these networks, which we leave to future work.
7 CONCLUSION
In this paper we have introduced the concept of graphex mean field games. To learn this challenging class of games, we have developed novel hybrid graphex learning approach to address the high complexity of sparse real world networks. Our empirical examples have shown that learning GXMFGs could be promising approach to understanding behavior in large and complex agent networks. For future work it would be interesting to develop and use more precise graphex estimators and to apply our setup to various research problems. Furthermore, spaces, as well as continuous time, could be a next step. We hope that our work contributes to the applicability and accuracy of mean field games for real world challenges.
extension to continuous state and action

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work has been co-funded by the Hessian Ministry of Science and the Arts (HMWK) within the projects "The Third Wave of Artificial Intelligence 3AI" and hessian.AI, and the LOEWE initiative (Hesse, Germany) within the emergenCITY center. The authors acknowledge the Lichtenberg high performance computing cluster of the TU Darmstadt for providing computational facilities for the calculations of this research. We thank the anonymous reviewers for their helpful comments on improving the manuscript.
REFERENCES
Luis Nunes Amaral, Antonio Scala, Mare Barthelemy, and Eugene Stanley. Classes of small- world networks. Proceedings of the National Academy of Sciences, 97(21))1114--1115 2000.
Berkay Anahtarci, Can Deha Kariksiz, and Naci Saldi. Q-learning in regularized mean mean-ficll games. Dynamic Games and Applications, 1 13(1):89-117, 2023.
Alexander Aurell, Rene Carmona, Gokce Dayanikli, and Mathieu Laurière. Optimal incentives to mitigate epidemics: a stackelberg mean field game approach. SIAM Journal on Control and Optimization, 60(2):5294-$322, 2022.
Dirk Becherer, Christoph Reisinger, and Jonathan Tam. Mean-field games of speedy information access with observation costs. arXiv preprint arXiv:2309.07877, 2023.
Christian Borgs, Jennifer Chayes, Henry Cohn, and Yufei Zhao. An Lp theory of sparse graph convergence II: Ld convergence, quotients and right convergence. The Annals of Probability, 46 (1):337-396, 2018a.
Christian Borgs, Jennifer T' Chayes, Henry Cohn, and Nina Holden. Sparse exchangeable graphs and their limits via graphon processes. Journal of Machine Learning Research, 18:1-71, 1, 2b.
Christian Borgs, Jennifer Chayes, Henry Cohn, and Yufei Zhao. An Lp theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 372(5):3019-300 2019.
Peter Caines and Minyi Huang. Graphon mean field games and the gmfg equations: s-nash equilibria. In 2019 IEEE 58th Conference on Decision and Control, pp. 286-292. IEEE, 2019.
Pierre Cardaliaguet and Saced Hadikhanloo. Learning in mean field games: the fictitious play. ESAIM: Control, Optimisation and Calculus of Variations, 23(2):569-50) 2017.
Guilherme Carmona. Nash equilibria of games with a continuum of players, 2004.
François Caron and Emily B Fox. Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society Series Statistical Methodology, 79(5): 195-1166, 2017.
François Caron, Francesca Panero, and Judith Rousseau. On sparsity, power-law, and clustering properties of graphex processes. Advances in Applied Probability, pp. 1-43, 2022.
Eunjoon Cho, Seth A Myers, and Jure Leskovec. Friendship and mobility: user movement in location- based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1082-1090, 2011.
Dean Corbae and Pablo D'Erasmo. Capital buffers in quantitative model of banking industry dynamics. Econometrica, 8966):975-3003,, 2021.
Kai Cui and Heinz Koeppl. Approximately solving mean field games via entropy-regullrizeed deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 1909-1917. PMIR, 2021a.
Kai Cui and Heinz Koeppl. Learning graphon mean field games and approximate nash equilibria. In International Conference Learning Representations, 2021b.
10

---

Published as a conference paper at ICLR 2024
Kai Cui, Wasiur R KhudaBukhsh, and Heinz Koeppl. Hypergraphon mean field games. Chaos: An Interdisciplinary Journal of Nonlinear Science, 32(11), 2022.
Romuald Elie, Julien Perolat, Mathieu Laurière, Matthieu Geist, and Olivier Pietquin. On the convergence of model free learning in mean field games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7143-7150, 2020.
Christian Fabian, Kai Cui, and Heinz Koeppl. Learning sparse graphon mean field games. In International Conference on Artificial Intelligence and Statistics, pp. 4486-4514. PMLR, 2023,
William Feller. An introduction to probability theory and its applications, Volume 2, volume 81, John Wiley & Sons, 1991.
Shuang Gao, Peter E Caines, and Minyi Huang. Lag graphon mean field games: Graphon invariant subspaces. 2021 60th IEEE Conference on Decision and Control (CDC), pp. 5253-5260. IEEE, 2021.
Alfonso Conzalez-Briones, Fernando De La Prieta, Mohd Saberi Mohamad, Sigeru Omatu, and Juan M Corchado. Multi-agent systems applications in energy optimization problems: A state-of- the-art review. Energies, 11)):1922, 2018.
Sven Gronauer and Klaus Diepold. Multi-agent deep reinforcement learning: survey. Artificial Intelligence Review, pp. 1-49, 2022.
Xin Guo, Renyuan Xu, and Thaleia Zariphopoulou. Entropy regularization for mean field games with learning. Mathematics of Operations Research, (7(4):3239-3260) 2022.
Minyi Huang, Roland P Malhamé, and Peter E Caines. Large population stochastic dynamic games: closed-looy mckean-vlasov systems and the nash certainty equivalence principle. Commun. Inf. Syst., 6()):221-252, 2006.
Svante Janson. Graphons and cut metric sigma-finite measure spaces. arXiv preprint 1rxiv:1608.01883, 2016.
Svante Janson. On convergence for graphexes. European Journal of Combinatorics, 104:103549, 2022.
Olav Kallenberg. Exchangeable random measures in the plane. Journal of Theoretical Probability, 3: 81-136, 1990.
Jérôme Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web, pp. 1343-1350, 2013.
Lactitia Laguzet and Gabriel Turinici. Individual vaceination as nash equilibrium in sir model with application to the 2009-2011 influenza a (hin1) epidemic in france. Bulletin of Mathematical Biology, 77:1955-4 1984, 2015.
Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese Journal of Mathematics, (1):229-260, 2007.
Mathieu Laurière, Sarah Perrin, Matthieu Geist, and Olivier Pietquin. Learning mean field games: A survey. arXiv preprint arXiv:2205. /2944, 2022a.
Mathieu Laurière, Sarah Perrin, Sertan Girgin, Paul Muller, Ayush Jain, Theophile Cabannes, Geor- gios Piliouras, Julien Pérolat, Romuald Elie, Olivier Pietquin, et al. Scalable deep reinforcement learning algorithms for mean field games. In International Conference on Machine Learning, pp- 12078-12095. PMLR, 2022b.
Wonjun Lee, Siting Liu, Hamidou Tembine, Wuchen Li, and Stanley Osher. Controlling propagation of epidemics via mean-field games. arXiv preprint wxxv:2006.001444 2020.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Ming Min and Ruimeng Hu. Signatured deep fictitious play for mean field games with common noise. In International Conference Machine Learning, pp. 7736-7747. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2024
Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, and Bobby Bhattacharjee. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM Conference Internet Measurement, pp. 29-42, 2007.
Zacharie Naulet, Daniel M Roy, Ekansh Sharma, and Victor Veitch. Bootstrap estimators for the tail-index and for the count statistics of graphex processes. Electronic Journal of Statistics, 15: 282-325, 2021.
Mark Newman. Networks. Oxford university press, 2018.
Julien Pérolat, Sarah Perrin, Romuald Elic, Mathieu Laurière, Georgios Piliouras, Matthieu Geist, Karl Tuyls, and Olivier Pietquin. Scaling mean field games by online mirror descent. In Proceedings of the st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp- 1028 1037, 2022.
Sarah Perrin, Julien Pérolat, Mathieu Laurière. Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 13:13199-13213, 2020.
Sarah Perrin, Mathicu Laurière, Julien Pérolat, Matthieu Geist, Romuald Élie, and Olivier Pietquin. Mean field games flock! the reinforcement learning way. In Proceedings of the Thirtieth Interna- tional Joint Conference on Artificial Intelligence, IJCAI-21, pp. 356-362, 2021.
Ursula Redmond and Pádraig Cunningham. A temporal network analysis reveals the unprofitability of arbitrage in the prosper marketplace. Expert Systems with Applications, 4092) 2013.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. International Scientific Conference and International Workshop Present Day Trends of Innovations, 2012.
Deepanshu Vasal, Rajesh Mishra, and Sriram Vishwanath. Sequential decomposition graphon mean field games. In 2021 American Control Conference (ACC), pp. 730-736. IEEE, 2021.
Victor Veitch and Daniel M Roy. The class of random graphs arising from exchangeable random measures. arXiv preprint arXiv:1512.00
2015.
Bimal Viswanath, Alan Mislove, Meeyoung Cha, and Krishna P Gummadi. On the evolution of user interaction in facebook. In Proceedings of the 2nd ACM Workshop Online Social Networks, pp. 37-42, 2009.
Duncan J Watts. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology, 105(2):493-527 1999.
Qiaomin Xie, Zhuoran Yang, Zhaoran Wang, and Andreea Minea. Learning while playing in mean- field games: Convergence and optimality. In International Conference on Machine Learning, pp. 11436-11447. PMLR, 2021.
Ge You, Shangqian Gan, Hao Guo, and Abd Alwahed Dagestani. Public opinion spread and guidance strategy under covid-19: A sis model analysis. Axioms, 11(6):296, 2022.
Reza Zafarani and Huan Liu. Social computing data repository asu, 2009.
Kaiqing Zhang, Zhuoran Yang, and Tamer Bayar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp. 321-384, 2021.
12

---

Published as a conference paper at ICLR 2024
A OVERVIEW
On the following pages, we often write Sa- to express an error term depending on a" such that lim -000 E 0. The following lemma will be of frequent help us for proving various conver- gence results. In the subsequent sections, we often just refer to Assumption implication formalized by the next lemma.
| but tacitly also mean its
Lemma 2. Assumption / implies sup-isasi Sn_ I (W(a, (a B) ((3) da - as v + oo where the supremum taken over all measurable functions g R. [-1,1].
Proof of Lemma To show the statement, we adapt a proof strategy in Lovász 2012 proof of Lemma 8. to our case. We reformulate
sup / -15551 R- JR+
-W,,), ((3) d3 da
sup {
(VVa,B)-W..oo f(a)g(8)ddde
-15f.911 JR.
[ / (W(a, - Wx(a, (f(a) - (aa)) - of (B)) d8 do
sup
05T.5' a''' S1 JR, JR,
1 (W(a,8)) - ()(a, (())g(3)d do do
sup
oSt.f' S1 R4 JR+
1 JR R2
(W(,,))-W B)) f(a)g/ (B)) dB
J [
(W(a,)) Wa 3)) (((a)((3)d8d) d8
JR.
+ {
(W(a, (V(a,B)-WW(a.. B) ('(a)g d3
R4 JR+
< 4 W| - wo
4sup U.V
W(a, 8) Wa(a, dadg - + as リ 0
UXV
where the inequality in the last line follows from Janson (2066 equation 2.5) and the convergence is a consequence of Assumption T
We continue with proving the first theoretical statement from the main paper.
Proof of Lemma 7 Since in the limiting mean field core system we 'cut off" the graphex at parameter a", can think of the remaining part of the graphex standard graphon, where point to Veitch & Roy| (2015) Section 3.1 and Theorem 5.6) for a detailed argument. Thus, the limiting core system can be interpreted standard graphon mean field game which means that the existence of a mean field core equilibrium follows from Cui & Koeppl (2021b Theorem 1).
B PROOF OF THEOREM I
We prove the claim by induction over t = O. The induction start follows from a law of large numbers argument similar to the one for the first term below. For the induction, we leverage the inequality
E [1in) - (1,'))
<
i" (f,a" j p.t.00 U.,')
1.p.
Ai pr (f,aa) - i p (
+
W.
+
p.. P.p. -
- -M.P..o
+ E
A ((,p" - -ip
13

---

Published as a conference paper at ICLR 2024
+ pi w. (o,w((faa) - -f,a")((ttii
- -ifi(ffaa)]
In the following, we upper bound each of the five terms separately.
First term.
We start with the first term
E
(141((,a")
pi p Lp (a.
1
E
f(x', a (ast da - Σ r'EX
ΣEmr pla(())
a+
2'ENZEX
(a) (a) Lo ((a, (), d8 I (a)
Σ
na, (u x)) P
x' 1'1 S
uEll
Ea Ea. Lp
1
-E
Σ
Ma' a)) - ho
Σ (a,e(x)
α**
α
ZEE
ZEX
Σ
Mant (u x) P
x' 2,, Swe (a) JR
W(a, (a's,) d8 f(x', a) a)
NEll
Ea
Lp 1
+ a
E
Σ
(
f(x
iEV. ica" /2/
Valkoll Valkol
x. x]]
E
f(Xi a)
/2|Byl V2l
(
Ea¹
Lp
+
1
E
Σ
1-- (viieo) Valeol
f(X da
a*
V iica" /2|Eul
27
x,))
E
f(X; (X do
X,
Valmpl Valnol
[(x,a)) 1
max
Ea Lp 1
(x,a))xX
1-1
ax
E.
S
Via" V2T
1/2
Ear Lp
1
M2aa * E2
SE,
α*
a*
FE
++0 10000
for a' and v large enough, where we exploited the fact that hev, are independent if condi- tioned on X, (X)
Second term.
For the second term we have
E
(f.a") / pt (f
1
E
Σ
Σ Po (z)tt (u x)
at
St.ar Ex''ue
14

---

Published as a conference paper at ICLR 2024
P x' Id, u, Fw, (a) /- W(a,8)ig, d8 s(,'
Has (u x3) P 2o2' I1, (w.a((a) / W(a, 8) d3
Σ (x,())
Σ
5( a(2',a)da
2,2'EX
wEl
Lr + (())
(aa, 3)R3, d3 1-" W(a, d3
Σ
fa'
a" ((**)
x'EX
(L o(1))
W(a, 3)02,1 d8- - I W(a, 3) dB 1
da
a'EWaa-
[L o(1))
! (), W(a, (z) dB da
max ZEA
a"EWaa-(0s
which converges to 0 - oo, where the convergence follows from Assumption T and 13 being bounded by 1 by construction.
Third term.
The third term converges to 0 by the following argument:
E
C. (f,a") (...
1
E
Σ
Σ (o) (u x))
E. uell
P x' 11, Ew.r (a) 1" ((a,)) 9) d8 s(ol,a)
0o aat (u x) P x' 1d, Ew.a (a) 10" ((a, 3) d8
E (T)
Σ
f(x,, [(', da da
x.x'EX
well
M
max Xx
E
| (u 1))=))a0 - Ta, (u |x) da
a*
M
max
E
Σ
Ma,t (u x) ane (u |x) da
a²
jE Vu.jei jia 22
V
Valnal
max (x
#a. (u x) - - (u x da
c-1 V9l
M
2D
2
+
as v - co.
E
E
E
Here, Dr denotes the finite number of discontinuities of æ.
Fourth term.
We have
E
j t.j. (f,
3.. Pm (f.")
E
Σ
(x)
Σ
teat (u (x)
a+
2, EX
well
x x Iz u, Ew (a) 1"d "((a, Viaa))'' d8) s(x',a)
1
P
15

---

Published as a conference paper at ICLR 2024
x' 2, u, Ew.a (a) ['" W(a, 3) f()'
Σ (1
E. wEll
M
Σ
l" 3(3,
{-" W(a, 3) d3 da W(a, (1) /"" ((a,,))oos( da
E
a' EW. (a*)
x'EX
M a a'EW,a- (ar)
max WEE
E
which goes to zero as + co. This convergence follows from the induction assumption. To see this, we consider the functions a (z. 33 (a,, 33 (x=xa) which, combined with the induction assumption and Fubini's 's theorem, yields
1 E %
L-" W(a, ((a,)))a da
W(a, ()
/ E ( a²) (T a*)] da - 0 as + 00.
(x,
Fifth term.
Finally, for the fifth term we know that
j P.p.. (J,a") - ((ttl
=E
E
Σ
( (u|x)
a
2,x' EX well
(w. //
1
p x' 1 u.
W(a, d3 f( a) da
f(d',
1
Σ
(a)m(a) (u (u)x)
α
Ex well
x' 12, (w. ( (0 W(a, )), Ma a) (ad da P
a
1
Σ
Phe (1)
11
pa"
Σ (Has(e)5((,aadd
Sw.-- (a*)
a
JO
ZEX
a
DEN
a²
E
|
(f',
ui (f')"')
Ew.a- (a*)
where we define the function
f(z, = M (
1 2'1,,u, at " W(a, ds) s(d'aa)
x'E NEW
and apply the induction assumption. This concludes the proof by induction.
C CALCULATION OF THE NEIGHBORHOOD PROBABILITY DISTRIBUTION
Binary state space case. Consider some uniformly. at random picked node t with degree k, latent parameter a and state æn. Furthermore, denote by æı,..., Ty the states of its neighbors. Let j be the number of neighbors in the first state 81.
p n:
(Gole+1 (pt) = j. F0.4+ x²)
16

---

Published as a conference paper at ICLR 2024
k
P T
(Go (Mi) = j, GuA = j' = 20,,000+1- =x)
z'Ex f==0
k
Σ
x0.t G (iT)) = -', = x') P (30,441 = / (px = v0,
20, = d))
n
x'EN f'=0
P 30,++1 (pi)) - |00,+11 x. Got jj; Fo,t nt)
Gir.
p t
Goot (fi))) = j', .0.tt = x') =
Σ
mb.e (u x') p(aa (x1 x' u. j'
k
x'EN y'=0
wEll
P
Go (ax)) = Go.t (it) = J', 2o, xo)
Now, we consider
P
Gr.k (pT) = / (pi)) = j', 20,1 = x')
= -* Go (pt) = i Go (p.) = 5 + (1)
{ PK (o (AT)) = Gö. =,,)= 3) (o)))()ss (3)
= = + JRŽ
= =o( + S
Σ
II
k
The (u xt/) P (Iaa 1/s u, Gh (AT) dB.
JR
(01 (1),2) i=1 wel
E 1 (m:=ss) = j} and 3 = (3)..... Be) a vector of random variables where each one is the latent parameter of one of the k neighbors. Here, Sajs=j is the conditional density function of 3 given that the neighborhood has exactly j agents in state $1- Similarly, 3 = (B (B1,..., Bx) E If is one realization of the k latent neighbor parameters B. Now, we determine
where X² = { Fk) E X
f,,00t (3,5)
fa(3) = j1B = B)
$ S (3)
P(GUA =
P(G =)
where we tacitly assume that P(Gut = j) > 0. The case P(G = 5) 0
can be neglected since P(G j) 2 P (G (pT) = j vo, = x') implies that P (G%, (px) = j', = =xd) which means that the respective summands for the cal- 12uk
culation of PK Gu,t41 (fi)) = j. 2,,41 = 2) are zero and hence can be neglected. We know
that
W(a
fe(3) II
Ew(a)
im1
and
P(Gy = j]| = (3) = E
Σ
II
(w) 1m1
We also have
P(G = =]] /
W(a, Bi)
B1)
Σ
(
d3
Ew Ea(a)
(E) 1=1
W(a, Bi)
Σ E
Ew (a) 11 (2rs)
d3
J4 (EE
17

---

Published as a conference paper at ICLR 2024
which eventually yields
(EE E [T= ((a,)))
Po (1:)) ((a, (w(a)
DIG ( Juy Dee
I
M (21) d5"
Neglecting values larger than a", we obtain the following formulation for the limiting system P'r (G (me) = j Caa, (me) j', Faxe wax=xx)
E(m..))ex II W(a,8) (r(()) (3))
= =Joccy Soarr E(ermee)ex IT== W(a
(w(a) / (R (2)) d3'
Σ
I1
Bit (u xt) P (xx 2 u, G (1+) d3.
(1) 1= wEM
The following inequality connects the two systems
Pn (Ga, (1²) = j Ga (1²) = j Faat = x')
P Go (ft) = C..e (p²)) = v00 =0=)= < < + Ear (2)
xo,
To see this, we reformulate
Pr (Ga, (1x) = =i G. (ux) = i Ja, xd)
P" Coltt1 (itt) j Go, (fit) = 20,, a')
- -Voar Foo.n.9 E(emmeeex 11
Een. II ((a,3) 1000 (()))
(a)
W(a,
Ew (a) 11 (z+) d3
k
Σ
II
B.a (u a() P (are 1/, u, GB (14)) dB
(x....))) DEXY El
EOu E I
W(..%))
p (H:)
(a())
Jen Say E(srmewexx E
I1
((
M (zi)
d33'
Σ
Ta, (u x4)) P (zi |2/ Gy,, (at)) d3
(EX))))) t=1 nell
S Tmn Tan + +Tmm + T(v) Tiv)
where Ta), Tan, Tan,, T(vy, Tiv) denote five terms which are defined and bounded next. Start with
Ta Vaae Spa0. Elermeeex I
E(m I W(a.fi)
(w(o) M, (v:)
W(a.%)
(w)a) 11 1. (2)) dB
Σ
II
Thtt (u x1) P (2s 2/ u, GR. (Hi)) ds
(e) U2) NeW
Eigr..wweN E [
((.)8))
13 (y:)
(a)
JRL Spaarr E E(ErmeeEE I (a(a) 10 1R dg'
W(a
Σ
II
T (u x()) P (Na 2/ u, G2., (1+)) d3
(E) wEll
18

---

Published as a conference paper at ICLR 2024
/
I a (
En- 011)
Σ (nn--.
(iml
E
(aa, B.) (w(
II
Σ well
(u x.) P (xra a'', u, G (pe)) dā
Biit
( dea aml
co +1( Σ
Σ E
(01-.- (a (E).)
k
W(a, Bi)
Σ
Biit (u md) (ara a/es u, G.. (me)) d3
Ew(a)
wEll
I1 (1RR - -10 (11))
Er +k(aa) +k(aa)*-1000
Σ (u1...uuJE2 (#I...u))E2)
Σ
E
W(a, 31)
Σ
Tii (u x4) P ((1 x/ G3 (Hi)) dB
Ew (a)
wEll
= + o[1)
by applying Theorem I in the last line. Moving on the second term
E(mn- | Sp.arre E E(esmeede I
k ((a
1' (v:)
Ew
Tay
W(a,
(a( M (2,) d3'
d3'
Σ (E
I
20 (u xt) P (xe a/ u, CZ (He) d3
Σ Be E I ((,,&.)
P (3))
(a)
Saz E Exemm.e)
E
I &w (a)
W(a.f%)
f (zi) d3'
Σ
112
00 (u z P (zi a/,, u, G (HI) ds
Bie
note that the difference of the two denominators is bounded by
W(a, B) (2) Ew(a) (a) (Z,,(2z)
Σ II
100
b W
3) 2y (2),((ss)
Σ (AL,...A)EZ)
E
az'
s Ear o(1)
Ew(a)
by an argument as for the term Tay Hence, the second term also bounded by
Tay S Ear + +())
Finally, are left with defining and bounding the third, fourth and fifth terms Tovy; Tay-- They are given by
Tin) = /
Ennn..meee E I
W(a.8.)
(a)
Pl (y:)
Jag Exs
Wla
pu (2s) d3'
(a)
19

---

Published as a conference paper at ICLR 2024
M II
Σ
20 (u 24) P p 2 u, G3 (me) d8
MimE)E) i=1 HEll
Di IE W.J.Y
((a.3))
P (U:)
(a(
B4 Jat E(mmaneex E
II
li= (a) 1 (zi) d3
Σ
II
Bi. (u x4) P (xt I u, C3. (At) d3
()) i=1 well
and
/ E(m... E
W(a,8:)
BB, (y:)
(w(a)
T(v)= =
Ses E(srmee)ex E
II
W(a.()
11 (2i) d3
Ew(a)
Σ
IE
Bis (u xx)) P (xv 2/. u, G3,, (at) aB
(E ilwEM
E Wen E
k
((a.)))
A (8:)
i==1
(a)
Rat Sax
Jexyy E
I
w(a,01)
Ew Ewr 13 (zi) d33'
Σ
I1
n But (u xx))
(av x u, G. (At) dB
(1 1=1 well
and
/es Say
E
E
(a(
PB (v:)
T(v)
E
I
W(o.
Ew (a) 13/ (zx) 033'
&
Σ
IE
a.e (u x4))
P (xi
a/ u. G. (A()) dB
(x1...2))E EEYY i= wew
E(orn E
I (a.
po (y:)
(a(
J4 JR. Eeemewee E
I li=1 (w (1) (2i)
((.
d33'
na. (u xt) P (I: 2 u, GY (At)) d3 (E....)))) weld
Σ
I
where each of the three terms is bounded by arguments in the proof of Theorem This establishes inequality (2p. The just proved inequality (2) also implies by induction that
Prim (G& (Hr:) = j. Fa.: = 2) - P n. (GO, (AT) = j. zo.: = 2)) < o(1) + Fa
(3)
where S.* an error term depending on a* with lim +oo c.- Exploiting the symmetry the limiting model, we can further reformulate the probability in the limiting system as
Σ I
T (u
x+) P (a: 2/ u, G (1x)
(Ex) 1=1 uell
Σ
T..t (w 81) P P(x, s1,u, G3. (At) d3:
20

---

Published as a conference paper at ICLR 2024
II
Σ
Bett (u 82) P P( 82, u, G3 (AT) dB,
i=j' +1 well
min(jsy')
Σ
IIE YiluEM
TBe (u (( 81, G (1²))
t=max (0,+-+-''"
II E
Die Tu (s22 ",, GR. (p:)
1=++1 NEN
++3'=E
(G-²)
(ul (2) P (s1 82: u, G3i (pe))
f wEW
II
Σ
( (2) ( $2 G3 (me))
F -111 wEll
Combining these findings we arrive
PT.. (Ga, (14) = Fa,,1111 = x²)
Pai (Gra (Hi) j ta, =x)=xx)))) x') Σ Tu P (xx((1 pI u, 1
-ΣΣ
Z'E
Nell
E(on--wwex 1I li==1 (w(a) 11, (vi)
((,
Soaay Saaarj E(ELmOwERY 11
W(a33))
M (zi) d,3'
Sw (a)
min(id7)
Σ
I1
Bie (u 81) P ( 51, G3 (we))
(==1 well
5'
II Σ
T Te (u
- P(s2 s1)
s1, u. G3. (Hi))
1= 1 well
II
Σ
00 Th. (2) P (s1 82, u, Go. (wi))
(= uEll
tht (u (2) 82) P (s02 82, u, G (1x)) d3g ... ...3.
+=j+f'-(# wEl
wEll
for the limiting system.
Extension to general finite state spaces. Consider some uniformly, at random picked node vo with degree state zo and latent parameter a. Furthermore, denote by Ii,..., 2y the states of its neighbors. Let G gt ...., k E g be the neighborhood and X' {s....., sa} the finite state space, where d is the number of different states, and 91 is the number of neighbors in the first state 81, 922 in the second state 82, and so on.
ge)
pd T
Kuuk Go
(pT)
G, =
Σ
Σ
P
(vu.k
Go (A/) G, G,G. G., x', 20,41 =
C'Egt
Σ
Σ
P
(fT) Go
G., = xz
FEN G'egt
P n
20, = x 30,441 = x Go (1/) = G.,
21

---

Published as a conference paper at ICLR 2024
P* Go (pi) = G 20,,+11 = I, Go = ,0,
20,1 = 2 TÔ. (u x') (x: I u,,
Σ d'EX' G'EGt
Σ
G (fit) = G.', Too, = =')
Σ
wEll
Cuck p
0, (ft)) G Go (p!) G², 20, = xz)
We focus on
P"r Go (pt) G Gbtt (ii) G¹, Iu,t z¹)
= 00,+1 (Ri)) G G (ft)) G¹) + o(1)
= =o + / P"
Gu.k (p+)) = G Go (PT) = G. B) (0)
R
k
o(1 + / Soiogt=0
Σ
II
The (u (=]x) P (a: 2 u, G. (At)) dB.
pt
(2imm)))) E i=1 well
where X2 = (x......zx)) E Ex :bj [d] Ets (m:=a))) 93}. Similar to the binary state case, we can calculate
I / ( E(s E [I W(a,3)) (alaa 11 (1F;)
JRy DxExE E II
Wla.9)) P4 // (25) d3
(w(a)
This brings us to the limiting case
Px (Ga,441 (Hi) G G (Me) ,i, Fast x')
Eomn..neexx 11 Ew (w( (3..
W(a.)))
= -Joan Spaar E(Ermewees l
W(a.8()
(w 1 (2) d
Σ
I1
T.e (u x;) P (Is 24 u, GR (Hi) ds.
(.....)))EE
NEEL
Following the argumentation in the binary case, we can establish the two inequalities
Px (G& (1²) = G G (1t) =
Ta,t Ta,t = x')
-P Gu (Ét)) G
G (pT) G², x0, = =a) < <<(1) +Ea- (4)
and
P (Gh,, (1)) = G, Ra,t x)) - P Pi (G*t (p%) = Ru, = 2)) < <(()) + Eaa (5)
For notational convenience, let us define set of matrices A (G, GG) for each pair of vectors G,G E g and finite l E N
d A², = = {A- (an))se(4 E Naxd Σ are = gi and
atj = g/. Vi,j [d]
Keeping in mind the symmetry of the limiting model, we have
Σ IΣ
Th. (u xx) P (xra 2/6 u, G3., (me))
(2 Ex 1=1 uell
d
Σ
Σ Te (u 89) P (2: 885 u, G7 (1:))
(xx j=1=i1
NEW
22

---

Published as a conference paper at ICLR 2024
d
Jf aij..... adj
Σ
II
Σ
de Bie
(u 83) P
Pss 83 u, G2 (itt)
(1y))actO) (CCC))EEA"CC,))) (G=
i=1
Nuell
Eventually, the previous results yield
PT (G (14)
G,Ja,t11 = 2) PaT (Ga,t (Hi) Fa, =2') Σ
-E> Σ
Tast (u x2) ((x u.. G')
x'EX x'EX (o1....9a)EN. t1t...9.Ebk
NEM
Σ NExx IT ((a,8.)
13, (Vi)
(a)
E
1o.ar So.ay ExEmmEEeE I W(a.s)
Ew(a) 1B 1
(zi) d3'
(AG.G))
d II f=1 01j.
II
Σ Auel
TBa sz) P P(s: 8jz u. G3 (ft))
d.
.dl.
D PROOF OF THEOREM
This proof focuses on binary state spaces X' (s,, 82) The extension of the proof given below to arbitrary finite state spaces is straightforward, although the notations are sometimes less convenient. We prove the claim via induction over and start with the case
E
M ( (GC,D)) 1
V2|Eal
E
[dde(t
[(,, (()
Vork
LEV.
DEN
VEW
Poin. (k)
> f(x, a(t
Jo poi (k)daa
xEX
(1)) W
S E
Σ [ddeg(m)=k)
Va|Eo!
((x,a))a da
0c Wo (1)) da
4-1 Val
iEV
ZEX
VEW
Poiw. (k) Σ
f(x, a) (l
Jo Poiw. (k)da
FEX
+ E
Ew
| Poil (k)
00
Σ
f(x, ()
100
Poi (k)da
ZEX
VEW
Poiw (k)
Σ
[(x, af
So Poi (k)da
NEx
VEW
E
[deg(())=k)
Σ a1
0o Poi.. (k) da
ieV.
Valkol
ZER
Woi (k) Σ (( da
+(( o(1)
ZEx
where the second summand goes to zero by a standard LLN argument. To see the convergence the first summand, we keep in mind Assumption I and recall Caron et al. (2022) Proposition 1) which states that
25w fw
|Ev] (1 o(1))
2
23

---

Published as a conference paper at ICLR 2024
Furthermore, by Caron al. 2022 Theorem 2) and Veitch & Roy 2015 Theorem 5.5) know that
Vu = (1 (()) / Poi (k) da.
Combining these insights, obtain
2 E.l
(1 (1+)(1))VEE
VEW W So Poiy, (k)
(1+ (1)) ((1)
(1+ =(1)) ( So (k) da
da
Thus, by Kolmogorov's strong law of large numbers (see, e.g. Feller (1991 for details) and Veitch & Roy (2015) Lemma 5.1) we have
VEW
E
Σ LEV.
(deg(v))=))
Σ (t)
So Poi W (k)da (k)dda
1-1 Val
ZEN
E/
Poil, (k)
o(1)
6-1
V2 Evl
aeX
which concludes the induction start.
Now, it remains show the induction step which we do by leveraging the following upper bound on the term of interest.
E
v.le (ft1(f) vf+2(f.0)
5 E
LA
E
p
(f) f. p
(n]
E
u.lk p
W.W. (ʃ) i u.k p (0)
E
p k
L. (f) p p
t. (f)
E
p.kkk
w.W. (f) p. p..p.. (f)
+ E
p
w..w (f) - -1
First term.
By the law of total expectation have
E
u.ke (
[nl
Exl
E
Σ
(deg(t;)=k)
fax
(x) do
V2,kk
BEV.
1/2Euu
DEX
Σ [dde((m)==)
V2l
Σ
Σ fa (2 x)
4-1 V2
xEX
weld
(a,,3)) f(z', a) )
Σ P xt x'ex
x' 1211
u.
1
Sw. Saarr (a)
/2 Ey [Vrnkl
c. 0(1) E
[dde((p.)=k)
Va|eul
Σ
f(x, ((x,a))" (4) da
V2/Bul
xEX
1 [deR(v:)==]
Ral
( Σ #adt (u x))
1-1
E
/2
NEX
weld
W(a,3) f(a .) aa
P
12| U.
Eip (a)) JR.
#'E
24

---

Published as a conference paper at ICLR 2024
E2
= c.- E 0(1) + [Vaal
Σ iEV.
1 [deg(e))=k]
da
x1
E
V2
f(x da
x
V2 B S 0c))
Σ
1 (deg((.))=k)
Val
1(X do
|Venel
Val
11) 27
E
f(x+)), da
X,
Ea- 011) + V Eu [Vekkl
|
E
f( da
1-1 wal
iVV.
27
valvol
E
f(Xi () da
X,
V21kol
I Ec) + E2
2M,
1 (doR(v:)=R)
[Vr
/2
KEVe
0(1)+ 2M, V Exl.
(Vee
2M
Ea.
0(1)+
[V,
2|E,]
-00 as +0000
for a and y large enough, where we point out that the {X/+1 hev. are independent if conditioned on X, (Xi
Second term.
The second term can be bounded by
E
v.k pa.0c 1,,
(f)
u.k p
[r]
2 E [V2.1
E
Σ iV
1 (drg()=))=))
V
Ept (2,((2)
Σ
Etas
Na.1 22)
V2|Bul
TEX
nell
P
x' Ir, U,
W(a, (,, d3 ((d a) aa da
S a- (a)
e'EX
Σ
=dkg(()==)
Px
Guik (At) = Na.t = x
Σ wEll
na, (u x))
1-1 V2l
VEV.
ZEN
j=0
1 (j,k (ik-))) 1) (0n-)))((((a)) f(z'.a)
Σ P
x
I, u,
x'Ex
< < +11)aa +
+
E
[dcg(vv)=k))
VaTeul
Σ (2))(x))
Σ
Ro,t (u x)
1-1
iEV.
ValBul
ZEX
NEWl
Σ P
x' x. U.
W(a, Wa,,3) dB f(3',a) da
Enp (a) JR+
S'E
25

---

Published as a conference paper at ICLR 2024
k
- -E (d)g(
vallol
(a,a(x) (x)
Σ
Ps
( (pi) = =j aie = x)
Σ ueul
ao, (u xx)
1-1
VEV,
Valkol
ZEX
1=0
Σ P
x'
u, (i, -j) f(x' f(z',
F'EX
= = + O(1)ea S
for a" and y large enough, where the inequality above leverages inequality (
Third term. This term can be reformulated as
E
u.kk Mi
(f)
Pi &
c.p.w (D]]
W.W.
V2
E
Σ VEV
1 (d)
ValBul
Paep (Guk (PT) j. Erst =x)
[Vunl
ValBol
5=0 xE
Σ MEH
na,t (u (x)
Σ P
x 11 1o (1 f(x', ,)) do
2x ExE
2 Ev
Pa (Ga, (pit) J. Fa,t = x)
Σ
Ma,t (u (x)
Ve,kl
==0
uEul
Σp P N'EX
I u, R. ( 5) s(x', a)
E
Σ (d))
Valkul
Pr @G (P²) j. = x)
Guck
Ve.l
iEV.
Valkel j=0
P (Gaa (pit) = j, L,, = x)) da)
We focus on
ΣΣ E Pri x=0xE
(Guk (it) B. = x)) Pz (Go, (pi) j, So,t = =))l
and recall
Pa.p (G% (11)) = j, 1 = xx)
= =/ha ".aor ZEX well t= f=xax (0.++J'-k) R) Sp.orrJ E(s I Ew(a) R'g (2i) d3'
min(id')
Σ DEXt II W(a.B))
(w(aa 12,,, (Vi)
Σ
W(a.3')
)')
P (Gaa (pt)) j', Faat = x') Ka, (u x²) P
x x1Ix,u, u,
k
Σ tBr (u 81) P (s1 81, u, Go. (Ri))
è
NuEu
Σ Tone (u 82) P (81 82, u, C3,, (At))
8'-
k G
Σ #B, (u [1) P (s2 s1, u, GR., (At))
NuEld
k- i+t
Σ mome (u 82) P 82, u, G3,, (p()) wel
d, ... ..
26

---

Published as a conference paper at ICLR 2024
For sake of simplicity, we introduce the following auxiliary notations (where we fix some x', x'. E):
j'
①1 = (Gh (PP) j', Faat = x') Mant (u x²) P
x x',
K
E DWE II,-=1
11,,, (115)
Ew (a))
Jo.0-1 E Ees II==
W(a
(a((a) ( d.
8
1 6
< Bhe (u 81) P P(1 11,1 u, G (A)))
(I))
wEll
j-t
(II)
Σ
tt (u 82) P (s1 82, u, G (At))
WEM
d'c
(
k --
Σ Lue
(IV)
# (u (1) (822 81, u, Go (it))
(-
k- -ste
(V) Σ
Ap (u 82) P (s2 52, u, G3., (ix))
wue
such that
Pa. i (G 1,41 (p.) = 1111,111
h min (is')
-f Jo.rr Z'EX' j'='' well max (0.
Σ
(I) (II) (mI) (IV) (VV (V)d3, d..3g..
Analogously, we define (I'), (II', (III), (IV'), (V') such that
Pa.
GuA (,141
(Pt) = j. 11.41 =
(is')
= =f p.ar)) I'EX f'=0
ΣΣΣ
E
(T) (IT) (IT) (IV') (V') d3, .0.8...... dBe.
(0.
Thus, using a telescope sum we can reformulate the term of interest
E
Pr..
(Guh (fT) j. Seat = 2)) Pz.f (G (fit) j. Ea,t = x))
1=
min(io'))
ΣΣΣ
Σ
[1( ((') (II) (III) (IV)-
1= xEX (0.0-1 x'ex =0=0 well mmx
[I(II) - (II)) (T)) (II) (IV) (V) E[( - (III)I (()) (())(()))))))) (1)) (IV) (V)
E [I(VV) - (IV)I (1)- (IT) (0r- ( [[(() (() (1) (II) (IV))
d8 .3.g
min min (is'}
Σ3 ΣΣ
Σ
IE [II) - (T')) -00))-000 0(1) - - [I - -I'I -(1)
-=x= 10.0-| x'Ex well t= (0.
E [|III) - (III) O(1) + E [[(VV) [IV')] 0(1) + E [[()) - (V)))
The first term converges for oo by induction, i.e.
E [1)) (T') 0(1) o(1)
Since the remaining four terms are structurally very similar, we just prove convergence for the second term and point out that convergence for the terms three to five be established analogously. Thus,
27

---

Published as a conference paper at ICLR 2024
for the second term we have
|(
'
E ( - (II'II 0 = LE
aan (u 31) ((1 |si, GE, (it))
Nuell
nB, (u 81) P (sl 81, u, Gg (it)) ) 0(1).
Σ WEW
.0).
We briefly recall that for arbitrary p. < oo and finite l E N we have
p - of = (p 1 + + 9² =... (p
p 3 = (p (1) (6)
which brings us to
E [IIII- - (II')] O(1)
E
Σ WEE
ap (u 81) P
((1) (1 81, u, G3 (it))
S1, u, G.a (pt) )){|
Σ NuE
tB, (u [1) (sl
0(1)
Σ a (u $1) (P' (sl 81, u, G4.00 ((t3)) P (sl $1, u, G (it))
E
0(1)
NEll
t (u $1) E P $1 $1, u, G (p)) - P p s1 2ilss,u4 u. G5.0 (it)) O(1)
WEM
$ o11 E O(1)
Combining all of these findings, we eventually arrive at p (....(())
E
u.k p [i
(J)
w.
M
E.
Gu. (Pt) = j, =x]= x)
E
1 [deg(())=k)
Pri
V2,
VEVo
-= xEx
-P
GG (pT) = j, F.,t =x) da
Mf 2 Ew
<
E
(o(1) +ar 0(1)) da = =o(1) F 0(1).
Vo.e
iEVe,k
/
Fourth term. For the fourth term we have
E
v.k p
w. ( - f.t P.p..w (D]
E
E
Σ PaIj (Gh, (At) = =j = x)
Va.al
VEVo.k
j=0 ZE
12,u, Σ Nast (u x)) P al 2z, u, I
(iik (( f(a a) da
WEW
/2
ValBul
Parpi (Gh, (p() = j. Hat x))
SEV..
2=
28

---

Published as a conference paper at ICLR 2024
* ai (u (z). P p( | s,u, u, (J. 5) I ( ())
Σ
NEW
F2 Vu,al
1 E
Σ
Σ Pa (Go (fT) = Baz =x)
iE Vank
Valkel
x=Ox
Σ WEl
Tap (u x))
$a, (u x)| P x'
I, u, 12'12,
to (1 s(x', a) da
+ E
v 2 E Vu.ll
ΣΣΣ
ta, (u) x) P
P(2' x'
2, u, 1
(2,k
KEVe,
j= ZE WEM
[Pr i (oa,, (ii") j. La.t = x)
Pa (G (Pt) j, a, = x)) f(x'; da]
We start with analyzing the first summand, i.e.
Ev
E
Parpa (G (pG) = J. taat x)
Vu,al
S 1EVo,
ks Ta, (u | x) - aa,t (u x) P -P(x (2' I, b (i. ()) f(2'
Σ NEl
< E
E [Vikkl
Vilvvl
Paip (Ca, (RT) = Rest = x)
VEVi, igftt
Val
==
Σ NEU
a (u 2) #hat (u x)) P p xr u, (1, ()) a()'aa)
V2|EoT
2M, f
Poi a (k) da
W
6-1
+
So
Poiw a (k) da
Fll |Vukl
Valiol
T Mr
1
S E
da
+
2 Ey
E
VEVu.
1
=0
0
as - 00.
ETE
VlEy
VTE,
Now it remains to bound the second summand, which is done as follows
E
E
Σ
Valeol
#a (u x)) P x' I Ir u, T (j, A - -j)
1
Vink
SEV..
ValBol
1=0 TE well
PH.A (G%,
(p.)))
j. Ba,t =x) Pr (G&,, (PP) j, =x) da]
M
VilEvl
ΣΣΣ
Voll
1-1
VVV
Va1Bol
xEX well
IE [| (Gh, (f.)) = j, Baat =x) - -Pa,j (G%, (pr) = j, Fa,t = =) da.
To further analyze
E Pa. (Gh, (P.) = j,, 1) - P (G%. (pt)) = j Stat = 2z) ]
we define for notational convenience (and tacitly assuming that &
3'
<2
V2l
Propi (Gh, (pT)= f. m)
29

---

Published as a conference paper at ICLR 2024
min
= -YoOo ΣEΣ Σ
10.0011 w'Ex' 1'=0 well (U,J'''
(1)())) (1)))))000 -II) (IV) (V) ...d3
and
Pa (Ga,s (Ri)) = 31 Bast =
= -fann ΣEΣ Σ (T) (II') (Wr) (V') d,3 -.3
h
min(id')
x'Ex f'=0 well (0.+3'''
with
11 Pr..a (G (PC) j¹, Faat x²) m (u (u) P x x', u, Te
Eomn..nwexxy II Wi
1. (21))
(ax)
S0.0... E E(S IT=
W(a
Ew(()) 1/ d3
8.
(II) (0)
Σ
Bret (u $1) P (s1 81, G (AR)
Nell
(II)
Σ
00 Bii (u 82) P ((1 82, u, G But (at))
5'-e
k 5
(IV)
j - 1
Σ
Biat (u si) P(s2) s1. u, G (pt))
wuel
h- s+8
(V)
Σ NEE
Dia (u 82) P (s2 82, u, GR. (px))
and (I), (Ir), (.r). (IV',, and (V') defined accordingly. As on the previous pages, we use telescope sum to arrive at the bound
P (G%, (PT) = j, Ens x)) - Pa. (Ga,, (Pi) = j, f,, = ==]]]
DEX
min(i
ΣΣΣ
Σ
E [1 (T) 0(1) + [[(I) - (II') O(1)
1= xEX ( xeX j j'=0 well t= (0,++''
+ E (IIII) (II') I1 0(1) + E (IV) - (IV') I| 0(1) + ([()) - - 0(1) d3, ..
where the first term goes to 0 for v - oo by induction, i.e.
E [1() (1') -(1) o().
For the remaining four terms, we recall equation (6) which yields
E P n. (Gh, (fT) = j, j, = x) Pa.a (G&,, (pT) j. = x;)
x=
min(is'))
<0(
ΣΣΣ
Σ O(1)
0z 10,a*1 x'EX 5'=0 max (R
E
Σ m (u' 81) T (u' |
+E
Σ
AB. (u' (822 TZ. (u' 82)
Ell
Lu'eul
d3 ...3.
30

---

Published as a conference paper at ICLR 2024
Eventually, this brings to
2
Σ
ΣΣΣ xxX NEN
Vu.l
iEVu,
E
|| P
(Ga, (pt)
J, Ba,t = - P (G (ft) J. R., = = da
My /
min(s,)}
<o(
Σ
valEul
ΣΣ
ΣEΣ
Σ O(1)
Venal
j= [0,ar1*
iEV
x'EX j'=0 m=max ('
E
Σ Lu'E
Fie
(u'
|11)
N5. (u' |s))|
+E
Σ
mi. (ul
82) mie (ul 82)
Lu'll
d3
d3
which is upper bounded by for - by argument for the first term. This concludes this part of the proof.
Fifth term.
We start with u.k Pr.pi
(J) fit P. [n]
E
/2
k
=E
E
Valkul
Σ
Σ Pr (Goar (P() = J. j. = 2))
Velal
VeVi
j=0 ZEN
Σ wEll
Na.t (u x))
x x
(J, (1)- f(z', a) da
x'EN
2
V2|Bul
P Ti (Gk (14")
-, =x)
iEV.k
2=
Σ WEM
The (u x)) Σ P P x' I 1, 1 (0 1) f(x,
FEN
M 2
Valpul
E
PRiji (G&, (pr)) j, 2))
Venkl
V...
O
PR. (Ga,, (wL) = jiZa,t x)1l da.
Next, we reformulate
h E
Prip (Ga, (AT) = j, Sa, =x) - - (Ga,, (11) = j, Fa,t x3)
by applying a telescope sum trick as for the third term, namely we state
Pria (G%, (pi) = j, fatt = x)
min(in))
= -Jan Σ ΣΣΣ
Σ
... d3. (I) (I) (II) d8)
x'EX =0=0 well
(0,+f x}
and also
Pr (Ga, (uT) fa, =x)
min(id')
= =I(
ΣΣΣ
Σ
(I)- (II) (II) -IV') (V') d8, ...d3
f'E well (0
31

---

Published as a conference paper at ICLR 2024
where we define
(1) = Pr. (Fa, (f4) = j', Fa,t = x¹) n (u (2). (xx 1 u1
8'
k
E(on...nee. Il==1
W(a,0))
11/ (111
(a((a)
Sa.orje E(ELmEEEER Il,
W(a.0'
17 23, (zi) d3
(w(a)
(II) (7) Σ
Bii (u (1) P P(1 51, u, GZ,, (A:))
NuEll
j-t
(III
Σ
Tie (u 82) P P(s 82, u, G3., (At))
NuE
d'-8
(IV) =
k (
Σ
Biet (u $1) ((22 81, u, G7 (pt))
AMEM
k-5' stt
(V) Σ Ti.t (u |22) P (82 82, u. G3, (At))
wEl
and (T'), (IT'), (III', (IV'), (V') are defined correspondingly. Thus, we obtain the useful upper bound
E
Pripa (G.,, (PC) aa,t = =x) -Porip (Gi,, (p() = j. fost = =))
J=0xEX
min(jw')
Σ
E (1) - (f')I 001) + [1(I) - (II')) 0(1)
== xEX [0,0*) x'EX j'= wel max (0.j+''-))
+ [[III) - (III' 0(1) + E [[(VV) (IV') 0(1) + ([V) - (V'Il 0(1)d8 .............. d,3x
Here,
E [I(]= - (1) 0(1)
converges to 0 by induction and an argument as in the proof of inequality 2 Next, we focus on the term
E (II)) (II' -
E
Σ weu
The (u [1) . (s1 18, u, G3 (p:))
Bret (u 51) P ((1 |1, u, G. (p!?) ) '1 0(1)
Σ
.01)
where we once again equation 6 to obtain
E [II)- (0VII--(1
=E
Σ
The (u 81) ((1 81, u, GR. (pt))
nell
E (u 81) (si 181 U,,, (x)))())) 0(1)
wew
$
Σ
20 B
(u (1) [ (s) 81, u, GD, (pt) (s, 81: u. G (4:)) 0(1)
WEW
32

---

Published as a conference paper at ICLR 2024
(w(a) /._ W(a, dB 1
Ew( S W(a, B)us, d3
20 $ Σ
Bi (u 81) max
sEd
WEW
O(() t
=[1] + tEa
where the convergence of the first term for - follows from Theorem Finally, the terms
E [ (II) E [[(VV) (IV')I), and E [I(V) (V'Il
can be upper bounded in similar fashion which completes this part of the proof.
Sixth term.
We have
E
p P..... (J) f (1. [1
th w. (f) u p. (f.v)]
v E
/ V2tEv1
&
E
Σ [dcg(1)==k)
Σ (x)
Σ j=0
Pr (Ca, (4i) = j Io,t = x)
Volke
i-1
V
V2|eol
TEX
Σ wEul
Tas (u x))
xt' [r, u (j, k - -1) Ma' a)) do
N'EN'
Ew S0 Poina (k) da
Jo Poila (k)
(k)
Σ
Σ
Px (G (mi) = j waat x)
ZEN
f=0
Σ
k Ta, (u x)
E
P((2
P
x' 1 1 - 1i,k- S ax)
uEN
Z'E
E2l
Σ (deg(t))=k)
ValBul
Σ
Vanke
VeV.
Valkul
ZEN
Ew
Poin. (k)
Jo Poi (ls) da
xEX
E 1 WL .0)
S
where we apply the induction assumption and define the functions
k
a() = Σ Pr (G.,, (pt) = j Fe,t x)
Σ
Tast (u x)
1=0
uell
Σ P
x'
( (ad
xr, uy 1
x'eX'
This concludes the proof.
E PROOF OF THEOREM 3
For notational convenience we define ali) == E.
Furthermore, we define
a sarJc Vv.
Vr i Vv
CV.
/2 Ey
The next lemma is crucial for proving Theorem
3
33

---

Published as a conference paper at ICLR 2024
Lemma 3. Consider Lipschitz continuous II up finite number of discontinuities D with
I = (T). Under Assumptions and 2 and the policy V R.) E IIVv,l, Rs E II arbitrary, for any uniformly bounded family of functions 9 from X to R and any p, 0, te T, there exist v, of > 0 such that for all > v' and o > af
sup E [()() - E ( [[( <E
gEG
holds uniformly over πं E II, V. for some V S. Vv with VVI (1-p) Vv Furthermore. for any uniformly Lipschitz, uniformly bounded familyy of measurable functions H. from X B(X) to I and any e, > 0, I. E 'T, there exist v/,o' o' > O such that for all v > v' and a" > a'
sup
EE h(XE,, G (
E [((X(()))) (0te,(()))) <E
(8)
bER
holds uniformly over π E 11, Vi some V C Vu with [V (1 p) |V,-l
Proof. Let us start by showing that 7 implies
8 Therefore, we upper bound the term of interest by
E [M(x,,, f.,, G (Px) )] E
h X Xa(s), (M))
E ((X e ((t) - EB ((x,, (()))))]
-E [K(X (4())
[(XKes G (0(0,,((L))) [( G (()))
First term.
We start with [x(,,. G%,
E
-E (x)) - (H))(()
S Ln
TEx
Ln
Σ
L W(o(i, (10 S (aal))))))ss
E (ii))
ZE
Lh
10 Waa(0, So ((a((),8)u,,(c dB
E.t +
(a()a(i)
E.- + o(1)
where the second summand goes to zero for v - oc by Theorem and by choosing a" sufficiently high, the sum can be bounded by E.
Second term
For this term we have
(X C (n.))] h(X,,,, G (H))
Ln
Σ
G (1:)()
(o)))())((a) /
zEN
Ln Σ
(a(()
ZE.
Swa (a(i)) 1 ((a(t),B)pp.
S Ear + Li E
(pp((((())
(
| ((aai)))))a.d
Ew (a(())
Ewar (a(1))
DEX
Lp
W(a(1),
Ew (a((i)
Ea- + o(1)
where the second and third summand converge to zero for v - oo by Assumption ! sufficiently high a", the second term is upper bounded by
Thus, for
34

---

Published as a conference paper at ICLR 2024
Third term. Finally, the third term is bounded by 7 i..
E ((.,,, G (())))()))) - [(Xaa) Gao. (Hi))) <E.
This concludes the first part of the proof. Now it remains to establish (7) via induction over t. At t O, the induction assumption holds by the construction of the model. Thus, it remains to show the induction step
sup geg
E [((x,,))11) E [9((x <E.
We define
(x,
Σ (u/p))
Σ
P(x' 1, G)g((")
wEM
x'EX
which allows us to apply the induction assumption and thereby (by the implication we have proved above) to our term of interest, i.e.
sup
E (0((x,,,1)) E [g(X (((()))++)) gEg
E
- E (u)) <e
and concludes the proof.
Proof of Theorem we have
The proof leverages Lemma More precisely, for the situation as in Lemma
sup Rlell
(T (mI,...,, mv.) Jí (~ ...,...,, m..... . voii
< J ( mvl) - Ja (Ta(s) + sup R,ell
Jalo (Fa(t) - Ja(n) (#+)
+ sup #1E
Ju a(i))
(Ttz) J ( To ....... m..
E (T (Xi,er ((()) E (Taoco (Ra(), Gat G2())c(m.))
E [T (Xic, ((t)) E TTe (Xa(t.) Ca Caln,((u))) 5e
sup eIl
where the last inequality follows from Lemma
3 by defining
(x G)
Σ ((llu)r(Z,,,,
aEL/
for æ E TT. This concludes the proof.
F PROOF OF THEOREM
The proof is similar to the proof of Theorem (1) /
3 As before, we start with a helpful lemma and define
Lemma 4. Consider Lipschitz continuous π E II up to a finite number of discontinuities D.. with (T). Under Assumptions [ and 2 and the policy (x² .r!....T' VVll) = [ n.) E IV.
for any uniformly bounded family of functions G from X to R and any E, p > 0, t E T, there exist v' a' > 0 such that for all v' and a* > a'
sup E [[g(X(t)) - [o(Xa(9)))) <e SEG
35

---

Published as a conference paper at ICLR 2024
holds uniformly over n, II, V for some V2 S Vv with V 2 21-121197 Vol. Furthermore, for any uniformly Lipschitz, uniformly bounded family of measurable functions H. from X B((2) to R and any p, 0. te T N. there exist v/ a' such that for all v >> v and of > a'
sup bEH
E
Go C000, (Ai) E [ G. ((e)) <E
(10)
holds uniformly over Rg E 11 for some V2 S V, with |4 2 (1 [vol
Proof. To show that
9 implies (T). we use the upper bound
h(Lis, C
- E
1( (a()) G Caio)
E h(X,.. G. ((:))) - E h(Xx,, G (mi))
R MXXes, G. (mi) E M(Xis, Go [(m)))
E M(Xi,. G. (H))))
|(xx(0)) G ((
First term.
We start with
(
G (2t))]
- E MxXa,, Git (4))
$ Ln
G. (f1)) (p))
DEX
Ln
Σ
1000 ((a(i)
Ew (a(i))
ZEX
Ln
Σ
Ma((), / ((a(i),))u,
Ea +
ST (c)i)
E.. + o(1)
where the first term goes to zero for - oo by Theorem and by choosing a* sufficiently high, the sum can be bounded by c.
Second term
Moving on to the second term, we know that
E [1 (x aeek (mx)) E MMx.,. G (()))
Ln
E
Gif (m))
E (a (m)) (w)))) = + o11
where the last line follows from applying inequality (5). Therefore, by choosing a sufficiently high a", the second term is smaller than
Third term. Finally, the third term is bounded by 9 analogously to the proof of Theorem 3
E h(X,,, G (H))) ((Xo()))) Gk (())))))))) <E
This concludes the first part of the proof. Thus, we still have to prove 9 via induction over t. This can be done as in Lemma so we point to the preceding proof for details.
Proof of Theorem 4 This proof analogous to the one of Theorem The only difference that instead of leveraging Lemma we now use Lemma 4 Then, the result follows immediately. 1
36

---

Published as a conference paper at ICLR 2024
G EXPERIMENT DETAILS
In this section, we describe problem and algorithm details, and give additional periphery MF com- parisons on the real network datasets that were omitted in the main text. Note that for separable power-law graphexes used in this work, the computations in Algorithm I simplify to calculating the same MF and neighborhood probabilities for all a, improving the complexity of the algorithm in practice. For Algorithm| we use G ~ Multinomial p The code available in the supplementary material.
Algorithm hyperparameters For the implementation of Algorithm 1 we use an inverse step size (temperature) of 7 50 and perform 5000 iterations seen in Figure 2 As degree cutoffs for the periphery, we use kmax = 8 for SIS and SIR, and kmax = 6 for RS, i.c. all nodes with degree k kmax follow the MF policy.
SIS problem. In the SIS problem, we assume state space X' = {SS I consisting of the susceptible state æ S and the infected state æ I. The time horizon T' is the time until a cure is found. Each agent may choose to avoid infections, taking actions U = {P, P) to protect themselves (P) or not (P). The resulting infection dynamics are then defined by the transition kernels
++ (x+x - AG g (11)
(S S,P.)) =1,
for some infection rate Tι 0, where the last term is a scaling factor that scales linearly with the number of neighbors around & = (i.e. randomly meeting neighboring contacts) and eventually saturates to as k + so (too many contacts to meet). The recovery dynamics are given by
p*(S T,u, G) = Tn, Vu E U, E g
for some recovery rate Tn [0, 1). Finally, assume costs for infection and protective actions r(z, u, G) er (1)) + c())
for some coefficients er, cp > 0. In our experiments, use 7 0.2, tn- 0.05, T 500, (o(T) 0.5, cr and cp 0.5.
SIR problem. In the SIR problem, in contrast to the SIS problem, we use the state space X' = RR, i.c. we extend [II by the new recovery dynamics
P*(R I, G) = ph G) = -R. Yu Eu
p*(R R, u, G) = 1, E GE
and the same cost function as in SIS. For experiments, we use the parameters T = =0.05, TR = 0.01, T = 500, (o( po( 0.1, e₁ = 1 and cp 0.25.
RS problem. Lastly, in the RS problem we have agents that are either aware (A) or unaware (A) of the rumor. Agents that are aware may choose to propagate (P) the rumor unaware agents or not (P), resulting in actions U = PJ. The spreading probability is then dependent on the number of propagating agents in the neighborhood, which can be modelled by using the state space X' = (A, A, P. P}, where P and P are aware agents trying to spread the rumor. As result, the overall dynamies are given by
pk (u A, u, G) =
(*(A| u. =)
Pk(A u, u, =1 V' E G gb
2
(AI T(G(1P) 1 1
Yu YuEU,Ge
Since the goal is to spread neighbors that are unaware of the rumor, the rewards for propagation are given by positive rewards scaling with the number of unaware agents, and costs scaling with the number of aware agents.
r(z,
G) = G + G(P)
1r(x))
We 77 0.3, 7 50, (o(S) (m) 0.1, cp 0.8 and rp 0.5.
37

---

Published as a conference paper at ICLR 2024
Table 2: Expected time-averaged total variation Ap = 27 E > [1]
Ilit
E [0, 1] between the
overall GXMFG MF prediction μ and the empirical MF in E.: do
Ee: deg(u;) 6 xxp-
exemplarily for k = 2 and k = 5 (# standard deviation, 5 trials).
Expected total variation Au² in %
Expected total variation Ap in %
network
SIS (%)
SIR (%)
RS (%)
SIS (%)
SIR (%)
RS (%)
Prosper
0.80 0.22
0.86 + 0.43
0.76 + 0.45
1.01 + 0.04
1.21 0.51
1.03 0.74
Dogster
1.36 + 0.25
1.73 +: 0.79
1.02 + 0.53
2.29 + 0.55
3.02 + 0.89
1.67 + 1.43
Pokec
0.95 + 0.05
2.39 + 0.03
1.00 + 0.13
1.56 + 0.09
3.76 + 0.21
1,45 + 0.13
Livemocha
1.16 + 0.17
2.08 + 0.90
0.92 0.59
1.03 = 0.13
1.99 0.95
1.02 + 0.67
Flickr
4.26 - 0.11
7.47 = 0.28
2.16 + 0.10
3.37 + 0.13
12.03 0.47
3.75 0.12
Brightkite
1.23
8.17 + 0.24
2.46 + 0.34
2.17 = 0.22
11.19 0.96
2.83 + 0.64
Facebook
1.32 +: 0.10
10.20 + 0.67
3.56 + 0.21
3.00 + 0.27
12.71 + 1.42
4.06 + 0.72
Hyves
5.99 + 0.35 6.17 + 1.26
1.65 + 0.56
4.44 + 0.44 9.03 + 1.47 2.44 + 0.62
we also show the resulting mean field deviations for low k-degree nodes the periphery. Similarly to the results the main text Table [ we find that the mean field predicted by our GXMFG framework matches the empirical observations in the system on the real networks.
Additional comparisons on real data. In Table 2
Empirical comparison to the LPGMFG model In this paragraph, compare GXMFG approach to the LPGMFG model proposed by Fabian et al. (2023). Note that LPGMFGs include the more restricted class of GMFGs (Cui & Koeppl| 202 lb) which makes a separate comparison of our approach to GMFGs obsolete. The detailed results can be found in Table where we repeat the GXMFG results from the main text for readability and easy comparison. Since the LPGMFG model does not allow for specific policies for agents with finite degree k all agents follow the policy learned for agents with infinite degree. For implementation details on the LPGMFG model we refer to Paaiian et al. 2023).
Table shows that our GXMFG approach clearly outperforms LPGMFGs on all tasks and empirical networks. While the difference some network-task combinations is relatively moderate, e.g. 4.28 (LPGMFG) vs. 2.78 (GXMFG) on Dogster SIS, the GXMFG performance on other networks and tasks, such as Flickr RS (15.80 2.24), SIS Brightkite (17.07 vs. 1.37), SIR Hyves (39.94 vs. 10.06), is many times better then for the LPGMFG benchmark. These results strongly support the conceptual advantage of the hybrid graphex learning approach existing work such as LPGMFGs. The GXMFGs ability to depict finite degree agents in the limiting model proves to be a crucial advantage over GMFGs and LPGMFGs that assume exclusively infinite degree agents. This is reflected by its superior performance on various tasks and real world networks as seen in Table 3
38

---

Published as a conference paper at ICLR 2024
Table 3: Average expected total variation Ap = 1 E2 12 fit Hellal E [o. 1] between the overall
GXMFG MF prediction μ4 and the empirical MF fil - 2, ox; (#t standard deviation, 5 trials).
Ap in % for LPGMFG
A in % for GXMFG
network
SIS (%)
SIR (%)
RS (%)
SIS (%)
SIR (%)
RS (%)
Prosper
2.66 0.22
5,41 + 0.35
2.80 0.43
0.53 0.21
2.06 = 0.25
1.58 + 0.31
Dogster
4.28 + 0.23
8.83 + 1.16
4.25 - 0.66
2.78 + 0.44
4.93 = 0.98
1.89 + 0.66
Pokec
6.26 + 0.03
11.45 = 0.10
5.67 = 0.11
2.14 + 0.05
4.93 = 0.12
2.19 + 0.08
Livemocha
4.46 0.10
8.56 0.43
4.40 + 0.83
2.57 0.20
4.40 1.08
2.51 0.54
Flickr
16.90 = 0.03
35.49 = 0.05
15.80 + 0.10 3.57 0.08
8.58 0.24
2.24 0.11
Brightkite
17.07 = 0.30
32.27 + 0.37
14.69 + 0.47 1.37 0.11 10.92 0.77
3.37 + 0.25
Facebook
16.22 = 0.16 28.89 - 0.23
13.03 + 0.07 2.90 + 0.09
13.57 + 0.37
5.01 0.27
Hyves
21.94 = 0.11 39.94 + 0.50
17.46 + 0.34 5.07 + 0.24
10.06 + 0.81
2.62 + 0.44
39


Reviews:
[{"review_id": "gBU7uwifxA", "reviewer": "Reviewer_P6cQ", "summary": "In this paper, the authors study a class of games with many players who are interacting through a sparse graph structure. More specifically, they are interested in the regime where the number of players tend to infinity. The main solution concept is an extension of the notion of Nash equilibrium. The authors propose a learning algorithm based on online mirror descent. They conclude the paper with examples and numerical simulations.", "questions": "1. I am wondering if some assumptions are missing. For example below Lemma 1, should $f$ be at least measurable (and perhaps more?) with respect to $\\alpha$ for the integral to make sense?\n\n2. Assumption 2 as used for instance in Lemma 1 does not seem to make much sense (unless I missed something): What is $\\boldsymbol{\\pi}$? We do not know in advance the equilibrium policy and even if we did, we would still need to define the set of admissible deviations for the Nash equilibrium. Could you please clarify?\n\n3. Algorithm 1, line 14: Could you please explain or recall what is $Q^{k, \\mu^{\\tau_{\\mathrm{max}}}}$?\n\nSome typos: Should the state space be either $\\mathcal{X}$ or $X$ (see section 3 for instance)? Does $\\mathbb{G}^\\infty_{\\alpha,t}$ depend on $\\boldsymbol{\\mu}$ or not (see bottom of page 4)? Etc.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper studies an interesting problem and is relatively clearly written. As far as I know, this is a new extension of MFG to sparse graphs. The algorithm is very inspired from existing ones but there is an adaptation to the problem under consideration (core vs periphery).", "weaknesses": "The model is quite abstract at some places. For the theoretical results, they are mostly about the analysis of the game and I am not sure how relevant they are for this conference (although they are certainly interesting for a certain community). It might have been more interesting to focus more on the learning algorithm. \n\nThere are some typos which make it hard to check the correctness of some parts (see questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q5LsF6DBEl", "reviewer": "Reviewer_hgJx", "summary": "This paper introduces Graphex Mean Field Games (GXMFGs), a framework for addressing the challenge of learning agent behavior in large populations. GXMFGs leverage graphon theory and graphexes, which represent limiting objects in sparse graph sequences. This approach suits real-world networks with both dense cores and sparse peripheries. The paper presents a specialized learning algorithm for GXMFGs. \n\nKey contributions include:\n\n1. Introduction of GXMFGs, extending the scope of Mean Field Games.\n2. Provides theoretical guarantees to show that GXMFGs accurately approximates finite systems.\n3. Development of a learning algorithm tailored to GXMFGs.\n4. Empirical validation on synthetic and real-world networks, demonstrating GXMFGs' ability to model agent interactions and determine equilibria effectively.", "questions": "- Providing an intuitive explanation for assumptions 1(b) and 1(c) would greatly enhance the paper's overall readability and accessibility.\n\n- While the paper assumes finite state and action spaces, it may be beneficial to explore whether the proposed approach can be extended to scenarios with infinite action spaces. \n- Including the code for the simulations, would enhance reproducibility.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Well-Written and Organized: The paper demonstrates strong writing and organization, enhancing its overall readability and accessibility.\n\n- Clear Motivation: The paper effectively conveys a clear and compelling motivation for addressing the problem it tackles.\n\n- Thorough Discussion of Prior Works: The paper provides a comprehensive and well-structured overview of prior works related to the research area.\n\n- The paper provides solid theoretical contributions complimented with supporting empirical studies strengthens the paper's arguments and findings.", "weaknesses": "As the current paper falls outside the scope of my research interests, I am unable to identify any significant weaknesses in the paper. Consequently, my confidence in assessing the paper is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KFdqHGoMzN", "reviewer": "Reviewer_e4bh", "summary": "This paper introduces Graphex Mean Field Games (GXMFGs) which build on the graph theoretical concept of graphexes to include sparse network structures between agents. This improves over prior work on Graphon Mean Field Games which only allows for modelling with dense graphs. The authors derive convergence properties for the finite game. In addition, a learning algorithm based on online mirror descent is provided for a particular class of GXMFGs that follow a core-periphery network structure. Finally, the theoretical claims are empirically validated over both synthetic and real-world networks.", "questions": "In Figure 3a, it looks like the curves are diverging rather than converging as k increases? Are the curves coloured correctly?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper has a clear motivation to extend Graphon Mean Field Games to deal with sparse graphs which are frequently seen in practice. The hybrid graphex approach proposed in this work looks like a natural and intuitive solution.\n- The technical development is principled and the analysis is nontrivial.\n- The overall presentation and clarity is good.", "weaknesses": "- Even though the authors explained in the paper, I didn't like the fact that the proposed GXMFGs have no baseline competitors to compare against. While I agree that one could argue on the contrary that the ability to work with sparse graphs is precisely the unique advantage of GXMGFs, I think that the authors should at least spend some efforts to discuss (if empirical comparison with LPGMFG is indeed unsuitable) how GXMFGs would compare with LPGMFG and GMFG in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)