Learning Graphon Mean Field Games and Approximate Nash Equilibria

Kai Cui, Heinz Koeppl

Introduction

Scaling multi-agent reinforcement learning (MARL) to thousands or millions of agents is notoriously difficult due to the "curse of dimensionality"—the state and action spaces explode as you add more players. Mean Field Games (MFGs) offer a solution by assuming agents are identical and interact only with the "average" behavior of the population. However, standard MFGs have a major flaw: they assume every agent is exactly the same.

In the real world, structure matters. Whether it's a power grid, a social network, or a supply chain, some agents are "hubs" with many connections, while others are on the periphery. This paper addresses the challenge of maintaining this network structure while still benefiting from the scalability of mean-field approximations. It introduces a scalable framework by combining MFGs with Graphons—mathematical objects that represent the limit of dense graphs as the number of nodes goes to infinity—to model these non-symmetric interactions.

Methods: Graphon Mean Field Games (GMFGs)

The authors propose the first discrete-time formulation for Graphon Mean Field Games (GMFGs). Their approach involves several key components:

  1. The GMFG Framework: They define a system where an agent's position in a "limit graph" (represented by an index $\alpha \in [0, 1]$) determines how much they are influenced by others.
  2. Theoretical Guarantees: They rigorously prove that a solution to the GMFG (a Graphon Mean Field Equilibrium) is an $(\epsilon, p)$-Markov Nash Equilibrium. This means that in a sufficiently large finite-agent game, almost all agents are playing nearly optimally. The authors acknowledge that in a graph limit, you can't always guarantee a perfect Nash Equilibrium for every single agent. Instead, they show you can guarantee it for a fraction $(1-p)$ of agents, where $p$ vanishes as the system grows.
  3. Learning Algorithms:
  4. Equivalence Classes: They discretize the continuous graphon into $M$ "types" of agents, solving the game using backwards induction.
  5. Direct Reinforcement Learning: They adapt Proximal Policy Optimization (PPO) to solve the GMFG by including the agent's graphon index $\alpha$ as part of the input state. They use Sequential Monte Carlo (SMC) methods to estimate the evolving mean field during training.

Environments and Topologies

The paper evaluates the framework on two simulated environments designed to test different network topologies:

  • SIS-Graphon: A decentralized epidemic model where agents choose whether to take costly precautions (like social distancing) based on the infection risk from their neighbors.
  • Investment-Graphon: A market competition model where firms invest to improve product quality, but their profits are diminished by the quality of products from "connected" competitors.

To test these environments, the authors utilize three distinct graph topologies: Uniform Attachment, Ranked Attachment, and Erdős–Rényi graphs.

Heatmaps of the three graphon topologies used: Uniform Attachment, Ranked Attachment, and Erdős–Rényi.

Key Insights and Results

A major "aha moment" in the research is seeing how network position changes behavior. In the SIS model, "hub" agents (those with high connectivity) learn to take precautions much earlier and more consistently than peripheral agents because their risk of infection—and their impact on the network—is much higher.

Evolution of policies and states over time for different agent indices (α) across the three graphon topologies, demonstrating how network position dictates strategy.

Furthermore, the authors show that "naive" applications of state-of-the-art MARL (like MAPPO) fail to converge in these large-scale settings because they don't explicitly account for the non-stationarity of the global mean field. By treating the problem as a GMFG, convergence becomes stable.

Quantitative experiments show that as the number of agents $N$ increases toward 100, the maximum deviation between the finite-agent rewards and the theoretical mean-field rewards consistently decreases, validating the theory. The direct RL approach using PPO achieved exploitability scores ($\epsilon$) near 2, whereas a uniform random policy resulted in exploitability scores over 30. The "Equivalence Classes" method also proved highly stable; the learned equilibria remained consistent regardless of whether the graphon was divided into 10 or 50 slices.

Limitations and Future Work

  • Dense Graphs Only: The biggest limitation is that Graphons only model dense graphs (where the number of edges grows quadratically with the number of nodes). Most real-world social networks are sparse. Extending this to sparse graph limits (like "graphings") is a significant open challenge.
  • Centralized Information: The current model assumes agents know their position in the graphon ($\alpha$). In practice, agents might need to estimate this position from local observations.
  • Future Directions: The authors suggest extending the theory to continuous state spaces, partial observability, and scenarios with "common noise" that affects all agents simultaneously.

Summary updated

Abstract

Recent advances at the intersection of dense large graph limits and mean field games have begun to enable the scalable analysis of a broad class of dynamical sequential games with large numbers of agents. So far, results have been largely limited to graphon mean field systems with continuous-time diffusive or jump dynamics, typically without control and with little focus on computational methods. We propose a novel discrete-time formulation for graphon mean field games as the limit of non-linear dense graph Markov games with weak interaction. On the theoretical side, we give extensive and rigorous existence and approximation properties of the graphon mean field solution in sufficiently large systems. On the practical side we provide general learning schemes for graphon mean field equilibria by either introducing agent equivalence classes or reformulating the graphon mean field system as a classical mean field system. By repeatedly finding a regularized optimal control solution and its generated mean field, we successfully obtain plausible approximate Nash equilibria in otherwise infeasible large dense graph games with many agents. Empirically, we are able to demonstrate on a number of examples that the finite-agent behavior comes increasingly close to the mean field behavior for our computed equilibria as the graph or system size grows, verifying our theory. More generally, we successfully apply policy gradient reinforcement learning in conjunction with sequential Monte Carlo methods.
BibTeX
@inproceedings{cui2022learning,
  author = {Kai Cui and Heinz Koeppl},
  title = {{Learning Graphon Mean Field Games and Approximate Nash Equilibria}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=0sgntlpKDOz},
}
Figure