MF-OMO: An Optimization Formulation of Mean-Field Games

DOI10.1137/22M1524084arXiv2206.09608OpenAlexW4391110185WikidataQ129574199 ScholiaQ129574199MaRDI QIDQ6188322FDOQ6188322

Authors: Xin Guo, Junzi Zhang 

Publication date: 7 February 2024

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: Theory of mean-field games (MFGs) has recently experienced an exponential growth. Existing analytical approaches to find Nash equilibrium (NE) solutions for MFGs are, however, by and large restricted to contractive or monotone settings, or rely on the uniqueness of the NE. This paper proposes a new mathematical paradigm to analyze discrete-time MFGs without any of these restrictions. The key idea is to reformulate the problem of finding NE solutions in MFGs as solving an equivalent optimization problem, called MF-OMO, with bounded variables and trivial convex constraints. It is built on the classical work of reformulating a Markov decision process as a linear program, and by adding the consistency constraint for MFGs in terms of occupation measures, and by exploiting the complementarity structure of the linear program. This equivalence framework enables finding multiple (and possibly all) NE solutions of MFGs by standard algorithms such as projected gradient descent, and with convergence guarantees under appropriate conditions. In particular, analyzing MFGs with linear rewards and with mean-field independent dynamics is reduced to solving a finite number of linear programs, hence solvable in finite time. This optimization reformulation of MFGs can be extended to variants of MFGs such as personalized MFGs.

Full work available at URL: https://arxiv.org/abs/2206.09608

zbMATH Keywords

optimizationcomplementarityNash equilibriumoccupation measurelinear programmean-field games and optimization (MF-OMO)

Mathematics Subject Classification ID

Linear programming (90C05) Optimality conditions and duality in mathematical programming (90C46) Noncooperative games (91A10) Games with infinitely many players (91A07) Dynamic games (91A25) Mean field games and control (49N80) Mean field games (aspects of game theory) (91A16)

Cites Work

• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Mean field games
• Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle
• Occupation measures for controlled Markov processes: Characterization and optimality
• Mean field forward-backward stochastic differential equations
• On sequential decisions and Markov chains
• The Linear Programming Approach to Approximate Dynamic Programming
• Mean-field backward stochastic differential equations: A limit approach
• The master equation in mean field theory
• Generalized polynomial approximations in Markovian decision processes
• Title not available (Why is that?)
• Fast projection onto the simplex and the \(l_1\) ball
• Existence of Markov Controls and Characterization of Optimal Markov Controls
• Time-average control of martingale problems: A linear programming formulation
• Linear programming and sequential decisions
• Linear Programming and Markov Decision Chains
• On Linear Programming in a Markov Decision Problem
• Stationary solutions and forward equations for controlled and singular martingale problems
• Linear Programming in a Markov Chain
• Markov-Nash equilibria in mean-field games with discounted cost
• The Master Equation and the Convergence Problem in Mean Field Games
• Linear programming algorithms for semi-Markovian decision processes
• Infinite-Dimensional Linear Programming Approach to SingularStochastic Control
• Probabilistic theory of mean field games with applications II. Mean field games with common noise and master equations
• Control and optimal stopping mean field games: a linear programming approach
• Mean-field games of optimal stopping: a relaxed solution approach
• From the master equation to mean field game limit theory: a central limit theorem
• A Probabilistic Approach to Extended Finite State Mean Field Games
• Unified reinforcement Q-learning for mean field game and control problems
• Q-learning in regularized mean-field games
• The LP approach in average reward MDPs with multiple cost constraints: The countable state case
• Linear programming fictitious play algorithm for mean field games with optimal stopping and absorption

This page was built for publication: MF-OMO: An Optimization Formulation of Mean-Field Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188322)