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

In this work, we show that finding Nash equilibrium solutions for a general class of discrete-time mean-field games is equivalent to solving an optimization problem with bounded variables and simple convex constraints, called MF-OMO (Mean-Field Occupation Measure Optimization) (Section 3). This equivalence is established without assuming either the uniqueness of the Nash equilibrium solution or the contractivity or monotonicity conditions.

The equivalence is built through several steps. The first step, inspired by the classical linear program formulation of the single-agent Markov decision process (MDP) problem [61], is to introduce occupation measure for the representative player, and to transform the problem of finding Nash equilibrium solutions to a constrained optimization problem (Theorem 4) by the strong duality of the linear program to bridge the two criteria of Nash equilibrium solutions. The second step is to utilize a solution modification technique (Proposition 6) to deal with potentially unbounded variables in the optimization problem and obtain the MF-OMO formulation (Theorem 5). Further analysis of this equivalent optimization formulation enables establishing the connection between the suboptimality of MF-OMO and the exploitability of any policy for mean field games (Section 4). This is obtained by the perturbation analysis on MDPs (Lemma 13) and by the strong duality of linear programs.

These equivalence and connections enable adopting families of optimization algorithms to find multiple (and possibly all) Nash equilibrium solutions of mean-field games. In particular, detailed studies on the convergence of MF-OMO with the projected gradient descent (PGD) algorithm to Nash equilibrium solutions of mean-field games are presented (Theorem 11). For instance, PGD is shown to be capable of retrieving all possible Nash equilibrium solutions when there are finitely many of them, with proper initializations. Moreover, analyzing mean-field games with linear rewards and mean-field independent dynamics is shown to be reduced to solving a finite number of linear programs, hence solvable in finite time (Proposition 12).

Finally, this MF-OMO framework can be extended to other variants of mean-field games, as illustrated in the case of personalized mean-field games in Section 7.

Our approach is inspired by the classical linear program framework for MDPs, originally proposed in [51] for discrete-time MDPs with finite state-action spaces and then extended first to semi-MDPs [56] and then to approximate dynamic programming [63, 21], as well as to continuous-time stochastic control [66, 10, 45] and singular control [67, 44] with continuous state-action spaces, among others [72, 25, 24, 38]. In the similar spirit, our work builds an optimization framework for discrete-time mean-field games.

There are several existing computational algorithms for finding Nash equilibrium solutions of discrete-time mean-field games. In particular, [31, 58] assume strict monotonicity, while [59] assumes weak monotonicity, all of which also assume the dynamics to be mean-field independent. In addition, [34, 32, 3] focus on contractive mean-field games, [6] studies mean-field games with unique Nash equilibrium solutions, and [20, 4] analyze mean-field games that are sufficiently close to some contractive regularized mean-field games. Under these assumptions, global convergence is obtained for some of these algorithms. In contrast, we focus on presenting an equivalent optimization framework for mean-field games, and establishing local convergence without these assumptions.

The most relevant to our works are earlier works of [11, 29, 30] on continuous-time mean-field games, in which they replace the best-response/optimality condition in Nash equilibrium solutions by the linear program optimality condition. Their reformulation approach leads to new existence results for relaxed Nash equilibrium solutions and computational benefits. In contrast, our work formulates the problem of finding Nash equilibrium solutions as a single optimization problem which captures both the best-response condition and the Fokker-Planck/consistency condition. Our formulation shows that finding Nash equilibrium solutions of discrete-time mean-field games with finite state-action spaces is generally no harder than solving a smooth, time-decoupled optimization problem with bounded variables and trivial convex constraints. Such a connection allows for directly utilizing various optimization tools, algorithms and solvers to find Nash equilibrium solutions of mean-field games. Moreover, our work provides, for the first time to our best knowledge, provably convergent algorithms for mean-field games with possibly multiple Nash equilibrium solutions and without contractivity or monotonicity assumptions.

Take $\mathcal{S}=\mathcal{A}=\{1,\dots,n\}$ and an arbitrary initial distribution $\mu_{0}$. At time $0$, for any $L_{0}\in\Delta(\mathcal{S}\times\mathcal{A})$ and any $i,j=1,\dots,n$, the rewards $r_{0}(i,j,L_{0})=0$, and the transitions are deterministic such that $P_{0}(i^{\prime}|i,j,L_{0})=\mathbf{1}_{\{i^{\prime}=j\}}$. When $t>0$, the rewards and the transition probabilities may depend on $L_{t}$. Specifically, if the population congregates at the same state $i$ and chooses to stay, i.e., $L_{t}(s,a)=\mathbf{1}_{\{s=i,a=i\}}$, then the rewards $r_{t}(i,j,L_{t})=r^{i}\mathbf{1}_{\{i=j\}}$ for some $r^{i}>0$, and the transition probabilities will be deterministic $P_{t}(i^{\prime}|i,j,L_{t})=\mathbf{1}_{\{i^{\prime}=j\}}$. If $L_{t}$ deviates from state $i$ and action $i$, the rewards and transition probabilities will be adjusted as follows:

• •

  $r_{t}(i,j,L_{t})=\mathbf{1}_{\{i=j\}}(r^{i}-r^{i}\|L_{t}-\mathbf{1}_{\{(s,a)|s=i,a=i\}}\|_{2}^{2}/2)$, for any $i,j=1,\dots,n$ and $t=1,\dots,T$.²²2Here for a totally ordered finite set $\mathcal{X}$, we use $\mathbf{1}_{\mathcal{X}}$ to denote the binary vector in $\mathbb{R}^{|\mathcal{X}|}$ which has entry value $1$ for those indices $x\in\mathcal{X}$ and has entry value $0$ otherwise.

• •

  $P_{t}(i^{\prime}|i,j,L_{t})=\dfrac{\mathbf{1}_{\{i^{\prime}=j\}}+C_{t}\|L_{t}-\mathbf{1}_{\{(s,a)|s=i,a=i\}}\|_{2}^{2}}{1+nC_{t}\|L_{t}-\mathbf{1}_{\{(s,a)|s=i,a=i\}}\|_{2}^{2}}$ for any $i^{\prime},i,j=1,\dots,n$ and $t=1,\dots,T$.

Here $C_{t}$ $(t=1,\dots,T)$ are some non-negative constants.

It is easy to verify that for any $j^{\star}\in\text{argmax}_{i=1,\dots,n}r^{i}$, if we define

• •

  $\pi_{t}(a|s)=\mathbf{1}_{\{a=j^{\star}\}}$ for any $s,a=1,\dots,n$ and $t=0,\dots,T$;

• •

  $L_{0}(s,a)=\mu_{0}(s)\pi_{0}(a|s)$ and $L_{t}(s,a)=\mathbf{1}_{\{s=j^{\star},a=j^{\star}\}}$, for any $s,a=1,\dots,n$ and $t=1,\dots,T$,

then $\pi=\{\pi_{t}\}_{t\in\mathcal{T}}$ and $L=\{L_{t}\}_{t\in\mathcal{T}}$ constitute a Nash equilibrium solution. Thus there are several distinct Nash equilibrium solutions with both $\pi$ and $L$ being different, defined by the index $j^{\star}\in\text{argmax}_{i=1,\dots,n}r^{i}$ as $\pi^{(j^{\star})}$ and $L^{(j^{\star})}$. As contractivity and strict monotonicity imply the uniqueness of the Nash equilibrium solution, the mean-field game above is neither contractive nor strictly monotone. To see that it is not weakly monotone either, consider any two mean-field flows $L_{t}^{(1)}=L_{t}^{(j_{1}^{\star})}$ and $L_{t}^{(2)}=L_{t}^{(j_{2}^{\star})}$ with $j_{1}^{\star}\neq j_{2}^{\star}\in\text{argmax}_{i=1,\dots,n}r^{i}$. Then

$$\begin{split}&\sum_{t=0}^{T}\sum_{s=1}^{n}\sum_{a=1}^{n}(L_{t}^{(1)}(s,a)-L_{t}^{(2)}(s,a))(r_{t}(s,a,L_{t}^{(1)})-r_{t}(s,a,L_{t}^{(2)}))\\ &={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}T(r^{j_{1}^{\star}}+r^{j_{2}^{\star}})=2T\max\nolimits_{i=1,\dots,n}r^{i}}>0,\end{split}$$

violating the requirement of weak monotonicity.

We now propose a new analytical framework that enables finding multiple Nash equilibrium solutions, without either the restrictive uniqueness assumption of the Nash equilibrium solution or contractivity [34, 20] and monotonicity [59, 58] conditions.

To start, let us introduce a new variable $d_{t}(s,a)$ for any $t\in\mathcal{T}$, $s\in\mathcal{S},a\in\mathcal{A}$, which represents the occupation measure of the representative agent under some policy sequence $\pi=\{\pi_{t}\}_{t\in\mathcal{T}}$ in $\mathcal{M}(L)$, the mean-field induced MDP, i.e., $d_{t}(s,a)=\mathbb{P}(s_{t}=s,a_{t}=a)$, with $s_{0}\sim\mu_{0}$, $s_{t+1}\sim P_{t}(\cdot|s_{t},a_{t},L_{t})$, $a_{t}\sim\pi_{t}(\cdot|s_{t})$ for $t=0,\dots,T-1$. Given the occupation measure $d=\{d_{t}\}_{t\in\mathcal{T}}$, define a mapping $\Pi$ that retrieves the policy from the occupation measure. This set-valued mapping $\Pi$ maps from a sequence $\{d_{t}\}_{t\in\mathcal{T}}\subseteq\Delta(\mathcal{S}\times\mathcal{A})$ to a set of policy sequences $\{\pi_{t}\}_{t\in\mathcal{T}}$: for any $\{d_{t}\}_{t\in\mathcal{T}}\subseteq\Delta(\mathcal{S}\times\mathcal{A})$, $\pi\in\Pi(d)$ if and only if

$$\pi_{t}(a|s)=\frac{d_{t}(s,a)}{\sum_{a^{\prime}\in\mathcal{A}}d_{t}(s,a^{\prime})}$$

(4)

when $\sum_{a^{\prime}\in\mathcal{A}}d_{t}(s,a^{\prime})>0$, and $\pi_{t}(\cdot|s)$ is an arbitrary probability vector in $\Delta(\mathcal{A})$ when $\sum_{a^{\prime}\in\mathcal{A}}d_{t}(s,a^{\prime})=0$.

Next, consider any finite-horizon MDP $\mathcal{M}$ (e.g., the mean-field induced MDP $\mathcal{M}(L)$) with a finite state space $\mathcal{S}$, a finite action space $\mathcal{A}$, an initial state distribution $\mu_{0}$, a reward function $r_{t}(s,a)$, and dynamics $P_{t}(s^{\prime}|s,a)$ for $t=0,\dots,T$, $s,s^{\prime}\in\mathcal{S}$ and $a\in\mathcal{A}$. For brievity, we use $\mathbb{P}^{\pi}(\cdot)$ for the state and/or action distribution generated by $s_{0}\sim\mu_{0}$, $s_{t+1}\sim P_{t}(\cdot|s_{t},a_{t})$, $a_{t}\sim\pi_{t}(\cdot|s_{t})$ for $t=0,\dots,T-1$.

Then, our first component of MF-OMO relies on a linear program formulation of an MDP problem, as follows.

The proof of Lemma 2 is a suitable modification for its well-known counterpart in the discounted and average reward settings [21, 40, 70].

We now show that $\pi=\{\pi_{t}\}_{t\in\mathcal{T}}$ is a Nash equilibrium solution if and only if there exist $d^{\star}=\{d_{t}^{\star}(s,a)\}_{t\in\mathcal{T}}$ and $L=\{L_{t}(s,a)\}_{t\in\mathcal{T}}$, such that $\pi\in\Pi(d^{\star})$ and the following two conditions hold.

• (A)

  Optimality of the representative agent: $d^{\star}=\{d_{t}^{\star}(s,a)\}_{t\in\mathcal{T}}$ solves the following LP problem

  	$\displaystyle\text{maximize}_{d}\quad$	$\displaystyle\sum_{t\in\mathcal{T}}\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}d_{t}(s,a)r_{t}(s,a,L_{t})$		(5)
  	subject to	$\displaystyle\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}d_{t}(s,a)P_{t}(s^{\prime}|s,a,L_{t})=\sum_{a\in\mathcal{A}}d_{t+1}(s^{\prime},a),$		(6)
  		$\displaystyle\hskip 119.50148pt\forall s^{\prime}\in\mathcal{S},t\in\mathcal{T}\backslash\{T\},$
  		$\displaystyle\sum_{a\in\mathcal{A}}d_{0}(s,a)=\mu_{0}(s),\quad\forall s\in\mathcal{S},$
  		$\displaystyle d_{t}(s,a)\geq 0,\quad\forall s\in\mathcal{S},a\in\mathcal{A},t\in\mathcal{T}.$

• (B)

  Consistency between the agent and the mean-field: $d_{t}^{\star}(s,a)=L_{t}(s,a)$ for any $s\in\mathcal{S},a\in\mathcal{A},t\in\mathcal{T}$.

Here condition (A) corresponds to the optimality condition 1) in Definition 2.1 according to Lemma 2. Condition (B) indicates that the occupation measure of the single agent matches the mean-field flow of the population, so that the agent is indeed representative. Condition (B), when combined with condition (A), in fact implies the consistency condition 2) in Definition 2.1. Formally, we have the following lemma.

To get the preliminary version of MF-OMO, notice that the linear program in condition (A) can be rewritten as

$$\begin{array}[]{ll}\text{minimize}_{d}&c_{L}^{\top}d\\ \text{subject to}&A_{L}d=b,\quad d\geq 0,\end{array}$$

(7)

where $c_{L}\in\mathbb{R}^{SA(T+1)}$ and $b\in\mathbb{R}^{ST+S}$ are

$$c_{L}=\left[\begin{array}[]{c}-r_{0}(\cdot,\cdot,L_{0})\\ \vdots\\ -r_{T}(\cdot,\cdot,L_{T})\end{array}\right],\quad b=\left[\begin{array}[]{c}0\\ \vdots\\ 0\\ \mu_{0}\end{array}\right],$$

(8)

$r_{t}(\cdot,\cdot,L_{t})\in\mathbb{R}^{SA}$ is a flattened vector (with column-major order), and the matrix $A_{L}\in\mathbb{R}^{S(T+1)\times SA(T+1)}$ is

$$A_{L}=\left[\begin{array}[]{ccccccc}W_{0}(L_{0})&-Z&0&0&\cdots&0&0\\ 0&W_{1}(L_{1})&-Z&0&\cdots&0&0\\ 0&0&W_{2}(L_{2})&-Z&\cdots&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&0&\cdots&W_{T-1}(L_{T-1})&-Z\\ Z&0&0&0&\cdots&0&0\end{array}\right].$$

(9)

Here $W_{t}(L_{t})\in\mathbb{R}^{S\times SA}$ is the matrix with the $l$-th row ($l=1,\dots,S$) being the flattened vector $[P_{t}(l|\cdot,\cdot,L_{t})]\in\mathbb{R}^{SA}$ (with column-major order), and the matrix $Z$ is defined as

$$Z:=[\overbrace{I_{S},\dots,I_{S}]}^{A}\in\mathbb{R}^{S\times SA},$$

(10)

where $I_{S}$ is the identity matrix with dimension $S$. In addition, the variable $d$ is also flattened/vectorized in the same order as $c_{L}$. Accordingly, hereafter both $d^{\star}=\{d^{\star}_{t}\}_{t\in\mathcal{T}}$ and $L=\{L_{t}\}_{t\in\mathcal{T}}$ are viewed as flattened vectors (with column-major order) in $\mathbb{R}^{SA(T+1)}$ or a sequence of $(T+1)$ flattened vectors (with column-major order) in $\mathbb{R}^{SA}$, depending on the context, and we use $L_{t}(s,a)$ and $L_{s,a,t}$ (resp. $d_{t}(s,a)$ and $d_{s,a,t}$) alternatively.

By the strong duality of linear program [50], $\{d_{t}^{\star}(s,a)\}$ is the optimal solution to the above linear program (7) if and only if the following KKT conditions hold for $d^{\star}$ and some $y$ and $z$:

$$\begin{split}&A_{L}d^{\star}=b,\quad A_{L}^{\top}y+z=c_{L},\\ &z^{\top}d^{\star}=0,\quad d^{\star}\geq 0,\quad z\geq 0.\end{split}$$

(11)

Now, combining condition (A) (in the form of equation (11)) with condition (B), we have the following preliminary version of MF-OMO.

In the above derivation, we have used $L$ to represent the population mean-field flows and $d$ to denote the occupation measure of the representative agent. The optimal occupation measure (i.e., the solution to the linear program) associated with the representative agent is denoted by $d^{\star}$.

The above constrained optimization problem (12) in Theorem 4 can be rewritten in a more computationally-efficient form by adding bound constraints to the auxiliary variables $y$ and $z$ and moving potentially nonconvex constraints to the objective. Note that the consequent nonconvex objectives are in general much easier to handle than nonconvex constraints (cf. (12)). In addition, the boundedness of all variables is essential to the later analysis of the optimization framework in Sections 4 and 5.

Theorem 5 is immediate from the following two results, which show how the bounds on the auxiliary variables $y$ and $z$ in (MF-OMO) are obtained. Note that only $L$ is needed to construct the Nash equilibrium solution, hence there is no loss to add additional bounds on $y$ and $z$ according to Corollary 7.

The interpretation of $y$ and $z$ is motivated by the following remark.

The following corollary follows immediately by the definitions of $\hat{y}$ and $\hat{z}$ in Proposition 6.

The key is to notice that $|[V_{t}^{\star}(L)]_{s}|\leq(T-t+1)r_{\max}$, $|\hat{z}_{t}^{a}(s)|\leq(T-t+1)r_{\max}+r_{\max}+(T-t)r_{\max}$ and $|\hat{z}_{T}^{a}(s)|\leq 2r_{\max}$, for any $s\in\mathcal{S},\,a\in\mathcal{A},\,t=0,\dots,T-1$.