Research map / Learning theory and algorithms / Submodular and game algorithms
Learning Discrete-Time Major-Minor Mean Field Games
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 major-minor mean field game (M3FG) model and a tabular projected fictitious play algorithm that learns equilibria without knowing common noise, with propagation-of-chaos and exploitability convergence guarantees.
Problem
Computing Nash equilibria in large multi-player games with both many homogeneous minor players and strong major players (plus common noise), which standard MFGs cannot model; the mean field becomes stochastic due to the major player.
Approach
A discrete-time major-minor MFG in which the mean field is stochastic and conditioned on major state and action; a fictitious play algorithm with partitioning of the probability simplex yields a tabular, finite MDP approximation that does not assume common noise is known.
Key results
- Fictitious play optimizes both minor and major approximate exploitabilities over iterations, whereas naive fixed-point iteration oscillates and runs into limit cycles.
- Theory: total exploitability is a strong Lyapunov function with rate O(1/tau) in continuous-time fictitious play; propagation of chaos at rate O(1/sqrt N) in distribution.
- FP-learned policies stabilize as discretization becomes fine (M=120 bins), and N-player returns converge to the projected mean field prediction as N grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use fictitious play instead of fixed-point iteration | M3FG equilibrium learning · SIS | minor exploitability | Helped |
| Use fictitious play instead of fixed-point iteration | M3FG equilibrium learning · Buffet | minor exploitability | Helped |
| Use fictitious play instead of fixed-point iteration | M3FG equilibrium learning · Advertisement | minor exploitability | Helped |
| Use fictitious play instead of fixed-point iteration | M3FG equilibrium learning · SIS | major exploitability | Helped |
| Use fictitious play instead of fixed-point iteration | M3FG equilibrium learning · Buffet | major exploitability | Helped |
| Use fictitious play instead of fixed-point iteration | M3FG equilibrium learning · Advertisement | major exploitability | Helped |
| Increase the number of minor players | M3FG finite-player system · SIS, Buffet, and Advertisement | objective agreement with projected mean-field prediction | Helped |
| Use a sufficiently fine mean-field discretization | Fictitious play · SIS, Buffet, and Advertisement | final objectives | Helped |
Surprising findings
- The mean field is stochastic in the major-minor setting, so propagation of chaos holds only in distribution and the stronger convergence mode used in standard MFGs fails.
Limitations
- Scalability of the partition-based discretization degrades with larger minor state spaces.
- Theoretical guarantees rely on Lipschitz policy and monotonicity assumptions that the discretized policies only partially satisfy.
- FP finds only one equilibrium when multiple Nash equilibria exist.
Experimental setup
Benchmarks: SIS epidemics control Buffet problem Advertisement duopoly model
Metrics: approximate exploitability N-player episodic objective
Baselines: fixed-point iteration (FPI)
Builds on: fictitious play for mean field games mean field games with common noise Lasry-Lions monotonicity
Closest papers by meaning
- Bench-MFG: A Benchmark Suite for Learning in Stationary Mean Field Games (NeurIPS 2026 · similarity 0.92)
- Bounded Rationality Equilibrium Learning in Mean Field Games (AAAI 2025 · similarity 0.91)
- Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation (ICLR 2025 · similarity 0.90)
- Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL (ICML 2024 · similarity 0.89)
- Solving Continuous Mean Field Games: Deep Reinforcement Learning for Non-Stationary Dynamics (NeurIPS 2025 · similarity 0.89)
- Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis (NeurIPS 2025 · similarity 0.89)
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.