# Control theory approach to continuous-time finite state mean field games

Yurii Averboukh111Higher School of Economics, Moscow, Russia,
e-mail:mailto:averboukh<EMAIL_ADDRESS>
###### Abstract

In the paper, we use the equivalent formulation of a finite state mean field
game as a control problem with mixed constraints to study the dependence of
solutions to finite state mean field game on an initial distribution of
players. We introduce the concept of value multifunction of the mean field
game that is a mapping assigning to an initial time and an initial
distribution a set of expected outcomes of the representative player
corresponding to solutions of the mean field game. Using the control
reformulation of the finite state mean field game, we give the sufficient
condition on a given multifunction to be a value multifunction in the terms of
the viability theory. The maximal multifunction (i.e. the mapping assigning to
an initial time and distribution the whole set of values corresponding to
solutions of the mean field game) is characterized via the backward
attainability set for the certain control systems.
MSC Classification (2020): 49N80, 91A16, 49J45, 60J27, 34H05 .
Keywords: continuous-time finite state mean field game, value multifunction,
viability, backward attainability domain, master equation.

##  1 Introduction

The mean field game theory examines systems of identical players those
interacts via some external media. It was proposed independently by Lasry,
Lions [25], [26] and Huang, Caines, Malhamé [16], [17]. In the paper, we study
the continuous-time finite state mean field games that is the infinite player
dynamic game under assumptions that the players are similar, when the dynamics
of each players is given by a continuous-time finite state Markov chain with
transition probabilities depending on distribution of all players and player’s
actions. The finite state mean field games find various application in the
analysis of socio-econimic systems and modeling of cybersecurity [18], [24],
[22], [19], [21].

The study of the continuous-time finite state mean field games started with
papers [4], [14]. In those papers the approach based on the mean field game
system consisting of Bellman and kynetic equations was developed. Notice that,
for the finite state mean field game, the mean field game system is a system
of ODEs with mixed (initial and boundary) conditions. The results of the
aforementioned papers were extended to the case of finite state mean field
games with common noise acting in a finite sequence of times in [9].

The further progress of the theory of finite state mean field games is due to
the probabilistic approach [11] and master equation [5], [6], [7], [12]. The
master equation first proposed by Lions [27] for the second-order mean field
games is used to justify the convergence of feedback equilibria in the finite
player games to the solution of the mean field game and to study the
dependence of the solution of the mean field game on the initial distribution
of players. However, the theory of master equation for the mean filed games is
developed in the case of unique solution to the mean field game [6], [7], [12]
or in the presence of the common noise [5].

In the paper, we study the dependence of solutions of the continuous-time
finite state mean field game in the general case without any uniqueness
assumptions. To this end, we express the mean field game as a finite-
dimensional control problem with mixed constraints and use the concept of
value multifunction that is a set-valued mapping assigning to an initial time
and an initial distribution of players a set of expected outcomes of the
representative player. The maximal value multifunction comprises all solutions
of the mean field game. We find the sufficient condition on a given
multifunction to be a value multifunction in the terms of the viability
theory. Furthermore, we characterize the maximal value function using the
attainability domain for the certain dynamical system in the backward time
constructed by the original mean filed game. Finally, we show that a graph of
smooth solution of the master equation is a value multifunction.

The paper is organized as follows. In Section 2, we introduce the main
concepts of the continuous-time finite state mean field games. Section 3 is
concerned with the relaxation of the control space. The control problem
equivalent to the finite state mean field game is introduced in Section 4. The
study of dependence of the solution of the finite state mean field game on the
initial distribution is studied in Section 5. Here we introduce the mean field
game dynamical system and show that a multifunction satisfying the viability
condition for this dynamical system is a value mutifunction. Furthermore, we
prove that the maximal value multifunction can be found using the
attainability domain for the certain dynamical system. The last result of
Section 5 gives the link between the solution of master equation and the value
multifunction.

##  2 Problem setting

In this section, we discuss the mean field game system for the finite state
case and deduce the master equation in the multivalued form. Since we do not
impose condition ensuring the uniqueness of the optimal control of the
representative player, the strong analysis of the finite state mean filed
involves the relaxation of the control space which is introduced in Section 3.

###  2.1 Mean field game system for finite state space

Without loss of generality, we assume the state space is $\\{1,\ldots,d\\}$,
where $d\in\mathbb{N}$. Distributions on the space $\\{1,\ldots,d\\}$ lie in
the $d$-dimensional simplex

$\Sigma^{d}\triangleq\\{(m_{1},\ldots,m_{d}):\,m_{i}\geq 0,\ \
m_{1}+\ldots+m_{d}=1\\}.$

In the following, we regard $m\in\Sigma^{d}$ as a row-vector and endow
$\Sigma^{d}$ with the Euclidean metric. Additionally, we embed $\Sigma^{d}$
into the Euclidian space of row-vectors denoted below by $\mathbb{R}^{d*}$.

Recall that mean field games examine systems of infinitely many similar
players. In the finite state case (see [4], [14]), the dynamics of each player
is given by the Markov chain with the Kolmogorov matrix depending on the
current distribution of agents

$Q(t,m,u)=(Q_{i,j}(t,m,u))_{i,j=1}^{d}.$

Here, $t$ stands for a time, $m$ is a distribution of all player, $u$ is a
control of the player chosen from some set $U$. We consider the mean field
game on the finite time horizon $[t_{0},T]$ and assume that each player tries
to maximize

$\mathbb{E}\left[\sigma(X(T),m(T))+\int_{t_{0}}^{T}g(t,X(t),m(t),u(t))dt\right],$
(1)

where $X$ is the stochastic process describing the motion of the player,
$m(t)$ is the distribution of players at time $t$, whereas $u(t)$ denotes the
instantaneous control of the player.

We impose the following conditions on the control space, the Kolmogorov matrix
and the payoff functions.

  1. (C1)

The set $U$ is a metric compact.

  2. (C2)

The functions $Q_{i,j}$, $\sigma$ and $g$ are continuous.

  3. (C3)

The dependence of $Q_{i,j}$ and $g$ on $m$ is Lipschitz continuous uniformly
w.r.t. $t$ and $u$.

The solution of the mean field game is given by the common solution of two
problems. The first one describes the dynamics of the distribution of players,
when the second problem is the optimization problem for the representative
player. To introduce them, let us describe the strategies used by the players.

We assume that the players are informed about current time and state. Since
the state space is finite, one can assume that, a policy is now a $d$-tuple
$u(\cdot)=(u_{i}(\cdot))_{i=1}^{d}$, where $u_{i}(\cdot)$, $i=1,\ldots,d$, are
measurable functions from $[t_{0},T]$ to $U$. Below, we assume that the player
who occupies the state $i$ at time $t$ uses the control $u_{i}(t)$. Therefore,
the dynamics of distribution of players obeys the following Kolmogorov
equation:

$\frac{d}{dt}m_{j}(t)=\sum_{i=1}^{d}m_{i}(t)Q_{i,j}(t,m(t),u_{i}(t)),\ \
j=1,\ldots,d,\ \ m(t_{0})=m_{0}.$ (2)

It is convenient to rewrite this system in the vector form. To this end, given
a vector of controls $u=(u_{i})_{i=1}^{d}\in U^{d}$ and $m\in\Sigma^{d}$,
denote the matrix with the elements $Q_{i,j}(t,m,u_{i})$ by
$\mathcal{Q}(t,m,u)$. Notice that now $U^{d}$ serves as a new control space.
Therefore, system (2) can be rewritten as follows:

$\frac{d}{dt}m(t)=m(t)\mathcal{Q}(t,m(t),u(t)),\ \ m(t_{0})=m_{0}.$ (3)

The second problem is the optimization problem for each player. Given a flow
of probabilities $m(\cdot)$, we obtain the Markov decision problem with the
dynamics determined by the Kolmogorov matrix

$Q(t,m(t),u)$

and objective function (1). Recall that we use the feedback strategies. Within
this framework, the solution of the optimal control problem can be obtained
from the dynamic programming. To introduce it for the Markov decision problem,
we define the Hamiltonian by the following rule: for $t\in[0,T]$,
$m\in\Sigma^{d}$, $\phi\in\mathbb{R}^{d}$, set

$H_{i}(t,m,\phi)\triangleq\max_{u\in
U}\left[\sum_{j=1}^{d}Q_{i,j}(t,m,u)\phi_{j}+g(t,i,m,u)\right],$ (4)
$H(t,m,u)=(H_{i}(t,m,u))_{i=1}^{d}.$

For any flow of probabilities is $m(\cdot)$, the value function
$\phi:[0,T]\rightarrow\mathbb{R}^{d}$ satisfies the Bellman equation

$\frac{d}{dt}\phi(t)=-H(t,m(t),\phi(t)),\ \ \phi_{i}(T)=\sigma(i,T),$ (5)

whereas the feedback optimal strategy is computed by the rule

$\hat{u}_{i}(t)\in\underset{u\in
U}{\operatorname{Argmax}}\left[\sum_{j=1}^{d}Q_{i,j}(t,m,u)\phi_{j}(t)+g(t,i,m(t),u)\right].$
(6)

A solution of the system (3), (5), (6) is a solution of the finite state mean
field game.

###  2.2 Master equation in the multivalued form

To study the dependence of the solution of the mean field game on the initial
distribution of players, Lions proposed the concept of the master equation
[27]. The equivalence between the classical formulation and master equation
for the second order case is shown in [10]. Moreover, there the master
equation technique was used to deduce the convergence of solutions of
$N$-player stochastic differential games to the solution of the mean field
game. These results were extended to the finite state mean field games in [7],
[12]. The assumptions of the aforementioned works include the uniqueness of
the control maximizing the expression of the Hamiltonian (i.e. the Hamiltonian
is assumed to be strictly convex). In the paper, we do not impose this
condition. Thus, it is reasonable to introduce the master equation in the
multivalued setting. In Proposition 2.1 below, we derive this equation under
assumption that there exists a smooth value function of the mean field game.
Proposition 5.9 in Section 5 states that each smooth solution of the master
equation in the multivalued form provides the solution of the mean field game
system.

The main object of the master equation is the function
$\Phi:[0,T]\times\Sigma^{d}\rightarrow\mathbb{R}^{d}$ such that the quantity
$\Phi_{i}(s,\mu)$ can be interpreted as the optimal outcome of the
representative player who starts at the time $s$ from the state $i$ under
assumptions that the initial distribution of agents is $\mu$ and all players
use an optimal strategy realizing a solution of the MFG. Below,
$\partial\Phi/\partial s$ denotes the derivative of $\Phi$ w.r.t. time
variable, while ${\partial\Phi}/{\partial\mu}$ stands for the derivative of
$\Phi$ w.r.t. measure, i.e., given $s\in[0,T]$ and $\mu\in\Sigma^{d}$,
${\partial\Phi}/{\partial\mu}(s,\mu)$ is a $d\times d$ matrix such that, for
every $\mu^{\prime}\in\Sigma^{d}$,

$\Phi(s,\mu^{\prime})-\Phi(s,\mu)=(\mu^{\prime}-\mu)\frac{\partial\Phi}{\partial\mu}(s,\mu)+o(\|\mu^{\prime}-\mu\|).$
(7)

To introduce the master equation, for $\phi\in\mathbb{R}^{d}$, put

$\begin{split}\mathcal{O}(t,m,\phi)\triangleq\Bigl{\\{}m\mathcal{Q}&(t,m,u):u=(u_{i})_{i}^{d},\\\
&\sum_{j=1}^{d}Q_{i,j}(t,m,u_{i})\phi_{j}(t)+g(t,i,m(t),u_{i})=H_{i}(t,m,\phi)\Bigr{\\}}.\end{split}$

######  Proposition 2.1.

Let $\Phi:[0,T]\times\Sigma^{d}\rightarrow\mathbb{R}^{d}$ be a continuously
differentiable function such that, for every $t_{0}\in[0,T]$,
$m_{0}\in\Sigma^{d}$, there exists a solution to mean field game system (3),
(5), (6) $(\phi(\cdot),m(\cdot))$ such that $\Phi(t,m(t))=\phi(t)$ for
$t\in[t_{0},T]$ and $m(t_{0})=m_{0}$. Then, $\Phi$ satisfies the master
equation in the multivalued form

$\frac{\partial}{\partial
s}\Phi(s,\mu)+H(t,\mu,\Phi(s,\mu))\in-\mathcal{O}(s,\mu,\Phi(s,\mu))\frac{\partial\Phi}{\partial\mu}(s,\mu).$
(8)

###### Proof.

By assumption the function $t\mapsto\Phi(t,m(t))$ solves Bellman equation (5),
when $m(\cdot)$ satisfies (2) for the strategy $\hat{u}$ obeying (6). The
later assumption implies the inclusion

$\frac{d}{dt}m(t)\in\mathcal{O}(t,m(t),\Phi(t,m(t))).$ (9)

Differentiating $\Phi(t,m(t))$, from the Bellman equation and the definition
of the derivative of the function $\Phi$ w.r.t. measure (see (7)), we obtain

$\frac{\partial\Phi(t,m(t))}{\partial
t}+H(t,m(t),\Phi(t,m(t)))+\frac{dm(t)}{dt}\cdot\frac{\partial\Phi(t,m(t))}{\partial\mu}=0.$

Using this, (9) and plugging in the resulting inclusion only for the initial
position $(s,\mu)$, we arrive at master equation in the multivalued form (8).
∎

######  Remark 2.2.

If, for each $t\in[0,T]$, $m\in\Sigma^{d}$ and $\phi\in\mathbb{R}^{d}$, there
exists a unique $\bar{u}=(\bar{u}_{i})_{i=1}^{d}$ such that

$\begin{split}\sum_{j=1}^{d}Q_{i,j}&(t,m,u_{i})\phi_{j}+g(t,i,m(t),u_{i})\\\
=&\sum_{j=1}^{d}Q_{i,j}(t,m,\bar{u}_{i})\phi_{j}+g(t,i,m(t),\bar{u}_{i}),\end{split}$

the Hamiltonian is differentiable w.r.t. $\phi$, and master equation (8) takes
the more familiar single-valued form

$\frac{\partial}{\partial s}\Phi(s,\mu)+H(t,\mu,\Phi(s,\mu))+\frac{\partial
H(t,\mu,\phi)}{\partial\phi}\frac{\partial\Phi}{\partial\mu}(s,\mu)=0.$

##  3 Relaxation of the finite state mean field game

In the previous section, we assumed that players occupying the same state use
the same control. However, in the case when the Hamiltonian is not strictly
convex, the optimal control is nonunique. Furthermore, the set of feedback
strategies is neither convex nor closed. To overcome this difficulties, we use
the relaxed (randomized) feedback strategies [15].

A feedback strategy is a mapping

$t\mapsto\nu(t)\triangleq(\nu_{1}(t,du),\ldots,\nu_{d}(t,du))$

such that

  * •

$\nu_{i}(t,\cdot)$ is a probability on $U$;

  * •

the dependence $t\mapsto\int_{U}\zeta(u)\nu_{i}(t,du)$ is measurable for any
continuous function $\zeta:U\rightarrow\mathbb{R}$.

The relaxed strategies imply that the players occupying the state $i$ at the
time $t$ distribute their controls according to the probability
$\nu_{i}(t,du)$.

Thus, for a fixed flow of probabilities $m(\cdot)$ and a relaxed strategy
$\nu(\cdot)$, the motion of a representative player is the Markov chain with
the Kolmogorov matrix

$\left(\int_{U}Q(t,m(t),u)\nu_{i}(t,du)\right)_{i,j=1}^{d}.$

With some abuse of notation, for $t\in[0,T]$, $m\in\Sigma^{d}$,
$\nu=(\nu_{1},\ldots,\nu_{d})\in(\mathcal{P}(U))^{d}$, we set

$\mathcal{Q}_{i,j}(t,m,\nu)\triangleq\left(\int_{U}Q_{i,j}(t,m,u)\nu_{i}(du)\right),$
$g_{i}(t,m,\nu)=g(t,i,m,\nu)\triangleq\int_{U}g(t,i,m,u)\nu_{i}(du).$

Here and below $\mathcal{P}(U)$ stands for the set of all Borel probabilities
on $U$.

Furthermore, notice that

$H_{i}(t,m,\phi)=\max_{\nu_{i}\in\mathcal{P}(U)}\left[\sum_{j=1}^{q}\int_{U}Q(t,m,u)\nu_{i}(du)\cdot\phi_{j}+g_{i}(t,m,\nu_{i})\right].$

Finally, we introduce the matrix and vector notation:

$\mathcal{Q}(t,m,\nu)=(\mathcal{Q}_{i,j}(t,m,\nu))_{i,j=1}^{d}.$
$H(t,m,\phi)\triangleq(H_{1}(t,m,\phi),\ldots,H_{d}(t,m,\phi))^{T},$
$g(t,m,\nu)=(g_{1}(t,m,\nu),\ldots,g_{d}(t,m,\nu))^{T},$
$\sigma(m)\triangleq(\sigma(1,m),\ldots,\sigma(d,m))^{T}.$

Using this notation, we give the following definition.

######  Definition 3.1.

Let $t_{0}\in[0,T]$ be an initial time, $m_{0}\in\Sigma^{d}$ be an initial
distribution of players. We say that a pair $(\phi(\cdot),m(\cdot))$ is a
solution of the mean field game if there exists a relaxed feedback strategy
$\hat{\nu}(\cdot)=(\hat{\nu}_{1}(\cdot),\ldots,\hat{\nu}_{d}(\cdot))$ such
that

  1. 1.

$m(\cdot)$ satisfies the Kolmogorov equation

$\frac{d}{dt}m(t)=m(t)\mathcal{Q}(t,m(t),\hat{\nu}(t)),\ \ m(t_{0})=m_{0}.$
(10)

  2. 2.

$\phi(\cdot)$ satisfies Bellman equation (5), i.e.,

$\frac{d}{dt}\phi(t)=-H(t,m(t),\phi(t)),\ \ \phi(T)=\sigma(m(T))$ (11)

  3. 3.

$\hat{\nu}$ is an optimal control, i.e., for a.e. $t\in[t_{0},T]$,

$\hat{\nu}_{i}(t)\in\underset{\nu_{i}\in\mathcal{P}(U)}{\operatorname{Argmax}}\left[\sum_{j=1}^{q}\int_{U}Q(t,m,u)\nu_{i}(du)\cdot\phi_{j}+\int_{U}g(t,i,m,u)\nu_{i}(du)\right]$
(12)

or, equivalently,

$\frac{d}{dt}\phi(t)+\mathcal{Q}(t,m(t),\hat{\nu}(t))\phi(t)+g(t,m(t),\hat{\nu}(t))=0.$

######  Theorem 3.2.

Under assumptions (C1)–(C3), there exists at least one solution of the mean
field game.

The proof is given in the Appendix. It relies on the fixed point arguments and
representation of the feedback strategies by control measures.

Below we also will use the probabilistic representation of the finite state
mean field game. It is convenient to introduce the dynamics of the
representative player using generator. Let $t\in[0,T]$,
$i\in\\{1,\ldots,d\\}$, $m\in\Sigma^{d}$, $\nu\in(\mathcal{P}(U))^{d}$. Define
the generator $\Lambda_{t}[m,\nu]$ that is a linear operator on
$\mathbb{R}^{d}$ by the following rule: for $\psi\in\mathbb{R}^{d}$,
$\Lambda_{t}[m,\nu]\psi$ is the vector with coordinates

$(\Lambda_{t}[m,\nu]\psi)_{i}\triangleq\sum_{j=1}^{d}\mathcal{Q}_{i,j}(t,m,\nu)\psi(j),\
\ i=1,\ldots,d.$

Given $s,r\in[0,T]$, $s<r$, a flow of probabilities $m(\cdot)$ and a relaxed
feedback strategy $\eta(\cdot)$, we say that the 5-tuple
$(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\in[s,r]},P,X)$, where
$(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\in[s,r]},P)$ is a filtered
probability space, and $X$ is a $\\{\mathcal{F}_{t}\\}_{t\in[s,r]}$-adapted
stochastic process taking values in $\\{1,\ldots,d\\}$, provides a motion of
the representative player on $[r,s]$ if, for any $\psi\in\mathbb{R}^{d}$, the
process

$\psi_{X(t)}-\int_{s}^{t}(\Lambda_{\tau}[m(\tau),\eta(\tau)]\psi)_{X(\tau)}d\tau$

is a $\\{\mathcal{F}_{t}\\}_{t\in[s,r]}$-martingale.

Notice that, for every initial probability on $\\{1,\ldots,d\\}$, at least one
motion of the representative player always exists [23, Theorem 3.11] (see also
[20, Propositions 4.1 and Example 4.5]). One can introduce the probabilities
$\mu_{i}(t)\triangleq P(X(t)=i)$. If $\mu_{*}=(\mu_{*,i})_{i=1}^{d}$ is the
initial distribution at the time $s$, then the vector
$\mu(t)=(\mu_{i}(t))_{i=1}^{d}$ obeys the Kolmogorov equation

$\frac{d}{dt}\mu(t)=\mu(t)\mathcal{Q}(t,m(t),\eta(t)),\ \ \mu(s)=\mu_{*}.$
(13)

Now let us reformulate Definition 3.1 within the framework of the
probabilistic approach.

######  Proposition 3.3.

The pair $(\phi(\cdot),m(\cdot))$ solves the mean field game with the
equilibrium feedback strategy $\hat{\nu}(\cdot)$, if and only if (10), (11)
holds and $\hat{\nu}(\cdot)$ is the optimal feedback relaxed strategy at any
initial distribution for the Markov decision problem on $[t_{0},T]$

$\text{maximize
}\mathbb{E}\left[\sigma(X(T),m(T))+\int_{t_{0}}^{T}g(t,X(t),m(t),\eta(t))dt\right]$
(14)

subject to a feedback relaxed strategy
$\eta(\cdot):[t_{0},T]\rightarrow(\mathcal{P}(U))^{d}$ and a corresponding
motion of the representative player
$(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\in[t_{0},T]},P,X)$ at any
initial position, where $\mathbb{E}$ stands for the expectation according to
the probability $P$.

###### Proof.

It suffices to prove that the fact that $\hat{\nu}$ is optimal control for the
Markov decision problem on $[t_{0},T]$ with payoff given by (14) subject to a
strategy $\eta$ and a corresponding motion of the representative player
$(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\in[t_{0},T]},P,X)$ is equivalent
to (12). This directly follows from the dynamic programming principle. ∎

Notice that the expectation of payoff (14) is determined only by
$\eta(\cdot)$, $m(\cdot)$ and the initial distribution $\mu_{0}$ equation (13)
with $s=t_{0}$ and $\mu_{*}=\mu_{0}$ by the formula:

$\begin{split}\mathbb{E}\Bigl{[}\sigma(X(T),&m(T))+\int_{t_{0}}^{T}g(t,X(t),m(t),\eta(t))dt\Bigr{]}\\\
&=\mu(T)\sigma(m(T))+\int_{t_{0}}^{T}\mu(t)g(t,m(t),\eta(t))dt.\end{split}$
(15)

Thus, the optimal feedback strategies do not depend on the concrete choice of
the realization of the motion of the representative player.

##  4 Optimal control reformulation

The purpose of the section is to show that the finite state mean field game
interpreted in the sense of Definition 3.1 is equivalent to the following
control problem:

$\begin{split}\text{minimize
}J(\phi(\cdot),&m(\cdot),\mu(\cdot),\nu(\cdot))\triangleq\\\
&\mu_{0}\phi(t_{0})-\mu(T)\sigma(m(T))+\int_{t_{0}}^{T}\mu(t)g(t,m(t),\nu(t))dt\end{split}$
(16)

subject to $(\phi(\cdot),m(\cdot),\mu(\cdot),\nu(\cdot))$ satisfying

$\frac{d}{dt}m(t)=m(t)\mathcal{Q}(t,m(t),\nu(t)),$ (17)
$\frac{d}{dt}\mu(t)=\mu(t)\mathcal{Q}(t,m(t),\nu(t)),$ (18)
$\frac{d}{dt}\phi(t)=-H(t,m(t),\phi(t)),$ (19)
$m(t_{0})=m_{0},\,\mu(t_{0})=\mu_{0},\,\phi(T)=\sigma(m(T)).$ (20)

Notice that the state vector for this problem is $(\phi,m,\mu)$, where
$\phi\in\mathbb{R}^{d}$, $m,\mu\in\Sigma^{d}$, when the control parameter is
$\nu=(\nu_{1},\ldots,\nu_{d})\in(\mathcal{P}(U))^{d}$. One may regard the
vector $\phi(t)$ as the upper bound of the rewards; $m(t)$ stands for the
distribution of all players; $\mu(t)$ describes the evolution of fictitious
player.

######  Proposition 4.1.

For every control process $(\phi(\cdot),m(\cdot),\mu(\cdot),\nu(\cdot))$
satisfying (17), (18), (19), (20)

$J(\phi(\cdot),m(\cdot),\mu(\cdot),\nu(\cdot))\geq 0.$

###### Proof.

First, let $e^{k}$ stand for the $k$-th coordinate vector of
$\mathbb{R}^{d*}$. Notice that, for any
$\mu_{0}=(\mu_{0,1},\ldots,\mu_{0,d})\in\Sigma^{d}$,

$\mu_{0}=\sum_{k=1}^{d}\mu_{0,k}e^{k}.$

Furthermore, let $[t_{0},T]\ni t\mapsto\mu^{k}(t)\in\Sigma^{d}$ be a solution
of the initial value problem

$\frac{d}{dt}\mu^{k}(t)=\mu^{k}(t)\mathcal{Q}(t,m(t),\nu(t)),\ \
\mu^{k}(t_{0})=e^{k}.$ (21)

The trajectory $\mu^{k}(\cdot)$ describes the probability distribution for the
representative player who starts at time $t_{0}$ from the state $k$. Notice
that, if $\mu(\cdot)$ satisfies (18), then

$\mu(\cdot)=\sum_{k=1}^{d}\mu_{0,k}\mu^{k}(\cdot).$

Put

$\begin{split}J_{k}(\phi(\cdot)&,m(\cdot),\mu^{k}(\cdot),\nu(\cdot))\\\
&\triangleq\phi_{k}(t_{0})-\mu^{k}(T)\sigma(m(T))-\int_{t_{0}}^{T}\mu^{k}(t)g(t,m(t),\nu(t))dt\\\
&=e^{k}\phi(t_{0})-\mu^{k}(T)\sigma(m(T))-\int_{t_{0}}^{T}\mu^{k}(t)g(t,m(t),\nu(t))dt.\end{split}$
(22)

Notice that the quantity

$\mu^{k}(T)\sigma(m(T))+\int_{t_{0}}^{T}\mu^{k}(t)g(t,m(t),\nu(t))dt$

is the reward of the representative player who starts from the state $k$ and
uses the strategy $\nu$ in the case when the distribution of all players is
given by $m(\cdot)$. Since $\phi_{k}(\cdot)$ is equal to the maximal expected
reward of the representative player, we deduce that

$J_{k}(\phi(\cdot),m(\cdot),\mu^{k}(\cdot),\nu(\cdot))\geq 0.$ (23)

Furthermore, if $\mu(\cdot)$ satisfies (18), then

$J(\phi(\cdot),m(\cdot),\mu(\cdot),\nu(\cdot))=\sum_{k=1}^{d}\mu_{0,k}J_{k}(\phi(\cdot),m(\cdot),\mu^{k}(\cdot),\nu(\cdot)).$
(24)

This and (23) give the conclusion of the proposition. ∎

In the following theorem, we assume that the data of the mean field game
$m_{0}$ and $\sigma$ are fixed.

######  Theorem 4.2.

For the function
$t\mapsto(\phi^{*}(t),m^{*}(t))\in\mathbb{R}^{d}\times\Sigma^{d}$ and the
control $t\mapsto\nu^{*}(t)$ the following statements are equivalent.

  1. (i)

The pair $(\phi^{*}(\cdot),m^{*}(\cdot))$ solves the mean field game with
initial distribution $m_{0}$, whereas $\nu^{*}(\cdot)$ is the corresponding
equilibrium feedback strategy.

  2. (ii)

There exists a flow of probabilities $\mu^{*}(\cdot)$ and an initial
distribution $\mu_{0}^{*}\in\Sigma^{d}$ with nonzero coordinates such that
$(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))$ provides the
solution of the optimal control problem (16)–(20) for $\mu_{0}=\mu_{0}^{*}$.

  3. (iii)

For every $\mu^{*}(\cdot)$ satisfying (18), the control process
$(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))$ is the solution
of the optimal control problem (16)–(20) with $\mu_{0}=\mu^{*}(t_{0})$.

  4. (iv)

The triple $(\phi^{*}(\cdot),m^{*}(\cdot),\nu^{*}(\cdot))$ is such that, for
some $\mu_{0}\in\Sigma^{d}$ with nonzero coordinates and $\mu^{*}(\cdot)$, the
process $(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))$
satisfies (17)–(20) and the equality

$J(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))=0.$

  5. (v)

For every $\mu^{*}(\cdot)$ satisfying (18) and $\mu_{0}=\mu^{*}(t_{0})$, the
control process $(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu(\cdot))$
satisfies (17)–(20) and the following equality holds:

$J(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))=0.$

###### Proof.

The scheme of implications proving the desired equivalence can be illustrate
by the following commutative diagram.

$\textstyle{\mathrm{(i)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathrm{(iv)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\mathrm{(v)}}$$\textstyle{\mathrm{(ii)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\mathrm{(iii)}}$

Obviously, we have that (iii) implies (ii). Analogously, (iv) follows from
(v).

Now we prove implication (v)$\Rightarrow$(iii). Let $\mu^{*,k}$,
$k=1,\ldots,d$, satisfy (21) for $m(\cdot)=m^{*}(\cdot)$ and
$\nu=\nu^{*}(\cdot)$. Condition (v) implies that each value
$J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))=0$.
Further, let $\mu_{0}=(\mu_{0,1},\ldots,\mu_{0,d})$ be an arbitrary element of
$\Sigma^{d}$. The function $\mu^{*}(\cdot)$ defined by

$\mu^{*}(t)\triangleq\sum_{k=1}^{d}\mu_{0,k}\mu^{*,k}(t)$

solves (18) with initial condition $\mu^{*}(t_{0})=\mu_{0}$. Moreover, we have
that

$J(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))=\sum_{k=1}^{d}\mu_{0,k}J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))=0.$

This and Proposition 4.1 yield that
$(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))$ provides the
solution of the optimal control problem (16)–(20) for every $\mu^{*}(\cdot)$,
$\mu_{0}$ satisfying ODE (18) and initial condition $\mu^{*}(t_{0})=\mu_{0}$.
Thus, (v) implies (iii) and, consequently, (ii).

By Proposition 3.3, statement (i) is equivalent to the following one:
equations (17), (19) hold true and
$J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))=0$.
Indeed, let
$(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\in[t_{0},T]},P,X^{k})$ be the
motion of the representative player corresponding to the control
$\nu^{*}(\cdot)$, flow of probabilities $m^{*}(\cdot)$ and initial
distribution $e^{k}$. Proposition 3.3 yields that

$\phi_{k}^{*}(t_{0})=\mathbb{E}\left[\sigma(X^{k}(T),m(T))+\int_{t_{0}}^{T}g(t,X^{k}(t),m(t),\nu(t))dt\right],$

where $\mu^{*,k}_{i}=P(X^{k}(t)=i)$,
$\phi^{*}(t_{0})=(\phi^{*}_{k}(t_{0}))_{k=1}^{d}$. This and equality (15)
imply that

$\phi_{k}^{*}(t_{0})=\mu^{*,k}(T)\phi^{*}(T)+\int_{t_{0}}^{T}\mu^{*,k}(t)g(t,m^{*}(t),\nu^{*}(t))dt.$

Using the definition of $J_{k}$, we deduce that optimality of $\nu^{*}(\cdot)$
is equivalent to the equality
$J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))=0$.

Therefore, if (i) holds, then one can use (24) and deduce (v).

Let us prove implication (iv)$\Rightarrow$(i). Since

$J(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))=\sum_{k=1}^{d}\mu_{0,k}J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))$

and

$J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))\geq
0,\,k=1,\ldots,d,$

we conclude that
$J_{k}(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*,k}(\cdot),\nu^{*}(\cdot))=0$. This
together with (17) and (19) is equivalent to (i).

To complete the proof, we prove the implication (ii)$\Rightarrow$(iv). Assume
that $(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))$ provides
the optimal solution of the control problem (16), (17), (18), (19). From
Proposition 4.1, it follows that

$J(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))\geq 0.$

Furthermore, recall (see Theorem 3.2) that, for the initial distribution
$m_{0}$, there exists at least one solution of the finite state mean field
game $(\phi^{\natural}(\cdot),m^{\natural}(\cdot))$ with the corresponding
equilibrium strategy $\nu^{\natural}(\cdot)$. Using the implication
(i)$\Rightarrow$(v) for the solution of the mean field game
$(\phi^{\natural}(\cdot),m^{\natural}(\cdot))$ and the equilibrium feedback
strategy $\nu^{\natural}(\cdot)$, we deduce that the infimum of
$J(\phi^{\prime}(\cdot),m^{\prime}(\cdot),\mu^{\prime}(\cdot),\nu^{\prime}(\cdot))$
over the set of 4-tuples obeying (17)–(19) is not greater than $0$. This leads
the equality

$J(\phi^{*}(\cdot),m^{*}(\cdot),\mu^{*}(\cdot),\nu^{*}(\cdot))=0.$

This means that (ii) implies (iv). ∎

######  Corollary 4.3.

If $m_{0}$ has nonzero-coordinates, then the following statements are
equivalent.

  * •

The pair $(\phi^{*}(\cdot),m^{*}(\cdot))$ solves the mean field game with the
initial distribution $m_{0}$, whereas $\nu^{*}(\cdot)$ is the corresponding
equilibrium feedback strategy.

  * •

The process $(\phi^{*}(\cdot),m^{*}(\cdot),\nu^{*}(\cdot))$ is optimal in the
problem

$\begin{split}\text{minimize
}J^{\prime}(\phi(\cdot),m(\cdot),\nu(\cdot))\triangleq
m_{0}\phi(&t_{0})-m(T)\sigma(m(T))\\\
-&\int_{t_{0}}^{T}m(t)g(t,m(t),\nu(t))dt\end{split}$

subject to (17), (19) and $m(t_{0})=m_{0}$, $\phi(T)=\sigma(m(T))$.

  * •

The triple $(\phi^{*}(\cdot),m^{*}(\cdot),\nu^{*}(\cdot))$ satisfies (17),
(19), the boundary condition $m^{*}(t_{0})=m_{0}$,
$\phi^{*}(T)=\sigma(m^{*}(T))$ and the equality
$J^{\prime}(\phi^{*}(\cdot),m^{*}(\cdot),\nu^{*}(\cdot))=0$.

###### Proof.

The desired equivalence follows from Theorem 4.2 and the fact that, if
$m(\cdot)$ and $\mu(\cdot)$ satisfying (17) and (18) respectively are such
that $m(t_{0})=\mu(t_{0})$, then $m(\cdot)=\mu(\cdot)$. ∎

##  5 Dependence of the solution of the mean field game on the initial
distribution

Generally, the solution of the mean field game is nonunique [8]. Thus, it is
reasonable to examine the multifunction assigning to an initial time and
initial distribution of players a set of expected values of the representative
player. This concept generalized the notion of value function briefly
discussed in §2.2. In this section, we study the value multfunction using the
viability and attainability theories.

######  Definition 5.1.

We say that $\mathcal{V}:[0,T]\times\Sigma^{d}\rightrightarrows\mathbb{R}^{d}$
is a value multifunction if, for any $t_{0}\in[0,T]$, $m_{0}\in\Sigma^{d}$,
$\phi_{0}\in\mathcal{V}(t_{0},m_{0})$, there exists a solution of the mean
field game $(\phi(\cdot),m(\cdot))$ such that

$\phi(t_{0})=\phi_{0},\ \ m(t_{0})=m_{0}.$

We also consider the maximal value function that is multivalued mapping
assigning to each pair $(t_{0},m_{0})$ the set of all vectors $\phi_{0}$ such
that $\phi_{0}=\phi(t_{0})$, $m_{0}=m(t_{0})$ for some solution of the mean
field game $(\phi(\cdot),m(\cdot))$. Denote the maximal value multifunction by
$\mathcal{W}$.

First, let us present the sufficient condition for a given multifunction
$\mathcal{V}:[t_{0},T]\times\Sigma^{d}\rightrightarrows\mathbb{R}^{d}$ to be a
value multifunction. To this end, we use the viability property for the
dynamics in the space
$\mathbb{R}^{d}\times\Sigma^{d}\times\Sigma^{d}\times\mathbb{R}$ given by
equations (17)–(19) and the following differential equation:

$\begin{split}\frac{d}{dt}z(t)=-\mu(t)\mathcal{Q}&(t,m(t),\nu(t))\phi(t)\\\
&-\mu(t)H(t,m(t),\phi(t))-\mu(t)g(t,m(t),\nu(t)).\end{split}$ (25)

######  Definition 5.2.

We say that the set
$\mathcal{A}\subset[0,T]\times\mathbb{R}^{d}\times\Sigma^{d}\times\Sigma^{d}\times\mathbb{R}$
is viable w.r.t. the dynamics (17)–(19), (25) if, for every $s,r\in[0,T]$,
$s<r$, $(s,\phi_{*},m_{*},\mu_{*},z_{*})\in\mathcal{A}$, there exists a
feedback relaxed control $\nu(\cdot)$ and a 4-tuple
$(\phi(\cdot),m(\cdot),\mu(\cdot),z(\cdot))$ such that

  * •

$\phi(\cdot)$, $m(\cdot)$, $\mu(\cdot)$, $z(\cdot)$ and $\nu(\cdot)$ satisfy
(17)–(19), (25);

  * •

$\phi(s)=\phi_{*}$, $m(s)=m_{*}$, $\mu(s)=\mu_{*}$, $z(s)=z_{*}$;

  * •

$(r,\phi(r),m(r),\mu(r),z(r))\in\mathcal{A}$.

######  Theorem 5.3.

Assume that, given a multifunction
$\mathcal{V}:[0,T]\times\Sigma^{d}\rightrightarrows\mathbb{R}^{d}$, one can
find a closed set
$\mathcal{A}\subset[0,T]\times\mathbb{R}^{d}\times\Sigma^{d}\times\Sigma^{d}\times\mathbb{R}$
such that

  * •

$\mathcal{A}$ is viable w.r.t. (17)–(19), (25);

  * •

the inclusion $(T,\phi,m,\mu,z)\in\mathcal{A}$ implies that $\phi=\sigma(m)$,
$z=0$;

  * •

if $\phi_{0}\in\mathcal{V}(t_{0},m_{0})$, then
$(t_{0},\phi_{0},m_{0},\mu_{0},0)\in\mathcal{A}$ for some
$\mu_{0}\in\Sigma^{d}$ with nonzero coordinates.

Then, $\mathcal{V}$ is a value multifunction.

The proof of the Theorem relies on the following lemma.

######  Lemma 5.4.

If $(\phi(\cdot),m(\cdot),\mu(\cdot),z(\cdot),\nu(\cdot))$ obeys (17)–(19),
(25), then, for every $s,r\in[0,T]$, $s<r$,

$z(r)-z(s)=\mu(s)\phi(s)-\mu(r)\phi(r)-\int_{s}^{r}\mu(t)g(t,m(t),\nu(t))dt.$
(26)

###### Proof.

In fact,

$\mu(r)\phi(r)-\mu(s)\phi(s)=\int_{s}^{r}\frac{d}{dt}\left[\mu(t)\phi(t)\right]dt.$

Since $\mu(\cdot)$ and $\phi(\cdot)$ satisfy equations (18) and (19)
respectively, we obtain that

$\frac{d}{dt}[\mu(t)\phi(t)]=\mu(t)\mathcal{Q}(t,m(t),\nu(t))\phi(t)+\mu(t)H(t,m(t),\phi(t)).$

This and (25) imply representation (26).

∎

###### Proof of Theorem 5.3.

Let $(t_{0},\phi_{0},m_{0},\mu_{0})$ be such that

$(t_{0},\phi_{0},m_{0},\mu_{0},0)\in\mathcal{A},$

and let $\mu_{0}$ have nonzero coordinates. Using the standard viability
technique (see [3, Theorem 3.3.4]), we deduce that there exists
$(\phi(\cdot),m(\cdot),\mu(\cdot),z(\cdot),\nu(\cdot))$ satisfying (17)–(19),
(25) and boundary conditions

$m(t_{0})=m_{0},\ \ \phi(t_{0})=\phi_{0},\ \ \mu(t_{0})=\mu_{0},\ \
z(t_{0})=0,$ $\phi(T)=\sigma(m(T)),\ \ z(T)=0.$

Using Lemma 5.4 and definition of the function $J$ (see (16)), we conclude
that

$\begin{split}z(T)&=z(t_{0})+\mu(t_{0})\phi(t_{0})-\mu(T)\phi(T)-\int_{t_{0}}^{T}\mu(t)g(t,m(t),\nu(t))dt\\\
&=z(t_{0})+J(m(\cdot),\phi(\cdot),\mu(\cdot),\nu(\cdot)).\end{split}$

From the boundary conditions, it follows that

$J(\phi(\cdot),m(\cdot),\mu(\cdot),\nu(\cdot))=0.$

This means that, for $(\phi(\cdot),m(\cdot),\nu(\cdot))$, statement (iv) of
Theorem 4.2 is in force. By Theorem 4.2 $(\phi(\cdot),m(\cdot))$ is a solution
of the finite state mean field game. Thus, $\mathcal{V}$ is a value
multifunction. ∎

Now let us characterize the maximal value multifunction $\mathcal{W}$ in the
terms of the attainability domain. Denote

$\hat{\vartheta}\triangleq(1/\sqrt{d},\ldots,1/\sqrt{d})=\frac{1}{\sqrt{d}}(1,\ldots,1)=\frac{1}{\sqrt{d}}\sum_{i=1}^{d}e^{k}.$

######  Theorem 5.5.

Let $\mathcal{A}_{*}$ be the set of 5-tuples $(s,\phi(s),m(s),\mu(s),z(s))$
such that $s\in[0,T]$, when the 4-tuple
$(\phi(\cdot),m(\cdot),\mu(\cdot),z(\cdot))$ satisfies (17)–(19), (25) for
some relaxed strategy $\nu(\cdot)$ and the boundary condition

$m(T)\in\Sigma^{d},\ \ \phi(T)=\sigma(m(T)),\ \ \mu(T)\in\Sigma^{d},\ \
z(T)=0.$

Then, given $t_{0}\in[0,T]$, $m_{0}\in\Sigma^{d}$,

$\mathcal{W}(t_{0},m_{0})=\\{\phi_{0}:(t_{0},\phi_{0},m_{0},\hat{\vartheta},0)\in\mathcal{A}_{*}\\}.$

######  Remark 5.6.

In Theorem 5.5 one can replace $\hat{\vartheta}$ with an arbitrary row-vector
with nonzero coordinates.

The proof of Theorem 5.5 uses the following auxiliary statement.

######  Lemma 5.7.

Assume that $(\phi(\cdot),m(\cdot),\mu(\cdot),z(\cdot),\nu(\cdot))$ satisfies
(17)–(19), (25). Then, the function $t\mapsto z(t)$ is nondecreasing.

###### Proof.

Consider the Markov decision problem on $[s,r]$ with the dynamics given by the
Markov chain with the Kolmogorov matrix

$\mathcal{Q}(t,m(t),\nu(t))$

and the reward equal to

$\mathbb{E}\left[\phi_{X(r)}(r)+\int_{s}^{r}g(t,X(t),m(t),\nu(t))dt\right].$
(27)

From dynamic programming principle it follows that that the value function of
this problem at $t\in[s,r]$ is equal to $\phi(t)$.

Let $(\Omega,\mathcal{F},\\{\mathcal{F}_{t}\\}_{t\in[t_{0},T]},P,X)$ be a
motion of the representative player corresponding to the feedback relaxed
control $\nu(\cdot)$, the flow of probabilities $m(\cdot)$ and the initial
distribution at time $s$ equal to $\mu(s)$. As above, we have that the
probability $P(X(t)=i)=\mu_{i}(t)$ and, thus, obeys (18). We have that

$\begin{split}\mathbb{E}\Bigl{[}\phi_{X(r)}(r)+&\int_{s}^{r}g(t,X(t),m(t),\nu(t))dt\Bigr{]}\\\
&=\mu(r)\phi(r)+\int_{s}^{r}\mu(t)g(t,m(t),\nu(t))dt.\end{split}$

Since $\phi(s)$ is the value at time $s$ for the Markov decision problem with
the payoff given by (27) and the dynamics given by the Markov chain
$\mathcal{Q}(t,m(t),\nu(t))$ on $[s,r]$, we have that

$\mu(s)\phi(s)-\mu(r)\phi(r)-\int_{s}^{r}\mu(t)g(t,m(t),\nu(t))dt\geq 0.$

Combining this with (26), we obtain that $z(r)\geq z(s)$ when $r>s$. ∎

###### Proof of Theorem 5.5.

Notice that $\mathcal{A}_{*}$ is viable with respect to equations (17)–(19),
(25). Hence, by Theorem 5.3 the mapping
$(t_{0},m_{0})\rightarrow\\{\phi_{0}:(t_{0},\phi_{0},m_{0},\vartheta,0)\in\mathcal{A}_{*}\\}$
is a value multifunctions. Hence,

$\\{\phi_{0}:(t_{0},\phi_{0},m_{0},\hat{\vartheta},0)\in\mathcal{A}_{*}\\}\subset\mathcal{W}(t_{0},m_{0}).$
(28)

Let us prove the opposite inclusion.

Choose $\phi_{0}\in\mathcal{W}(t_{0},m_{0})$. This means that there exists a
solution of the mean field game $(\phi(\cdot),m(\cdot))$ such that
$\phi(t_{0})=\phi_{0}$, $m(t_{0})=m_{0}$. Let $\nu(\cdot)$ be a equilibrium
relaxed feedback strategy corresponding to this solution and let $\mu(\cdot)$
solve (18) with the initial condition $\mu(t_{0})=\hat{\vartheta}$. Further,
put

$z(s)\triangleq\mu(s)\phi(s)-\mu(T)\sigma(m(T))-\int_{s}^{T}\mu(t)g(t,m(t),\nu(t))dt.$

Notice, that $z(\cdot)$ satisfies (25) and
$z(t_{0})=J(m(\cdot),\phi(\cdot),\mu(\cdot),\nu(\cdot))$. By Theorem 4.2, we
conclude that $z(t_{0})=0$. Additionally, $z(T)=0$. Using Lemma 5.7, we obtain
that $z(s)=0$ for every $s\in[t_{0},T]$. This implies that
$(t_{0},m_{0},\phi_{0},\hat{\vartheta},0)\in\mathcal{A}_{*}$. Therefore,

$\mathcal{W}(t_{0},m_{0})\subset\\{\phi_{0}:(t_{0},\phi_{0},m_{0},\hat{\vartheta},0)\in\mathcal{A}_{*}\\}.$

This together with (28) yields the theorem. ∎

Let us complete the section by the fact that each solution of the master
equation determines a value multifunction.

Master equation (8) relies on the measurable feedback strategies. However, we
primary consider relaxed strategies. Thus, we relax the master equation and
arrive at the following:

$\frac{\partial}{\partial
s}\Phi(s,\mu)+H(t,\mu,\Phi(s,\mu))\in-\operatorname{co}\mathcal{O}(s,\mu,\Phi(s,\mu))\cdot\frac{\partial\Phi}{\partial\mu}(s,\mu).$
(29)

Here,

$\begin{split}\operatorname{co}\mathcal{O}(s,m,\phi)=\Bigl{\\{}m&\mathcal{Q}(t,m,\nu):\\\
&\mathcal{Q}(t,m,\nu)\phi+g(t,m(t),\nu)=H(t,m,\phi),\ \
\nu\in(\mathcal{P}(U))^{d}\Bigr{\\}}.\end{split}$

######  Definition 5.8.

We say that $\Phi:[0,T]\times\Sigma^{d}\rightarrow\mathbb{R}^{d}$ is a smooth
solution of master equation in the multivalued form (29) if $\Phi$ is
continuously differentiable and satisfies (29) for every $s\in[0,T]$ and
$\mu\in\Sigma^{d}$.

Here the derivative w.r.t. measure is understood in the sense of formula (7).

######  Proposition 5.9.

Let $\Phi$ be a smooth solution of master equation in the multivalued form
(29). Then, the multifunction

$\mathcal{V}(t_{0},m_{0})\triangleq\\{\Phi(t_{0},m_{0})\\}$

is a value multifunction.

###### Proof.

Choose $t_{0}\in[0,T]$, $m_{0}\in\Sigma^{d}$. We shall prove that there exists
a solution of the mean field game $(\phi(\cdot),m(\cdot))$ such that
$\phi(t_{0})=\Phi(t_{0},m_{0})$, $m(t_{0})=m_{0}$.

Let $\mathcal{O}^{\sharp}(s,\mu)$ be the set of row-vectors
$\xi\in\operatorname{co}\mathcal{O}(s,\mu,\Phi(s,\mu))$ such that

$-\xi\frac{\partial\Phi(s,\mu)}{\partial\mu}=\frac{\partial}{\partial
s}\Phi(s,\mu)+H(t,\mu,\Phi(s,\mu)).$ (30)

Obviously, $\mathcal{O}^{\sharp}(s,\mu)$ is convex. The continuity of the
function $\Phi$ and its derivatives yields that the mapping
$[0,T]\times\Sigma^{d}\mapsto\mapsto\mathcal{O}^{\sharp}(s,\mu)\subset\mathbb{R}^{d*}$
is upper semicontinuous. In particular, for each $(s,\mu)$, the set
$\mathcal{O}^{\sharp}(s,\mu)$ is compact.

Further, let $m(\cdot)$ solve the differential inclusion

$\frac{d}{dt}m(t)\in\mathcal{O}^{\sharp}(t,m(t)),\ \ m(t_{0})=m_{0}.$ (31)

Consider the multivalued mapping

$\begin{split}t\multimap\Bigl{\\{}\nu\in(\mathcal{P}(U))^{d}:\frac{d}{dt}&m(t)=m(t)\mathcal{Q}(t,m(t),\nu),\\\
\mathcal{Q}(t,m&(t),\nu)\Phi(t,m(t))+g(t,m(t),\nu)=H(t,m(t),\Phi(t,m(t)))\Bigr{\\}}.\end{split}$

By [1, §18.17, Filippov’s Implicit Function Theorem], this mapping admits a
measurable selector. Denote it by $\hat{\nu}(\cdot)$. Thus,

$\frac{d}{dt}m(t)=m(t)\mathcal{Q}(t,m(t),\hat{\nu}(t)),\ \ m(t_{0})=m_{0}.$
(32)
$\mathcal{Q}(t,m(t),\hat{\nu}(t))\Phi(t,m(t))+g(t,m(t),\hat{\nu}(t))=H(t,m(t),\Phi(t,m(t)))$
(33)

Furthermore, (30) and (31) yield the equality

$-\left(\frac{d}{dt}m(t)\right)\frac{\partial\Phi(s,\mu)}{\partial\mu}\Bigr{|}_{s=t,\mu=m(t)}=\frac{\partial}{\partial
s}\Phi(s,\mu)\Bigr{|}_{s=t,\mu=m(t)}+H(t,m,\Phi(s,m)).$ (34)

Now, set $\phi(t)\triangleq\Phi(t,m(t))$. Due to (34), we have that it
satisfies the Bellman equation

$\frac{d}{dt}\phi(t)=-H(t,m(t),\phi(t))$ (35)

and the boundary conditions

$\phi(T)=\Phi(T,m(T))=\sigma(m(T)),\ \ \phi(t_{0})=\Phi(t_{0},m(t_{0})).$ (36)

The fact that $\hat{\nu}(\cdot)$ is an optimal control for the representative
player directly follows from (33). Combining this with (32), (35) and (36), we
conclude that the pair $(\phi(\cdot),m(\cdot))$ is a solution of the mean
field game such that $\phi(t_{0})=\Phi(t_{0},m(t_{0}))$, $m(t_{0})=m_{0}$.
Since we choose $(t_{0},m_{0})$ arbitrarily, the multifunction $\mathcal{V}$
is the value mutifunction.

∎

## Appendix. Existence of the solution of the finite state mean field game

Below we give the proof of Theorem 3.2. It relies on fixed point arguments and
the notion of control measures. Notice that the approach based on control
measures is equivalent to one involving relaxed feedback strategies.
Simultaneously, the set of control measures is compact. This allows to use the
fixed point technique.

Throughout the Appendix we assume that the initial time $t_{0}\in[0,T]$ and
the initial distribution of players
$m_{0}=(m_{0,1},\ldots,m_{0,d})\in\Sigma^{d}$ are fixed. The notion of the
control measures is introduced as follows.

Let $\mathcal{U}$ denote the set of measures $\alpha$ on $[t_{0},T]\times U$
compatible with the Lebesgue measure, i.e., for any Borel set
$\Gamma\subset[t_{0},T]$,

$\alpha(\Gamma\times U)=\lambda(\Gamma),$

where $\lambda$ denotes the Lebesgue measure on $[t_{0},T]$. Within the
control theory, elements of $\mathcal{U}$ are often called control measures.
The meaning of this term is explained below. We endow the set $\mathcal{U}$
with the topology of narrow convergence, i.e., the sequence
$\\{\alpha^{n}\\}_{n=1}^{\infty}\subset\mathcal{U}$ converges to
$\alpha\in\mathcal{U}$ iff, for every $f\in C([t_{0},T]\times U)$,

$\int_{[t_{0},T]\times U}f(t,u)\alpha^{n}(d(t,u))\rightarrow\int_{[0,T]\times
U}f(t,u)\alpha(d(t,u))\text{ as }n\rightarrow\infty.$

Notice that $\mathcal{U}$ can be regarded as the compact convex subset of the
set of all charges on $[t_{0},T]\times U$ that is a Banach space.

The link between elements of $\mathcal{U}$ and weakly measurable functions is
straightforward. If $\nu:[t_{0},T]\rightarrow\mathcal{P}(U)$ be a weakly
measurable function, then the corresponding measure $\alpha$ is defined by the
rule: for $f\in C([t_{0},T]\times U)$,

$\int_{[t_{0},T]\times
U}f(t,u)\alpha(d(t,u))\triangleq\int_{t_{0}}^{T}\int_{U}f(t,u)\nu(t,du)dt.$
(37)

Conversely, given $\alpha\in\mathcal{U}$ by the disintegration theorem (see
[13, 78-111]) there exists a weakly measurable function $\nu$ such that (37)
holds true. This disintegration is unique almost everywhere, i.e., if
$\nu^{\prime}$ and $\nu^{\prime}$ are two weakly measurable functions
satisfying (37), then

$\nu^{\prime}(t,\cdot)=\nu^{\prime\prime}(t,\cdot)\text{ a.e.}$

Below, we denote the disintegration of the measure $\alpha\in\mathcal{U}$ by
$\alpha(\cdot|t)$.

Using the disintegration, one can give the meaning of the control measures.
The feedback formalization implies that, for each state $i$, we choose a
control measure $\alpha_{i}$, while the player occupying the state $i$ at time
$s$ shares his/her controls according to $\alpha_{i}(du|s)$, i.e., the
disintegration of the control measure gives the feedback strategy. Thus, the
Kolmogorov equation can be rewritten as follows:

$\frac{d}{dt}m_{j}(t)=m_{0,j}+\int_{[t_{0},t]\times
U}\sum_{i=1}^{d}m_{i}(\tau)Q_{i,j}(\tau,m(\tau),u)\alpha_{i}(d(\tau,u)).$ (38)

Here $m_{0}=(m_{0,1},\ldots,m_{0,d})$ is the initial distribution. If
$\alpha=(\alpha_{i})_{i=1}^{d}\in\mathcal{U}^{d}$ is a sequence of control
measures, then we denote the solution of (38) by $m[\cdot,\alpha]$.

Now, let $\phi[\cdot,\alpha]$ stand for the solution of the Hamiltion-Jacobi
equation with the $m(\cdot)=m[\cdot,\alpha]$, i.e.,

$\frac{d}{dt}\phi[t,\alpha]=-H(t,m[t,\alpha],\phi[t,\alpha]),\ \
\phi[T,\alpha]=\sigma(m[T,\alpha]).$ (39)

Further, if $t\in[t_{0},T]$, $m\in\Sigma^{d}$, $\phi\in\mathbb{R}^{d}$, then
denote by $\Xi_{i}(t,m,\phi)$ the set of elements $u\in U$ maximizing the
quantity

$\left[\sum_{j=1}^{d}Q_{i,j}(t,m,u)\phi_{j}+g(t,i,m,u)\right],$

i.e., from the definition of $H_{i}$ (see (4)) it follows that, if
$u\in\Xi_{i}(t,m,\phi)$, then

$\left[\sum_{j=1}^{d}Q_{i,j}(t,m,u)\phi_{j}+g(t,i,m,u)\right]=H_{i}(t,m,\phi).$

Since $U$ is a metric compact, the set $\Xi_{i}(t,m,\phi)$ is nonempty for
each $t$, $m$ and $\phi$. Moreover, if $m(\cdot)$ and $\phi(\cdot)$ are
continuous function, then the dependence

$t\mapsto\Xi_{i}(t,m(t),\phi(t))$

is upper semicontinuous.

When $m(\cdot)=m[\cdot,\alpha]$ and $\phi(\cdot)=\phi[\cdot,\alpha]$, we
denote the graph of the mapping

$t\mapsto\Xi_{i}(t,m[t,\alpha],\phi[t,\alpha]),$

i.e., we set

$\begin{split}\mathcal{K}_{i}[\alpha]\triangleq\Bigl{\\{}(t,u^{*})\in&[t_{0},T]\times
U:\\\
\sum_{j=1}^{d}&Q_{i,j}(t,m[t,\alpha],u^{*})\phi_{j}[t,\alpha]+g(t,i,m[t,\alpha],u^{*})\\\
=&\max_{u\in
U}\bigl{[}\sum_{j=1}^{d}Q_{i,j}(t,m[t,\alpha],u)\phi_{j}[t,\alpha]+g(t,i,m[t,\alpha],u)\bigr{]}\Bigr{\\}}.\end{split}$
(40)

Using this, we can reformulate the definition of the solution of the finite
state mean field game in the term of control measures.

######  Proposition A.1.

A pair $(\phi(\cdot),m(\cdot))$ is a solution of the mean field game iff there
exists a
$\hat{\alpha}=(\hat{\alpha}_{1},\ldots,\hat{\alpha}_{d})\in\mathcal{U}^{d}$
such that

  1. 1.

$m(\cdot)=m[\cdot,\hat{\alpha}]$, $\phi(\cdot)=\phi[\cdot,\hat{\alpha}]$;

  2. 2.

for each $i=1,\ldots,d$,
$\operatorname{supp}(\hat{\alpha}_{i})\subset\mathcal{K}_{i}[\hat{\alpha}]$.

###### Proof.

First, assume that $\phi(\cdot)$, $m(\cdot)$ is the solution of the finite
state mean field game in the sense of Definition 3.1. Let
$\hat{\nu}=(\hat{\nu}_{1},\ldots,\hat{\nu}_{d})$ be the corresponding
equilibrium strategy. For each $\hat{\nu}_{i}$, define the control measures
$\hat{\alpha}_{i}$ by (37). Thanks to (38), we have that

$m(\cdot)=m[\cdot,\hat{\alpha}],\ \ \phi(\cdot)=\phi[\cdot,\hat{\alpha}].$

Inclusion (12) and equality (4) imply that, for a.e. $t\in[t_{0},T]$,

$\begin{split}\int_{U}\Bigl{[}\sum_{j=1}^{d}Q_{i,j}(t,m[t,\hat{\alpha}],u)&\phi_{j}[t,\hat{\alpha}]+g(t,i,m[t,\hat{\alpha}],u)\\\
&-H_{i}(t,m[t,\hat{\alpha}],u)\Bigr{]}\hat{\nu}_{i}(t,du)=0.\end{split}$ (41)

Integrating this w.r.t. time variable and using (37), we obtain that

$\begin{split}\int_{[t_{0},T]\times
U}\Bigl{[}\sum_{j=1}^{d}Q_{i,j}(t,m[t,\hat{\alpha}],u)&\phi_{j}[t,\hat{\alpha}]+g(t,i,m[t,\hat{\alpha}],u)\\\
&-H_{i}(t,m[t,\hat{\alpha}],u)\Bigr{]}\hat{\alpha}(d(t,u))=0.\end{split}$ (42)

This, the definitions of the set $\mathcal{K}_{i}$ (see (40)) and the function
$H_{i}$ (see (4)) yield that

$\operatorname{supp}(\hat{\alpha}_{i})\subset\mathcal{K}_{i}[\hat{\alpha}].$

Therefore, each solution of the finite state mean field type satisfies the
properties of this proposition.

Conversely, assume that $\phi(\cdot)$, $m(\cdot)$ and
$\hat{\alpha}=(\hat{\alpha}_{1},\ldots,\hat{\alpha}_{d})$ satisfy properties
1,2 of the proposition. We define the relaxed controls $\hat{\nu}_{i}$ to be
equal to the disintegration of $\hat{\alpha}_{i}$. Hence, $\phi(\cdot)$ and
$m(\cdot)$ satisfy equations (10), (11).

Further, due to (40), inclusion

$\operatorname{supp}(\hat{\alpha}_{i})\subset\mathcal{K}_{i}[\hat{\alpha}]$

implies (42). Since $\hat{\nu}_{i}$ is a disintegration of $\hat{\alpha}_{i}$,
we conclude that (41) holds true for a.e. $t\in[t_{0},T]$. This and definition
of $H_{i}$ (see (4)) give inclusion (12). ∎

In the light of Proposition A.1, we reduce the existence theorem for the
finite state mean field game to the fixed point problem for the multivalued
mapping $\Phi$ that assigns to $\alpha\in\mathcal{U}^{d}$ the set of sequence
of measures $\beta=(\beta_{1},\ldots,\beta_{d})\in\mathcal{U}^{d}$ such that

$\operatorname{supp}(\beta_{i})\subset\mathcal{K}_{i}[\alpha],\ \
i=1,\ldots,d.$

To apply the fixed point theorem, we prove that $\Phi$ has compact and convex
values and is upper semicontinuous.

Since the set $\mathcal{K}_{i}[\alpha]$ is compact, we have that the set of
measures $\beta_{i}\in\mathcal{U}$ those are supported on
$\mathcal{K}_{i}[\alpha]$ is compact and convex. To prove the upper
semicontinuity of the mapping $\Phi$, we, first, prove that $m[\cdot,\alpha]$
and $\phi[\cdot,\alpha]$ depend on $\alpha$ continuously, then apply the fact
that the mapping assigning to the functions $m(\cdot)$, $\phi(\cdot)$ the
graph of $\Xi_{i}(\cdot,m(\cdot),\phi(\cdot))$ is upper semicontinuous.

In the following, we say the sequence
$\\{\alpha^{n}\\}_{n=1}^{\infty}\subset\mathcal{U}^{d}$ converges to
$\alpha\in\mathcal{U}^{d}$ provided that each sequence of measures
$\\{\alpha_{i}^{n}\\}_{n=1}^{\infty}$ converges narrowly to $\alpha_{i}$,
where $\alpha^{n}=(\alpha_{1}^{n},\ldots,\alpha_{d}^{n})$,
$\alpha=(\alpha_{1},\ldots,\alpha_{d})$.

######  Lemma A.2.

If $\\{\alpha^{n}\\}\subset\mathcal{U}^{d}$ converges to
$\alpha\in\mathcal{U}^{d}$, then $\\{m[\cdot,\alpha^{n}]\\}_{n=1}^{\infty}$
converges to $m[\cdot,\alpha^{*}]$ in $C([t_{0},T],\Sigma^{d})$.

###### Proof.

To simplify designation set

$m^{n}(\cdot)\triangleq m[\cdot,\alpha^{n}],\ \ m^{*}(\cdot)\triangleq
m[\cdot,\alpha^{*}].$

Recall that $m^{n}(t)$ is a vector with coordinates
$(m_{1}^{n}(t),\ldots,m_{d}^{n}(t))$, while
$m^{*}(t)=(m^{*}_{1}(t),\ldots,m^{*}_{d}(t))$. We have that

$\begin{split}|m_{j}^{n}(t)-m^{*}_{j}(t)&|\\\ =\Bigl{|}\int_{[t_{0},t]\times
U}&\sum_{i=1}^{d}m_{i}^{n}(\tau)Q_{i,j}(\tau,m^{n}(\tau),u)\alpha_{i}^{n}(d(\tau,u))\\\
&-\int_{[t_{0},t]\times
U}\sum_{i=1}^{d}m_{i}^{*}(\tau)Q_{i,j}(\tau,m^{*}(\tau),u)\alpha_{i}^{*}(d(\tau,u))\Bigr{|}\\\
\leq\int_{[t_{0},t]\times
U}&\sum_{i=1}^{d}|m_{i}^{n}(\tau)Q_{i,j}(\tau,m^{n}(\tau),u)-m_{i}^{*}(\tau)Q_{i,j}(\tau,m^{*}(\tau),u)|\alpha_{i}^{n}(d(\tau,u))\\\
&+\Bigl{|}\int_{[t_{0},t]\times
U}\sum_{i=1}^{d}m_{i}^{*}(\tau)Q_{i,j}(\tau,m^{*}(\tau),u)\alpha_{i}^{n}(d(\tau,u))\\\
&\hskip 40.0pt-\int_{[t_{0},t]\times
U}\sum_{i=1}^{d}m_{i}^{*}(\tau)Q_{i,j}(\tau,m^{*}(\tau),u)\alpha_{i}^{*}(d(\tau,u))\Bigr{|}.\end{split}$
(43)

Notice that

$\begin{split}\sum_{i=1}^{d}|&m_{i}^{n}(t)Q_{i,j}(t,m^{n}(t),u)-m_{i}^{*}(t)Q_{i,j}(t,m^{*}(t),u)|\\\
&\leq
C_{0}\sum_{i=1}^{d}|m_{i}^{n}(t)-m_{i}^{*}(t)|+dC_{1}\|m^{n}(t)-m^{*}(t)\|\leq
C_{2}\|m^{n}(t)-m^{*}(t)\|.\end{split}$ (44)

Here $C_{0}$ is the upper bound of $|Q_{i,j}(t,m,u)|$, $C_{1}$ is the common
Lipschitz contant for the functions $m\mapsto Q_{i,j}(t,m,u)$, while
$C_{2}\triangleq\sqrt{d}C_{0}+dC_{1}$.

Further, let $L$ be a positive number. Set

$\tau_{l}^{L}\triangleq Tl/L.$

For each $i,j\in\\{1,\ldots,d\\}$, $l\in\\{0,\ldots,L-1\\}$, consider the
function $f^{L}_{i,j,l}:[t_{0},T]\times U\mapsto\mathbb{R}$ such that

  * •

$f_{i,j,l}^{L}(t,u)=m_{i}^{*}(t)Q_{i,j}(t,m^{*}(t),u)$ if
$t\in[0,\tau_{l}^{L}]$;

  * •

$f_{i,j,l}^{L}(t,u)=0$ if $t\in[\tau^{L}_{l+1},T]$;

  * •

the function $t\mapsto f_{i,j,l}^{L}(t,u)$ is linear on
$[\tau_{l}^{L},\tau_{l+1}^{L}]$.

Notice that, for every $t\in[\tau_{l}^{L},\tau_{l+1}^{L}]$ and each
$\alpha\in\mathcal{U}$,

$\begin{split}\Bigl{|}\int_{[t_{0},T]\times
U}f_{i,j,l}^{L}&(t,u)\alpha(d(t,u))\\\ &-\int_{[t_{0},T]\times
U}m_{i}^{*}(t)Q_{i,j}(t,m^{*}(t),u)\alpha(d(t,u))\Bigr{|}\leq
C_{0}T/L.\end{split}$ (45)

Since $\\{\alpha_{i}^{n}\\}$ narrowly converge to $\alpha^{*}_{i}$, we have
that there exists $N_{L}$ such that, for any $n\geq N_{L}$, and every
$i,j\in\\{1,\ldots,d\\}$ and $l=\\{0,\ldots,L-1\\}$,

$\Bigl{|}\int_{[t_{0},T]\times
U}f_{i,j,l}^{L}(t,u)\alpha_{i}^{n}(d(t,u))-\int_{[t_{0},t]\times
U}f_{i,j,l}^{L}(t,u)\alpha_{i}^{n}(d(t,u))\Bigr{|}\leq 1/L.$

Plugging this, (44) and (45) into the right-hand side of (43), we conclude
that, for each $k=1,\ldots,d$ and $n\geq N(L)$,

$|m_{j}^{n}(t)-m^{*}_{j}(t)|\leq\int_{t_{0}}^{T}C_{2}\|m^{n}(\tau)-m^{*}(\tau)\|d\tau+C_{3}/L.$

Here we denote $C_{3}\triangleq d(C_{0}T+1)$. Hence, if $n\geq N(L)$,

$\|m^{n}(t)-m^{*}(t)\|\leq
C_{2}\sqrt{d}\int_{t_{0}}^{T}\|m^{n}(\tau)-m^{*}(\tau)\|d\tau+\sqrt{d}C_{3}/L.$

Applying the Gronwall’s inequality we obtain that, for $n\geq N(L)$ and each
$t\in[t_{0},T]$,

$\|m^{n}(t)-m^{*}(t)\|\leq C_{4}/L,$

where $C_{4}$ is a constant equal to $\sqrt{d}C_{3}\exp(C_{2}\sqrt{d}T)$. This
gives the statement of the lemma. ∎

Using the continuity of the mapping $\alpha\mapsto m[\cdot,\alpha]$ we are
able to derive the following.

######  Lemma A.3.

The mapping $\Phi$ is upper semicontinuous, i.e., if
$\\{\alpha^{n}\\}_{n=1}^{\infty}\subset\mathcal{U}^{d}$ converges to
$\alpha^{*}\in\mathcal{U}^{d}$, $\\{\beta^{n}\\}_{n=1}^{\infty}\subset{U}^{d}$
is such that $\beta^{n}\in\Phi(\alpha^{n})$ and
$\\{\beta^{n}\\}_{n=1}^{\infty}$ converges to $\beta^{*}$, then
$\beta^{*}\in\Phi(\alpha^{*})$.

###### Proof.

It suffices to show that each probability $\beta^{*}_{i}$ is supported on
$\mathcal{K}_{[}\alpha^{*}]$, where
$\beta^{*}=(\beta^{*}_{1},\ldots,\beta^{*}_{d})$.

Lemma A.2 states that $m[\cdot,\alpha^{n}]\rightarrow m[\cdot,\alpha^{*}]$ in
$C([t_{0},T];\Sigma^{d})$ as $n\rightarrow\infty$. Hence, from the definition
of $\phi[\cdot,\alpha]$ (see (39)) and continuous dependence of the solution
of ODE on parameter, we conclude that
$\\{\phi[\cdot,\alpha^{n}]\\}_{n=1}^{\infty}$ converges to
$\phi[\cdot,\alpha^{*}]$ when $n\rightarrow\infty$. This and very definition
of the set $\mathcal{K}_{i}[\alpha]$ (40) yield that, if a sequence
$\\{(t^{n},u_{i}^{n})\\}_{n=1}^{\infty}\subset[0,T]\times U$ converges to some
$(t^{*},u^{*}_{i})$ and $(t^{n},u^{n}_{i})\in\mathcal{K}[\alpha^{n}]$, then
$(t^{*},u^{*})\in\mathcal{K}[\alpha^{*}]$.

Further, recall that $\beta^{n}=(\beta^{n}_{1},\ldots,\beta^{n}_{d})$, whilst
the convergence of $\\{\beta^{n}\\}$ to $\beta^{*}$ means that, for each $i$
$\beta^{n}_{i}$ narrowly converges to $\beta^{*}_{i}$. Due to [2, Proposition
5.1.8], we have that, for every
$(t^{*},u_{i}^{*})\in\operatorname{supp}(\beta^{*}_{i})$, there exists a
sequence $\\{(t^{n},u_{i}^{n})\\}$ that converges to $(t^{*},u^{*}_{i})$ such
that $(t^{n},u_{i}^{n})\in\operatorname{supp}(\beta_{i}^{n})$. The
construction of $\Phi$ implies that
$\operatorname{supp}(\beta^{n}_{i})\subset\mathcal{K}_{i}[\alpha^{n}]$.
Therefore, using the upper semicontinuity of the $\mathcal{K}_{i}$ (see
above), we conclude that $(t^{*},u^{*}_{i})\in\mathcal{K}_{i}[\alpha^{*}]$.
This gives the conclusion of the lemma. ∎

###### Proof of Theorem 3.2.

Since the multivalued mapping $\Phi$ has convex and compact values and is
upper semicontinuous (see Lemma A.3), by the Fan–Glicksberg fixed point
theorem (see [1, Corollary 17.55]) it admits a fixed point. Denote it by
$\hat{\alpha}$. Let $\hat{m}(\cdot)\triangleq m[\cdot,\hat{\alpha}]$,
$\hat{\phi}(\cdot)\triangleq\phi[\cdot,\hat{\alpha}]$. By Proposition A.1, the
pair $(\hat{\phi}(\cdot),\hat{m}(\cdot))$ is the solution of the finite state
mean field game in the sense of Definition 3.1. ∎

Acknowledgment.  The article was prepared in the framework of a research grant
funded by the Ministry of Science and Higher Education of the Russian
Federation (grant ID: 075-15-2020-928).

## References

  * [1] C. D. Aliprantis and K. C. Border.  Infinite Dimensional Analysis: A Hitchhiker’s Guide.  Springer, Berlin, Heidelberg, 2006.
  * [2] L. Ambrosio, N. Gigli, and G. Savaré.  Gradient flows: in metric spaces and in the space of probability measures.  Lectures in Mathematics. ETH Zurich. Birkhäuser, Basel, 2005.
  * [3] J.-P. Aubin.  Viability theory.  Birkhäuser, Boston, 2009.
  * [4] R. Basna, A. Hilbert, and V. N. Kolokoltsov.  An approximate Nash equilibrium for pure jump Markov games of mean-field-type on continuous state space.  Stochastics, 89(6-7), 2016.
  * [5] E. Bayraktar, A. Cecchin, A. Cohen, and F. Delarue.  Finite state mean field games with Wright-Fisher common noise as limits of ${N}$-player weighted games.  Preprint at ArXiv:2012.04845, 2020.
  * [6] E. Bayraktar, A. Cecchin, A. Cohen, and F. Delarue.  Finite state mean field games with Wright-Fisher common noise.  J. Math. Pures Appl., 147:98–162, 2021.
  * [7] E. Bayraktar and A. Cohen.  Analysis of a finite state many player game using its master equation.  SIAM J. Control. Optim., 56(5):3538–3568, 2018.
  * [8] E. Bayraktar and X. Zhang.  On non-uniqueness in mean field games.  Proc. Amer. Math. Soc., 148:4091–4106, 2020.
  * [9] C. Belak, D. Hoffmann, and F. T. Seifried.  Continuous-time mean field games with finite state space and common noise.  Appl. Math. Optim., 2021.  accepted.
  * [10] P. Cardaliaguet, F. Delarue, J.-M. Lasry, and P.-L. Lions.  The Master Equation and the Convergence Problem in Mean Field Games.  Princeton University Press, Princeton, 2019.
  * [11] A. Cecchin and M. Fischer.  Probabilistic approach to finite state mean field games.  Appl. Math. Opt., 81(2):253–300, 2020.
  * [12] A. Cecchin and G. Pelino.  Convergence, fluctuations and large deviations for finite state mean field games via the master equation.  Stochastic Process. Appl., 129:4510–4555, 2019.
  * [13] C. Dellacherie and P.-A. Meyer.  Probabilities and Potential.  North Holland, Amsterdam, 1979.
  * [14] D. A. Gomes, J. Mohr, and R. R. Souza.  Continuous time finite state mean field games.  Appl. Math. Opt., 68:99–143, 2013.
  * [15] X. Guo and O. Hernández-Lerma.  Continuous-Time Markov Decision Processes.  Springer, New York, 2009.
  * [16] M. Huang, P. E. Caines, and R. P. Malhamé.  Large-population cost-coupled LQG problems with nonuniform agents: individual-mass behavior and decentralized Nash equilibria.  IEEE Trans. Automat. Control, 52:1560–1571, 2007.
  * [17] M. Huang, R. P. Malhamé, and P. E. Caines.  Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle.  Commun. Inf. Syst., 6:221–251, 2006.
  * [18] S. Katsikas and V. N. Kolokoltsov.  Evolutionary, mean-field and pressure-resistance game modelling of networks security.  J. Dyn. Games, 6(4):315–335, 2019.
  * [19] V. Kolokoltsov and A. Bensoussan.  Mean-field-game model for botnet defense in cyber-security.  Appl. Math. Opt., 74(3):669–692, 2016.
  * [20] V. Kolokoltsov, J. J. Li, and W. Yang.  Mean field games and nonlinear Markov processes.  Preprint at arXiv:1112.3744v2, 2011.
  * [21] V. Kolokoltsov and O. Malafeyev.  Many agent games in socio-economic systems: corruption, inspection, coalition building, network growth, security.  Springer Nature, New York, 2019.
  * [22] V. Kolokoltsov and W. Yang.  Inspection games in a mean field setting.  Preprint at ArXiv:1507.08339, 2015.
  * [23] V. N. Kolokoltsov.  Nonlinear Markov process and kinetic equations.  Cambridge University Press, Cambridge, 2010.
  * [24] V. N. Kolokoltsov and O. A. Malafeyev.  Corruption and botnet defense: a mean field game approach.  Int. J. Game Theory, 47:977–999, 2018.
  * [25] J.-M. Lasry and P.-L. Lions.  Jeux à champ moyen. I. Le cas stationnaire.  C. R. Math. Acad. Sci. Paris, 343:619–625, 2006.
  * [26] J.-M. Lasry and P.-L. Lions.  Jeux à champ moyen. II. Horizon fini et contrôle optimal.  C. R. Math. Acad. Sci. Paris, 343:679–684, 2006.
  * [27] P.-L. Lions.  College de France course on mean-field games.  College de France, 2007-2011.


# Unilateral Ground Contact Force Regulations
in Thruster-Assisted Legged Locomotion

Eric Sihite  Electrical and Computer Engineering
Northeastern University
Boston, USA
<EMAIL_ADDRESS>Pravin Dangol  Electrical and Computer Engineering
Northeastern University
Boston, USA
<EMAIL_ADDRESS>Alireza Ramezani  Electrical and Computer
Engineering
Northeastern University
Boston, USA
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the regulation of the Ground Contact Forces (GRF) in
thruster-assisted legged locomotion. We will employ Reference Governors (RGs)
for enforcing GRF constraints in Harpy model which is a bipedal robot that is
being developed at Northeastern University. Optimization-based methods and
whole body control are widely used for enforcing the no-slip constraints in
legged locomotion which can be very computationally expensive. In contrast,
RGs can enforce these constraints by manipulating joint reference trajectories
using Lyapunov stability arguments which can be computed much faster. The
addition of the thrusters in our model allows to manipulate the gait
parameters and the GRF without sacrificing the locomotion stability.

###### Index Terms:

Humanoid Robots, Robot Dynamics and Control, Legged Robots

##  I Introduction

There are several examples of successful legged robots that can hop or trot
robustly in the presence of significant disturbances, such as the Raibert’s
hopping robots [1] and Boston Dynamics’ robots [2]. Other than these
successful examples, a large number of underactuated and fully actuated
bipedal robots have also been introduced. Agility Robotics’ Cassie [3],
Honda’s ASIMO [4] and Samsung’s Mahru III [5] are capable of walking, running,
dancing and going up and down stairs, and the Yobotics-IHMC [6] biped can
recover from pushes. Despite these accomplishments, these systems are prone to
falling over when navigating rough terrains. Even humans, which has naturally
robust gait, can trip and fall over when walking on uneven or slippery
surfaces. Therefore, the objective of this work is to extend our knowledge on
bipedal walking and explore the possibility of using thrusters to assist
bipedal robots to achieve a more stable walking gait.

In this paper, we will report our efforts in designing closed-loop feedback
for the thruster-assisted walking of a legged system called Harpy (shown in
Fig. 1), currently its hardware being developed at Northeastern University.
This biped is equipped with a total of eight actuators, and a pair of coaxial
thrusters fixed to its torso. The thrusters allow the robot to perform multi-
modal locomotion, where it can simply fly over difficult terrains where
walking can be highly costly or difficult for the robot to handle.

Thrusters can result in unparalleled capabilities. For instance, gait
trajectory planning (or re-planning), control and unilateral contact force
regulation can be treated significantly differently as we have shown
previously [7, 8, 9, 10, 11]. That said, real-time gait trajectory design in
legged robots has been widely studied and the application of optimization-
based methods is very common [12]. The optimization allows the implementation
of constraints to avoid slipping, but these methods can be cumbersome as they
are widely defined based on Whole Body Control (WBC) which can lead to
computationally expensive algorithms [13]. Other attempts entail optimization-
based, nonlinear approaches to secure safety and performance of legged
locomotion [14, 15, 16].

Figure 1: Illustration of a concept design for Harpy, a thruster-assisted
bipedal robot designed by the authors to study robust, efficient and agile
legged robotics.

We will capitalize on the thrusters action in Harpy and will show that one can
limit the use of costly optimization-based schemes by directly regulating
contact forces. We will resolve gait parameters and re-plan them during the
whole Single Support (SS) phase, which is the longest phase in a gait cycle,
by only assuming well-tuned supervisory controllers found in [17, 18, 19] and
by focusing on fine-tuning the joints desired trajectories to satisfy
unilateral contact force constraints. To do this, we will devise intermediary
filters based on the celebrated idea of Explicit Reference Governors (ERG)
[20, 21, 22]. ERGs relied on provable Lyapunov stability properties can
perform the motion planning problem in the state space in a much faster way
than widely used optimization-based methods. That said, these ERG-based gait
modifications and impact events (i.e., impulsive effects) can lead to severe
deviations from the desired periodic orbits and standard legged robots cannot
sustain these perturbations. Previously, we demonstrated that the thrusters
can be leveraged to enforce hybrid invariance in a robust fashion by applying
predictive schemes within the Double Support (DS) phase [9].

In this paper, we explore the implementation of ERG in enforcing ground
reaction force (GRF) constraints on a bipedal robot. First, the dynamic and
reduced order models of the robot are derived where the addition of thrusters
allow a fully actuated variable length inverted pendulum (VLIP) model. The
VLIP model will be used to model the GRF which will be used to calculate the
no-slip constraints and be enforced by the ERG. The implementation of the ERG
is done on the VLIP model and on the 3D biped model where we will show the
performance of applying the ERG on these systems. This paper is outlined as
follows: the dynamic modeling for Harpy reduced-order model (ROM) which will
be used in designing the ERG, the ERG algorithm used in this paper, and
followed by the numerical simulations and the concluding remarks.

##  II Dynamic Modeling and Control

This section contains the brief overview of the dynamic model used in this
paper for the simulation, which is followed with the derivation of the ROM to
be used in the ERG and controller design.

Figure 2: Leg kinematics of the robot where the leg joints are represented by
the hip frontal ($\gamma_{H}$), hip sagittal ($\phi_{H}$), and knee sagittal
($\phi_{K}$) angles. The thrusters are designed to rotate about the sagittal
angle; however in this paper, in order to simplify the controls, they can
apply force in any direction.

Figure 2 shows the degrees of freedom of the robot’s leg where there are three
actuated joints: hip frontal, hip sagittal, and knee sagittal joints. Combined
with the robot’s body, the system has a combined total of 12 degrees-of-
freedom (DoF). The thrusters are designed to rotate about the body’s sagittal
axis, but in the current modeling we assume that the thrusters can provide
forces in any direction to simplify the problem. In this case, the thruster
dynamics is also ignored. The model is simplified further by assuming that the
mass is concentrated at the body and the joints motors, which results in a
simpler model where the lower leg (shin and foot) are massless. The foot is
also considered to be small so they can be modeled as a point foot which
simplifies the ground force effect to the system at the cost of less stability
due to the smaller support polygon.

The dynamic model of Harpy, which is used in the numerical simulation, can be
derived using the Euler-Lagrangian dynamic formulation. The body rotation is
derived using the modified Lagrangian for dynamics in SO(3) which is done to
avoid the gimbal lock or singularity which exists in the Tait-Bryan
representation of the rotation matrix. Let $\bm{x}$ be the system states,
defined as follows

$\bm{x}=[\bm{c};\bm{r}_{B};\bm{\gamma}_{H};\bm{\phi}_{H};\bm{\phi}_{K};\dot{\bm{c}};\bm{\omega}_{B};\dot{\bm{\gamma}}_{H};\dot{\bm{\phi}}_{H};\dot{\bm{\phi}}_{K}],$
(1)

where $\bm{c}$ is the inertial position of the body center of mass,
$\bm{r}_{B}$ is the vector forming the components of the rotation matrix
$\bm{z}=\bm{R}_{B}\,\bm{z}^{B}$ which rotates from the body frame to the
inertial frame, $\bm{\omega}_{B}$ is the body angular velocity about the body
frame. Furthermore, $\bm{\gamma}_{H}$, $\bm{\phi}_{H}$, and $\bm{\phi}_{K}$
are the vectors representing the leg joint angles (hip frontal, hip and knee
sagittal, respectively), where each variables contains the left and right
component of the leg joints. Then the system equation of motion can be derived
in the standard ODE form

$\dot{\bm{x}}=\bm{f}(\bm{x},\bm{u}_{j},\bm{u}_{t},\bm{u}_{g}),$ (2)

where $\bm{u}_{j}$ is the leg joint actuation inputs, $\bm{u}_{t}$ is the
thruster forces, and $\bm{u}_{g}$ is the GRF. Each of these inputs are
separated into left and right leg components (e.g.
$\bm{u}_{g}=[\bm{u}_{g,l};\bm{u}_{g,r}]$).

The ground is modeled using the compliant ground model using a very stiff
unilateral spring and damping

$u_{gz}(p_{z},\dot{p}_{z})=\begin{cases}0&\mbox{if }p_{z}>0,\\\
-k_{pg}\,p_{z}-k_{dg}\dot{p}_{z}&\mbox{if }p_{z}\leq 0,\end{cases}$ (3)

where $k_{pg}$ and $k_{dg}$ are the ground spring and damping coefficient
respectively, and $p_{z}$ are the foot vertical position. Additionally,
$k_{dg}=0$ when $\dot{p}_{z}>0$ which is done to simulate a ground model with
undamped rebound. The ground friction forces in the $x$ direction is modeled
using the Stribeck friction model

$u_{gx}(\dot{p}_{x})=\left(-\mu_{c}+(\mu_{s}-\mu_{c})e^{-(\dot{p}_{x}/\sigma)^{2}}\right)\,u_{gz}\,|\dot{p}_{x}|+\mu_{v}\,\dot{p}_{x},$
(4)

where $\mu_{s}$, $\mu_{c}$, and $\mu_{v}$ are the static, Coulomb, and viscous
friction coefficients respectively, $\dot{p}_{x}$ is the foot velocity in $x$
direction, and $\sigma$ is the Stribeck velocity. The friction forces in $y$
direction can be derived in the same way. Then the GRF can be formed by
calculating the $u_{gx}$, $u_{gy}$, and $u_{gz}$ for each leg. The controller
design for $\bm{u}_{j}$ and $\bm{u}_{t}$ will be discussed in Section II-B.

###  II-A Reduced-Order Model (ROM)

Figure 3: Reduced-order, variable-length, inverted pendulum model with a
point-mass is subject to thruster forces. This model will be used to estimate
the GRF which will be used to calculate the no-slip constraint equations for
the ERG.

The controller for the thruster forces can be designed using the ROM
represented by the forced inverted pendulum shown in Fig. 3. This will be the
model used to derive the thruster forces components and the ERG. The dynamic
model is derived as follows

$\displaystyle
m\,\ddot{\bm{c}}=m\,\bm{g}+\bm{u}_{t,c}+\bm{J}_{s}^{\top}\,\bm{\lambda},$ (5)

where $m$ is the body mass, $\bm{g}=[0,0,-g]^{\top}$ is the gravitational
acceleration vector, $\bm{u}_{t,c}$ is the thruster forces about the center of
mass, $\bm{J}_{s}^{\top}\,\bm{\lambda}$ forms the constraint force acting on
the body which represents the GRF. The following kinematic constraint equation
is implemented

$\begin{gathered}\bm{J}_{s}\,(\ddot{\bm{c}}-\ddot{\bm{u}})=u_{r},\qquad\bm{J}_{s}=(\bm{c}-\bm{u})^{\top},\end{gathered}$
(6)

where $\bm{u}$ is the center of pressure and $u_{r}$ is the acceleration of
the pendulum length. Therefore, $\bm{\lambda}$ is the Lagrangian multiplier
where the constraint equation in (6) is satisfied and the dynamic equation can
be formulated as follows

$\begin{bmatrix}m\,\bm{I}&-\bm{J}_{s}^{\top}\\\
\bm{J}_{s}&\bm{0}\end{bmatrix}\begin{pmatrix}\ddot{\bm{c}}\\\
\bm{\lambda}\end{pmatrix}=\begin{pmatrix}m\,\bm{g}+\bm{u}_{t,c}\\\
u_{r}+\bm{J}_{s}\,\ddot{\bm{u}}\end{pmatrix}.$ (7)

Then the Lagrangian multiplier can be solved as follows

$\bm{\lambda}=\left(\tfrac{\bm{J}_{s}\bm{J}_{s}^{\top}}{m}\right)^{-1}\,\left(-\bm{J}_{s}\left(\bm{g}+\tfrac{\bm{u}_{t,c}}{m}\right)+u_{r}+\bm{J}_{s}\,\ddot{\bm{u}}\right),$
(8)

which is used to formulate the GRF

$\bm{u}_{g}=\bm{J}_{s}^{\top}\,\bm{\lambda}.$ (9)

The center of pressure is assumed to be constant ($\ddot{\bm{u}}=0$) during
the SS phase.

###  II-B Controller Design

The joint controller is designed to track the desired foot positions by using
the inverse kinematics to calculate the target joint angles. Let
$\bm{q}=[\bm{\gamma}_{H};\bm{\phi}_{H};\bm{\phi}_{K}]$ be the joint angles of
the legs. Given the trajectory $\bm{q}_{t}$, the joint controller $\bm{u}_{j}$
can be derived using the simple PID controller. The trajectory to track is
developed by using optimization on a 2D version of the dynamic model shown in
(2). This trajectory is not stable when utilized in the full 3D system which
motivates the use of thrusters to stabilize the dynamics.

The feedback control law for both $\bm{u}_{t,c}$ and $u_{r}$ are defined as
follows

$\displaystyle\bm{u}_{t,c}$
$\displaystyle=(\bm{I}-\bm{Y})(\bm{K}_{pt}(\bm{c}_{t}-\bm{c})+\bm{K}_{dt}(\dot{\bm{c}_{t}}-\dot{\bm{c}}))$
(10) $\displaystyle u_{r}$
$\displaystyle=\bm{J}_{s}^{\top}(k_{pr}(\bm{c}_{t}-\bm{c})+k_{dr}(\dot{\bm{c}_{t}}-\dot{\bm{c}}))$
$\displaystyle\bm{Y}$
$\displaystyle=\bm{J}_{s}(\bm{J}_{s}^{\top}\bm{J}_{s})^{-1}\bm{J}_{s}^{\top},$

where $\bm{K}$ and $k$ are the controller gains, $\bm{c}_{t}$ and
$\dot{\bm{c}}_{t}$ are the trajectories for the center of mass and its
velocity. $\bm{Y}$ is selected to cancel out the radial component of the
thruster force along the direction of $\bm{c}-\bm{u}$ which reduces the effect
of the thruster force to the GRF.

The thruster forces are also separated into the left and right side components
($\bm{u}_{t,l}$ and $\bm{u}_{t,r}$ respectively) which is also utilized to
stabilize the roll and yaw as follows

$\bm{u}_{t,l}=\begin{bmatrix}u_{yaw}\\\ 0\\\ u_{roll}\\\
\end{bmatrix},\qquad\bm{u}_{t,r}=\begin{bmatrix}-u_{yaw}\\\ 0\\\ -u_{roll}\\\
\end{bmatrix},$ (11) $\bm{u}_{t}=\begin{bmatrix}\bm{u}_{t,c}/2+\bm{u}_{t,l}\\\
\bm{u}_{t,c}/2+\bm{u}_{t,r}\end{bmatrix}$ (12)

where $u_{roll}$ and $u_{pitch}$ is the PD controller action to stabilize the
body’s roll and pitch orientation. The orientation stabilization thruster
forces have a net force of zero, which does not affect the reduced-order
thruster force used in (7).

##  III Explicit Reference Governor (ERG) and Enforcing GRF Constraints

Figure 4: ERG update law for the applied reference to achieve convergence into
the minimum energy level set which satisfies the constraint equation defined
in (13). $\bm{v}_{n}$ is only applied if the constraint is violated to push
the reference into the $\bm{h}_{w}>0$ region.

$\bm{h}_{r}=\bm{h}_{r}(\bm{x},\bm{x}_{r})$

$\bm{h}_{w}=\bm{h}_{r}(\bm{x},\bm{x}_{w})$

$\bm{v}_{r}=\bm{v}_{t}=\bm{v}_{n}=\bm{0}$

$\bm{C}_{r}=[\,\,\,\,]$

if  _$\min(\bm{h}_{w})\geq 0$ or $\min(\bm{h}_{r})\geq 0$_ then

$\bm{v}_{r}=\alpha_{r}\,(\bm{x}_{r}-\bm{x}_{w})$

end if

if  _$\min(\bm{h}_{w})\geq 0$ and $\min(\bm{h}_{r})<0$_ then

$n_{c}=\mathrm{length}(\bm{h}_{r})$

for  _$k=1:n_{c}$_ do

if  _$h_{r,i} <0$_ then

$\bm{C}_{r}=[\bm{C}_{r};\bm{J}_{r}(k,:)]$

end if

end for

$\bm{N}_{r}=\mathrm{null}(\bm{C}_{r})$

$[\sim,n]=\mathrm{size}(\bm{N}_{r})$

$\bm{v}_{t}=\bm{0}$

for  _$k=1:n$_ do

$\bm{n}_{k}=\bm{N}_{r}(:,k)/|\bm{N}_{r}(:,k)|$

$\bm{v}_{t}=\bm{v}_{t}+\alpha_{t}\,\bm{n}_{k}\,\bm{n}_{k}^{\top}\,(\bm{x}_{r}-\bm{x}_{w})$

end for

end if

if  _$\min(\bm{h}_{w}) <0$ and $\min(\bm{h}_{r})<0$_ then

$k_{min}=\min\limits_{k}\bm{h}_{w}$ (index of the smallest $\bm{h}_{w}$)

$\bm{r}_{k}=\bm{J}_{r}(k_{min},:)/|\bm{J}_{r}(k_{min},:)|$

if  _$\bm{h}_{r}(k_{min})\geq\bm{h}_{w}(k_{min})$_ then

$\bm{v}_{n}=\alpha_{n}\,\bm{r}_{k}\,r_{k}^{\top}\,(\bm{x}_{r}-\bm{x}_{w})$

else

$\bm{v}_{n}=-\alpha_{n}\,\bm{r}_{k}\,r_{k}^{\top}\,(\bm{x}_{r}-\bm{x}_{w})$

end if

end if

$\dot{\bm{x}}_{w}=\bm{v}_{r}+\bm{v}_{t}+\bm{v}_{n}$

$\bm{x}_{w}=\bm{x}_{w}+\Delta t\,\dot{\bm{x}}_{w}$

Algorithm 1 ERG algorithm

The ERG algorithm works by manipulating the controller state reference values
such that they are as close as possible to the desired reference trajectory
while obeying a set of constraints [22, 23]. The work done in [23] uses a
bounded Lyapunov function to show stability and how the constraints are always
satisfied by manipulating the reference such that the resulting Lyapunov
function is always contained within this boundary. Our version of ERG does not
use a Lyapunov function in the manipulated reference update law. Instead, we
use a simple heuristic approach where we manipulated the state reference by
only using the constraint equation and the system dynamics.

We assume that the system is controllable and we can track the state reference
$\bm{x}_{r}$. In this ERG formulation, we consider the constraint equations
derived in the following form

$\begin{gathered}\bm{h}_{r}(\bm{x},\bm{x}_{r})=\bm{J}_{r}(\bm{x})\,\bm{x}_{r}+\bm{d}_{r}(\bm{x})\geq
0,\end{gathered}$ (13)

which is affine in $\bm{x}_{r}$. However, some constraints (e.g. ground
friction constraints) can’t be derived in this form due to the nonlinear
nature of the system dynamics. Therefore, an approximation of the constraint
equations using Taylor series expansion about $\bm{x}_{r}$ can be utilized as
follows

$\begin{gathered}\bm{J}_{r}=\left.\left(\tfrac{\partial\bm{h}_{r}}{\partial\bm{x}_{r}}\right)\right|_{\bm{x}_{r}=\bm{x}_{r0}},\qquad\bm{d}_{r}=\bm{h}_{r}-\bm{J}_{r}\,\bm{x}_{r0},\end{gathered}$
(14)

where $\bm{x}_{r0}$ is the current reference value. Since the Jacobian
$\bm{J}_{r}$ forms the rowspace of $\bm{h}_{r}$ with respect to $\bm{x}_{r}$,
any adjustment in $\bm{x}_{r}$ done about the nullspace of $\bm{J}_{r}$ does
not affect $\bm{h}_{r}$ which will be utilized in the ERG algorithm to allow
partial tracking of $\bm{x}_{r}$ when the constraint $\bm{h}_{r}$ is violated.

The ERG algorithm can be represented using the applied reference $\bm{x}_{w}$
which is used in the controller instead of $\bm{x}_{r}$. The algorithm
determines the rate of change of $\bm{x}_{w}$ such that it’s as close as
possible to $\bm{x}_{r}$ while obeying the specified constraints
$\bm{h}_{w}=\bm{h}_{r}(\bm{x},\bm{x}_{w})\geq 0$. Assume that the controller
can perfectly track the applied reference $\bm{x}_{w}$, i.e.
$\bm{x}=\bm{x}_{w}$, then the ERG algorithm can be formulated using the
Lyapunov function

$\begin{gathered}V=(\bm{x}_{r}-\bm{x}_{w})^{\top}\,\bm{P}\,(\bm{x}_{r}-\bm{x}_{w}),\end{gathered}$
(15)

where $\bm{P}>0$ is diagonal, and by assuming that $\dot{\bm{x}}_{r}=0$ then
$\dot{V}=2(\bm{x}_{r}-\bm{x}_{w})^{\top}\,\bm{P}\,(-\dot{\bm{x}}_{w})$. Then
we can select $\dot{\bm{x}}_{w}$ such that $\dot{V}=0$ at the minimum level
set of $V$ that fulfills the constraint $\bm{h}_{w}\geq 0$ (defined as
$\bm{x}_{w,t}$), and $\dot{V}<0$ if $\min(\bm{h}_{w})\geq 0$ and
$\bm{x}_{w}\neq\bm{x}_{w,t}$. Here, $\bm{x}_{w,t}$ is the closest reference to
$\bm{x}_{r}$ that satisfy the constraint $\bm{h}_{w}\geq 0$, as illustrated in
Fig. 4.

Consider the following update law as illustrated in Fig. 4 and outlined in
Algorithm 1

$\begin{gathered}\dot{\bm{x}}_{w}=\bm{v}_{r}+\bm{v}_{t}+\bm{v}_{n}.\end{gathered}$
(16)

$\bm{v}_{r}$ represents the rate convergence of $\bm{x}_{w}$ directly to
$\bm{x}_{r}$ defined as follows

$\begin{gathered}\bm{v}_{r}=\hat{\alpha}_{r}\,(\bm{x}_{r}-\bm{x}_{w}),\\\
\hat{\alpha}_{r}=\begin{cases}\alpha_{r},&\text{if }\min(\bm{h}_{w})\geq
0\text{ or }\min(\bm{h}_{r})\geq 0\\\ 0,&\text{else}\\\
\end{cases}\end{gathered}$ (17)

where $\alpha_{r}>0$. $\bm{v}_{r}$ is zero if both the applied and target
reference violate the constraints. $\bm{v}_{t}$ represents the rate
convergence along the nullspace of $\bm{J}_{r}$ which allows $\bm{x}_{w}$ to
partially track $\bm{x}_{r}$ because the update about the nullspace does not
locally change the value of the constraint equations. Let $\bm{C}_{r}$ be the
rowspace of the violated constraints of $\bm{h}_{r}$, and
$\bm{N}_{r}=\mathrm{null}(\bm{C}_{r})=[\bm{n}_{1},\dots,\bm{n}_{n}]$ where $n$
is the size of the nullspace. Let $\bm{v}_{t}$ updates $\dot{\bm{x}_{w}}$ in
the directions of the nullspace as follows

$\begin{gathered}\bm{v}_{t}=\textstyle\sum^{n}_{k=1}\hat{\alpha}_{t}\,\bm{n}_{k}\,\bm{n}_{k}^{\top}(\bm{x}_{r}-\bm{x}_{w}),\\\
\hat{\alpha}_{t}=\begin{cases}\alpha_{t},&\text{if }\min(\bm{h}_{w})\geq
0\text{ or }\min(\bm{h}_{r})<0\\\ 0,&\text{else}\\\ \end{cases}\end{gathered}$
(18)

where $\alpha_{t}>0$. This update represents the sum of the projections of
$(\bm{x}_{r}-\bm{x}_{w})$ into $\bm{n}_{k}$. Finally, when the constraints for
both $\bm{h}_{w}$ and $\bm{h}_{r}$ are violated, which might happen if there
is a sudden change in parameters (e.g. change in center of pressure $\bm{u}$),
to allow $\bm{x}_{w}$ to shift towards the positive constraint values. Let $k$
be the index of the smallest element of $\bm{h}_{w}$, and let $\bm{r}_{k}$ be
the $k$’th row of $\bm{J}_{r}$. Then the update towards positive constraint
can be derived as follows

$\begin{gathered}\bm{v}_{n}=\hat{\alpha}_{n}\,\bm{r}_{k}\,\bm{r}_{k}^{\top}\,(\bm{x}_{r}-\bm{x}_{w})\\\
\hat{\alpha}_{n}=\begin{cases}\alpha_{n},&\text{if
}\min(\bm{h}_{w})\leq\min(\bm{h}_{r})<0\\\ -\alpha_{n},&\text{if
}\min(\bm{h}_{r})<\min(\bm{h}_{w})<0\\\ 0,&\text{else}\\\
\end{cases}\end{gathered}$ (19)

where $\alpha_{n}>0$.

Using the update law defined from (16) to (19) results in

$\displaystyle\dot{V}$
$\displaystyle=-2(\bm{x}_{r}-\bm{x}_{w})^{\top}\,\bm{Q}\,(\bm{x}_{r}-\bm{x}_{w}),$
(20) $\displaystyle\bm{Q}$
$\displaystyle=\bm{P}(\hat{\alpha}_{r}\,\bm{I}+\textstyle\sum^{n}_{k=1}\hat{\alpha}_{t}\,\bm{n}_{k}\,\bm{n}_{k}^{\top}+\hat{\alpha}_{n}\,\bm{r}_{k}\,\bm{r}_{k}^{\top}).$

$\dot{V}=0$ if $\min(\bm{h}_{w})\leq 0$ and
$\bm{n}_{k}\bot(\bm{x}_{r}-\bm{x}_{w})$, while $\dot{V}<0$ when
$\min(\bm{h}_{r})\geq 0$ or when $\min(\bm{h}_{w})\geq 0$. This allows the
$\bm{x}_{w}$ to converge to $\bm{x}_{w,t}$ which is the minimum energy
solution that satisfies $\bm{h}_{w}\geq 0$ as illustrated in Fig. 4. In case
both applied reference and target constraints equation are violated, we have
$\dot{V}>0$ which drives the $\bm{x}_{w}$ towards positive constraint value,
away from $\bm{x}_{r}$, if $\min(\bm{h}_{r})<\min(\bm{h}_{w})$.

##  IV Simulation Results

Figure 5: The simulation result of applying ERG on the VLIP model. The ERG
manipulated the applied reference trajectory to satisfy the constraints, which
can be seen more clearly in the pendulum angle and length around the 0.5 s
simulation time. Figure 6: The simulated GRF in the VLIP model where the no-
slip constraints have been successfully satisfied. These forces are the
estimated GRF using the model shown in (9). Also, illustrates the difference
between the GRF using target versus manipulated references. Figure 7:
Illustrates the simulated constraints when the applied and target references
are used in the VLIP model. When the target references are used instead of the
manipulated trajectories, almost all constraints are violated.

This section outlines the simulation setup and results of implementing the ERG
in the VLIP model and the 3D Harpy model. The simulation using the VLIP model
is done to show that the ERG is capable of manipulating the reference to
enforce the specified constraints, which is then will be utilized in the 3D
Harpy model.

###  IV-A VLIP Model

The ROM defined in (5) can be represented by the states
$\bm{q}_{vlip}=[\theta,\phi,l]^{\top}$ instead of the body CoM position, where
$\theta$ is the pendulum angle from vertical, $\phi$ is the pendulum heading,
and $l$ is the pendulum length. A simulation of this ROM is done where we
applied the ERG algorithm shown in Section III to apply some constraints on
the GRF and state trajectory. The target states references are defined as
follows:

$\bm{q}_{vlip}(t)=\begin{bmatrix}0.45+0.45\sin(\pi t-\pi)\\\ -1.5\sin(\pi
t-\pi)\\\ 0.4+0.1\cos(\pi t-\pi)\end{bmatrix},$ (21)

and $\dot{\bm{q}}_{vlip}=0$. The following constraints are enforced:

$\displaystyle\mu_{s}u_{g,z}-|u_{g,x}|$ $\displaystyle\geq 0,\qquad$
$\displaystyle u_{g,z}-20$ $\displaystyle\geq 0$ (22)
$\displaystyle\mu_{s}u_{g,z}-|u_{g,y}|$ $\displaystyle\geq 0,$
$\displaystyle\theta-5^{\circ}$ $\displaystyle\geq 0,$

where $\mu_{s}=0.45$ and $\bm{u}_{g}$ is defined in (9) and can be derived as
a function of state reference using the control law in (10). The ERG is
implemented in the controller (10) by using the applied reference $\bm{x}_{w}$
instead of $\bm{x}_{r}$, where the ERG will drive it to be as close as
$\bm{x}_{r}$ as possible while satisfying the constraints in (22). The
simulation was run using the controller gains $k_{p}=660$ and $k_{d}=60$ for
all the P and D gains respectively. Additionally, we initialized the
simulation with $\bm{x}_{w}=\bm{x}_{r}$ and used the following ERG update
rates: $\alpha_{r}=1$, $\alpha_{t}=5$, and $\alpha_{n}=2$.

Figures 5 to 7 show the simulation result of the ERG application to the VLIP
model. Figure 5 shows that the applied reference is significantly different
than the target reference at around $t=0.5$ s, which is done to avoid
constraint violation. Figures 6 and 7 show the comparison of the GRF and
constraint equations between using the manipulated vs target references. The
simulation result shows that most of the constraints are violated when using
target reference while the manipulated reference keeps the constraint equation
values above zero. There is a slight constraint violation near $t=1.4$ s using
the applied reference in Fig. 7, which is quickly pushed into the specified
threshold value by the $\bm{v}_{n}$ update law in (16). This indicates that
the ERG has successfully tracked the target reference (21) as closely as
possible while satisfying the constraint equations (22).

###  IV-B Full-Dynamics of Harpy

Figure 8: The evolution of the 3D-model states with the target and applied
references. Figure 9: Illustrates the GRF in the 3D model after applying ERG
which also shows the satisfaction of the no-slip constraints. Figure 10:
Illustrates the evolution of the constraints when applied ($\bm{x}_{w}$) and
target ($\bm{x}_{r}$) references are employed. Note that when the target
trajectories are employed the normal force constraints $u_{g,z}$ are violated.

We must first find a stable walking gait for the robot in order to simulate
the 3D Harpy model. This gait is found from a simulation where the frontal
dynamics is ignored using an optimization technique and simple 4th order
Bezier foot-end trajectories with a gait period of 0.75 s. This gait is not
stable when implemented in the full 3D model, so the appropriate thruster
forces defined in (12) are applied to stabilize the gait’s frontal dynamics
which allows the robot to walk stably using the 2D gait. Additionally, the
controller for the 3D model can be calculated by using the ROM and ERG to
satisfy the ground friction constraints to prevent slips. Currently $u_{r}$ is
not used in the full model due to the potential clash with the foot end
trajectories designed from this optimization. In exchange, we set $\bm{Y}=0$
in (10) to allow tracking about the pendulum’s radial axis using the
thrusters.

The ERG is implemented by estimating the GRF using the ROM in (7) as the robot
walks. The same GRF constraints as in (22) are used in this simulation (sans
the angle constraint), which can be derived using the reduced order states
$\bm{x}=[\bm{c};\dot{\bm{c}}]$, the reference states
$\bm{x}_{r}=[\bm{c}_{t};\dot{\bm{c}}_{t}]$, and the center of pressure
$\bm{u}$. The ground friction parameters used in the simulation are
$\mu_{s}=0.25$ and $\mu_{c}=0.225$ which makes the robot very prone to
slipping. The target trajectory for this robot is simply a constant forward
speed of 0.3 m/s, a sinusoidal lateral position with amplitude of 0.025 m and
period of 1.5 s, and a constant height of 0.6 m. The controller proportional
and derivative gains are set to be 400 and 40 respectively, and the following
ERG convergence rates are used: $\alpha_{r}=10$, $\alpha_{t}=15$, and
$\alpha_{r}=20$.

The simulation results can be seen in Fig. 8 which shows the target state
references $\bm{x}_{r}$, applied references $\bm{x}_{w}$, and the body center
of mass position states $\bm{x}$. The difference between $\bm{x}_{w}$ and
$\bm{x}_{r}$ indicates that the ERG has modified $\bm{x}_{w}$ such that the
resulting closed loop GRF followed the specified constraints. Figures 9 and 10
show the ground forces and the constraints equations respectively. As shown in
Fig. 9, the robot avoids slipping by having containing the ground friction
forces within the upper and lower bounds defined by the constraint equations
$|u_{g,x}|\leq\mu_{s}u_{g,z}$ and $|u_{g,y}|\leq\mu_{s}u_{g,z}$. The
constraint equations of both the applied reference and target reference
($\bm{h}_{w}$ and $\bm{h}_{r}$) indicates that the normal force constraint is
violated frequently. The applied reference used seems to have successfully
pushed the constraint equation back to positive region as it drops into the
negative region. However, there is a significant chattering which is very
likely caused by the non-smooth transition between the negative and positive
$\bm{h}_{w}$.

##  V Concluding Remarks and Future Works

The enforcement of the contact force constraints using Reference Governors
(RGs) has been successfully demonstrated. To do this, we employed the
thruster-assisted model of our bipedal robot call Harpy. This robot is under
development at Northeastern University. We demonstrated that an RG can
manipulate the joint trajectories when using pre-defined gait parameters would
lead to the violation of the constraints. For this purpose, we proposed an
algorithm. This algorithm has minimum computational overhead and can
potentially be used as an alternative to the computationally expensive
optimization-based schemes.

The application of thrusters in our model, which allowed us to have full
control over the unilateral contact forces, can lead to interesting path
planning and trajectory generation problems. These problems will be a major
part of our future research works.

## References

  * [1] M. H. Raibert, H. B. Brown Jr, and M. Chepponis, “Experiments in balance with a 3d one-legged hopping machine,” _The International Journal of Robotics Research_ , vol. 3, no. 2, pp. 75–92, 1984.
  * [2] M. Raibert, K. Blankespoor, G. Nelson, and R. Playter, “Bigdog, the rough-terrain quadruped robot,” _IFAC Proceedings Volumes_ , vol. 41, no. 2, pp. 10 822–10 825, 2008.
  * [3] Y. Gong, R. Hartley, X. Da, A. Hereid, O. Harib, J.-K. Huang, and J. Grizzle, “Feedback control of a cassie bipedal robot: Walking, standing, and riding a segway,” in _American Control Conference (ACC)_. IEEE, 2019, pp. 4559–4566.
  * [4] M. Hirose and K. Ogawa, “Honda humanoid robots development,” _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , vol. 365, no. 1850, pp. 11–19, 2006.
  * [5] W. Kwon _et al._ , “Biped humanoid robot mahru iii,” in _IEEE-RAS International Conference on Humanoid Robots_. IEEE, 2007, pp. 583–588.
  * [6] J. E. Pratt _et al._ , “The yobotics-ihmc lower body humanoid robot,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 10 2009, pp. 410–411.
  * [7] P. Dangol, A. Ramezani, and N. Jalili, “Performance satisfaction in midget, a thruster-assisted bipedal robot,” in _American Control Conference (ACC)_. IEEE, 2020, pp. 3217–3223.
  * [8] A. C. de Oliveira and A. Ramezani, “Thruster-assisted center manifold shaping in bipedal legged locomotion,” _International Conference on Advanced Intelligent Mechatronics (AIM)_ , 2020.
  * [9] P. Dangol and A. Ramezani, “Towards thruster-assisted bipedal locomotion for enhanced efficiency and robustness,” _International Federation of Automatic Control (IFAC)_ , 2020.
  * [10] P. Dangol and A. Ramezani, “Feedback design for harpy: a test bed to inspect thruster-assisted legged locomotion,” in _Unmanned Systems Technology XXII_. SPIE, 2020.
  * [11] K. Liang, E. Sihite, P. Dangol, A. Lessieur, and A. Ramezani, “Rough-terrain locomotion and unilateral contact force regulations with a multi-modal legged robot,” _American Control Conference (ACC)_ , 2021.
  * [12] A. Hereid, E. A. Cousineau, C. M. Hubicki, and A. D. Ames, “3d dynamic walking with underactuated humanoid robots: A direct collocation framework for optimizing hybrid zero dynamics,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2016, pp. 1447–1454.
  * [13] L. Sentis and O. Khatib, “A whole-body control framework for humanoids operating in human environments,” in _IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2006, pp. 2641–2648.
  * [14] K. Galloway, K. Sreenath, A. D. Ames, and J. W. Grizzle, “Torque saturation in bipedal robotic walking through control lyapunov function-based quadratic programs,” _IEEE Access_ , vol. 3, pp. 323–332, 03 2015.
  * [15] H. Dai and R. Tedrake, “Planning robust walking motion on uneven terrain via convex optimization,” in _IEEE-RAS International Conference on Humanoid Robots (Humanoids)_ , 11 2016, pp. 579–586.
  * [16] S. Feng, E. Whitman, X. Xinjilefu, and C. G. Atkeson, “Optimization based full body control for the atlas robot,” in _IEEE-RAS International Conference on Humanoid Robots_ , 11 2014, pp. 120–127.
  * [17] E. D. Sontag, “A lyapunov-like characterization of asymptotic controllability,” _SIAM journal on control and optimization_ , vol. 21, no. 3, pp. 462–471, 1983.
  * [18] P. V. Kokotovic, M. Krstic, and I. Kanellakopoulos, “Backstepping to passivity: recursive design of adaptive systems,” in _IEEE Conference on Decision and Control_ , vol. 4, 12 1992, pp. 3276–3280.
  * [19] S. P. Bhat and D. S. Bernstein, “Continuous finite-time stabilization of the translational and rotational double integrators,” _IEEE Transactions on Automatic Control_ , vol. 43, no. 5, pp. 678–682, 05 1998.
  * [20] E. G. Gilbert, I. Kolmanovsky, and Kok Tin Tan, “Nonlinear control of discrete-time linear systems with state and control constraints: a reference governor with global convergence properties,” in _IEEE Conference on Decision and Control_ , vol. 1, 12 1994, pp. 144–149.
  * [21] A. Bemporad, “Reference governor for constrained nonlinear systems,” _IEEE Transactions on Automatic Control_ , vol. 43, no. 3, pp. 415–419, 1998\.
  * [22] E. Gilbert and I. Kolmanovsky, “Nonlinear tracking control in the presence of state and control constraints: a generalized reference governor,” _Automatica_ , vol. 38, no. 12, pp. 2063–2073, 2002.
  * [23] E. Garone and M. M. Nicotra, “Explicit reference governor for constrained nonlinear systems,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 5, pp. 1379–1384, 2015.