Optimization Frameworks & Learning Algorithms for Discrete-Time Mean Field Games
Organizations: UC Berkeley · NYU Shanghai
Abstract
This monograph introduces discrete-time mean field games with finite state and action spaces, emphasizing optimization formulations and learning algorithms. Starting from Markov decision processes and finite-player stochastic games, it develops the notion of mean field Nash equilibrium, establishes existence and uniqueness results under suitable assumptions, and explains how mean field equilibria yield approximate equilibria in large finite-player games. Building on the linear programming formulation of Markov decision processes, occupation measures and primal-dual formulations connect equilibrium computation with mathematical optimization. The monograph presents fixed-point iterations, fictitious play, online mirror descent, and optimization-based methods, discussing their convergence properties and limitations. Numerical examples illustrate crowd motion, traffic routing, epidemic management, and the computation of multiple equilibria. It combines examples, theoretical results, and implementable algorithms, with bibliographic notes providing connections to the broader literature.
Figures & tables
| Jack confesses | Jack silent | |
|---|---|---|
| Ted confesses | (-3,-3) | (0, -5) |
| Ted silent | (-5,0) | (-1,-1) |
| Jack confesses | Jack silent | |
|---|---|---|
| Ted confesses | (-3,-3) | (-5,-5) |
| Ted silent | (-5,-5) | (-3,-3) |
| (4.5) |
| Method | Parameter | Value |
|---|---|---|
| OMD | Step size | |
| Damped fixed point | New-flow weight | |
| Softmax fixed point and softmax fictitious play | Temperature | |
| BPI | Inverse temperature |
| NE 1 | NE 2 | NE 3 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 0.05 | 70% | 30% | 0% | 75% | 20% | 5% | 65% | 35% | 0% |
| 0.2 | 50% | 50% | 0% | 65% | 30% | 5% | 60% | 35% | 5% |
| 0.8 | 45% | 50% | 5% | 40% | 55% | 5% | 30% | 70% | 0% |
| 1.0 | 40% | 60% | 0% | 45% | 55% | 0% | 25% | 75% | 0% |
| Structure | Mathematical object | Representative methods | Guarantee and limitation | Location in the monograph |
|---|---|---|---|---|
| Contractive response | Fixed point for single-valued best-response or regularized response. | Pure fixed-point iteration, softmax response, and damping. | Unique fixed point and global convergence when the update map is a contraction; the condition typically requires a short horizon or weak interactions, and a single-valued response (selection or regularization). | Sections 3.1 and 3.2 (Theorem 3.2.1 ); Section 4.1.1 (Proposition 4.1.1 ). |
| Potential MFG | Scalar potential over feasible occupation-measure or population flows; its first variation reproduces the coupling incentives. | Fictitious play as a Frank–Wolfe-type method, conditional-gradient methods, and smoothed policy iteration. | Reduction of MFNE computation to scalar optimization; convergence and exploitability guarantees under regularity assumptions; no universal guarantee for each update rule. | Section 2.7 ; Sections 4.1.2 and 4.1.3 ; bibliographic notes in Section 4.3 . |
| Monotone MFG | Lasry–Lions monotonicity: mean-field-independent transitions and monotone reward coupling. | Fictitious play with averaged best responses; online mirror descent. | Uniqueness of the equilibrium mean-field flow; convergence of fictitious play and online mirror descent under additional regularity assumptions. | Section 3.3 (Theorem 3.3.3 ); Sections 4.1.2 and 4.1.4 ; bibliographic notes in Section 4.3 . |
| General finite-state MFG | Occupation-measure primal–dual conditions with KKT complementarity; no potentiality, monotonicity, or contractivity needed. | Complementarity or feasibility solvers; MF-OMO with projected gradient descent; Adam/NAdam; multiple initializations for distinct equilibria. | Objective value zero is equivalent to an MFNE; generally nonconvex; local PGD theory gives local convergence, while Theorem 3.6.3 gives a one-sided implication from small exploitability to small MF-OMO objective. | Section 1.1.4 ; Sections 3.5 and 3.6 (Theorems 3.6.1 , 3.6.2 and 3.6.3 ); Section 4.2 ; Sections 5.3 and 5.4 . |
Mean Field Games
Mean field games model strategic decisions in large populations through coupled individual policies and aggregate population dynamics.
See all 21 papers