Research map / Multi-agent systems and games / Games and equilibria
Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach
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.
Introduces graphex mean field games (GXMFGs) for sparse, power-law networks and a hybrid online mirror descent algorithm (HOMD) that solves a graphex core equilibrium via OMD and periphery via backward induction, validated on synthetic graphs and KONECT real networks.
Problem
Mean field games on graphons only capture dense graphs, so they cannot model sparse, power-law networks where many agents have finite degree; learning equilibria in such graphex-based games is also hard.
Approach
Defines mean field games on graphexes (limits of sparse graph sequences) and splits agents into a high-degree core solved by online mirror descent over equivalence classes and a low-degree periphery solved as an MDP via backward induction, with theoretical convergence and approximate-optimality guarantees.
Key results
- On real KONECT networks, the GXMFG prediction deviates from the empirical mean field by about 0.5% to 5% for SIS and RS across all networks (e.g., Prosper SIS 0.53%, Hyves SIS 5.07%).
- SIR approximation is less accurate on some networks, e.g. Brightkite 10.92% and Facebook 13.57%.
- The paper reports GXMFG clearly outperforms LPGMFG on all considered tasks and real networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the hybrid graphex learning approach instead of LPGMFG | GXMFG learning on the considered real-world network tasks · Real-world networks; SIS, SIR, and RS | Δμ | Helped |
| Use the separable power-law graphex approximation on smaller networks | GXMFG · Brightkite and Facebook SIR | Δμ | Hurt |
| Use a separable power-law graphex for networks that may need more diverse graphexes | GXMFG · Hyves | Δμ | Hurt |
Surprising findings
- SIR approximation is notably worse on small networks such as Brightkite and Facebook, which the authors attribute to weaker asymptotic accuracy at small node counts.
Limitations
- Uses a separable power-law graphex, which may not fit all real networks (e.g., Hyves).
- Finite state and action spaces and discrete time only.
- Accuracy degrades for small networks where asymptotic approximation is weaker.
Experimental setup
Datasets: KONECT Prosper loans Dogster Pokec Livemocha Flickr Brightkite Facebook Hyves synthetic separable power-law graphex graphs
Benchmarks: SIS epidemic MFG SIR epidemic MFG rumor spreading MFG KONECT real networks
Metrics: core exploitability expected total variation distance between empirical and pred Delta mu
Baselines: LPGMFG naive fixed point iteration
Builds on: graphon mean field games online mirror descent linear-program graphon MFGs (LPGMFG) graphex theory
Closest papers by meaning
- Learning Mean Field Control on Sparse Graphs (ICML 2025 · similarity 0.92)
- Bench-MFG: A Benchmark Suite for Learning in Stationary Mean Field Games (NeurIPS 2026 · similarity 0.90)
- Last-iterate Convergence in Regularized Graphon Mean Field Game (AAAI 2025 · similarity 0.89)
- Graphon Mean Field Games with a Representative Player: Analysis and Learning Algorithm (ICML 2024 · similarity 0.88)
- Learning Discrete-Time Major-Minor Mean Field Games (AAAI 2024 · similarity 0.88)
- Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis (NeurIPS 2025 · similarity 0.88)
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.