# First-order mean-field games on networks and Wardrop equilibrium

Fatimah Al Saleh , Tigran Bakaryan , Diogo A. Gomes , and Ricardo Ribeiro
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>, Email:
<EMAIL_ADDRESS>, Email<EMAIL_ADDRESS>, Email:
<EMAIL_ADDRESS>
###### Abstract

Here, we examine the Wardrop equilibrium model on networks with flow-dependent
costs and its connection with stationary mean-field games (MFG). In the first
part of this paper, we present the Wardrop and the first-order MFG models on
networks. Then, we show how to reformulate the MFG problem into a Wardrop
problem and prove that the MFG solution is the Wardrop equilibrium for the
corresponding Wardrop problem. Moreover, we prove that the solution of the MFG
problem can be recovered using the solution to the associated Wardrop problem.
Finally, we study the cost properties and the calibration of MFG with Wardrop
travel cost problems. We describe a novel approach to the calibration of MFGs.
Further, we show that even simple travel costs can give rise to non-monotone
MFGs.

##  1 Introduction

Models for flows on networks arise in the study of traffic and pedestrian
crowds. These models encode congestion effects, the behavior and preferences
of agents, such as aversion to crowds and their attempts to minimize travel
time. A well-studied stationary model is the Wardrop model introduced in
[War52]. In this model, the cost of crossing a network edge depends on the
agents’ flow in that edge. Agents minimize their costs by taking into account
that flow. Multiple authors have studied Wardrop equilibria; see, for example,
the survey [CSM11]. In the context of optimal transport, Wardrop equilibrium
was addressed in [CS11] and [CJS08]. The Wardrop model was initially
formulated on a directed network. However, in problems such as pedestrian
networks, the network is a priori undirected. Accordingly, the Wardrop model
is not directly applicable. Further, the Wardrop model looks at a single edge
as an aggregate entity. Thus, it does not describe the microstructure in the
edge. Hence, in [GMAS19] authors introduced a mean-field game (MFG) model on
undirected networks that attempts to model and address these matters.

MFG theory was introduced in [LL06, HMC06] to describe the dynamics of systems
with a large number of rational agents. In these models, agents seek to
optimize an individual functional that depends on both their actions and the
distribution of the other agents. A MFG model is determined by a backward-in-
time Hamilton-Jacobi equation (HJ) coupled with a forward-in-time Fokker-
Planck (FP) or transport equation. The HJ equation describes the optimal
behavior of an agent; the FP equation governs the distribution of the agents.
MFG models have been used to address pedestrian flows [BDFMW14], crowds
[LW11], population dynamics [BMP11], building evacuation problems [DTT17], and
in the study of traffic flows [BZP14].

Recently, there has been a broad interest in studying nonlinear PDEs on
networks due to their applications in traffic and pedestrian dynamics. Various
notions of viscosity solutions to HJ equations on networks were studied in
[ACCT13, SC13, IMZ13]. Later in [CM13], the authors proved the equivalency of
the viscosity solutions of HJ equations on networks. The existence and
uniqueness of viscosity solutions to Eikonal equations on networks are
addressed in [CMS13]. More recently, progress on junction problems has been
obtained in [LS16, LS17]. Stationary HJ equations on networks were considered
in [SS18] and [ISM17]. Concerning transport phenomena on networks, the survey
paper [BD11] examines a substantial number of results. More recent works in
this direction include [GHP16, CDMT17].

Several authors in the MFG community examined MFGs on networks, in particular
for second-order problems. For example, stationary second-order MFGs were
studied in [CCM17, CM16, ADLT19]. The time-dependent case was studied in
[CCM15, ADLT20]. However, prior methods for MFGs on networks are not valid for
first-order MFGs, where a distinct set of phenomena occurs that includes the
loss of smoothness for Hamilton-Jacobi (HJ) equations and lack of continuity
for the value function at the vertices. First-order MFGs on networks were
considered in [BM], [BFMP19], [BMP21] and [BB12], in particular in the context
of optimal visiting problems where agents have multiple targets. The methods
in those papers, because are applied to general time-dependent problems are
quite different from ours, where we take full advantage of the stationary
nature of the game. Recently, in [AMMT] time-dependent MFGs on networks were
examined in the light of weak solutions. First-order deterministic MFGs with
control on the acceleration were studied in [AMMT20]. As far as the authors
are aware, there is no systematic approach for solving stationary first-order
MFGs on networks, despite their relevance in applications that cannot be
modeled by second-order MFGs, such as vehicular networks or dense crowds.

The relation between Wardrop equilibrium and MFGs on networks was first
observed in [GMAS19]. However, the precise correspondence between these two
models was not established there. Here, we address this problem; that is, how
to convert a MFG on a network into a standard Wardrop problem and further use
the solution of the corresponding Wardrop problem to solve the original MFG.

As we mentioned before, the standard Wardrop equilibrium is formulated on a
directed network. In this paper, we consider a Wardrop model, where agents
enter through a finite set of vertices with a prescribed current intensity and
leave through a set of exit vertices where they pay an exit cost. Although our
MFG model is defined on undirected networks, the preceding problem is closely
related to a MFG model on networks. In our MFG model, the entry currents and
the exit costs are given, but the current direction in each edge is not
prescribed a priori. We discuss an explicit way to transform one problem into
the other.

In Section 2, we begin by outlining the main definitions and results about
Wardrop equilibria. We define the stationary Wardrop model on a directed
network, with flow-dependent travel costs on the edges. Furthermore, we prove
the uniqueness of the Wardrop equilibrium (see Theorem 2.8). Next, we describe
our MFG model on networks. We start by considering a MFG model on a single
edge and recalling the current method introduced in [GNP17, GNP16] (see
Section 3). First, we define a current dependent cost (see Definition 3.2) on
the edge for the MFG model. Then, we establish the connection between the cost
and the solution to the MFG system (see, for instance, (1.1)). In Section 4,
we continue our discussion about MFG models on networks. In each edge $e_{k}$,
our model is given by a one-dimensional, stationary, first-order MFG system

$\displaystyle\begin{cases}H_{k}(x,u_{x}(x),m(x))=0\\\
(-m(x)D_{p}H_{k}(x,u_{x}(x),m(x))_{x}=0\end{cases}$ (1.1)

together with boundary conditions at the vertices. Here, $u$ is the value
function for an agent and $m$ is the probability density of agents. The first
equation in (1.1) is the Hamilton-Jacobi (HJ) equation and the second equation
is the Fokker-Planck (FP) or transport equation.

The first main contribution of this paper is the reformulation of the MFG
problem into a Wardrop problem and the development of a method to recover the
MFG solution from the solution to the corresponding Wardrop model. In Section
5, we start with the undirected network of the MFG model and build a new
directed network on which we define a corresponding Wardrop problem. Then, we
prove that the solution of the MFG model is the Wardrop equilibrium (see
Theorem 5.3). Moreover, Proposition 5.4 proves that the associated Wardrop
problem has a unique solution. This result gives the uniqueness of the
solution to the original MFG problem (see Proposition 5.7). To complete the
correspondence between MFG and Wardrop models, in Section 6, we show how to
recover the solution to the MFG problem from the associated Wardrop
equilibrium (see Theorem 6.7).

In MFG models, the cost in an edge can change from point to point. In
contrast, in the Wardrop model, the cost is a function of the edges; each edge
is treated as a homogeneous entity. Thus, the conversion between MFG and
Wardrop models averages the microscopic effects in the MFG into a macroscopic
cost that determines the Wardrop. Section 7 comprises the second main result
of the paper. There, we study how the microscopic properties of the MFG
encoded in the Hamiltonian translate into macroscopic properties of the
corresponding Wardrop model. Moreover, we explore a class of Hamiltonians for
which the associated cost function satisfies the assumptions required for the
unique correspondence between MFG and Wardrop models (see the assumptions of
Proposition 5.4).

In a Wardrop equilibrium, the cost incurred by an agent on an edge is the
travel time. This time depends on the flow of agents and, thus, can be
measured experimentally. Therefore, in principle, these models are simple to
calibrate: it is enough to have data on the flow rates and corresponding
velocities. This calibration problem is more delicate for MFG models.
Therefore, in Section 8, we show how to calibrate a MFG model on a single edge
using the notions and results of the previous sections. The problem is the
following.

###### Problem 1.

Consider the cost $c$ for an agent to cross an edge. Suppose $c$ is given as a
function of the current and the direction of travel. Find a MFG model whose
cost coincides with $c$.

Note that the cost, $c$, may not be the travel time, and as far as the authors
know, before this work, there was no systematic approach to solving Problem 1.
We rigorously state the preceding problem in Section 8 and solve it. In
particular, we show how non-monotone MFG models arise as solutions to Problem
1 for natural costs. Hence, non-monotone MFG models may be needed to model
general traffic problems. In non-monotone MFG, agents act as if they want to
be in congested areas, which is surprising from a modeling point of view.
These non-monotone problems are not well studied, and further research should
be pursued. The present work suggests several future directions. For example,
the study of non-monotone MFGs and their general properties and the extension
of our models to the dynamic setting. The lack of monotonicity for these MFG
models makes it possible that new phenomena arise, such as multiple equilibria
or instability. We believe these to be relevant questions for further
research.

##  2 Wardrop equilibrium model on networks

We consider a steady-state model of agents traveling through a network with
flow-dependent travel costs on the edges. Following the presentation of the
model’s elements, we discuss an equilibrium concept due to Wardrop [War52].
Later, in Section 5, we show how this concept is related to the MFG model
presented in Section 4. This model consists of the following:

  1. 1.

A finite directed network (graph), $\tilde{\Gamma}=(\tilde{E},\tilde{V})$,
where $\tilde{E}=\\{\tilde{e}_{k}:k\in\\{1,2,\dots,\tilde{n}\\}\\}$ is the set
of edges and $\tilde{V}=\\{\tilde{v}_{i}:i\in\\{1,2,\dots,\tilde{m}\\}\\}$ is
the set of vertices. To any edge $\tilde{e}_{k}$, we associate the pair
$(\tilde{v}_{r},\tilde{v}_{i})$ of its endpoints, which may be identified with
$\tilde{e}_{k}$ if there is no ambiguity.

  2. 2.

The _current_ or the flow is the number of agents crossing a given point per
unit of time. The current in the edge $\tilde{e}_{k}$ is denoted by
$\tilde{\jmath}_{k}$.

The current on the network is the $\tilde{n}$-dimensional vector
$\bm{\tilde{\jmath}}=(\tilde{\jmath}_{1},\dots,\tilde{\jmath}_{{\tilde{n}}})$.

  3. 3.

The _travel cost_ in each edge $\tilde{e}_{k}$ is given by a function
${\tilde{c}}_{k}:\tilde{E}\rightarrow\mathbb{R}$. The cost is local if
${\tilde{c}}_{k}$ depends only on $\tilde{\jmath}_{k}$.

We denote the vector of the costs in the edges by
$\bm{\tilde{c}}(\bm{\tilde{\jmath}})=(\tilde{c}_{1}(\bm{\tilde{\jmath}}),\dots,\tilde{c}_{\tilde{n}}(\bm{\tilde{\jmath}}))$.
Observe that
$\langle\bm{\tilde{c}}(\bm{\jmath}),\bm{\jmath}\rangle:=\sum_{k=1}^{\tilde{n}}\tilde{c}_{k}(\bm{\jmath})j_{k}$
is the social cost per unit of time corresponding to the distribution of
currents $\bm{\jmath}$.

  4. 4.

Agents enter the network through $\tilde{\lambda}$ entrance vertices and exit
it through $\tilde{\mu}$ exit vertices (disjoint from the entrance vertices).
For convenience, we assume that the last $\tilde{\mu}$ vertices in $\tilde{V}$
are the exit vertices. Furthermore, we suppose that entrance and exit vertices
have incidence $1$. As discussed in the remark below, this assumption entails
no loss of generality.

###### Remark 2.1.

Suppose a vertex with an incidence of more than $1$ is labeled as an entrance.
In that case, we attach an auxiliary entrance edge to it, relabeling its extra
vertex as the new entrance vertex. Similarly, relabeling is done for an exit
vertex by adding an auxiliary exit edge.

  5. 5.

A flow of agents, the entry current
$\tilde{\bm{\iota}}=(\tilde{{\iota}}_{1},\dots,\tilde{{\iota}}_{\tilde{\lambda}})>0$,
is prescribed at the entrance vertices. The entry currents in the other
vertices are zero. This information is encoded in a
$(\tilde{m}-\tilde{\mu})$-dimensional vector $\tilde{B}$. Each component of
$\tilde{B}$ corresponds to a non-exit vertex.

  6. 6.

At the $\tilde{\mu}$ exit vertices, agents pay an exit cost
$\tilde{\bm{\phi}}$. Here, we assume that this exit cost vanishes. As the
following remark explains, this assumption entails no loss of generality.

###### Remark 2.2.

If the exit cost at an exit vertex is nonzero, we attach an auxiliary exit
edge to it, relabeling its extra vertex as the new exit vertex. In the
auxiliary exit edge, the travel cost is the exit cost, and at the new exit
vertex, the exit cost is zero.

Let $\tilde{K}$ be the $(\tilde{m}-\tilde{\mu})\times\tilde{n}$ Kirchhoff
matrix, obtained by removing $\tilde{\mu}$ lines corresponding to the exit
vertices of $\tilde{\Gamma}$ from the _incidence matrix_ of $\tilde{\Gamma}$,
i.e.,

$\tilde{K}_{ik}=\begin{cases}1\ \ \text{if}\
\tilde{e}_{k}=(\tilde{v}_{i},\tilde{v}_{r})\\\ -1\ \ \text{if}\
\tilde{e}_{k}=(\tilde{v}_{r},\tilde{v}_{i})\\\ 0\ \ \text{if}\
\tilde{v}_{i}\not\in\tilde{e}_{k},\end{cases}$ (2.1)

where $i\in\\{1,2,\dots,\tilde{m}-\tilde{\mu}\\}$ and
$k\in\\{1,2,\dots,\tilde{n}\\}$. The rows in $\tilde{K}$ correspond to non-
exit vertices of the network, and the columns correspond to the edges.

###### Definition 2.3.

A distribution of currents, ${\bm{\tilde{\jmath}}}\geqslant 0$, is
_admissible_ if

$\tilde{K}\bm{\tilde{\jmath}}=\tilde{B}.$ (2.2)

The set of all admissible distributions of currents is denoted by
$\mathcal{A}$.

###### Remark 2.4.

The $\tilde{m}-\tilde{\mu}$ equations in (2.2) correspond to Kirchhoff’s law
for the non-exit vertices.

Next, following Smith ([Smi79]), we define the Wardrop equilibrium.

###### Definition 2.5.

A distribution of currents ${\bm{\tilde{\jmath}}}^{*}\in\mathcal{A}$ is a
_Wardrop equilibrium_ if, for all $\bm{\tilde{\jmath}}\in\mathcal{A}$,

$\langle\bm{\tilde{c}}({\bm{\tilde{\jmath}}}^{*}),{\bm{\tilde{\jmath}}}^{*}-\bm{\tilde{\jmath}}\rangle\leqslant
0.$ (2.3)

In Section 6, we prove that Definition 2.5 means that in a Wardrop
equilibrium, any current-carrying path is optimal because it minimizes the
travel cost to an exit.

We use the notion of monotonicity, defined below, to state and prove a result
on the uniqueness of Wardrop equilibria.

###### Definition 2.6.

A cost $\bm{\tilde{c}}$ is _monotone_ if, for any
$\bm{\tilde{\jmath}_{1}},\bm{\tilde{\jmath}_{2}}\in\mathcal{A}$,

$\langle\bm{\tilde{c}}(\bm{\tilde{\jmath}_{1}})-\bm{\tilde{c}}(\bm{\tilde{\jmath}_{2}}),\bm{\tilde{\jmath}_{1}}-\bm{\tilde{\jmath}_{2}}\rangle\geqslant
0.$ (2.4)

If $\bm{\tilde{\jmath}_{1}}\neq\bm{\tilde{\jmath}_{2}}$, the inequality in
(2.4) is strict; in that case, we say that $\bm{\tilde{c}}$ is _strictly
monotone_.

###### Example 2.7.

If $\tilde{c}_{k}$ depends only on $\tilde{\jmath}_{k}$ and is an increasing
function, then $\bm{\tilde{c}}$ is monotone.

Strict monotonicity of the cost is sufficient for uniqueness.

###### Theorem 2.8 (Uniqueness of Wardrop equilibrium).

Suppose the cost $\bm{\tilde{c}}$ is strictly monotone on $\mathcal{A}$. Then,
there is at most one Wardrop equilibrium.

###### Proof.

Suppose ${\bm{\tilde{\jmath}_{1}}}$ and ${\bm{\tilde{\jmath}_{2}}}$ are
Wardrop equilibria. Then, for any $\bm{\tilde{\jmath}}\in\mathcal{A}$, we have

$\langle\bm{\tilde{c}}({\bm{\tilde{\jmath}_{1}}}),{\bm{\tilde{\jmath}_{1}}}-\bm{\tilde{\jmath}}\rangle\leqslant
0\ \text{and}\
\langle\bm{\tilde{c}}({\bm{\tilde{\jmath}_{2}}}),{\bm{\tilde{\jmath}_{2}}}-\bm{\tilde{\jmath}}\rangle\leqslant
0.$ (2.5)

Accordingly,

$\langle\bm{\tilde{c}}({\bm{\tilde{\jmath}_{1}}})-\bm{\tilde{c}}({\bm{\tilde{\jmath}_{2}}}),{\bm{\tilde{\jmath}_{1}}}-{\bm{\tilde{\jmath}_{2}}}\rangle\leqslant
0,$

and because $\bm{\tilde{c}}$ is strictly monotone,
${\bm{\tilde{\jmath}_{1}}}={\bm{\tilde{\jmath}_{2}}}$. ∎

Next, we discuss a necessary condition for the existence of a Wardrop
equilibrium.

###### Definition 2.9.

A current distribution $\bm{\tilde{\jmath}_{0}}\geqslant 0$ on
$\tilde{\Gamma}$ is a _current loop_ if it is a nontrivial solution of
$\tilde{K}\bm{\tilde{\jmath}_{0}}=0$.

###### Proposition 2.10.

If $\bm{\tilde{\jmath}^{*}}$ is a Wardrop equilibrium, then

$\langle\bm{\tilde{c}}(\bm{\tilde{\jmath}^{*}}),\bm{\tilde{\jmath}_{0}}\rangle\geqslant
0,$

for any current loop, $\bm{\tilde{\jmath}_{0}}$.

###### Proof.

Let $\bm{\tilde{\jmath}^{*}}$ be a Wardrop equilibrium and let
$\bm{\tilde{\jmath}_{0}}$ be a current loop. Set

$\bm{\tilde{\jmath}}(\varepsilon)=\bm{\tilde{\jmath}^{*}}+\varepsilon\bm{\tilde{\jmath}_{0}}.$

Since $\bm{\tilde{\jmath}_{0}}$ is a loop,
$\bm{\tilde{\jmath}}(\varepsilon)\in\mathcal{A}$, for
$\varepsilon\in\mathbb{R}^{+}_{0}$. Condition (2.3), for the particular
$\bm{\tilde{\jmath}}(\varepsilon)$, implies that

$\langle\bm{\tilde{c}}(\bm{\tilde{\jmath}^{*}}),\bm{\tilde{\jmath}^{*}}-(\bm{\tilde{\jmath}^{*}}+\varepsilon\bm{\tilde{\jmath}_{0}})\rangle=-\varepsilon\langle\bm{\tilde{c}}(\bm{\tilde{\jmath}^{*}}),\bm{\tilde{\jmath}_{0}}\rangle\leqslant
0,\ \forall\varepsilon>0.$

Thus,
$\langle\bm{\tilde{c}}(\bm{\tilde{\jmath}^{*}}),\bm{\tilde{\jmath}_{0}}\rangle\geqslant
0.$ ∎

Next, we examine the structure of the Wardrop equilibrium in a specific case
relevant to MFGs. The networks arising in MFGs are undirected. We associate to
these networks a network for which undirected edges correspond to pairs of
directed edges with opposite orientations. Thus, these networks have as a
primary building block the loop network in Figure 1.

Fig. 1: Loop subnetwork.

###### Proposition 2.11.

Consider a network containing the edge
$\tilde{e}_{k}=(\tilde{v}_{r},\tilde{v}_{i})$ and the reverse edge
$\tilde{e}_{l}=(\tilde{v}_{i},\tilde{v}_{r})$. Let
$\tilde{\jmath}_{k}\geqslant 0$ be the current in $\tilde{e}_{k}$, and
$\tilde{\jmath}_{l}\geqslant 0$ be the current in $\tilde{e}_{l}$. Let
$\tilde{c}_{k}(\bm{\tilde{\jmath}})$ be the cost in $\tilde{e}_{k}$, and
$\tilde{c}_{l}(\bm{\tilde{\jmath}})$ be the cost in $\tilde{e}_{l}$, where
$\bm{\tilde{\jmath}}=(\tilde{\jmath}_{k},\tilde{\jmath}_{l})$. Furthermore,
suppose that the costs $\tilde{c}_{k}$ and $\tilde{c}_{l}$ satisfy the
following condition

$\tilde{c}_{k}(\bm{\tilde{\jmath}})+\tilde{c}_{l}(\bm{\tilde{\jmath}})>0.$
(2.6)

Then, any Wardrop equilibrium,
${\bm{\tilde{\jmath}}}^{*}=(\tilde{\jmath}^{*}_{k},\tilde{\jmath}^{*}_{l})$,
satisfies the complementary condition

$\tilde{\jmath}^{*}_{k}\cdot\tilde{\jmath}^{*}_{l}=0,\ \ k\neq l.$ (2.7)

###### Proof.

We prove the theorem for a network that has Figure 1 as a subnetwork. To
simplify the discussion below, we will omit all the edges and currents of this
network that are not depicted in Figure 1. Assume that
${\bm{\tilde{\jmath}}}^{*}=(\tilde{\jmath}^{*}_{k},\tilde{\jmath}^{*}_{l})$ is
a Wardrop equilibrium and does not satisfy (2.7), i.e., without loss of
generality $\tilde{\jmath}^{*}_{k}>\tilde{\jmath}^{*}_{l}>0$. Consider the
current loop
$\bm{\tilde{\jmath}_{0}}=(\tilde{\jmath}^{*}_{k}-\tilde{\jmath}^{*}_{l},0)$,
then by (2.3), we have

$\langle\bm{\tilde{c}}({\bm{\tilde{\jmath}}}^{*}),{\bm{\tilde{\jmath}}}^{*}-\bm{\tilde{\jmath}_{0}}\rangle=\langle(\tilde{c}_{k}({\bm{\tilde{\jmath}}}^{*}),\tilde{c}_{l}({\bm{\tilde{\jmath}}}^{*})),(\tilde{\jmath}^{*}_{l},\tilde{\jmath}^{*}_{l})\rangle\leqslant
0$

which contradicts the assumption (2.6). Hence, ${\bm{\tilde{\jmath}}}^{*}$
cannot be a Wardrop equilibrium. ∎

Next, we analyze the monotonicity of the cost on a network containing the
subnetwork in Figure 1.

###### Example 2.12.

The monotonicity condition for the subnetwork in Figure 1 is

$\langle(\tilde{c}_{1}(\bm{\tilde{\jmath}}),\tilde{c}_{2}(\bm{\tilde{\jmath}}))-(\tilde{c}_{1}(\bm{\hat{\jmath}}),\tilde{c}_{2}(\bm{\hat{\jmath}})),\bm{\tilde{\jmath}}-\bm{\hat{\jmath}}\rangle\geqslant
0,$

where $\bm{\tilde{\jmath}}=(\tilde{\jmath}_{1},\tilde{\jmath}_{2})$ and
$\bm{\hat{\jmath}}=({\hat{\jmath}}_{1},{\hat{\jmath}}_{2})$. Then, we get

$(\tilde{c}_{1}(\bm{\tilde{\jmath}})-\tilde{c}_{1}(\bm{\hat{\jmath}}),\tilde{\jmath}_{1}-\hat{\jmath}_{1})+(\tilde{c}_{2}(\bm{\tilde{\jmath}})-\tilde{c}_{2}(\bm{\hat{\jmath}}),\tilde{\jmath}_{2}-\hat{\jmath}_{2})\geqslant
0.$

Suppose that
$\tilde{c}_{1}(\bm{\tilde{\jmath}})=\hat{c}_{1}(\tilde{\jmath}_{1}-\tilde{\jmath}_{2})$
and
$\tilde{c}_{2}(\bm{\tilde{\jmath}})=\hat{c}_{2}(\tilde{\jmath}_{2}-\tilde{\jmath}_{1})$.
Then, we have

$(\hat{c}_{1}(\tilde{\jmath}_{1}-\tilde{\jmath}_{2})-\hat{c}_{1}(\hat{\jmath}_{1}-\hat{\jmath}_{2}),\tilde{\jmath}_{1}-\hat{\jmath}_{1})+(\hat{c}_{2}(\tilde{\jmath}_{2}-\tilde{\jmath}_{1})-\hat{c}_{2}(\hat{\jmath}_{2}-\hat{\jmath}_{1}),\tilde{\jmath}_{2}-\hat{\jmath}_{2})\geqslant
0.$

The previous example can be generalized to networks built out of subnetworks
like the one in Figure 1. The sum in the monotonicity condition

$\sum_{k}(\tilde{c}_{k}({\bm{\tilde{\jmath}}})-\tilde{c}_{k}({\bm{\hat{\jmath}}}))({\tilde{\jmath}}_{k}-{\hat{\jmath}}_{k})\geqslant
0$

can be organized in related pairs of edges.

##  3 Mean-field games problem in a single edge

We start the discussion of MFGs on networks by analyzing a single edge.

###  3.1 MFG system in an edge

Consider an edge that is identified with the interval $[0,1]$. In this edge,
the Hamiltonian is a function
$H:[0,1]\times\mathbb{R}\times\mathbb{R}_{0}^{+}\to\mathbb{R}$, smooth and
convex in the second variable. The two unknowns that determine the MFG are the
player’s density $m:[0,1]\to\mathbb{R}_{0}^{+}$ and the value function
$u:[0,1]\to\mathbb{R}$. These two functions solve the MFG

$\begin{cases}H\left(x,u_{x}(x),m(x)\right)=0\\\
\left(-m(x)D_{p}H(x,u_{x}(x),m(x)\right)_{x}=0.\end{cases}$ (3.1)

The first equation is the Hamilton-Jacobi (HJ) equation; the second equation
is the Fokker-Plank or transport equation.

From the second equation in (3.1), the current

$j=-mD_{p}H\left(x,u_{x},m\right)$ (3.2)

is constant along the edge. Thus, in principle, we can solve (3.2) for $u_{x}$
and replace it in the first equation. Accordingly, we obtain an algebraic
equation for $m$; see Proposition 3.8 for details. This equation defines a
distribution of players $m(x,j)$. This procedure is known as the current
method introduced in [GNP16].

Next, we illustrate this method for a family of Hamiltonians that is a
prototype for MFG with congestion.

###### Example 3.1.

Let

$H(x,p,m)=\frac{|p|^{2}}{2m^{\alpha}}+V(x)-g(m),$

where $g$ is an increasing function, $V$ is a smooth function and
$0\leqslant\alpha\leqslant 2$ is the congestion strength. Then, (3.1) becomes

$\begin{cases}\frac{|u_{x}|^{2}}{2m^{\alpha}}+V(x)=g(m)\\\
(-m^{1-\alpha}u_{x})_{x}=0.\end{cases}$ (3.3)

There are two special values of the parameter $\alpha$, $\alpha=0$ for the
uncongested MFG, and $\alpha=1$, which corresponds to the critical congestion
model. In this last case, the system decouples, $u$ is a linear function, and
$m$ can be obtained by solving the first equation in (3.3).

Because the current, $j=-m^{1-\alpha}u_{x}$, is constant, we transform (3.3)
into the following algebraic system

$\begin{cases}\frac{j^{2}}{2m^{2-{\alpha}}}+V(x)=g(m)\\\
j\int_{0}^{1}m^{\alpha-1}dx=u(0)-u(1),\\\ \end{cases}$ (3.4)

provided $m>0$. We refer to the last equation in (3.4) as the _edge equation_.
In this equation, either $u(0)$ or $u(1)$ is given by boundary conditions. The
sign of the current indicates the direction in which the agents travel, from
$0$ to $1$ when $j>0$ and from $1$ to $0$ when $j<0$. When $j>0$, the edge
equation determines $u(0)$ as a function of $u(1)$, whereas when $j<0$, this
equation determines $u(1)$ as a function of $u(0)$. This depends on how
boundary conditions are specified, as we discuss next.

###  3.2 Travel cost in an edge

Consider an edge and, as before, assume that this edge is identified with the
interval $[0,1]$ and the vertices with $\\{0,1\\}$. Given the current $j$ in
this edge, there are two costs. $c_{01}(j)$ is the cost of moving from left to
right (i.e., from $0$ to $1$); $c_{10}(j)$ is the cost of moving from right to
left (i.e., from $1$ to $0$). To define these costs, we introduce the
Lagrangian

$L(x,v,m)=\sup_{p}{-pv-H(x,p,m)}.$

The cost $c_{xy}$ between two points $0\leqslant x\leqslant 1$ and $0\leqslant
y\leqslant 1$ is

$c_{xy}=\min_{\begin{subarray}{c}x,T\\\ x(0)=x\\\
x(T)=y\end{subarray}}\int_{0}^{T}L(x,v,m)dt.$

For $0<x<1$ and $0<y<1$, the HJ equation satisfies the dynamic programming
principle

$u(x)=\inf_{y}c_{xy}+u(y).$

When $x=0,1$ and $y=1-x$, the cost and the boundary conditions are related as
follows.

###### Definition 3.2.

Given a distribution of players $m(x,j)$. For $j\in\mathbb{R}$, the optimal
cost of traveling from $0$ to $1$ on the edge is

$c_{01}(j)=\min_{\begin{subarray}{c}x,T\\\ x(0)=0\\\
x(T)=1\end{subarray}}\int_{0}^{T}L(x,\dot{x},m(x,j))dt,$ (3.5)

where the minimum is taken over all Lipschitz trajectories and all possible
terminal times. The cost $c_{10}$ is defined analogously:

$c_{10}(j)=\min_{\begin{subarray}{c}x,T\\\ x(0)=1\\\
x(T)=0\end{subarray}}\int_{0}^{T}L(x,\dot{x},m(x,j))dt.$ (3.6)

The agent at a vertex of an edge has two options: leaving this edge or
crossing it to get to the opposite vertex of the same edge. This is encoded in
the following inequalities

$\begin{cases}u(1)\leqslant c_{10}(j)+u(0),\\\ u(0)\leqslant
c_{01}(j)+u(1).\end{cases}$ (3.7)

Moreover, the self-consistency in MFGs requires that the direction in which
the agent moves to be aligned with the direction of the current. This is
reflected in the following condition

$\begin{cases}j>0\Rightarrow u(0)=c_{01}(j)+u(1),\\\ j<0\Rightarrow
u(1)=c_{10}(j)+u(0).\end{cases}$ (3.8)

###### Remark 3.3.

The optimality conditions in (3.7) imply the following local compatibility
condition

$-c_{01}(j)\leqslant c_{10}(j).$

This can be interpreted as loops having a non-negative cost

$c_{01}(j)+c_{10}(j)\geqslant 0.$

###### Proposition 3.4.

If the costs in (3.7) are non-negative, then the inequalities in (3.7) are
redundant.

###### Proof.

The optimality conditions (3.7) imply,

$-c_{01}(j)\leqslant u(1)-u(0)\leqslant c_{10}(j).$

If $j\neq 0$, one of the two inequalities is an equality. Since the costs are
non-negative, then the other inequality holds. ∎

Now, we analyze the variational problems that define the costs $c_{01}$ and
$c_{10}$.

Starting with $c_{01}$, we parametrize, in (3.5), the velocity $v$ by the
space coordinate $x$, so $dx=vdt$ provided $\dot{x}>0$, we get

$c_{01}(j)=\min\int_{0}^{1}{\frac{L(x,v(x,j),m(x,j))}{v(x,j)}}dx,$ (3.9)

where the minimum is taken in the set,
$\text{Lip}_{x}\left([0,1]\times\mathbb{R}\right)$, of functions
$v:[0,1]\times\mathbb{R}\to\mathbb{R}^{+}$ that are Lipschitz in the first
variable. Similarly, we have

$c_{10}(j)=\min\int_{0}^{1}-{\frac{L(x,v(x,j),m(x,j))}{v(x,j)}}dx,$ (3.10)

where the minimum is taken in the set
$\text{Lip}_{x}\left([0,1]\times\mathbb{R}\right)$, of functions
$v:[0,1]\times\mathbb{R}\to\mathbb{R}^{-}$ that are Lipschitz in the first
variable.

###### Proposition 3.5.

If $L(x,v,m)$ is coercive in $v$ and $L(x,0,m)>0$, then the following holds

  1. 1.

There exist two functions $v_{+}^{*}>0$ and $v_{-}^{*}<0$ that minimize (3.9)
and (3.10), respectively. Moreover, these functions solve the Euler-Lagrange
equation

$-\frac{L(x,v(x,j),m(x,j))}{v(x,j)^{2}}+\frac{D_{v}L(x,v(x,j),m(x,j))}{v(x,j)}=0.$
(3.11)

  2. 2.

We have

$c_{01}(j)=\int_{0}^{1}{D_{v}L(x,v_{+}^{*}(x,j),m(x,j))}dx,\text{for any
}j\in\mathbb{R}.$ (3.12)

and

$c_{10}(j)=-\int_{0}^{1}{D_{v}L(x,v_{-}^{*}(x,j),m(x,j))}dx,\text{for any
}j\in\mathbb{R}.$ (3.13)

  3. 3.

If $v\mapsto L(x,v,m)$ is strictly convex in $v$, then $v_{+}^{*}$ is unique
in $\mathbb{R}^{+}$, and $v_{-}^{*}$ is unique in $\mathbb{R}^{-}$.

###### Proof.

Because $L(x,0,m)>0$, we have

$\lim_{v\rightarrow 0}\frac{L(x,v(x,j),m(x,j))}{v(x,j)}=+\infty,$

and by coercivity, we have

$\lim_{v\rightarrow\infty}\frac{L(x,v(x,j),m(x,j))}{v(x,j)}=+\infty.$

Then, for every $x$, there exists a minimizer $v_{+}^{*}>0$ of
$\frac{L(x,v,m)}{v}$ which solves (3.11). This pointwise minimizer is a
minimizer of (3.9).

By (3.11), we have

$D_{v}L(x,v_{+}^{*}(x,j),m(x,j))=\frac{L(x,v_{+}^{*}(x,j),m(x,j))}{v_{+}^{*}(x,j)}.$
(3.14)

Thus, we get (3.12).

Now, we prove the uniqueness of the minimizer. Because (3.11) holds, we have

$\displaystyle D^{2}_{vv}\left(\frac{L}{v}\right)$
$\displaystyle=D_{v}\left(\frac{D_{v}L}{v}-\frac{L}{v^{2}}\right)$
$\displaystyle=\frac{D^{2}_{vv}L}{v}-2\frac{D_{v}L}{v^{2}}+2\frac{L}{v^{3}}$
$\displaystyle=\frac{D^{2}_{vv}L}{v}.$

The above identity with $D^{2}_{vv}L(x,v,m)>0$ and $v_{+}^{*}>0$ implies that
$v\mapsto\frac{L(x,v,m)}{v}$ is strictly convex. Therefore, the integrand of
the variational problem is strictly convex, which gives the uniqueness of
$v^{*}_{+}$.

Following the same steps, we can prove similar results for $v_{-}^{*}$. ∎

###### Remark 3.6.

The cost $c_{01}$ in (3.12) is defined for any $j\in\mathbb{R}$. In
particular, when $j<0$, $c_{01}$ is the cost of moving against the current.

We now examine the relation between the cost and value functions.

###### Proposition 3.7.

For $j>0$, the cost $c_{01}(j)$ is given by

$c_{01}(j)=\int_{0}^{1}c_{01}(x,j)dx,$

where $c_{01}(x,j)=-u_{x}$ and solves the MFG system

$\begin{cases}H(x,-c_{01}(x,j),m(x,j))=0,\\\
-mD_{p}H(x,-c_{01}(x,j),m(x,j))=j.\end{cases}$ (3.15)

Similarly, for $j<0$, the cost $c_{10}(j)$ is given by

$c_{10}(j)=\int_{0}^{1}c_{10}(x,j)dx,$

where $c_{10}(x,j)=u_{x}$ and solves the MFG system

$\begin{cases}H(x,c_{10}(x,j),m(x,j))=0,\\\
-mD_{p}H(x,c_{10}(x,j),m(x,j))=j.\end{cases}$

###### Proof.

Consider an edge with a current $j>0$. By the fundamental theorem of calculus,

$u(0)=u(1)-\int_{0}^{1}{u_{x}}dx.$

By the first identity in (3.8), we have

$u(0)=u(1)+c_{01}(j).$

Hence,

$c_{01}(j)=-\int_{0}^{1}{u_{x}}dx.$ (3.16)

Thus, $-u_{x}$ can be regarded as a cost per unit length. We define
$c_{01}(x,j)=-u_{x}$. Therefore, $c_{01}(x,j)$ solves (3.15), and we have

$c_{01}(j)=\int_{0}^{1}c_{01}(x,j)dx.$

The proof for the case $j<0$ is similar. ∎

###### Proposition 3.8.

If $H$ is strictly convex in $p$, we have the following

  1. 1.

$u_{x}=-D_{v}L\left(x,\frac{j}{m},m\right);$ (3.17)

  2. 2.

$m(x,j)$ solves

$H\left(x,-D_{v}L\left(x,\frac{j}{m},m\right),m\right)=0.$ (3.18)

###### Proof.

Since $H$ is strictly convex in $p$, $p\rightarrow D_{p}H(x,p,m)$ is
invertible. Moreover, if $D_{v}L(x,v,m)=-p$ and $v=-D_{p}H(x,p,m)$, we have

$p=-D_{v}L(x,-D_{p}H(x,p,m),m).$

From (3.2), we have

$D_{p}H(x,u_{x},m)=-\frac{j}{m}.$

Accordingly, we get

$p=-D_{v}L\left(x,\frac{j}{m},m\right).$ (3.19)

Since $u_{x}=p$, we have the first statement.

Now, using (3.19) in the HJ equation in (3.1), we obtain (3.18), which
determines $m$ as a function of $x$ and $j$. ∎

###### Proposition 3.9.

Let $m(x,j)$ be determined by (3.18). If $j>0$, then, (3.12) becomes

$c_{01}(j)=\int_{0}^{1}D_{v}L\left(x,\frac{j}{m(x,j)},m(x,j)\right).$ (3.20)

Similarly, if $j<0$, then, (3.13) becomes

$c_{10}(j)=-\int_{0}^{1}D_{v}L\left(x,\frac{j}{m(x,j)},m(x,j)\right).$ (3.21)

###### Proof.

For $j>0$, we use (3.17), to substitute $u_{x}$ in (3.16), to get (3.20). The
proof of the case $j<0$, is similar. ∎

###### Remark 3.10.

Note that, (3.20) and (3.21) are not valid, in general, for $j<0$ and $j>0$,
respectively. In these cases, we must use (3.12) and (3.13).

##  4 Mean-field game model on a network

Now, we examine the MFG formulation on networks. While this problem shares
various aspects with the Wardrop model, a significant difference is that MFGs
are set up in undirected networks.

###  4.1 The network and the data

In the MFG model, we are given the following.

  1. 1.

A finite undirected network, $\Gamma=(E,V)$, where
$E=\\{e_{k}:k\in\\{1,2,\dots,n\\}\\}$ is the set of edges and
$V=\\{v_{i}:i\in\\{1,2,\dots,m\\}\\}$ is the set of vertices. To any edge
$e_{k}$, we associate the pair $(v_{r},v_{i})$ of its endpoints.

  2. 2.

Agents enter the network through $\lambda$ entrance vertices and exit it
through $\mu$ exit vertices (disjoint from the entrance vertices). For
convenience, we assume that the last $\mu$ vertices in $V$ are the exit
vertices. Furthermore, we suppose that entrance and exit vertices have
incidence $1$. If this is not the case, we proceed as in Remark 2.1.

  3. 3.

A flow of agents, the entry current
${\bm{\iota}}=({\iota}_{1},\dots,{\iota}_{\lambda})>0$, is prescribed at the
entrance vertices. The entry currents in the other vertices are zero.

  4. 4.

At the $\mu$ exit vertices, agents pay an exit cost $\bm{\phi}$. Here, we
assume that this exit cost vanishes. If the exit cost is nonzero, we proceed
as in Remark 2.2 by adding an auxiliary edge.

Fig. 2: MFG network.

###### Example 4.1.

Consider a three edges network like the one in Figure 2. Let $v_{1}$ and
$v_{3}$ be entrance vertices, and let $v_{2}$ and $v_{4}$ be exit vertices. We
attach an exit edge to $v_{2}$ and an entrance edge to $v_{3}$, so we get the
new network in Figure 3.

Fig. 3: MFG network with entrance and exit edges.

###  4.2 The variables and the costs

On the network $\Gamma$, we define the following variables:

  * •

Edge currents: In each edge, we have a _current_ variable representing the
number of agents crossing that edge per unit of time. The current $j_{k}$ in
the edge $e_{k}=(v_{r},v_{i})$ is decomposed into positive and negative parts;
that is, $j_{k}=j_{k}^{i}-j_{k}^{r}$ with

$j_{k}^{i}\cdot j^{r}_{k}=0,\ \ j_{k}^{i},j^{r}_{k}\geqslant 0,$ (4.1)

where $j^{i}_{k}$ is the current going to the vertex $v_{i}$ and $j^{r}_{k}$
is the current going to the vertex $v_{r}$. The complementary condition means
that all agents in an edge move in the same direction.

  * •

Transition currents: The _transition current_ from $e_{k}$ to $e_{l}$ through
a common vertex $v_{r}$ is denoted by $j_{kl}^{r}$. The transition currents
also satisfy the complementary condition

$j_{kl}^{r}\cdot j_{lk}^{r}=0,\ \ j_{kl}^{r},j_{lk}^{r}\geqslant 0.$ (4.2)

  * •

Hamiltonian: On each edge $e_{k}=(v_{r},v_{i})$, identified with the $[0,1]$
interval, we have a MFG system

$\begin{cases}H_{k}(x,u_{x},m)=0\\\ -mD_{p}H_{k}(x,u_{x},m)=j_{k},\end{cases}$
(4.3)

where $j_{k}$ is the current on $e_{k}$, parametrized accordingly.

  * •

Value function: The _value function_ in the edge $e_{k}=(v_{r},v_{i})$ at the
vertex $v_{i}$ is denoted by $u_{k}^{i}$. Note that the notation of the value
function emphasizes that it is not defined at the vertex but rather on an
edge/vertex pair. These values, $u_{k}^{i}$ and $u_{k}^{r}$, are the boundary
data for the HJ equation on the edge $e_{k}$.

On $\Gamma$, we have the following costs

  1. 1.

Travel costs: According to Section 3, in the edge $e_{k}=(v_{r},v_{i})$ we
define the cost of moving from $v_{r}$ to $v_{i}$, $c_{k}^{i}(j_{k})$, and the
cost of moving from $v_{i}$ to $v_{r}$, $c_{k}^{r}(j_{k})$, associated with
(4.3). More precisely, let $(u^{k},m^{k})=(u^{k}(x),m^{k}(x,j_{k}))$ solves
(4.3), then, $c_{k}^{i}(j_{k})$ is determined by (3.9) with the Legendre
transform of $H_{k}$, $L_{k}$, and $m^{k}$. Similarly, $c_{k}^{r}(j_{k})$ is
determined by (3.10) with $L_{k}$ and $m^{k}$.

Note that the cost in the edge depends only on the current in this edge. The
travel cost from an auxiliary entrance vertex to an original vertex in the
entrance edge is zero, and the travel cost in the opposite direction is
$+\infty$. The travel cost from an original vertex to an auxiliary exit vertex
is the exit cost, and the travel cost in the opposite direction is $+\infty$.

  2. 2.

Switching costs: For moving from $e_{k}$ to $e_{l}$ through a common vertex
$v_{i}$, agents pay a _switching cost_ , $\psi_{kl}^{i}$. Often, we may
require $\psi_{kl}^{i}\geqslant 0$. We assume, for simplicity, that
$\psi_{kl}^{i}$ is independent of the transition current.

For any vertex, $v_{i}$, that has over two incident edges, we require the
following triangle-type inequality in the switching costs,

$\psi_{kl}^{i}\leqslant\psi_{kp}^{i}+\psi_{pl}^{i}.$ (4.4)

###### Remark 4.2.

If we need to add extra vertices or edges, we modify the switching costs as
follows. The switching cost from an entrance edge to an original edge is $0$,
and from an original edge to an entry edge is $\infty$. Similarly, the
switching cost from an exit edge to an original edge is $\infty$, and from an
original edge to an exit edge is $0$. This avoids entry through exits and exit
through entrances.

###  4.3 The equations

Finally, we set up the equations that determine the MFG. These comprise the
MFG system in the edges and the optimality conditions at the vertices that
arise from switching and from the MFG on each edge, as considered in Section
3. Further, we have a further condition that represents the balance of the
flow of agents at the different vertices, Kirchhoff’s conditions.

#### Optimality conditions at the vertices.

In the process of minimizing their travel cost, agents choose the least
expensive path. In particular, they can switch from $e_{k}$ to $e_{l}$ through
the common vertex $v_{i}$ by paying a cost $\psi_{kl}^{i}$. This possibility
is encoded in the following inequality

$u^{r}_{k}\leqslant u_{l}^{r}+\psi_{kl}^{i},\ \forall\ i,k,l.$ (4.5)

#### Complementarity conditions at the vertices.

If the transition current $j_{kl}^{i}$ is not zero, then agents are moving
from $e_{k}$ to $e_{l}$ through $v_{i}$. This implies that
$u_{k}^{r}=u_{l}^{r}+\psi_{kl}^{i}$. So, we have the following

$j_{kl}^{i}\cdot(u^{r}_{k}-u^{r}_{l}-\psi_{kl}^{i})=0,\ \ \forall i,k,l.$
(4.6)

#### Optimality conditions in the edges.

In the edge $e_{k}=(v_{r},v_{i})$, for any $j_{k}$ we have

$\begin{cases}u^{r}_{k}\leqslant c_{k}^{i}(j_{k})+u_{k}^{i},\\\
u^{i}_{k}\leqslant c_{k}^{r}(j_{k})+u^{r}_{k}.\end{cases}$ (4.7)

Moreover,

$\begin{cases}j_{k}>0\implies u^{r}_{k}=c_{k}^{i}(j_{k}^{i})+u_{k}^{i},\\\
j_{k}<0\implies u_{k}^{i}=c_{k}^{r}(-j_{k}^{r})+u^{r}_{k}.\end{cases}$

The costs $c_{k}^{i}$ and $c_{k}^{r}$ may not be the same, unless the
Hamiltonian is even, as discussed in Section 3.

#### Complementarity conditions in the edges.

In the edge $e_{k}=(v_{r},v_{i})$, we have the complementary conditions

$\begin{cases}j_{k}^{i}\cdot(u_{k}^{r}-u_{k}^{i}-c_{k}^{i}(j_{k}))=0,\\\
j_{k}^{r}\cdot\left(u_{k}^{i}-u_{k}^{r}-c_{k}^{r}(j_{k})\right)=0.\end{cases}$
(4.8)

#### Balance equations and Kirchhoff’s law.

Consider an edge $e_{k}=(v_{r},v_{i})$, and the set $\mathcal{E}$ of the
incident edges at $v_{i}$ distinct from $e_{k}$. The current $j_{k}^{i}$ is
equal to the sum of the transition currents from $e_{k}$ to all the other
incident edges at $v_{i}$

$\sum_{e_{l}\in\mathcal{E}}j_{kl}^{i}=j^{i}_{k};$ (4.9)

this identity models the splitting of the current at a vertex. We have a
similar equation for the gathering of the transition currents; the current
$j_{k}^{r}$ is the sum of the transition currents to $e_{k}$ from all the
incident edges at $v_{i}$

$\sum_{e_{l}\in\mathcal{E}}j_{lk}^{i}=j^{r}_{k}.$ (4.10)

In particular, we have Kirchhoff’s law at $v_{i}$; that is, the sum of the
incoming currents $j_{k}$ is equal to the sum of the outgoing currents,
$j_{l}$,

$\sum_{k}j_{k}=\sum_{l}j_{l},$ (4.11)

because of the current decomposition

$\sum_{k}(j_{k}^{i}-j_{k}^{r})=\sum_{l}(j_{l}^{r}-j_{l}^{s}).$

#### Entry edge equations.

In every entry edge $e_{k}=(v_{r},v_{i})$, given the entering current
${\iota}_{i}$ at the entrance vertex $v_{i}$, we have

$\begin{cases}j^{i}_{k}={\iota}_{i},\\\ j^{r}_{k}=0.\end{cases}$ (4.12)

#### Exit edge equations.

In every exit edge $e_{l}=(v_{i},v_{s})$, we assume the exit cost vanishes, so
we have

$u^{s}_{l}\leqslant 0,$ (4.13)

with equality if $j^{s}_{l}>0$. In $e_{l}$, we also have

$j^{i}_{l}=0.$ (4.14)

##  5 Reformulation of the MFG as Wardrop model

Here, we reformulate the MFG model from Section 4 as a Wardrop equilibrium
model, as described in Section 2. Then, after identifying the network, the
currents, and the costs in the Wardrop model, we show that the MFG solution
corresponds to a Wardrop equilibrium.

The network in the Wardrop model is directed. In contrast, in the MFG model,
it is undirected. To establish the correspondence between MFG and Wardrop
models, we show how to build a new directed network, $\bar{\Gamma}$, from the
MFG undirected network, $\Gamma$.

  1. 1.

To each current and transition current, we associate a directed edge. This
amounts to doubling all undirected edges and creating transition edges
corresponding to the transition currents.

  2. 2.

Each of the two vertices of these directed edges corresponds to a pair
$(e_{k},v_{i})$, where $e_{k}$ is an edge and $v_{i}$ is one of its vertices
in $\Gamma$. This pair is built as follows.

     * •

In the case of a current $j_{k}^{i}$ in an edge $e_{k}\in\Gamma$ with vertices
$(v_{r},v_{i})$, the vertices of the new edge correspond to the pairs
$(e_{k},v_{r})$ and $(e_{k},v_{i})$.

     * •

In the case of a transition current $j_{kl}^{i}$ from the edge $e_{k}$ to the
edge $e_{l}$ through the vertex $v_{i}$, the new vertices correspond to the
pairs $(e_{k},v_{i})$ and $(e_{l},v_{i})$.

###### Remark 5.1.

A natural notation for the edges in $\bar{\Gamma}$ is to use the same indices
from the corresponding current in the MFG. For example, $\bar{e}_{k}^{i}$ for
the edge carrying the current $j_{k}^{i}$, and $\bar{e}_{kl}^{i}$ for
$j_{kl}^{i}$. However, to avoid heavy notation and keep consistency with the
previous notation, we relabel the edges and the vertices and write
$\bar{\Gamma}=(\bar{E},\bar{V})$ for
$\bar{E}=\\{\bar{e}_{\kappa}:\kappa\in\\{1,2,\dots,\bar{n}\\}\\}$ and
$\bar{V}=\\{\bar{v}_{i}:i\in\\{1,2,\dots,\bar{m}\\}\\}$. When the precise
correspondence is needed, we use the identification
$\bar{e}_{\kappa}=\bar{e}_{k}^{i}$ or $\bar{e}_{\kappa}=\bar{e}_{kl}^{i}$.

  3. 3.

Because entrance currents at exit vertices and exit currents at entrance
vertices vanish, we delete the corresponding edges so that $\bar{\Gamma}$ has
entrance and exit vertices with incidence $1$.

###### Example 5.2.

Consider the network in Example 4.1. We follow the previous steps to transform
this network from the MFG to the Wardrop setting. Accordingly, we get the new
network $\bar{\Gamma}$ in Figure 4, which consists of $22$ edges and $10$
vertices. The blue edges correspond to the currents and the red edges
correspond to the transition currents. The dashed edges will be deleted, as
discussed in the third step above. Thus, these dashed edges are not a part of
$\bar{\Gamma}$.

Fig. 4: New Wardrop network $\bar{\Gamma}$.

The correspondence between the variables in the MFG model and the Wardrop
model is as follows.

  1. 1.

The value function from the MFG is a function on the new vertices because
$u_{k}^{i}$ is a function on pairs $(e_{k},v_{i})$, where $v_{i}$ is a vertex
of $e_{k}$. While this function does not appear explicitly in the Wardrop
model, it is relevant in our analysis.

  2. 2.

Each current or transition current in the MFG network corresponds to an edge
in the new network $\bar{\Gamma}$. Thus, we have a natural correspondence
between currents in the two models, $j$ and $\bar{\jmath}$. If
$\bar{e}_{\kappa}=\bar{e}_{k}^{i}$, we set $\bar{\jmath}_{\kappa}=j_{k}^{i}$,
and if $\bar{e}_{\kappa}=\bar{e}_{kl}^{i}$, we set
$\bar{\jmath}_{\kappa}=j_{kl}^{i}$.

  3. 3.

By combining (4.9) and (4.10) at every pair $(e_{k},v_{i})$ which is not an
entrance or an exit, we obtain the Kirchhoff’s law in the corresponding vertex
of $\bar{\Gamma}$

$j_{k}^{r}+\sum_{e_{l}\in\mathcal{E}}j_{kl}^{i}=j_{k}^{i}+\sum_{e_{l}\in\mathcal{E}}j_{lk}^{i},$
(5.1)

which can be written in terms of the variable $\bar{\jmath}$
straightforwardly.

  4. 4.

Moreover, at entrance vertices, where we have the entry current assignments,
we have the first equation in (4.12). This equation and (5.1) are encoded as a
matrix equation

$K\bar{\bm{\jmath}}=B.$

Thus, we have a linear equation for every vertex in $\bar{\Gamma}$ that is not
an exit.

  5. 5.

Let $\bar{e}_{k}^{i}\in\bar{\Gamma}$ and $\bar{e}_{k}^{r}\in\bar{\Gamma}$ be
the edges corresponding to the undirected edge $e_{k}=(v_{r},v_{i})\in\Gamma$,
with orientations corresponding to the currents $j_{k}^{i}$ and $j_{k}^{r}$,
respectively. Based on the discussion in Section 3, the MFG has two costs
$c_{k}^{i}$ and $c_{k}^{r}$ in the edge $e_{k}$. The cost for traveling in
$\bar{e}_{k}^{i}$ is
$\bar{c}_{k}^{i}(\bm{j_{k}})=c_{k}^{i}(j_{k}^{i}-j_{k}^{r})$, where
$\bm{j_{k}}=(j_{k}^{i},j_{k}^{r})$, and the cost for traveling in
$\bar{e}_{k}^{r}$ is
$\bar{c}_{k}^{r}(\bm{j_{k}})=c_{k}^{r}(j_{k}^{r}-j_{k}^{i})$.

  6. 6.

The switching costs $\psi_{kl}^{i}$ from the MFG are constant travel costs in
the new Wardrop model; that is,
$\bar{c}_{\kappa}(\bm{j}):=\bar{c}^{i}_{kl}(\bm{j})=\psi_{kl}^{i}$ in the
transition edges $\bar{e}_{\kappa}=\bar{e}_{kl}^{i}$.

Applying this to the network in Figure 4, we get the new Wardrop network as in
Figure 5.

Fig. 5: New Wardrop network with costs.

The main result connecting MFGs with Wardrop models is

###### Theorem 5.3.

Let M be a MFG model and W be the corresponding Wardrop model. Suppose that a
pair $(\bm{u},\bm{{\jmath}^{*}})$ solves M. Then, the corresponding
$\bm{\bar{{\jmath}}^{*}}$ is a Wardrop equilibrium for W.

###### Proof.

For any admissible $\bm{\bar{\jmath}}$, we have

$K\bm{{\bar{\jmath}}^{*}}=B\ \text{and}\ K\bm{\bar{\jmath}}=B.$

Subtracting the two equations, we get

$K(\bm{{\bar{\jmath}}^{*}}-\bm{\bar{\jmath}})=0.$

Let $\bm{u}$ be the vector of value functions arising from the MFG.
Multiplying (5) by $\bm{u^{T}}$, gives

$\bm{u^{T}}K(\bm{{\bar{\jmath}}^{*}}-\bm{\bar{\jmath}})=0.$

Except for the currents pointing towards an exit vertex (which appears only
once), each current appears twice, one for each of its vertices but with
different signs. The previous computation can be organized as

$\sum_{\bar{e}_{k}^{i}}(u_{k}^{r}-u_{k}^{i})(\bar{\jmath}^{i*}_{k}-\bar{\jmath}_{k}^{i})+\sum_{\bar{e}_{kl}^{i}}(u_{k}^{i}-u_{l}^{i})(\bar{\jmath}^{i*}_{kl}-\bar{\jmath}_{kl}^{i})=0,$
(5.2)

the first sum is over the edges of W where the vertices of $e_{k}$ are $v_{r}$
and $v_{i}$; this includes the exit edges since, in that case,
$u_{k}^{i}\leqslant 0$. The second sum is over the transition edges of W
corresponding to transitions through the vertex $v_{i}$ from $e_{k}$ to
$e_{l}$. Based on the complementarity conditions in the edges (4.8), there are
two cases for the first term, either

$\bar{\jmath}^{i*}_{k}>0\Rightarrow
u_{k}^{r}-u_{k}^{i}=\bar{c}_{k}^{i}(\bm{\bar{\jmath}}^{*})$

or, noting (4.7),

$\bar{\jmath}^{i*}_{k}=0\Rightarrow
u_{k}^{r}-u_{k}^{i}\leqslant\bar{c}_{k}^{i}(\bm{\bar{\jmath}}^{*}).$

Because $\bar{\jmath}^{i}_{k}\geqslant 0$,

$\bar{\jmath}^{i*}_{k}=0\Rightarrow(u_{k}^{r}-u_{k}^{i})(\bar{\jmath}^{i*}_{k}-\bar{\jmath}_{k}^{i})\geqslant\bar{c}_{k}^{i}(\bm{\bar{\jmath}}^{*})(\bar{\jmath}^{i*}_{k}-\bar{\jmath}_{k}^{i}).$

Similarly, based on the complementarity conditions at the vertices (4.6), we
have two cases for the second term, either

$\bar{\jmath}^{i*}_{kl}>0\Rightarrow u_{k}^{i}-u_{l}^{i}=\psi_{kl}$

or, noting (4.5),

$\bar{\jmath}^{i*}_{kl}=0\Rightarrow u_{k}^{i}-u_{l}^{i}\leqslant\psi_{kl}.$

Because $\bar{\jmath}^{i}_{kl}\geqslant 0$,

$\bar{\jmath}^{i*}_{kl}=0\Rightarrow(u_{k}^{i}-u_{l}^{i})(\bar{\jmath}^{i*}_{kl}-\bar{\jmath}_{kl}^{i})\geqslant\psi_{kl}(\bar{\jmath}^{i*}_{kl}-\bar{\jmath}_{kl}^{i}).$

Using these results in (5.2), we get

$\sum_{\begin{subarray}{c}\bar{e}_{k}^{i}\\\
\bar{\jmath}^{i*}_{k}>0\end{subarray}}\bar{c}_{k}^{i}(\bm{\bar{\jmath}}^{*})(\bar{\jmath}^{i*}_{k}-\bar{\jmath}_{k}^{i})+\sum_{\begin{subarray}{c}\bar{e}_{k}^{i}\\\
\bar{\jmath}^{i*}_{k}=0\end{subarray}}\bar{c}_{k}^{i}(\bm{\bar{\jmath}}^{*})(\bar{\jmath}^{i*}_{k}-\bar{\jmath}_{k}^{i})+\sum_{\begin{subarray}{c}\bar{e}_{kl}^{i}\\\
\bar{\jmath}^{i*}_{kl}>0\end{subarray}}\psi_{kl}(\bar{\jmath}^{i*}_{kl}-\bar{\jmath}_{kl}^{i})+\sum_{\begin{subarray}{c}\bar{e}_{kl}^{i}\\\
\bar{\jmath}^{i*}_{kl}=0\end{subarray}}\psi_{kl}(\bar{\jmath}^{i*}_{kl}-\bar{\jmath}_{kl}^{i})\leqslant
0.$

This implies

$\langle\bm{\bar{c}}(\bm{{\bar{\jmath}}^{*}}),\bm{{\bar{\jmath}}^{*}}-\bm{\bar{\jmath}}\rangle\leqslant
0.$

Accordingly, $\bm{{\bar{\jmath}}^{*}}$ is a Wardrop equilibrium. ∎

Next, we prove a uniqueness result for the new Wardrop equilibrium. For this,
we present some definitions. We say that the cost is _reversible_ if the cost
for traveling along an edge from left to right is the same as the cost for
traveling from right to left along the same edge, i.e., $c_{01}(j)=c_{10}(j)$.
The cost is _even_ if $c_{01}(-j)=c_{01}(j)$. We discuss these properties in
Section 7.

###### Proposition 5.4.

If for every edge $e_{k}=(v_{r},v_{i})$ corresponding to an edge in the MFG,
the costs are reversible, even, increasing for positive current, and
satisfying (2.6), then in the new Wardrop model, the current is unique in the
corresponding edge.

###### Proof.

For an edge $e_{k}=(v_{r},v_{i})$, let
$\bar{c}_{k}^{i}(\bm{j_{k}})=c_{k}^{i}(j_{k}^{i}-j_{k}^{r})=c_{k}^{i}(j_{k})$
be the cost in the new Wardrop, where $c_{k}^{i}$ is the cost in the MFG,
$\bm{j_{k}}=(j_{k}^{i},j_{k}^{r})$. Similarly, let
$\bar{c}_{k}^{r}(\bm{j_{k}})=c_{k}^{r}(j_{k}^{r}-j_{k}^{i})=c_{k}^{r}(-j_{k})$.
For the Wardrop monotonicity, we need monotonicity over all edges. Thus, we
need to examine the expression

$\sum_{k}(\bar{c}_{k}({\bm{\tilde{\jmath}}})-\bar{c}_{k}({\bm{\hat{\jmath}}}),{\bm{\tilde{\jmath}}}-{\bm{\hat{\jmath}}}),$

which can be written for each edge

$\sum_{k}(c_{k}^{i}({\tilde{\jmath}}_{k})-c_{k}^{i}({\hat{\jmath}}_{k}))({\tilde{\jmath}}_{k}^{i}-{\hat{\jmath}}_{k}^{i})+(c_{k}^{r}(-{\tilde{\jmath}}_{k})-c_{k}^{r}(-{\hat{\jmath}}_{k}))({\tilde{\jmath}}_{k}^{r}-{\hat{\jmath}}_{k}^{r}).$

The costs corresponding to the transition currents do not play any role
because they are constants. Since the cost is reversible (i.e.
$c_{k}^{i}(j)=c_{k}^{r}(j)=c(j)$), we get

$\sum_{k}(c({\tilde{\jmath}}_{k})-c({\hat{\jmath}}_{k}))({\tilde{\jmath}}_{k}^{i}-{\hat{\jmath}}_{k}^{i})+(c(-{\tilde{\jmath}}_{k})-c(-{\hat{\jmath}}_{k}))({\tilde{\jmath}}_{k}^{r}-{\hat{\jmath}}_{k}^{r}).$
(5.3)

Because of (2.7), we verify four cases for Wardrop equilibrium. These are as
follows.

  1. 1.

If ${\tilde{\jmath}}_{k}^{r}={\hat{\jmath}}_{k}^{r}=0$, then (5.3) becomes

$\sum_{k}(c({\tilde{\jmath}}_{k}^{i})-c({\hat{\jmath}}_{k}^{i}))({\tilde{\jmath}}_{k}^{i}-{\hat{\jmath}}_{k}^{i}).$

  2. 2.

If ${\tilde{\jmath}}_{k}^{i}={\hat{\jmath}}_{k}^{i}=0$, then since $c$ is
even, (5.3) becomes

$\sum_{k}(c(-{\tilde{\jmath}}_{k}^{r})-c(-{\hat{\jmath}}_{k}^{r}))({\tilde{\jmath}}_{k}^{r}-{\hat{\jmath}}_{k}^{r}).$

  3. 3.

If ${\tilde{\jmath}}_{k}^{i}={\hat{\jmath}}_{k}^{r}=0$, then, since $c$ is
even, (5.3) becomes

$\sum_{k}(c({\tilde{\jmath}}_{k}^{r})-c({\hat{\jmath}}_{k}^{i}))({\tilde{\jmath}}_{k}^{r}-{\hat{\jmath}}_{k}^{i}).$

  4. 4.

If ${\tilde{\jmath}}_{k}^{r}={\hat{\jmath}}_{k}^{i}=0$, then (5.3) becomes

$\sum_{k}(c({\tilde{\jmath}}_{k}^{i})-c({\hat{\jmath}}_{k}^{r}))({\tilde{\jmath}}_{k}^{i}-{\hat{\jmath}}_{k}^{r}).$

In all four cases, the sums are non-negative because the cost $c(j)$ is
increasing for $j>0$. The inequality is strict if $c(j)$ is strictly
increasing and ${\tilde{\jmath}}_{k}^{i}\neq{\hat{\jmath}}_{k}^{i}$. Because
the cost is strictly monotone, by Theorem (2.8), the Wardrop equilibrium is
unique. ∎

###### Remark 5.5.

For general costs, a condition that implies uniqueness is the following

  1. 1.

The cost $c_{k}^{i}$ is increasing in $\mathbb{R}^{+}_{0}$, if
${\tilde{\jmath}}_{k}^{r}={\hat{\jmath}}_{k}^{r}=0$.

  2. 2.

The cost $c_{k}^{r}$ is increasing in $\mathbb{R}^{+}_{0}$, if
${\tilde{\jmath}}_{k}^{i}={\hat{\jmath}}_{k}^{i}=0$.

  3. 3.

The following inequality holds

${\tilde{\jmath}}_{k}^{r}c_{k}^{r}(-{\hat{\jmath}}_{k}^{i})+{\hat{\jmath}}_{k}^{i}c_{k}^{i}(-{\tilde{\jmath}}_{k}^{r})\leqslant{\tilde{\jmath}}_{k}^{r}c_{k}^{r}({\tilde{\jmath}}_{k}^{r})+{\hat{\jmath}}_{k}^{i}c_{k}^{i}({\hat{\jmath}}_{k}^{i})$

if ${\tilde{\jmath}}_{k}^{i}={\hat{\jmath}}_{k}^{r}=0$.

  4. 4.

The following inequality holds

${\tilde{\jmath}}_{k}^{i}c_{k}^{i}(-{\hat{\jmath}}_{k}^{r})+{\hat{\jmath}}_{k}^{r}c_{k}^{r}(-{\tilde{\jmath}}_{k}^{i})\leqslant{\tilde{\jmath}}_{k}^{i}c_{k}^{i}({\tilde{\jmath}}_{k}^{i})+{\hat{\jmath}}_{k}^{r}c_{k}^{r}({\hat{\jmath}}_{k}^{r})$

if ${\tilde{\jmath}}_{k}^{r}={\hat{\jmath}}_{k}^{i}=0$.

###### Remark 5.6.

In Proposition 5.4, we proved the uniqueness of the currents. However, under
the same assumptions, we do not have uniqueness of the transition currents.
For example, consider $4$ edges that intersect in a single vertex, as in
Figure 6. Let the currents in $e_{1}$ and $e_{3}$ be $j_{1}=j_{3}=10$, and the
currents in $e_{2}$ and $e_{4}$ be $j_{2}=j_{4}=5$. For the transition
currents, we may have $j_{13}=10$, $j_{24}=5$, and $j_{14}=j_{23}=0$.
Alternatively, we may have, for example, $j_{13}=7.5$ and
$j_{24}=j_{14}=j_{23}=2.5$.

Fig. 6: 4 edges intersect in 1 vertex.

###### Proposition 5.7.

Under the same assumptions of Proposition 5.4, in the MFG, the current is
uniquely defined in each edge.

###### Proof.

Suppose the MFG has two current solutions in one edge. By theorem 5.3, these
two currents are the Wardrop equilibrium current solutions, and by the
uniqueness of the currents in the Wardrop model, these two currents are the
same. ∎

##  6 Recovering MFG solution from the Wardrop solution

Now, we show how to recover the MFG solution from the corresponding Wardrop
model solution. We start with a MFG problem and build the corresponding
Wardrop problem. We follow the same procedure as in Section 5 to convert the
MFG model into a Wardrop model. Accordingly, the structure of the network and
the costs arise from the MFG. Then, we solve the new Wardrop problem and use
its solution to recover the solution of the MFG. This consists in recovering
the currents, the transition currents, and the value function. To recover the
current in an edge $e_{k}$ of a MFG from the current in the Wardrop model, we
consider the difference of the currents in the two directed edges associated
to $e_{k}$ in the Wardrop model. For the transition currents, the
correspondence is immediate. Kirchhof’s law (5.1) in the new Wardrop network,
$\bar{\Gamma}$, implies the splitting and gathering equations (4.9) and (4.10)
in the MFG network $\Gamma$, as the following proposition shows.

###### Proposition 6.1.

Consider a MFG model satisfying (2.6) and (4.4) with strict inequality. Let
$\bm{\tilde{{\jmath}}^{*}}$ be the corresponding Wardrop equilibrium. Then,
(4.9) and (4.10) hold on every non-entrance and non-exit vertex.

###### Proof.

In the Wardrop model, we have Kirchhoff’s law (5.1) for every non-entrance and
non-exit vertex. Because of (4.1), either $j_{k}^{r}=0$ or $j_{k}^{i}=0$.
Without loss of generality, assume that $j_{k}^{i}=0$, then (5.1) becomes

$j_{k}^{r}+\sum_{e_{l}\in\mathcal{E}}j_{kl}^{i}=\sum_{e_{l}\in\mathcal{E}}j_{lk}^{i}.$
(6.1)

We must show that the corresponding transition currents $j_{kl}^{i}$ are zero.
Suppose, by contradiction, that one of the currents $j_{kl}^{i}$ is nonzero,
then by (6.1), we have $j_{\tilde{l}k}^{i}>0$, for some $\tilde{l}$. Consider
the Wardrop equilibrium $\bm{\tilde{{\jmath}}^{*}}$, take $\sigma>0$ small
enough, and set $\bm{\hat{\jmath}}$ by changing the following coordinates.

$\hat{\jmath}_{kl}^{i}=j_{kl}^{i*}-\sigma,$
$\hat{\jmath}_{\tilde{l}k}^{i}=j_{\tilde{l}k}^{i*}-\sigma,$

and

$\hat{\jmath}_{\tilde{l}l}^{i}=j_{\tilde{l}l}^{i*}+\sigma.$

Note that $\bm{\hat{\jmath}}\in\mathcal{A}$. Because
$\bm{\tilde{{\jmath}}^{*}}$ is a Wardrop equilibrium, we get

$\sigma(-c_{\tilde{l}l}(\bm{\tilde{{\jmath}}^{*}})+c_{\tilde{l}k}(\bm{\tilde{{\jmath}}^{*}})+c_{kl}(\bm{\tilde{{\jmath}}^{*}}))\leqslant
0,$

which is

$\sigma(-\psi^{i}_{\tilde{l}l}+\psi^{i}_{\tilde{l}k}+\psi^{i}_{kl})\leqslant
0.$

Thus,

$\psi^{i}_{\tilde{l}l}\geqslant\psi^{i}_{\tilde{l}k}+\psi^{i}_{kl},$

which contradicts the strict inequality (4.4). Hence, $j_{kl}^{i}$ must be
zero. Using this in (6.1), we get (4.10). Similarly, we get (4.9). ∎

Next, we retrieve the value function. For this, we present the following
definitions and a key result.

###### Definition 6.2.

Given a Wardrop equilibrium, a _regular vertex_ is a vertex that belongs to an
edge where the current is positive.

###### Definition 6.3.

A walk is a sequence of vertices and edges of a graph. A positively directed
walk is a walk of regular vertices connected by edges with positive currents.

###### Lemma 6.4.

Suppose all loops have positive costs. Any regular vertex is connected to an
exit by a positive walk. Moreover, Wardrop equilibrium admits no loops.

###### Proof.

Let $\tilde{v}$ be a regular vertex. Then, at $\tilde{v}$, there are walks of
positive currents that either end at an exit or have an infinite number of
vertices. Having these loops is incompatible with Wardrop equilibrium. To
prove this, consider a Wardrop equilibrium $\bm{{\tilde{\jmath}}^{*}}$ and a
loop of positive currents. Next, take $\sigma>0$ small enough. For the
currents in each edge of the loop, we set

${\hat{{\jmath}}}_{k}={{\tilde{\jmath}}^{*}}_{k}-\sigma.$

For all other edges, ${\hat{{\jmath}}}_{k}={{\tilde{\jmath}}^{*}}_{k}$. Since
the cost is positive, we have

$\langle\tilde{c}({\bm{\tilde{\jmath}}}^{*}),{\bm{\tilde{\jmath}}}^{*}-({\bm{\tilde{\jmath}}}^{*}-\sigma)\rangle=\sigma\tilde{c}({\bm{\tilde{\jmath}}}^{*})\geqslant
0,$ (6.2)

which contradicts the Wardrop equilibrium condition. ∎

Because of Lemma 6.4, we can always connect any regular vertex
$\tilde{v}_{i}\in\tilde{e}_{k}=(\tilde{v}_{r},\tilde{v}_{i})$ to an exit
vertex. Hence, we define

$\tilde{u}_{k}^{i}=\sum_{l}\tilde{c}_{l}({\tilde{\jmath}}_{l}),$ (6.3)

where $\tilde{u}_{k}^{i}$ is the candidate for the value function at
$\tilde{v}_{i}$, $\tilde{c}_{l}({\tilde{\jmath}}_{l})$ is the cost in each
edge of the walk and the sum is taken over the current-carrying edges.

###### Proposition 6.5.

Given the Wardrop equilibrium $\bm{{\tilde{\jmath}}^{*}}$, the value function
$\tilde{u}$ in (6.3) is well defined at all regular vertices, i.e., given two
different walks starting at the same regular vertex, the value function
$\tilde{u}$ in these walks is the same. Moreover, a walk to an exit is at
least as expensive as a current-carrying walk to any exit.

###### Proof.

Let $\tilde{u}$ be the value function at a regular vertex with two outgoing
walks, and suppose the first walk is less expensive than the second one.
Consider the Wardrop equilibrium $\bm{{\tilde{\jmath}}^{*}}$ and take
$\sigma>0$ small enough. For the currents in each edge of the first walk, we
set

${{\jmath}}^{1}_{k}={{\tilde{\jmath}}^{*}}_{k}+\sigma.$

For the currents in each edge of the second walk, we set

${{\jmath}}^{2}_{k}={{\tilde{\jmath}}^{*}}_{k}-\sigma.$

For all other edges that are not in the walks or that are common between them,
${{\jmath}}^{1}_{k}={{\jmath}}^{2}_{k}={{\tilde{\jmath}}^{*}}_{k}$. Since the
new corresponding currents $\bm{{{\jmath}^{1}}}$ and $\bm{{{\jmath}^{2}}}$
satisfy Kirchhoff’s law, applying the definition of Wardrop equilibrium (2.3)
on the second walk, we get

$\langle\tilde{c}({\bm{\tilde{\jmath}}}^{*}),{\bm{\tilde{\jmath}}}^{*}-({\bm{\tilde{\jmath}}}^{*}-\sigma)\rangle=\sigma\tilde{c}({\bm{\tilde{\jmath}}}^{*})\geqslant
0$ (6.4)

because the cost is positive, which contradicts the Wardrop equilibrium
condition.

Note that if the second walk is not current-carrying, the proof still holds;
following the same steps, we can prove that for any current-carrying walk and
any other walk, the other walk is at least as expensive as the current-
carrying walk. ∎

###### Proposition 6.6.

Consider a Wardrop model and suppose all vertices are regular. Then, the value
function $\tilde{u}$ in the Wardrop model is the value function $u$ in the MFG
model and satisfies (4.5) and (4.7).

###### Proof.

The value function $u$ is the infimum among all walks. Hence, by Proposition
6.5, $\tilde{u}=u$. By Proposition 6.5, for
$\tilde{e}_{k}=(\tilde{v}_{r},\tilde{v}_{i})$, we have

$\tilde{u}^{r}_{k}\leqslant\tilde{c_{k}}(\tilde{\jmath}_{k})+\sum_{l}\tilde{c}_{l}(\tilde{\jmath}_{l}),$

The sum here is over the current-carrying edges. By (6.3), we can write the
previous inequality as

$\tilde{u}^{r}_{k}\leqslant\tilde{c_{k}}(\tilde{\jmath}_{k})+\tilde{u}^{i}_{k}.$

If $\tilde{\jmath}_{k}>0$, then we have

$\tilde{u}^{r}_{k}=\tilde{c_{k}}(\tilde{\jmath}_{k})+\tilde{u}^{i}_{k}.$

If the edge $\tilde{e}_{k}$ is a transition edge, then we can get (4.5)
similarly; we just need to replace the travel costs by the switching costs. ∎

###### Theorem 6.7.

The MFG equations hold if all vertices are regular in the Wardrop model.

###### Proof.

In Proposition 6.1, we proved the correspondence between the currents and the
balance equations. In Proposition 6.6, we proved the correspondence between
the value functions and the optimality equations. Hence, the MFG equations are
satisfied. ∎

By this, we proved that we can recover the solution of an MFG problem,
$(\bm{u},\bm{{\jmath}^{*}})$ from the curents of the corresponding Wardrop
problem, $\bm{\tilde{{\jmath}}^{*}}$.

##  7 Cost properties

In this section, we study the properties of the cost implied by the
microstructure of the MFG in a single edge. We begin by addressing
reversibility, and then we examine monotonicity.

###  7.1 Reversibility of the cost

Now, we study the reversibility of the costs; that is, whether for a given
current, the travel direction of a single agent is the same whether he/she
travels against to/with the current. In reversible MFG, agents’ costs are
insensitive to the direction of travel and only depend on the density of other
agents.

###### Proposition 7.1.

If the Hamiltonian is an even function in $p$, i.e., $H(x,-p,m)=H(x,p,m)$, and
strictly convex, then we have the following

  1. 1.

The cost is reversible; that is, $c_{01}(j)=c_{10}(j),\ \forall
j\in\mathbb{R}$.

  2. 2.

The cost is even; that is, $c_{01}(-j)=c_{01}(j),\ \forall j\in\mathbb{R}$.

###### Proof.

Since $H$ is even, $L$ is also even, i.e.,

$L(x,-v,m)=L(x,v,m).$

The density $m$ is determined by solving (3.18). For $j>0$, traveling from $0$
to $1$, the optimal velocity is $v=\frac{j}{m}$, which solves the necessary
optimality condition (3.11). For same $j$ and $m$, we look at the optimal
trajectory connecting $1$ to $0$. We claim that the velocity $-v$ is optimal.
This is true because $-v$ also solves (3.11). Then, by (3.12), we have

$c_{01}(j)=c_{10}(j).$

Thus, the cost is reversible.

Now we prove the second statement. Consider the HJ equation in (3.1) and the
definition of the current in (3.2). If we replace $j$ by $-j$, $p=u_{x}$ by
$-p=-u_{x}$, and keep $m$ unchanged, the HJ in (3.1) holds because $H$ is even
and (3.2) holds because $D_{p}H$ is odd in $p$. Hence,

$m(x,-j)=m(x,j).$ (7.1)

Because $H$ is strictly convex, $L$ is strictly convex. Thus, by Proposition
3.5, there exists $v_{+}^{*}>0$ unique solution of (3.11) in $\mathbb{R}$ .
Using (7.1) in (3.11) we get

$v_{+}^{*}(x,-j)=v_{+}^{*}(x,j),\ \ \forall j.$

Similarly,

$v_{-}^{*}(x,-j)=v_{-}^{*}(x,j),\ \ \forall j.$

Then, (3.12) implies

$c_{01}(-j)=c_{01}(j).$

∎

###### Example 7.2 (Even Hamiltonian).

Suppose the Hamiltonian is

$H(x,p,m)=\frac{p^{2}}{2}-m.$

Then, the Lagrangian is

$L(x,v,m)=\frac{v^{2}}{2}+m.$

The corresponding MFG system is

$\begin{cases}\frac{u_{x}^{2}}{2}=m,\\\ (-mu_{x})_{x}=0.\end{cases}$

The density $m$ is obtained by substituting $u_{x}=-\frac{j}{m}$ in the HJ
equation, which gives the identity

$\frac{1}{2}\left(-\frac{j}{m}\right)^{2}=m.$

Accordingly,

$m=\left(\frac{j^{2}}{2}\right)^{1/3}.$

On the other hand, (3.14) implies

$v=(2m)^{1/2}.$

Hence, substituting the formula for $m$ in the previous identity, we get

$v=\left(2\left(\frac{j^{2}}{2}\right)^{1/3}\right)^{1/2}.$

Then, by (3.12), the cost is

$c_{01}(j)=\int_{0}^{1}2^{1/3}|j|^{1/3}dx=2^{1/3}|j|^{1/3}.$

This cost is independent of the sign of $j$ because the Hamiltonian is even.
We can see this using (3.20), where we get the same cost

$c_{01}(j)=\int_{0}^{1}\frac{j}{m}=\frac{j}{(j^{2}/2)^{1/3}}=(2j)^{1/3}.$

###  7.2 Monotonicity of the costs

For general MFGs of the form (3.1), under the monotonicity condition

$\displaystyle\begin{bmatrix}-\frac{2}{m}D_{m}H&D^{2}_{pm}H\\\
D^{2}_{pm}H&2D^{2}_{pp}H\end{bmatrix}\geqslant 0,$ (7.2)

the uniqueness of the solution in several cases was proved in [Lio08] (also
see [Por14]). As we see next, this condition is relevant for the monotonicity
of the costs.

###### Proposition 7.3.

For $j>0$, the following holds

$\displaystyle\begin{bmatrix}\frac{\partial c_{01}}{\partial j}\\\
\frac{\partial m}{\partial
j}\end{bmatrix}=\frac{1}{(D_{p}H)^{2}+mD_{p}HD_{pm}^{2}H-mD_{m}HD_{pp}^{2}H}\begin{bmatrix}-D_{m}H\\\
-D_{p}H\end{bmatrix}.$ (7.3)

Moreover, if (7.2) holds, then

$\frac{\partial c_{01}}{\partial j}\geqslant 0.$

For $j<0$, the following holds

$\displaystyle\begin{bmatrix}\frac{\partial c_{10}}{\partial j}\\\
\frac{\partial m}{\partial
j}\end{bmatrix}=\frac{1}{-(D_{p}H)^{2}+mD_{p}HD_{pm}^{2}H+mD_{m}HD_{pp}^{2}H}\begin{bmatrix}-D_{m}H\\\
D_{p}H\end{bmatrix}.$ (7.4)

Moreover, if (7.2) holds, then

$\frac{\partial c_{10}}{\partial j}\leqslant 0.$

###### Proof.

Assuming $j>0$, and differentiating (3.15) with respect to $j$, we get

$\begin{cases}\begin{aligned} &-D_{p}H(x,-c_{01},m)\frac{\partial
c_{01}}{\partial j}+D_{m}H(x,-c_{01},m)\frac{\partial m}{\partial j}=0,\\\
&mD^{2}_{pp}H(x,-c_{01},m)\frac{\partial c_{01}}{\partial
j}-\left(D_{p}H(x,-c_{01},m)+mD^{2}_{pm}H(x,-c_{01},m)\right)\frac{\partial
m}{\partial j}=1,\end{aligned}\end{cases}$ (7.5)

where $c_{01}=c_{01}(x,j)$ and $m=m(x,j)$. The solution of (7.5) is given by
(7.3), which proves the first result.

For the second result, notice that $D_{m}H\leqslant 0$ and the determinant of
the matrix in (7.2) is

$A=-\frac{4}{m}D_{m}HD^{2}_{pp}H-(D^{2}_{pm}H)^{2}\geqslant 0.$

Using this and by Cauchy’s inequality, we get that the denominator in (7.3)
satisfies

$\displaystyle M=(D_{p}H)^{2}+mD_{p}HD_{pm}^{2}H-mD_{m}HD_{pp}^{2}H$
$\displaystyle\geqslant(D_{p}H)^{2}-(D_{p}H)^{2}-\frac{1}{4}m^{2}(D^{2}_{pm}H)^{2}-D_{m}HD^{2}_{pp}Hm$
$\displaystyle=\frac{Am^{2}}{4}\geqslant 0.$

Consequently, (7.2) implies

$\frac{\partial c_{01}}{\partial j}\geqslant 0.$

The proof for the case $j<0$ is similar. ∎

###### Remark 7.4.

If $D_{m}H(x,-c_{01},m)\leqslant 0$, then $m$ and $c_{01}$ have the same
monotonicity with respect to $j$ and opposite otherwise. This is so because we
have by the first equation in (7.5) that

$\frac{\partial c_{01}}{\partial
j}=-\frac{mD_{m}H(x,-c_{01},m)}{j}\frac{\partial m}{\partial j}.$ (7.6)

The condition (7.2) is not necessary for the monotonicity of the cost, as we
show in the following example for separable Hamiltonians.

###### Example 7.5.

Suppose $H$ is separable, that is, of the form $H(x,p,m)-g(m)$. Then

$D^{2}_{pm}H=0\ \text{and}\ D_{m}H=-g^{\prime}(m).$

From (7.3), we get

$\frac{\partial c_{01}}{\partial
j}=\frac{g^{\prime}(m)}{(D_{p}H)^{2}+D_{pp}Hmg^{\prime}(m)}.$ (7.7)

If $g^{\prime}(m)>0$ then $\frac{\partial c_{01}}{\partial j}\geqslant 0$. If
$g^{\prime}(m)<0$, the analysis is more delicate.

Let $\gamma>1$. Consider the case where

$H(p,m)=\frac{|p|^{\gamma}}{\gamma}-g(m).$

Then, we have

$\displaystyle D_{p}H(p,m)=p|p|^{\gamma-2},$ $\displaystyle
D_{p}H(p,m)^{2}=|p|^{2\gamma-2}\implies(D_{p}H(-c_{01},m))^{2}=(\gamma
g(m))^{2-\frac{2}{\gamma}},$ $\displaystyle
D^{2}_{pp}H(p,m)=(\gamma-1)|p|^{\gamma-2}\implies
D^{2}_{pp}H(-c_{01},m)=(\gamma-1)(\gamma g(m))^{1-\frac{2}{\gamma}}.$

Substituting in (7.7), we get

$\frac{\partial c_{01}}{\partial j}=\frac{g^{\prime}(m)}{(\gamma
g(m))^{2-\frac{2}{\gamma}}+(\gamma-1)(\gamma
g(m))^{1-\frac{2}{\gamma}}mg^{\prime}(m)}.$ (7.8)

Thus, to get $\frac{\partial c_{01}}{\partial j}\geqslant 0$ when
$g^{\prime}(m)<0$, we need

$\gamma g(m)+(\gamma-1)mg^{\prime}(m)\leqslant 0.$ (7.9)

A case where the prior inequality holds is the following. Consider

$g(m)=m^{-\beta},\ \beta>0.$

Then, (7.9) becomes

$\gamma-(\gamma-1)\beta\leqslant 0.$

Hence, for $\beta\geqslant\frac{\gamma}{\gamma-1},$ we have $\frac{\partial
c_{01}}{\partial j}\geqslant 0$.

Now, we study the monotonicity of $c_{01}$ for $j\leqslant 0$. In this case,
agents are traveling against the current, so we cannot use the result in
Proposition 3.9 to compute $c_{01}$.

###### Proposition 7.6.

For $j<0$, the following holds

$\frac{\partial c_{01}(j)}{\partial
j}=\int_{0}^{1}{\frac{1}{v^{*}_{+}}D_{m}L(x,v^{*}_{+}(x,j),m(x,j))\frac{\partial
m(x,j)}{\partial j}}dx.$ (7.10)

Moreover, if (7.2) holds, then

$\frac{\partial c_{01}(j)}{\partial j}\leqslant 0.$ (7.11)

###### Proof.

To simplify the notation, we will write $v$ instead of $v^{*}_{+}$. We write
(3.14) as follows

$v(x,j)D_{v}L(x,v(x,j),m(x,j))-L(x,v(x,j),m(x,j))=0.$

Then, we differentiate with respect to $j$ to get

$\displaystyle v(x,j)D^{2}_{vv}L(x,v(x,j),m(x,j))\frac{\partial
v(x,j)}{\partial j}+v(x,j)D^{2}_{vm}L(x,v(x,j),m(x,j))\frac{\partial
m(x,j)}{\partial j}$ (7.12) $\displaystyle-
D_{m}L(x,v(x,j),m(x,j))\frac{\partial m(x,j)}{\partial j}=0.$

Also, differentiating (3.12) with respect to $j$, we get

$\displaystyle\frac{\partial c_{01}(j)}{\partial
j}=\int_{0}^{1}D^{2}_{vv}L(x,v(x,j),m(x,j))\frac{\partial v(x,j)}{\partial j}$
$\displaystyle+D^{2}_{vm}L(x,v(x,j),m(x,j))\frac{\partial m(x,j)}{\partial
j}dx.$

Substituting $D^{2}_{vv}L(x,v(x,j),m(x,j))\frac{\partial v(x,j)}{\partial j}$
from (7.12), we get (7.10). To prove the second result, notice that in (7.10),
we have

$\frac{1}{v^{*}_{+}}D_{m}L(x,v^{*}_{+}(x,j),m(x,j))\geqslant 0,$

and by (7.4), we have

$\frac{\partial m(x,j)}{\partial j}\leqslant 0.$

Thus, we get (7.11). ∎

###  7.3 Analysis of the velocity field

Lions’ monotonicity condition (7.2) is related to crowd aversion; that is,
agents try to avoid congested areas. As we have shown before, in this case,
both $c$ and $m$ increase with $j$. It is possible, however, to have a crowd-
seeking behavior, that is, $g$ is decreasing, with $c$ increasing in $j$ and
$m$ decreasing in $j$. This is something that happens in uncongested highways.
As speed increases, cars increase their distances. Hence, density decreases.
Here, we would like to investigate the dependence of the optimal velocity
field

$v(x,j)=\frac{j}{m(x,j)}$ (7.13)

on the current and on the density. We begin with the dependence on the
current.

###### Proposition 7.7.

Let $M=(D_{p}H)^{2}+mD_{p}HD_{pm}^{2}H-mD_{pp}^{2}HD_{m}H$. For $j>0$

$\frac{\partial}{\partial
j}\left[v(x,j)\right]=-\frac{vD^{2}_{pm}H+D^{2}_{pp}HD_{m}H}{M}.$

Moreover, in the separable case, if Lions condition holds, then

$\frac{\partial}{\partial j}\left[v(x,j)\right]\leqslant 0.$

If the reverse Lions’ condition holds (that is; (7.2) holds with opposite
inequality), then

$\frac{\partial}{\partial j}\left[v(x,j)\right]\geqslant 0.$

###### Proof.

Differentiating (7.13), with respect to $j$, we get

$\frac{\partial}{\partial
j}\left[v(x,j)\right]=\frac{1}{m}-\frac{j}{m^{2}}\frac{\partial m}{\partial
j}.$

From (7.3) and using that $v(x,j)=-D_{p}H(x,u_{x}(x,j),m(x,j))$, we have

$\frac{\partial m(x,j)}{\partial j}=\frac{-D_{p}H}{M}=\frac{j}{mM},$ (7.14)

Hence,

$\frac{\partial}{\partial
j}\left[v(x,j)\right]=\frac{1}{m}\left[1-\frac{j^{2}}{m^{2}}\frac{1}{M}\right]=-\frac{vD^{2}_{pm}H+D^{2}_{pp}HD_{m}H}{M}.$

In the separable case, we have

$\frac{\partial}{\partial
j}\left[v(x,j)\right]=-\frac{D^{2}_{pp}Hg^{\prime}(m)}{M}.$ (7.15)

If Lions’ condition holds, then by Proposition 7.3, $M\geqslant 0$. Thus,

$\frac{\partial}{\partial j}\left[v(x,j)\right]\leqslant 0.$

If the reverse Lions’ condition holds, we get the opposite inequality. ∎

Now, we study the relation between the velocity and the density through the
quantity $\frac{\partial m}{\partial v}$, which corresponds to the uncongested
model when it is greater or equal to zero.

###### Proposition 7.8.

For $j>0$, in the separable case, we have

$\frac{\partial m}{\partial v}=-\frac{v}{D^{2}_{pp}Hg^{\prime}(m)}.$ (7.16)

###### Proof.

We have

$\frac{\partial m}{\partial v}=\frac{\partial m}{\partial j}.\frac{\partial
j}{\partial v}.$

By (7.14) and (7.15), we get

$\frac{\partial m}{\partial
v}=-\frac{j}{mM}.\frac{M}{D^{2}_{pp}Hg^{\prime}(m)},$

which gives (7.16) after simplification. ∎

###### Remark 7.9.

From (7.16), we see that if $g(m)$ increasing, $m$ decreases with $v$. Whereas
if $g(m)$ decreasing, $m$ increases with $v$.

#### A summary

Now, we summarize the results in this section. In highways or pedestrian
traffic, we expect that as $j$ increases, $m$ increases and $v$ decreases. For
separable $H$, and $j>0$, if Lions’ condition (7.2) holds, then

  1. 1.

$c_{01}$ increases as $j$ increases, see Proposition 7.3.

  2. 2.

$m$ increases as $j$ increases, see Proposition 7.3.

  3. 3.

$v$ decreases as $j$ increases. see Proposition 7.7.

However, Lions’ condition is not needed for the previous points to hold.
Example 7.5 gives conditions under which $1$ and $3$ hold without
monotonicity. However, $2$ does not hold; see Remark 7.4.

##  8 Calibration of MFGs

In this section, we address Problem 1; that is, the precise correspondence
between MFG and Wardrop models. To study it in more detail, we consider the
following two inverse problems:

###### Problem 2.

Let $W$ be a Wardrop model on a single edge, identified with the interval
$[0,1]$ with $c:\mathbb{R}_{0}^{+}\to\mathbb{R}^{+}$ a reversible current-
dependent travel cost. Find $L$ such that, for any current $j$,

$\int_{0}^{T(j)}L(x,v,m)ds=c(j),$ (8.1)

where $T(j)>0$ is the crossing time for an agent moving at optimal speed.

###### Problem 3.

Let $W$ be a Wardrop model on a single edge, identified with the interval
$[0,1]$ with $c:\mathbb{R}_{0}^{+}\to\mathbb{R}^{+}$ a reversible current-
dependent travel cost. Find $L$ such that, for any current $j$,

$\int_{0}^{T(j)}L(x,v,m)ds=c(j),\ \text{and}\ T(j)=c(j).$ (8.2)

where $T(j)>0$ is the crossing time for an agent moving at optimal speed.

While Problem 2 may seem more natural, Problem 3 is more straightforward to
calibrate as it is enough to measure average speed $v$ as a function of
current to get the cost $c(j)$. In general, we are not aware of any other way
to assign a travel cost depending on the current.

The solution to these problems is not unique, and any solution can be used to
generate a MFG model associated with the cost $c$. One of the reasons for non-
uniqueness is that there are no microscopic effects in Wardrop models. In
Section 8.1, we work with a specific class of Lagrangians and illustrate how
to solve these problems. In particular, we work with $x$-independent
Lagrangians. There is no uniqueness in this class; see Example 8.1.

###  8.1 Identification of Wardrop cost problems with mean-field games

In Problem 2, we identify a corresponding MFG model whose travel cost on an
edge, for a given current $j$, is $c(j)$. We assume that agents travel from 0
to 1. Thus, the current is positive. We do not expect to recover the MFG
microstructure from the Wardrop model’s macrostructure, so we consider
Lagrangians without $x$-dependency. To have reversible costs, we consider
Lagrangians which are even in the velocity. More concretely, we restrict our
choice to

$L(x,v,m)=m^{\alpha}\mathcal{L}(v)+g(m),$ (8.3)

with $\mathcal{L}$ convex and even. This class is broad enough to include
interesting examples and specific enough that we can get closed formulas/
models for the cost. Because the Lagrangian is even and the cost is
reversible, solving the problem for $j>0$ is enough. Moreover, since there are
no location preferences in the edge, the incremental cost of the travel is the
same everywhere; that is, $u_{x}$ is constant in $x$. Therefore, the density
is constant, i.e., $m=m(j)$, as we can see from the MFG system. The
corresponding MFG is equivalent to

$\begin{cases}m^{\alpha}\mathcal{H}\left(\frac{u_{x}}{m^{\alpha}}\right)=g(m)\\\
-m\mathcal{H}^{\prime}\left(\frac{u_{x}}{m^{\alpha}}\right)=j,\end{cases}$
(8.4)

where $\mathcal{H}$ is the Legendre transform of $\mathcal{L}$. Following the
same steps as before, we find

$u_{x}=-m^{\alpha}\mathcal{L}^{\prime}\left(\frac{j}{m}\right).$ (8.5)

From the second equation in (8.4) and the relation
$-\mathcal{L}^{\prime}(-\mathcal{H}^{\prime}(p))=p$, we transform the MFG
system into the algebraic system

$\begin{cases}m^{\alpha}\mathcal{H}\left(-\mathcal{L}^{\prime}\left(\frac{j}{m}\right)\right)=g(m)\\\
c(j)=u(0)-u(1)=m^{\alpha}\mathcal{L}^{\prime}\left(\frac{j}{m}\right),\end{cases}$
(8.6)

provided $m>0$. Suppose that the last equation in (8.6) is solvable for $m$
and $j$, i.e. there exists an invertible function $\Psi_{c}$ such that

$m=\Psi_{c}(j).$ (8.7)

Now, let
$\Phi_{j}(m):=m^{\alpha}\mathcal{L}^{\prime}\left(\frac{j}{m}\right)$. Then,
by (8.7) and the last equation in (8.6), we have

$\Psi_{c}(j)=m=\Phi_{j}^{-1}(c(j)).$

Hence, we get

$\Psi_{c}^{-1}(j)=c^{-1}(\Phi_{j}(j)).$

Hence, $\Psi_{c}$ is well defined, at least locally, if
$m\rightarrow\Phi_{j}(m)$ is strictly monotone in $m$ for every $j$. If, in
addition, $c$ is strictly monotone, then $\Psi_{c}$ is invertible. Now,
inverting (8.7) and substituting in the first equation of (8.6), we get

$m^{\alpha}\mathcal{H}\left(-\mathcal{L}^{\prime}\left(\frac{\Psi_{c}^{-1}(m)}{m}\right)\right)=g(m).$
(8.8)

This relation identifies $g(m)$ in terms of $c,\mathcal{L}^{\prime}$ and
$\mathcal{H}$.

Next, we show an example that applies the previous discussion to solve the
inverse problem.

###### Example 8.1.

Let $\alpha\neq 1$, and $\beta>0$. Consider the Lagrangian,
$\mathcal{L}(v)=\beta\frac{v^{2}}{2}$, with corresponding Hamiltonian,
$\mathcal{H}(p)=\frac{p^{2}}{2\beta}$. The system (8.6) becomes

$\begin{cases}m^{\alpha-2}\beta j^{2}=2g(m)\\\ c(j)=m^{\alpha-1}\beta
j,\end{cases}$ (8.9)

provided $m>0$. The second equation gives, for $\alpha\neq 1$, $m$ as a
function of $j$:

$m=\left(\frac{c(j)}{\beta j}\right)^{\frac{1}{\alpha-1}}=:\Psi_{c}(j).$
(8.10)

Thus, if $\Psi_{c}$ is invertible, we obtain

$g(m)=\frac{\beta}{2}m^{\alpha-2}\left(\Psi_{c}^{-1}(m)\right)^{2}.$

Now, consider a linear cost, $c(j)=c_{1}+c_{2}j$. By (8.10), the density is

$m=\left(\frac{c_{1}}{\beta
j}+\frac{c_{2}}{\beta}\right)^{\frac{1}{\alpha-1}}.$

Assuming $c_{1},c_{2}\geqslant 0$, the range of $m$ is

$\begin{cases}\left[\left(\frac{c_{2}}{\beta}\right)^{\frac{1}{\alpha-1}},+\infty\right),\
\ \text{for}\ \ \alpha>1.\\\
\left(0,\left(\frac{c_{2}}{\beta}\right)^{\frac{1}{\alpha-1}}\right),\ \
\text{for}\ \ \alpha<1.\end{cases}$ (8.11)

For our linear cost, $\Psi_{c}$ is invertible and we have

$g(m)=\frac{\beta m^{\alpha-2}c_{1}^{2}}{2\left(\beta
m^{\alpha-1}-c_{2}\right)^{2}},$

which can be written as follows

$g(m)=\frac{1}{2\beta}\frac{c_{1}^{2}}{\left(m^{\alpha/2}-\frac{c_{2}}{\beta}m^{1-\alpha/2}\right)^{2}}.$

Fig. 7: For $\alpha=0.1$, $\frac{1}{g(m)}$ touches 0 at two points. Fig. 8:
For $\alpha=3$, $\frac{1}{g(m)}$ touches 0 at one point.

Note that such $g$ is non-monotone. For $\alpha<1$, it has one singularity at
0 and another one at
$m_{0}=\left(\frac{c_{2}}{\beta}\right)^{\frac{1}{\alpha-1}}$. This last value
$m_{0}$ is the maximal density. For $\alpha>1$, there is a singularity at
$m_{0}$, but it is a minimal density in this case. This is illustrated in
Figure 7 where we plot $\frac{1}{g(m)}$ for $\alpha=0.1$ and Figure 8 where we
plot $\frac{1}{g(m)}$ for $\alpha=3$, with $\beta=1$, $c_{1}=1$ and
$c_{2}=0.9$ in both figures.

The preceding example illustrates an important point: even with the simple
linear current-dependent cost, we obtain a coupling function $g(m)$ that is
non-monotone which falls outside standard MFG theory. If $\alpha<1$, $g(m)$ is
neither decreasing nor increasing for the values of $m$ in (8.11). For
$\alpha>1$, $g(m)$ is decreasing for the values of $m$ that satisfy (8.11).

###  8.2 Identification of Wardrop time problems with mean-field games

Now, we consider Problem 3. As discussed in Section 7.3, the optimal velocity
is $v=\frac{j}{m}$. Because the edge has length $1$ and the velocity, $v$, is
constant, we have

$T=\frac{m}{j}.$

To address this problem, we consider $L$ as in (8.3). In this case, we show
how to determine both $\mathcal{L}$ and $g$. Arguing as in Section 8.1, we
obtain

$\begin{cases}m^{\alpha}\mathcal{H}\left(-\mathcal{L}^{\prime}\left(\frac{j}{m}\right)\right)=g(m)&\\\
m^{\alpha}\mathcal{L}^{\prime}\left(\frac{j}{m}\right)=c(j)&\\\
c(j)=\frac{m}{j},\end{cases}$ (8.12)

provided $m>0$. As before, we study the case $j>0$. From the last equation in
(8.12), we get

$m=jc(j),\ \forall j>0.$ (8.13)

Let $\Psi_{c}(j)=jc(j)$, if $c$ is positive and increasing, then $\Psi_{c}(j)$
is invertible. Hence,

$j=\Psi_{c}^{-1}(m).$

Moreover, in this case, $m$ can take any value in $\mathbb{R}^{+}$. Using the
prior identity, we substitute $j$ in the second equation of (8.12). Next, we
use the result in the first equation of (8.12) to get

$g(m)=m^{\alpha}\mathcal{H}\left(-\frac{c(\Psi_{c}^{-1}(m))}{m^{\alpha}}\right).$
(8.14)

Up to here, $\mathcal{L}$ is an unknown. Now, we substitute $m$ from (8.13) in
the second equation in (8.12) to get

$\mathcal{L}^{\prime}\left(\frac{1}{c(j)}\right)=\frac{c(j)}{\left(jc(j)\right)^{\alpha}}.$

Finally, recalling that $v=1/c(j)$, we have

$\mathcal{L}^{\prime}\left(v\right)=\frac{v^{\alpha-1}}{\left(c^{-1}\left(\frac{1}{v}\right)\right)^{\alpha}}.$
(8.15)

If $c$ is increasing, the preceding expression defines
$\mathcal{L}^{\prime}(v)$ for $\lim_{j\to\infty}\frac{1}{c(j)}\leqslant
v\leqslant\frac{1}{c(0)}$. Thus, $\frac{1}{c(0)}$ is the maximal velocity. So,
to solve the inverse problem, we first use (8.15) to identify $\mathcal{L}$,
compute its Legendre transform $\mathcal{H}$ and use (8.14) to obtain $g$.

In the following example, we look at a simple cost structure, affine in $j$,
and show that non-monotone MFGs may arise.

###### Example 8.2.

Suppose $c(j)=1+j$. We want to find $\mathcal{L}$ and $g$ for which the cost
is $c(j)$. The system (8.12) simplifies to

$\begin{cases}g(m)=m^{\alpha}\mathcal{H}\left(-\frac{2m^{1-\alpha}}{\sqrt{1+4m}-1}\right),\\\
\mathcal{L}^{\prime}(v)=\frac{v^{2\alpha-1}}{(1-v)^{\alpha}}\\\
v=\frac{1}{1+j}\\\ m=j(1+j).\end{cases}$

The Lagrangian is convex if $\alpha\geqslant\frac{1}{2}$. However, the
resulting coupling may fail to be monotone, as Figure 9 illustrates.

Fig. 9: The coupling $g(m)$ decreasing with $m$, for $\alpha=0.6$.

###  8.3 Example: Braess paradox

Now, we present an application for the calibration of MFGs in Wardrop
problems. In particular, we show how the celebrated Braess paradox can arise
in MFGs.

###### Example 8.3 (Braess paradox).

Fig. 10: Braess paradox network

Consider the network in Figure 10 with the given costs. Agents want to move
from the entrance vertex $v_{1}$ to the exit vertex $v_{4}$ through the
network with the least travel cost. Assume that the exit cost is zero and the
entry current is $4000$. At $v_{1}$, half of the agents will go through the
edge $e_{1}$, and the other half will use the edge $e_{2}$ at the cost of
$65$. If we add a new edge $e_{5}=(v_{2},v_{3})$, as Figure 11 illustrates,
with zero travel cost, some agents will choose to take the path
$e_{2},e_{5},e_{3}$. If all agents are taking this path, this is a Wardrop
equilibrium. By adding $e_{5}$, the cost increases for everyone. This is the
well-known Braess paradox.

Fig. 11: Braess paradox network with edge in the middle.

Since we proved in Section 6 that MFGs can be recovered through Wardrop
problems, a natural question is which MFGs give rise to the particular cost
structure of the Braess paradox? The answer to this question is given by the
following computations that determine the MFG for the Braess paradox. For the
edges $e_{3}$ and $e_{2}$, we obtain, for $\alpha>\frac{1}{2}$,

$L(v)=\frac{|v|^{2\alpha}}{2\alpha 100^{\alpha}}\qquad
H(p)=100^{\alpha}\frac{|p|^{\kappa}}{\kappa},$

with $\kappa=\frac{2\alpha}{2\alpha-1}$, and

$g(m)=C_{\alpha},\qquad C_{\alpha}=\frac{100^{(\alpha-1)\kappa}}{\kappa}.$

The constant costs do not fit the previous calibration. However, in $e_{1}$
and $e_{4}$, for small $\epsilon$, we can set the cost to

$c(j)=45+\epsilon|j|.$

Similarly, in the edge $e_{5}$, we set the cost to

$c(j)=\epsilon|j|.$

Acknowledgments: The authors were partially supported by King Abdullah
University of Science and Technology (KAUST) baseline funds and KAUST OSR-
CRG2021-4674.

F. Al Saleh acknowledges King Faisal University for their support.

## References

  * [ACCT13] Y. Achdou, F. Camilli, A.a Cutrì, and N. Tchou.  Hamilton-Jacobi equations constrained on networks.  NoDEA Nonlinear Differential Equations Appl., 20(3):413–445, 2013\.
  * [ADLT19] Y. Achdou, M.-K. Dao, O. Ley, and N. Tchou.  A class of infinite horizon mean field games on networks.  Netw. Heterog. Media, 14(3):537–566, 2019.
  * [ADLT20] Y. Achdou, M.-K. Dao, O. Ley, and N. Tchou.  Finite horizon mean field games on networks.  Calc. Var. Partial Differential Equations, 59(5):Paper No. 157, 34, 2020.
  * [AMMT] Y. Achdou, P. Manuci, C. Marchi, and N Tchou.
  * [AMMT20] Y. Achdou, P. Mannucci, C. Marchi, and N. Tchou.  Deterministic mean field games with control on the acceleration.  NoDEA Nonlinear Differential Equations Appl., 27(3):Paper No. 33, 32, 2020.
  * [BB12] F. Bagagiolo and M. Benetton.  About an optimal visiting problem.  Appl. Math. Optim., 65(1):31–51, 2012.
  * [BD11] N. Bellomo and C. Dogbe.  On the modeling of traffic and crowds: A survey of models, speculations, and perspectives.  SIAM review, 53(3):409–463, 2011.
  * [BDFMW14] M. Burger, M. Di Francesco, P. A. Markowich, and M.-T Wolfram.  Mean field games with nonlinear mobilities in pedestrian dynamics.  Discrete Contin. Dyn. Syst. Ser. B, 19(5):1311–1333, 2014.
  * [BFMP19] F Bagagiolo, Silvia Faggian, Rosario Maggistro, and Raffaele Pesenti.  Optimal control of the mean field equilibrium for a pedestrian tourists’flow model.  Networks and Spatial Economics, 2019.
  * [BM] F Bagagiolo and L. Marzufero.
  * [BMP11] M. Burger, P. A. Markowich, and J.-F. Pietschmann.  Continuous limit of a crowd motion and herding model: analysis and numerical simulations.  Kinet. Relat. Models, 4(4):1025–1047, 2011.
  * [BMP21] F. Bagagiolo, R. Maggistro, and R. Pesenti.  Origin-to-destination network flow with path preferences and velocity controls: a mean field game-like approach.  J. Dyn. Games, 8(4):359–380, 2021.
  * [BZP14] D. Bauso, X. Zhang, and A. Papachristodoulou.  Density flow over networks: A mean-field game theoretic approach.  Proceedings of the IEEE Conference on Decision and Control, 2015-February(February):3469–3474, 2014.
  * [CCM15] F. Camilli, E. Carlini, and C Marchi.  A model problem for mean field games on networks.  Discrete Contin. Dyn. Syst., 35(9):4173–4192, 2015.
  * [CCM17] S. Cacace, F. Camilli, and C. Marchi.  A numerical method for mean field games on networks.  ESAIM Math. Model. Numer. Anal., 51(1):63–88, 2017.
  * [CDMT17] F. Camilli, R. De Maio, and A. Tosin.  Transport of measures on networks.  Netw. Heterog. Media, 12(2):191–215, 2017.
  * [CJS08] G. Carlier, C. Jimenez, and F. Santambrogio.  Optimal transportation with traffic congestion and Wardrop equilibria.  SIAM J. Control Optim., 47(3):1330–1350, 2008.
  * [CM13] F. Camilli and C. Marchi.  A comparison among various notions of viscosity solution for Hamilton-Jacobi equations on networks.  J. Math. Anal. Appl., 407(1):112–118, 2013.
  * [CM16] F. Camilli and C. Marchi.  Stationary mean field games systems defined on networks.  SIAM J. Control Optim., 54(2):1085–1103, 2016.
  * [CMS13] F. Camilli, C. Marchi, and D. Schieborn.  The vanishing viscosity limit for Hamilton-Jacobi equations on networks.  J. Differential Equations, 254(10):4122–4143, 2013.
  * [CS11] G. Carlier and F. Santambrogio.  A continuous theory of traffic congestion and Wardrop equilibria.  Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 390(Teoriya Predstavleniĭ, Dinamicheskie Sistemy, Kombinatornye Metody. XX):69–91, 307–308, 2011.
  * [CSM11] J. R. Correa and N. E. Stier-Moses.  Wardrop Equilibria.  American Cancer Society, 2011.
  * [DTT17] B. Djehiche, A. Tcheukam, and H. Tembine.  A mean-field game of evacuation in mutlilevel building.  IEEE Trans. Automat. Control, 62(10):5154–5169, 2017.
  * [GHP16] M. Garavello, K. Han, and B. Piccoli.  Models for vehicular traffic on networks, volume 9 of AIMS Series on Applied Mathematics.  AIMS, Springfield, MO, 2016.
  * [GMAS19] D. Gomes, D. Marcon, and F. Al Saleh.  The current method for stationary mean-field games on networks.  In 58th IEEE Conference on Decision and Control, CDC 2019, Nice, France, December 11-13, 2019, pages 305–310. IEEE, 2019.
  * [GNP16] D. Gomes, L. Nurbekyan, and M. Prazeres.  Explicit solutions of one-dimensional, first-order, stationary mean-field games with congestion.  2016 IEEE 55th Conference on Decision and Control, CDC 2016, pages 4534–4539, 2016.
  * [GNP17] D. Gomes, L. Nurbekyan, and M. Prazeres.  One-dimensional stationary mean-field games with local coupling.  Dyn. Games and Applications, 2017.
  * [HMC06] 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(3):221–251, 2006.
  * [IMZ13] Imbert, Cyril, Monneau, Régis, and Zidani, Hasnaa.  A hamilton-jacobi approach to junction problems and application to traffic flows.  ESAIM: COCV, 19(1):129–166, 2013.
  * [ISM17] R. Iturriaga and H. Sánchez Morgado.  The Lax-Oleinik semigroup on graphs.  Netw. Heterog. Media, 12(4):643–662, 2017.
  * [Lio08] P.-L. Lions.  Cours au Collège de France.  www.college-de-france.fr, 2007-2008.
  * [LL06] J.-M. Lasry and P.-L. Lions.  Jeux à champ moyen. I. Le cas stationnaire.  C. R. Math. Acad. Sci. Paris, 343(9):619–625, 2006.
  * [LS16] P. Lions and P. Souganidis.  Viscosity solutions for junctions: well posedness and stability.  Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl., 27(4):535–545, 2016.
  * [LS17] P. Lions and P. Souganidis.  Well-posedness for multi-dimensional junction problems with Kirchoff-type conditions.  Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl., 28(4):807–816, 2017.
  * [LW11] A. Lachapelle and M.-T. Wolfram.  On a mean field game approach modeling congestion and aversion in pedestrian crowds.  Transportation Research Part B: Methodological, 45:1572–1589, 2011\.
  * [Por14] A. Porretta.  On the planning problem for the mean field games system.  Dyn. Games Appl., 4(2):231–256, 2014.
  * [SC13] D. Schieborn and F. Camilli.  Viscosity solutions of Eikonal equations on topological networks.  Calc. Var. Partial Differential Equations, 46(3-4):671–686, 2013\.
  * [Smi79] M.J. Smith.  The existence, uniqueness and stability of traffic equilibria.  Transportation Research Part B: Methodological, 13(4):295–304, 1979\.
  * [SS18] A. Siconolfi and A. Sorrentino.  Global results for eikonal Hamilton-Jacobi equations on networks.  Anal. PDE, 11(1):171–211, 2018.
  * [War52] J G Wardrop.  Some theoretical aspects of road traffic research.  Proceedings of the Institution of Civil Engineers, 1(3):325–362, 1952.