Continuous Time Finite State Mean Field Games

Abstract

In this paper we consider symmetric games where a large number of players can be in any one of d states. We derive a limiting mean field model and characterize its main properties. This mean field limit is a system of coupled ordinary differential equations with initial-terminal data. For this mean field problem we prove a trend to equilibrium theorem, that is convergence, in an appropriate limit, to stationary solutions. Then we study an N+1-player problem, which the mean field model attempts to approximate. Our main result is the convergence as N→∞ of the mean field model and an estimate of the rate of convergence. We end the paper with some further examples for potential mean field games.

Appendix: Auxiliary Results

Proof of Proposition 1

To prove the first item we use the definition of h and α ^∗ and also that $v^{i}\sum_{j} \alpha^{*}_{j}(z,\theta,i)=0$ to get

$$h(z,\theta,i)+\sum_j \alpha^*_j(z, \theta,i)v^j= c\bigl(i,\theta ,\alpha ^*(z,\theta,i)\bigr)+\sum _j \alpha^*_j(z,\theta,i) \bigl(z^j+v^j-z^i-v^i\bigr). $$

Hence by the definition of h(z+v,θ,i) we have

$$h(z,\theta,i)+\sum_j \alpha^*_j(z, \theta,i)v^j\geq h(z+v,\theta,i). $$

From this (7) holds and we deduct that if h is differentiable

$$\alpha^*_j=\frac{\partial h(\Delta_iz,\theta,i) }{\partial z^j}. $$

Note that item (c) is a direct corollary of item (b), since

$$ h(p,\theta,i)=c\bigl(i,\theta,\alpha^*(p, \theta,i)\bigr)+\alpha^*(p,\theta ,i)\cdot p $$

(63)

and the function c is Lipschitz in θ and differentiable in α.

From this point on in this proof we will omit the index i as it is not relevant and simplifies the notation. To prove item (b) we will use the following inequalities, which are consequence of the uniform convexity of c: for all $\theta, \theta '\in\mathcal{S}^{d}$, $\alpha', \alpha\in(\mathbb{R}_{0}^{+})^{d}$, $\sum_{k} \alpha_{k}=\sum_{k} \alpha_{k}'=0$, and $p,p'\in\mathbb{R}^{d}$, we have

$$ c\bigl(\theta,\alpha'\bigr)+\alpha' \cdot p '\geq c(\theta,\alpha)+\alpha\cdot p'+\bigl( \nabla_\alpha c(\theta,\alpha )+p '\bigr)\cdot\bigl( \alpha'-\alpha\bigr)+\gamma\|\alpha'-\alpha \|^2, $$

(64)

and because α ^∗(p,θ) is a minimizer,

$$ \bigl(\nabla_\alpha c\bigl(\theta,\alpha ^*(p,\theta) \bigr)+p\bigr)\cdot\bigl(\alpha'-\alpha^*(p,\theta)\bigr)\geq0. $$

(65)

We will first prove that α ^∗ is uniformly Lipschitz in p: for that, we suppose that θ is fixed. By the definition of α ^∗ and (64) we have

hence

Now using (65) we obtain

$$0\geq\bigl(p'-p\bigr)\cdot\bigl(\alpha^*\bigl(p' \bigr)-\alpha^*(p)\bigr)+\gamma\bigl\Vert\alpha ^*\bigl(p '\bigr)- \alpha^*(p)\bigr\Vert^2. $$

Therefore

$$\|p-p'\|\bigl\Vert\alpha^*\bigl(p'\bigr)-\alpha^*(p)\bigr\Vert\geq \gamma\bigl\Vert\alpha ^*\bigl(p '\bigr)-\alpha^*(p)\bigr\Vert^2, $$

which implies

$$\bigl\Vert\alpha^*\bigl(p'\bigr)-\alpha^*(p)\bigr\Vert\leq\frac{1}{\gamma} \|p'-p \|. $$

This shows that α ^∗ is uniformly Lipschitz in p.

Now we prove that α ^∗ is Lipschitz in θ: for that, we suppose that p is fixed. Again by the definition of α ^∗ and by (64) we have

and then

$$0\geq\bigl(\nabla_\alpha c\bigl(\theta',\alpha^*(\theta) \bigr)+p\bigr)\cdot\bigl(\alpha ^*\bigl(\theta'\bigr)-\alpha^*( \theta)\bigr)+\gamma\bigl\Vert\alpha^*\bigl(\theta '\bigr)-\alpha ^*(\theta) \bigr\Vert^2. $$

Using (65) we get

$$0\geq \bigl[\nabla_\alpha c\bigl(\theta',\alpha^*(\theta) \bigr)-\nabla _\alpha c\bigl(\theta,\alpha^*(\theta)\bigr) \bigr]\cdot \bigl(\alpha^*\bigl(\theta'\bigr)-\alpha ^*(\theta)\bigr) +\gamma\bigl\Vert \alpha^*\bigl(\theta'\bigr)-\alpha^*(\theta) \bigr\Vert^2. $$

As ∇ _α c(θ,α) is Lipschitz in the variable θ we have

$$K_c\|\theta'-\theta\|\bigl\Vert\alpha^*(\theta)-\alpha^* \bigl(\theta'\bigr)\bigr\Vert \geq \gamma\bigl\Vert\alpha^*\bigl( \theta'\bigr)-\alpha^*(\theta) \bigl\Vert^2. $$

Therefore

$$\bigl\Vert\alpha^*(\theta)-\alpha^*\bigl(\theta'\bigr)\bigl\Vert\leq \frac{K_c}{\gamma } \| \theta-\theta' \|, $$

which implies that α ^∗ is Lipschitz in θ. □

Proof of Theorem 5

The main tool for proving Theorem 5 is once again the Dynkin Formula, now adapted to the present situation: suppose α and β are two admissible controls.

We recall the infinitesimal generator of the process (i,n) defined in (50). We have

(66)

where γ _β is defined by (30).

We have that, for any function $\varphi:I_{d} \times\mathcal{S}^{d}_{N} \times [0,+\infty) \rightarrow{\mathbb{R}}$, C ¹ in the last variable, and any t<T,

$$ \mathbb{E}^{\beta,\alpha}_{A_t(i, n)} \bigl[ \varphi^{{\mathbf{i}}_T}_{{\mathbf{n}}_T}(T)-\varphi ^i_n(t) \bigr] = \mathbb{E}^{\beta,\alpha}_{A_t(i, n)} \biggl[ \int _t^T \frac{d\varphi^{{\mathbf{i}}_s}_{{\mathbf{n}}_s}}{dt} (s) + \bigl(A^{\beta,\alpha }\varphi\bigr)^{{\mathbf{i}} _s}_{{\mathbf{n}}_s}(s) ds \biggr], $$

(67)

where A _t (i,n) denotes the event i _t =i and n _t =n.

Now we prove the theorem. In the Dinkyn formula (67) let φ=v. Using the terminal condition $v^{{\mathbf{i}}_{T}}_{{\mathbf {n}}_{T}}(T)=\psi^{{\mathbf{i}} _{T}} (\frac{{\mathbf{n}}_{T}}{N} )$ we have that, for any admissible control α,

$$ \mathbb{E}^{\beta,\alpha}_{A_t(i,n)} \biggl[ \psi^{{\mathbf {i}}_T} \biggl(\frac{{\mathbf{n}} _T}{N} \biggr)-v^{i}_{n}(t) \biggr] = \mathbb{E}^{\beta,\alpha}_{A_t(i,n)} \biggl[ \int _t^T \frac{d v^{{\mathbf{i}}_s}_{{\mathbf{n}}_s} }{dt}(s) + \bigl(A^{\beta ,\alpha}v\bigr)^{{\mathbf{i}} _s}_{{\mathbf{n}} _s}(s) ds \biggr]. $$

(68)

In the next steps we will use the definition of u, given in (31), and then (68), (66), (4) to have

where the last equation holds because v is a solution to the Hamilton-Jacobi equation (32). Note that in this last calculation we are also proving that, for the specific control $\tilde{\alpha}$ given by (34), we have $u^{i}_{n}(t,\beta,\tilde{\alpha})=v^{i}_{n}(t)$ which show us that $\tilde{\alpha}$ is the optimal control and that the objective function $u^{i}_{n}(t,\beta)$ is given by $v_{n}^{i}(t)$. □

Proof of Proposition 6

Let u be a solution to (32). Let $\tilde{u}=u+\rho(T-t)$. Then

$$- \frac{d\tilde{u}_n^i}{dt} =\rho+ \sum_{k,j} \gamma_{\beta,kj}^{n,i} \bigl(\tilde{u}^i_{n+e_{jk}}- \tilde{u}^i_n\bigr) + h \biggl( \Delta_i \tilde{u}_n,\frac{n}{N},i \biggr). $$

Let (i,n,t) be a minimum point of $\tilde{u}$ on $I_{d}\times\mathcal {S}^{d}_{N} \times[0,T]$. We have $\tilde{u}^{i}_{n+e_{jk}}\geq\tilde{u}^{i}_{n}$. This implies $\gamma_{\beta,kj}^{n,i} (\tilde{u}^{i}_{n+e_{jk}}-\tilde{u}^{i}_{n})\geq0$. We also have $\tilde{u}^{j}_{n}(t)-\tilde{u}^{i}_{n}(t)\geq0$ hence $\Delta_{i} \tilde{u}_{n}= (\tilde{u}^{1}_{n}(t)-\tilde{u}^{i}_{n}(t),\ldots,\tilde{u}^{d}_{n}(t)-\tilde{u}^{i}_{n}(t))\geq0$. Hence

$$-\frac{d\tilde{u}_n^i}{dt}(t) \geq h \biggl( \Delta_i \tilde{u}_n, \frac{n}{N}, i \biggr)+\rho\geq h \biggl(0,\frac{n}{N}, i \biggr)+ \rho, $$

because the definition of h(Δ _i p,θ,i), with Δ _i p≥0. Furthermore, if we take M<ρ<2M we get

$$-\frac{d\tilde{u}_n^i}{dt}(t)>0. $$

This shows that the minimum of $\tilde{u}$ is achieved at T hence

$$u_n^i(t) \geq-\|u(T)\|_{\infty}-2M (T-t). $$

Similarly, let (i,n,t) be a maximum point of $\tilde{u}$ on $I_{d}\times\mathcal {S}^{d}_{N}\times[0,T]$. We have $\tilde{u}^{i}_{n+e_{jk}}\leq\tilde{u}^{i}_{n}$. This implies $\gamma_{\beta,kj}^{n,i} (\tilde{u}^{i}_{n+e_{jk}}-\tilde{u}^{i}_{n})\leq0$. We also have $\Delta_{i} \tilde{u}_{n}\leq0$. Hence

$$-\frac{d\tilde{u}_n^i}{dt}(t) \leq h \biggl(\Delta_i \tilde{u}_n, \frac{n}{N}, i \biggr)+\rho\leq h \biggl(0,\frac{n}{N}, i \biggr)+ \rho. $$

Furthermore, if we take −2M<ρ<−M we get

$$-\frac{d\tilde{u}_n^i}{dt}(t)<0. $$

This shows that the maximum of $\tilde{u}$ is achieved at T hence

$$u_n^i(t)\leq\|u(T)\|_{\infty}+2M (T-t). $$

 □

Proof Lemma 3

Recall that α ^∗(p,θ,i) is Lipschitz in (p,θ). Let K be the corresponding Lipschitz constant. Since ∥p∥ bounded, we have |α ^∗(p,.,.)|≤C. Then

 □

Proof of Lemma 4

Let z be a solution of (40), and fix ϵ>0. We define $\tilde{z}= z+\epsilon(t-\nobreak T)$. Hence $\tilde{z}$ satisfies

$$-\dot{\tilde{z}}_m=-\epsilon+\sum_{m'\in I_d\times{\mathcal {S}^d_N}}a_{mm'}(t) ({\tilde{z}}_{m'}-{\tilde{z}}_m). $$

Let (m,t) be a maximum point of $\tilde{z}$ on $I_{d}\times{\mathcal {S}^{d}_{N}}\times[0,T]$. We have ${\tilde{z}}_{m}(t)\geq{\tilde{z}}_{m'}(t)$ and this implies $a_{mm'}(t) ({\tilde{z}}_{m'}-{\tilde{z}}_{m})\leq0$ ∀m′. Hence

$$-\frac{d\tilde{z}_m}{dt}(t) \leq-\epsilon. $$

This shows that the maximum of $\tilde{z}$ is achieved at T. Therefore, for all (m′,t),

$$z_{m'}(t)+\epsilon(t-T)=\tilde{z}_{m'}(t)\leq\tilde{z}_m(T)=z_m(T). $$

Letting ϵ→0, we get

$$z_{m'}(t)\leq\max_{m} z_m(T),\quad \forall\bigl(m',t\bigr). $$

From this inequality we have the following conclusions:

• 1. if z(T)≤0, we then have z _m′(t)≤0, for all (m′,t), and so z(t)≤0;

• 2. for all (m′,t),

  $$z_{m'}(t)\leq\|z(T)\|_{\infty}. $$

Now we define $\tilde{z}= z+\epsilon(T-t)$. Hence $\tilde{z}$ satisfies

$$-\dot{\tilde{z}}_m=\epsilon+\sum_{m'\in I_d\times{\mathcal {S}^d_N}}a_{mm'}(t) ({\tilde{z}}_{m'}-{\tilde{z}}_m). $$

Let (m,t) be a minimum point of $\tilde{z}$ on $I_{d}\times{\mathcal {S}^{d}_{N}}\times[0,T]$. We have $a_{mm'}(t) ({\tilde{z}}_{m'}-{\tilde{z}}_{m})\geq0$. Therefore we have

$$-\frac{d\tilde{z}_m}{dt}(t) \geq\epsilon. $$

This shows that the minimum of $\tilde{z}$ is also achieved at T, hence for all (m′,t) we have

$$z_{m'}(t)+\epsilon(T-t)=\tilde{z}_{m'}(t)\geq\tilde{z}_m(T)=z_m(T). $$

Letting ϵ→0, we get z _m′(t)≥min _m z _m (T). Hence

$$z_{m'}(t)\geq- \|z(T)\|_{\infty}, $$

and therefore we have ∥z(t)∥_∞≤∥z(T)∥_∞. □

Proof of Lemma 6

We note that if t≤s≤T we have K(t,s)K(s,T)=K(t,T), which implies

$$\frac{d}{ds} \bigl( K(t,s)K(s, T) \bigr)=0. $$

Hence, using (42) we get

$$-K(t,s)M(s)K(s,T)+ \biggl(\frac{d}{ds} K(t,s) \biggr) K(s,T)=0, $$

and therefore, by taking T=s we conclude that

$$ \frac{d}{ds} K(t,s)=K(t, s)M(s). $$

(69)

Multiplying (43) by K(t,s) and using Lemma 5, we have

$$-K(t,s)\dot{z}(s)\leq K(t,s)M(s) z(s) +K(t,s)f\bigl(z(s)\bigr). $$

Using the identity

$$\frac{d}{ds} K(t,s)z(s)=K(t,s) \dot{z}(s)+ K(t, s) M(s) z(s), $$

which follows from (69), we get

$$-\frac{d}{ds} \bigl(K(t,s)z(s) \bigr) \leq K(t, s)f\bigl(z(s)\bigr). $$

Thus, integrating between t and T, we have

$$z(t)-K(t, T)z(T)\leq\int_t^T K(t, s)f \bigl(z(s)\bigr) ds. $$

Note that if z(t)=K(t,T)z(T) is a solution of (40) with terminal data z(T)=b, then Lemma 4 implies that ∥z(t)∥_∞≤∥z(T)∥_∞, hence ∥K(t,T)z(T)∥_∞≤∥z(T)∥_∞.

Therefore for all $m\in I_{d}\times{\mathcal{S}}^{d}_{N}$ we have

$$z_m(t)\leq\|z(T)\|_{\infty}+\int_t^T \bigl\Vert f\bigl(z(s)\bigr)\bigr\Vert_{\infty}ds. $$

 □

Proof of Lemma 7

Note that (44) implies that v is a monotone decreasing function of s and is equivalent to

$$\everymath{\displaystyle} \begin{cases} \frac{ds}{d v}= \frac{-1}{Cv+C N v^2 + \frac{C}{N}},\\ s\biggl(\frac{C}{N}\biggr)\leq T. \end{cases} $$

This implies by direct integration that

$$s \biggl(\frac{2C}{N} \biggr) \leq T - \int _{\frac{C}{N}}^{\frac{2C}{N}} \frac{dv}{Cv+C N v^2 + \frac {C}{N}}. $$

Now

$$\int_{\frac{C}{N}}^{\frac{2C}{N}} \frac{dv}{Cv+C N v^2 + \frac{C}{N}} \geq \int _{\frac{C}{N}}^{\frac{2C}{N}} \frac{N}{2C^2+4C^3+C}dv = \frac {1}{2C+4C^2+1}. $$

Therefore if we define $T^{\star}=\frac{1}{2C+4C^{2}+1}$, we have that $s (\frac{2C}{N} ) \leq0$ if T≤T ^⋆. Hence this implies $v(0) \leq\frac{2C}{N}$, which yields the desired result when we take into account that v is a decreasing function of s. □