Research map / Learning theory and algorithms / Submodular and game algorithms
Graphon Mean Field Games with a Representative Player: Analysis and Learning Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a discrete-time graphon game with a single representative player on continuous state/action spaces, proves equilibrium existence and uniqueness, shows approximate equilibrium for finite networks, and gives an oracle-free online SARSA+MCMC learning algorithm with sample complexity analysis.
Problem
Graphon mean field games with heterogeneous, asymmetric interactions are hard to formulate and solve: the standard continuum-player formulation has measurability issues and no practical algorithm, and finite network games suffer from curse of dimensionality.
Approach
Replace the continuum of players with a single representative player labeled by a uniform label U, whose state law jointly with the label is the population measure; the player reacts to the graphon-weighted neighborhood measure. This yields existence/uniqueness results under mild assumptions, an approximate-equilibrium guarantee for finite networks, and an online oracle-free learning scheme (SARSA
Key results
- Algorithm on Flocking-Graphon converges in around 50 epochs consistently across four graphons (uniform, ranked, Erdős–Rényi, threshold).
- Sample complexity stated as O(κ^-5 ε^-4 log^2 ε^-1) for finding an ε-approximate equilibrium distribution with D=O(κ^-1 ε^-1) label classes.
- Existence and uniqueness of graphon equilibrium proved under mild assumptions; n-player policies derived from the graphon equilibrium form an approximate equilibrium with average error vanishing as n grows.
Limitations
- Convergence guarantee relies on strong assumptions including a contraction of the FPI operator and Lipschitz continuity of transitions and rewards in the measure argument.
- Label space must be discretized into D classes; continuous label space requires function approximation beyond the scope of the work.
- Uniqueness requires separable rewards and Lasry-Lions monotonicity, and the state/action spaces are finite in the learning section.
Experimental setup
Benchmarks: Flocking-Graphon SIS-Graphon Invest-Graphon
Metrics: convergence gap W1 distance to benchmark solution exploitability
Baselines: continuum-player graphon game formulation
Builds on: mean field games graphon games (continuum-player formulation) SARSA
Closest papers by meaning
- Last-iterate Convergence in Regularized Graphon Mean Field Game (AAAI 2025 · similarity 0.88)
- Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach (ICLR 2024 · similarity 0.88)
- Learning Discrete-Time Major-Minor Mean Field Games (AAAI 2024 · similarity 0.86)
- Learning Mean Field Control on Sparse Graphs (ICML 2025 · similarity 0.85)
- Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL (ICML 2024 · similarity 0.85)
- Bench-MFG: A Benchmark Suite for Learning in Stationary Mean Field Games (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.