# A time-dependent switching mean-field game on networks motivated by optimal
visiting problems

Fabio Bagagiolo  Dipartimento di Matematica
Università di Trento
Via Sommarive, 14, 38123 Povo (TN) Italy<EMAIL_ADDRESS>and
Luciano Marzufero  Dipartimento di Matematica
Università di Trento
Via Sommarive, 14, 38123 Povo (TN) Italy<EMAIL_ADDRESS>
###### Abstract.

Motivated by an optimal visiting problem, we study a switching mean-field game
on a network, where both a decisional and a switching time-variable are at
disposal of the agents for what concerns, respectively, the instant to decide
and the instant to perform the switch. Every switch between the nodes of the
network represents a switch from $0$ to $1$ of one component of the string
$p=(p_{1},\ldots,p_{n})$ which, in the optimal visiting interpretation, gives
information on the visited targets, being the targets labeled by
$i=1,\ldots,n$. The goal is to reach the final string $(1,\ldots,1)$ in the
final time $T$, minimizing a switching cost also depending on the congestion
on the nodes. We prove the existence of a suitable definition of an
approximated $\varepsilon$-mean-field equilibrium and then address the passage
to the limit when $\varepsilon$ goes to $0$.

###### Key words and phrases:

mean-field games, switching, networks, optimal visiting, optimal path,
impulsive continuity equations

###### 1991 Mathematics Subject Classification:

Primary 49N80; Secondary 05C21

This work was partially supported by MUR-PRIN2020 Project (No. 2020JLWP23)
“Integrated mathematical approaches to socio-epidemiological dynamics”

##  1\. Introduction

An optimal visiting problem in $\mathbb{R}^{d}$ is an optimal control problem
where an agent has to visit (touch) a finite number of fixed targets (regions
of $\mathbb{R}^{d}$) minimizing a suitable cost. The associated mean-field
game problem may consist in considering a huge population of agents (even
infinitely many) with the same goal and with the costs also depending on the
congestion of the population. In order to write a Dynamic Programming
Principle for the optimal visiting problem, some additional state-variables,
taking into account which targets have been already visited or not, must be
inserted. Such variables may be for example switching quantities as strings of
$0$ and $1$, where $1$ in the $i$-position means that the target $i$ has been
already visited and viceversa for $0$. Hence, starting from the string
$p_{o}=(0,\ldots,0)$, the goal can be seen as obtaining the string
$\bar{p}=(1,\ldots,1)$ paying as less as possible. Since all the possible
strings $p$ are in a finite number and the switches must follow a hierarchical
admissibility criterium, we interpret them as nodes of a direct network, where
$p_{o}$ is the origin and $\bar{p}$ is the final destination. The problem can
be seen then as the search for an optimal origin-destination path. Due to the
dynamical feature of the optimal visiting problem in $\mathbb{R}^{d}$, in our
network switching representation we keep the possibility for the agent to
choose the sequence of instants to perform the switches, within a fixed time
$T>0$. Again, the associated mean-field game consists in a huge population of
agents where the choice of the optimal path is also affected by a congestion
cost. In particular, the agents want to touch or spend time on the nodes of a
network, which represent the information on the visited targets, avoiding
queues and congested spots. Inspired by the dynamical model in [2], here we
present a model in a pure switching form which, in some way, takes anyway into
account a primitive structure of a continuous dynamics along the paths of a
network (which is not present here). The main goal is to prove the existence
of a mean-field equilibrium.

Our idea is then to study both the single-player problem and the crowd one
without a real dynamics, i.e., without a controlled continuous trajectory for
visiting the targets of the problem. For the single-player one, the state of
the system is represented by a discrete variable $p$, which basically
corresponds to the node of the network on which the agent is. Such a variable
acts also as a switching discrete control at the agent disposal, that is, once
the agent is on the node $p$, it has to choose optimally the next admissible
subsequent node $p^{\prime}$ after $p$. In this way, the agent switches to
$p^{\prime}$ and the state of the system becomes $p^{\prime}$. In performing
such a switch, the agent incurs a switching cost. A time-variable is accounted
for the problem too. In particular, besides the switching discrete control
variable $p$, the agent has to optimally choose the optimal time it is
convenient to switch to the next node of the network. Moreover, all the
admissible switches have to be performed within the fixed time $T$: if the
agent reaches the final node before $T$, it pays an earliness penalization
cost, while if it does not reach the final node and the time is over, it pays
a time-loseness penalization cost.

In the mean-field case, we study the behavior of infinitely many players that
have to solve the same single optimization problem as above, with the add of
some kind of congestion cost dependence in the switching costs. After studying
the single-player optimization problem and the properties of the corresponding
value function, we face the problem of the existence of a mean-field
equilibrium. This is done by performing a suitable fixed-point procedure for
an approximated problem, and then we address the passage to the limit in the
approximation. We need first an approximated problem because the switching
mass-evolution, solution of the mean-field equilibrium problem, turns out to
be piecewise continuous (even piecewise constant in some particular case) and
this fact makes the standard compactness and convexity requirements for fixed-
point results lacking in our case. Moreover, possibly due to non-uniqueness of
the optimal control, we have to work with set-valued functions and, similarly
as in [2], [7], we must consider agents splitting into fractions, each one of
them following one of the optimal behaviors. That suitably constructed and
rather new approximation leads then to Theorem 5.1, which proves the existence
of an approximated mean-field equilibrium via a fixed-point procedure for a
suitable set-valued map. The passage to the limit in the approximation is then
investigated in Theorem 6.1, by assuming a suitable hypothesis on the optimal
switching instants. Anyway, such a hypothesis can be satisfied by requiring
some suitable conditions on the costs (see Remark 3, the comments in §6.1 and
Appendix B).

As regards the uniqueness of the equilibrium, usually, in the mean-field games
theory, it is guaranteed by imposing a kind of monotonicity condition
satisfied by the costs with respect to the mass of the agents (see [21]). In
several cases, the adaptation of that property to uniqueness results does not
require too much work because the studied problem almost naturally fits that
condition. Our problem, due to many of its aspects, does not provide instead
an immediate evident way to adapt such a condition. However, inspired by [21],
in Appendix A, using a monotonicity-type property, we give some easy examples
and calculations which seem to be promising for a future and deeper study of
the uniqueness.

In general, as aforementioned, the study of single-player optimal visiting
problems requires an hybrid control framework in order to recover a dynamic
programming property and hence to derive an Hamilton-Jacobi equation. More
precisely, it requires a special framework able to include a memory of the
targets already visited. The need of that memory feature, associated with the
optimal visiting, dynamic programming and Hamilton-Jacobi equations has been
presented in [3, 4], where additional discrete state-variables were
introduced. The use of a switching/discontinuous/hybrid memory, as in the
present paper, was also used for a one-dimensional optimal visiting problem on
a network in [2], which basically inspired our model.

The model for a crowd of indistinguishable players is taken from the framework
of mean-field games [20, 19, 17, 12], while the adaptation of the same hybrid
structure to networks has been only very recently attempted, as in [2, 6] and,
more generally, in [10, 11]. For other studies in mean-field games on
networks, see also the recent preprint [1]. Some works which share the same
ideas to treat the mean-field case in the presence of switches in the dynamics
of the problem are [8, 7] and [4], where a mean-field optimal stopping
problem, possibly with sinks and sources, is discussed, and [16], where a
hybrid mean-field game is presented to model a multi-lane traffic flux of
vehicles. Moreover, other applications of a similar mean-field model can be
found in [23], where a continuous and a discrete set of switching labels are
introduced to study the case of a leader-follower dynamics. For what concerns
applicative motivations of our model, as already said, we start by the
overlying optimal visiting problem. For instance, such a problem complies with
tourists’ flow which has to visit several points of interest both in an
heritage city and in a museum environment (see [2], [13] and the references
therein). In [9] it is instead given an example of a situation where, in a
crowded environment, people have to perform a sequence of different operations
in different places, such as in big airports or train stations. Still
concerning the optimal visiting problem, but related to a single-player one,
in [5] it is given an example of a framework which is used to solve a series
of applied problems arising from the sport of orienteering races.

Finally, as we already said, we rewrite the optimal visiting problem as an
origin-to-destination one on a network, and of course the possible
applications and literature on this kind of problems are very huge. However,
our model seems to have other interesting applicative aspects as described
here below.

Other possible interpretations and applications of the model. Besides the
mainly motivating optimal visiting problem, another possible interpretation of
our model is as a mean-field game for the so-called (single-stage) optimal job
scheduling or for the similar open-shop scheduling problem in operations
research (see for example [25, 18]). In this model, every agent represents a
so-called job scheduler that has to produce its own optimal schedule. The
machines, given as datum of the problem, are supposed identical and they can
be interpreted as the targets of the visiting problem and then as the nodes of
the network. The jobs are also given as a datum and they are the tasks that
every job scheduler has to perform on each machine within the fixed time $T$.
The optimal time and the optimal node chosen by the agents in the optimization
process represent the processing time of a job (or of one or more operations)
that has to be worked on a machine. Furthermore, if an agent reaches the final
node (which means to have worked on all machines) before time $T$, then it has
to pay a penalization cost: every job scheduler has to spend enough time on
each machine to perform its job (or operations) and going faster may be
penalizing. In the mean-field game formulation we may have a huge number of
job-scheduler (agents) and hence, differently from the standard assumptions in
the job scheduling, every machine has to be able to work more than one job (or
more than one operation of a job) at a time. However, as usual, every job (or
operation) can not be processed simultaneously at more than one machine. Then,
the goal of every job scheduler is to optimize its schedule, minimizing a cost
which, among others, penalizes queues and job-congestion on each machine. In
some sense, the agents have to possibly use the “most available” machine. In
the mean-field equilibrium situation, the job schedulers perform their optimal
schedule: the best allocation of every job to the available machines together
with the corresponding optimal processing times.

Still in the scheduling-like framework, we believe that another possible
interpretation of the problem may be as an optimal co-flow scheduling,
possibly with a deadline (see for example [14]). In this model, several
prescribed units of data (the demand) must be transferred from some sources to
some sinks (nodes of a network) along some prescribed channels (edges of the
networks) with fixed capacity. Each one of those transfers is a single flow. A
co-flow is a set of a finite number of single flows and it has its own degree
of priority. The optimization problem is to schedule all the single flows,
without violating the capacity constraint, and minimizing the completion times
of the co-flows, averaged by their priorities.

The paper is organized as follows. In Section 2, we introduce the time-
dependent optimal switching problem, justified by an optimal visiting one, for
a single agent and for a crowd, giving all the theoretical elements and
hypotheses that motivate the use of a switching feature on a network. In
Section 3, we study the well-position of such a problem with fixed mass, i.e,
as a single-player optimization problem, showing the regularity of the value
function and a dynamic programming property. In Section 4, we start the study
for a population of agents by formally introducing the continuity equations
for the flow and a suitable interpretation of a possible solution. Then, in
Section 5, we introduce the mean-field game system of our problem, by proving
at first the existence of an approximated $\varepsilon$-mean-field equilibrium
through a fixed-point procedure. Finally, in Section 6, we address the passage
to the limit as $\varepsilon\to 0$.

##  2\. The time-dependent optimal switching problem on the network

Let $\\{{\mathcal{N}}_{j}\\}_{j=1,\ldots,N}\subset{\mathbb{R}}^{d}$ be the
collection of $N$ targets of the optimal visiting problem. As explained in the
Introduction, we consider the set of the $N$-strings
$p=(p^{1},p^{2},\ldots,p^{N})\in{\mathcal{I}}=\\{0,1\\}^{N}$, which has
cardinality equal to $2^{N}$, and which we interpret as the nodes of our
network. In particular, $p^{i}=1$ means that the ${\mathcal{N}}_{i}$ has
already been visited and viceversa for $p^{i}=0$. The node $(1,1,\ldots,1)$ is
the final destination and, once reached, the game ends.

By the meaning of the strings $p$, at every switch, just one component may
change and it can do that only from $0$ to $1$. Such a component corresponds
to the visited target. For example, for $N=4$ targets, if $p_{1}=(1,0,0,0)$,
$p_{2}=(1,1,0,0)$, $p_{3}=(0,1,1,0)$ and $p_{4}=(1,1,1,0)$, then from $p_{1}$
we can not switch to $p_{3}$ otherwise we lose the information that the first
target has been already visited. Moreover we can not switch to $p_{4}$
directly since, as we said, at every switch just one component flips.

Hence, to any $p\in{\mathcal{I}}$ we associate the number $k_{p}$ given by the
sum of the components of $p$, that is $k_{p}=p^{1}+\ldots+p^{N}$. In other
words, $k_{p}$ is the number of “$1$” in $p$, that is the number of the
visited targets. Then, for any $p\in{\mathcal{I}}$, we denote by
${\mathcal{I}}_{p}$ the set of all possible new variables (nodes) in
${\mathcal{I}}$ after a switch from $p$:

${\mathcal{I}}_{p}:=\\{\tilde{p}\in{\mathcal{I}}:\text{for every
}i=1,\ldots,N,\ \tilde{p}^{i}=p^{i}+1\ \text{ if }\ p^{i}\neq 1\ \text{ and }\
k_{\tilde{p}}=k_{p}+1\\}.$

We observe that, in particular, ${\mathcal{I}}_{\bar{p}}=\emptyset$, where
$\bar{p}=(1,1,\ldots,1)$.

######  Example 1.

For $N=3$ targets, all the possible ways to visit them are $N!=3!=6$ as we can
see in Figure 1. Hence our corresponding direct network is represented in
Figure 2, where $p_{o}=(0,0,0)$ is the origin and $\bar{p}=(1,1,1)$ is the
final destination. We then have for example
${\mathcal{I}}_{p_{o}}=\\{(1,0,0),(0,1,0),(0,0,1)\\}$ and
${\mathcal{I}}_{\tilde{p}=(0,0,1)}\\{(1,0,1),(0,1,1)\\}$.

${\mathcal{N}}_{1}$${\mathcal{N}}_{2}$${\mathcal{N}}_{3}$$\ast$ A First way

${\mathcal{N}}_{1}$${\mathcal{N}}_{2}$${\mathcal{N}}_{3}$$\ast$ B Second way

${\mathcal{N}}_{1}$${\mathcal{N}}_{2}$${\mathcal{N}}_{3}$$\ast$ C Third way

${\mathcal{N}}_{1}$${\mathcal{N}}_{2}$${\mathcal{N}}_{3}$$\ast$ D Fourth way

${\mathcal{N}}_{1}$${\mathcal{N}}_{2}$${\mathcal{N}}_{3}$$\ast$ E Fifth way

${\mathcal{N}}_{1}$${\mathcal{N}}_{2}$${\mathcal{N}}_{3}$$\ast$ F Sixth way

Figure 1. The six possible ways to visit all the three targets.

$(0,0,0)$$(0,0,1)$$(0,1,1)$$(1,0,1)$$(1,0,0)$$\ (0,1,0)$$(1,1,0)$$(1,1,1)$

Figure 2. The direct network corresponding to $N=3$ targets.

The possible optimal switching path from $p$ to $\bar{p}$ must be performed
within a fixed final time $T>0$. However here we will assume that an agent at
the time $T$ may be still on an intermediate node and then, in that case, it
will pay a final cost. Hence, for an agent in the node $p\neq\bar{p}$ at time
$t<T$, the number of the admissible subsequent switches is at most
$N-\sum_{i}p^{i}\leq N$. The control at disposal of an agent in the node $p$
at time $t$ is then: the number of switches $0\leq r\leq N-\sum_{i}p^{i}$; the
decision/switching instants $\sigma=(t=t_{0}<t_{1}<t_{2}<\ldots<t_{r}\leq T)$
and the switching path $\pi$ given by the sequence of the nodes
$p=p_{0},p_{1},\ldots,p_{r}$, satisfying $p_{1}\in{\mathcal{I}}_{p_{0}}$,
$p_{i+1}\in{\mathcal{I}}_{p_{i}}$, $i=0,1,\ldots,r-1$. We assume that the
choice $1\leq r<N-\sum_{i}p^{i}$ requires that $t_{r}=T$ and obviously
$p_{r}\neq\bar{p}$ (because the number of switches $r$ is not sufficient in
order to reach $\bar{p}$ from $p=p_{0}$). Moreover, if the choice is $r=0$,
then, necessarily, either $p=p_{0}\neq\bar{p}$ and $t=t_{0}=T$ (that is the
time is already over) or $p=p_{0}=\bar{p}$ and $t=t_{0}\leq T$ (that is the
agent may still have time at disposal but instead no more switches: it is
already on $\bar{p}$). In particular, this implies that an agent can not
decide to permanently stand still on a node $p$ along a switching path unless
$p=p_{r}=\bar{p}$ (or $t_{r}=T$). To resume, the control at disposal of the
agent, which is in $p$ at time $t$, is a triple as

$(r,\sigma,\pi)=(r,t_{0},t_{1},\ldots,t_{r},p_{0},p_{1},\ldots,p_{r})$

where $t_{0}=t$ and $p_{0}=p$. Actually, it is the switching evolution inside
the network at disposal of the agent with constraints as specified here above.
For example, referring to the network in Figure 2, the following switching
evolutions/controls are admissible

$\displaystyle\big{(}2,t_{0},t_{1},t_{2}\leq
T,(0,1,0),(1,1,0),(1,1,1)\big{)},$
$\displaystyle\big{(}2,t_{0},t_{1},t_{2}=T,(0,0,0),(1,0,0),(1,0,1)\big{)},$

whereas the following ones are not admissible

$\big{(}0,t_{0}<T,(1,1,0)\big{)},\quad\big{(}2,t_{0},t_{1},t_{2}<T,(0,0,0),(1,0,0),(1,0,1)\big{)}.$

In particular, $t_{0}\ldots,t_{r-1}$ are seen as decision instants and
$t_{1},\ldots,t_{r}$ are seen as switching instants. That is the agent at time
$t_{i}\in\\{t_{0},\ldots t_{r-1}\\}$ decides to switch from $p_{i}$ to
$p_{i+1}$ and to perform such a switch at the time
$t_{i+1}\in\\{t_{1},\ldots,t_{r}\\}$. Note that $t_{1},\ldots t_{r-1}$ are
both decision and switching instants, and this means that the decision about
the next switch occurs exactly at the actual switching time.

The cost to be minimized is (note that by the argumentation above if
$p\neq\bar{p}$ and $t<T$, then necessarily $r\geq 1$)

(1) $J(p,t,(r,\sigma,\pi),\rho)\\\
=\begin{cases}\sum_{i=1}^{r}C(p_{i-1},p_{i},t_{i-1},t_{i},\rho)+\tilde{C}(p_{r},t_{r})&\text{if
}p\neq\bar{p},t<T\\\ \tilde{C}(p,t)&\text{if }p=\bar{p}\text{ or
}(p\neq\bar{p},t=T)\end{cases},$

where:

  * –

$\rho=\left(\rho_{0},\ldots,\rho_{(2^{N}-1)}\right)\in
L^{2}([0,T],[0,1])^{2^{N}}$ is a $(2^{N})$-uple of $L^{2}$ functions
$\rho_{j}:[0,T]\longrightarrow[0,1]$. Here we are using a possible enumeration
of the nodes, and every $\rho_{j}(t)$ represents the mass of the agents at the
$j$-node at time $t$. In particular, in the overlying optimal visiting
problem, this gives the mass of agents with the same remaining targets to be
visited as detected by the positions of the zeros in the string representing
the node (we stress here again that $N$ is the number of targets in the
overlying optimal visiting problem, and $2^{N}$ is the number of the
$N$-strings of $0$ and $1$ bringing the information about the visited targets
and that, in our network problem, represent the nodes of the network itself.
See the Introduction and the beginning of Section 2.).

  * –

$\displaystyle
C:{\mathcal{D}}\subset{\mathcal{I}}\times{\mathcal{I}}\times[0,T]\times]0,T]\times
L^{2}([0,T],[0,1])^{2^{N}}$ $\displaystyle\longrightarrow[0,+\infty[$
$\displaystyle(p,p^{\prime},t,\tau,\rho)$ $\displaystyle\longmapsto
C(p,p^{\prime},t,\tau,\rho)$

(where $\mathcal{D}$ is such that $(p,p^{\prime},t,\tau\rho)\in\cal D$ if and
only if $p^{\prime}\in{\cal I}_{p}$ and $\tau>t$) is the cost function, that
is the cost that an agent incurs when, at the (decision) time $t$, being on
the node $p$, decides that it will switch to a new node
$p^{\prime}\in{\mathcal{I}}_{p}$ at the (switching) time $\tau>t$. We assume
that

    * $(i)$

For every $(p,p^{\prime})\in{\mathcal{I}}\times{\mathcal{I}}_{p}$ and
$\tau\in]0,T]$, the map $(t,\rho)\longmapsto C(p,p^{\prime},t,\tau,\rho)$ is
bounded and Lipschitz continuous in $[0,\tau-h]\times
L^{2}([0,T],[0,1])^{2^{N}}$, for all sufficiently small $h>0$ and
independently of $\tau$, that is, there exists $L>0$, depending only on $h$,
such that

$|C(p,p^{\prime},t^{\prime},\tau,\rho^{\prime})-C(p,p^{\prime},t^{\prime\prime},\tau,\rho^{\prime\prime})|\leq
L\left(|t^{\prime}-t^{\prime\prime}|+\|\rho^{\prime}-\rho^{\prime\prime}\|_{L^{2}([0,T],[0,1])}\right);$

    * $(ii)$

For every fixed $\rho$,
$(p,p^{\prime})\in{\mathcal{I}}\times{\mathcal{I}}_{p}$ and $t\in[0,T]$, $C$
is decreasing in $\tau\in]t,T]$ and $\lim_{\tau\rightarrow
t^{+}}C(p,p^{\prime},t,\tau,\rho)=+\infty$, uniformly with respect to
$(p,p^{\prime},t,\rho)$;

    * $(iii)$

$C(p,p,\cdot,\cdot)=0$ for every $p\in{\mathcal{I}}$ and
$C(\cdot,\cdot,T,T)=0$. These assumptions correspond to the cases when the
agent is on $p=p_{r}=\bar{p}$ and $t_{r}$ is not necessarily $T$ and when
$t_{r}=T$ but the agent is on $p=p_{r}\neq\bar{p}$, and moreover give some
kind of continuity of (1).

  * –

The cost $\tilde{C}$ is bounded and Lipschitz continuous in time and it
represents the final cost that an agent incurs at the end of the switching
path $(p_{r},t_{r})$. For example

    * –

If $t_{r}=T$, it depends on the number of the zeros in $p_{r}$ (that is the
number of the remaining targets to be visited);

    * –

If $p_{r}=\bar{p}$, it depends on the remaining time $T-t_{r}$ (that is the
agent is penalized if $\bar{p}$ is obtained before $T$);

    * –

If $p_{r}=\bar{p}$ and $t_{r}=T$, then it is null.

######  Definition 1.

Let $p\in{\cal I}$, $p^{\prime}\in{\cal I}_{p}$, and $t<T$ be fixed. We say
that the switch from $p$ to $p^{\prime}$ with decision instant $t$ optimally
generates $\tau\in]t,T]$ as switching instant if there exists a control
$(\bar{r},\bar{\sigma},\bar{\pi})$, with $\bar{r}\geq 1$,
$\bar{\sigma}=(t_{0}=t,t_{1}=\tau,t_{2},\dots,t_{\bar{r}})$ and
$\bar{\pi}=(p_{0}=p,p_{1}=p^{\prime},p_{2},\dots,p_{\bar{r}})$ which minimizes
the cost $J$ among all controls $(r,\sigma,\pi)$ such that $r\geq 1$,
$\sigma=(t_{0}=t,t_{1},\dots,t_{r})$,
$\pi=(p_{0}=p,p_{1}=p^{\prime},p_{2},\dots,p_{r})$. In other words: if
whenever an agent in $p$ at the time $t$ decides to switch to $p^{\prime}$
(independently of the optimality of such a choice) then $\tau$ is an optimal
choice as switching instant.

We denote by
$\varphi_{p,p^{\prime}}:t\longmapsto\varphi_{p,p^{\prime}}(t)=\tau$ the
function that, for all $p,p^{\prime}$ fixed, gives, for any $t$, the optimally
generated switching $\tau$. Note that the optimally generated $\tau$ may be
not unique and hence the function $\varphi_{p,p^{\prime}}$ may be multivalued.
Also note that $\varphi_{p,p^{\prime}}$ depends on $\rho$ too. In the sequel,
for notational convenience, we will often drop the index ${(p,p^{\prime})}$
and simply write $\varphi$.

Moreover, other modeling assumptions are the following:

  * $(iv)$

If at the decision time $t$, an agent in a node $p$ chooses the switching time
$\tau$ in order to switch to $p^{\prime}$, then, in the time interval
$[t,\tau[$, it is assumed that such an agent continues to concur to the total
mass present in the node $p$ (coherently with the fact that the switch will
occur at time $\tau$ and hence the agent will be on $p$ in the time interval
$[t,\tau[$). However, the agent can not change its decision (switching to
$p^{\prime}$ at time $\tau$) or take other decision in the time interval
$]t,\tau[$. In other words, in the time interval $]t,\tau[$ it must stay on
$p$;

  * $(v)$

For the switching from $p$ to $p^{\prime}$, if we have two different decision
times $t_{1}$, $t_{2}$ with $t_{1}<t_{2}$, which optimally generate the
switching times $\tau_{1},\tau_{2}<T$ respectively (see Definition 1), then
$\tau_{1}<\tau_{2}$.

Assumption $(iv)$ suggests the following useful definition.

######  Definition 2.

An agent which is in $p$ at time $t$ and uses the control

$(r,t_{0}=t,t_{1},\ldots,t_{r},p_{0}=p,p_{1},\ldots,p_{r})$

is called a decision-making agent at the decision instants
$t_{0},\ldots,t_{r-1}$. Actually, since there is no incoming flow in our
network (all the agents are already present at $t=0$), all the agents are
decision-making at $t=0$. In particular, any single agent will take a new
decision, mandatory, at time $\tau$ when it will switch to the new node; in
other words: all agents are decision-making at $t=0$ and they will return to
be decision-making again exactly when, and only when, they switch to a new
node.

######  Remark 1.

Assumption $(ii)$ means that, if the switching time is too much close to the
corresponding decision time, then the agent pays an high cost.

The second part of assumption $(iv)$ (the agent can not change the decision in
$[t,\tau[$) is certainly due to the discrete feature of the time-dependent
component $\sigma$ of the global control $(r,\sigma,\pi)$, but it may also be
justified by the overlying optimal visiting problem where, when an agent is
moving from one target to another then, under some assumptions, it is not
optimal to change destination or to come back to the previous node (see [2]).
Also, the interpretation as job scheduling may justify such an assumption.

From assumption $(v)$, it follows $(v^{\prime})$: any optimal switching time
less than $T$ originates from a unique decision time. This can be also
directly proved by assuming further hypotheses (see Remark 3). Moreover,
suppose that the decision time $t$ optimally generates the switching times
$\tau_{1}$, $\tau_{2}$ with $\tau_{1}<\tau_{2}$ for the switching from $p$ to
$p^{\prime}$. Then, in view of assumption $(v)$, in the time interval
$[\tau_{1},\tau_{2}[$ only the agents with decision time $t$ can switch from
$p$ to $p^{\prime}$. More generally, if we define
$\tau^{-}:=\inf_{\tau}\\{\text{$\tau$ is optimal for $t$}\\}$ and
$\tau^{+}:=\sup_{\tau}\\{\text{$\tau$ is optimal for t}\\}$, in the time
interval $[\tau^{-},\tau^{+}[$, only the agents with decision time $t$ can
switch from $p$ to $p^{\prime}$. Hence, we can consider the function
$\varphi:t\longmapsto\tau$, giving the optimal switching instant $\tau$ for
the decisional instant $t$, as a maximal monotone graph filling the jumps by
vertical segments, and so, in this case, $\varphi$ is a multivalued function.

All the previous assumptions and arguments can be justified by a possible
overlying optimal visiting problem with suitable energy and congestion costs
(see [2]). See also Remark 3.

The value function of the problem is

(2) $V(p,t,\rho)=\inf_{(r,\sigma,\pi)}J(p,t,(r,\sigma,\pi),\rho)$

and a control $(r,\sigma,\pi)$ is said to be optimal for $(p,t)$ if
$V(p,t,\rho)=J(p,t,(r,\sigma,\pi),\rho)$.

######  Definition 3.

Let $p\neq\bar{p}$, $t\in[0,T[$ and $\tau\in]t,T]$ be fixed. We say that
$\tau$ is optimal for $V(p,t,\rho)$ if there exists a control
$(\bar{r},\bar{\sigma},\bar{\pi})$ with $\bar{r}\geq 1$,
$\bar{\sigma}=(t_{0}=t,t_{1}=\tau,t_{2},\dots,t_{\bar{r}})$ and
$\bar{\pi}=(p_{0}=p,p_{1},p_{2},\dots,p_{\bar{r}})$ which is optimal, that is
minimizes the cost $J$ among all controls. In other words, there exists an
optimal control whose first switching instant is $\tau$.

Given next Proposition 2 (and in particular looking at its proof), the
previous definition is equivalent to require that there exists
$p^{\prime}\in{\cal I}_{p}$ such that the pair $(p^{\prime},\tau)$ realizes
the minimum in

$V(p,t,\rho)=\inf_{\begin{subarray}{c}p^{\prime}\in{\mathcal{I}}_{p}\\\
\tau\in]t,T]\end{subarray}}\left\\{V(p^{\prime},\tau)+C(p,p^{\prime},t,\tau,\rho)\right\\}.$

##  3\. The optimal switching problem with fixed mass $\rho$

In this section, we mostly assume that the mass $\rho\in
L^{2}([0,T],[0,1])^{2^{N}}$ is a priori fixed and then, when not needed, we do
not display it as entry of the cost $J$ and of the value function $V$.

######  Proposition 1.

For all $k>0$, the value function $V$ in (2) is bounded and Lipschitz
continuous in $[0,T-k]$, uniformly in $\rho$. Moreover, if $\rho^{n}$
converges to $\rho$ in $L^{2}([0,T],[0,1])$, then $V(p,\cdot,\rho^{n})$
uniformly converges to $V(p,\cdot,\rho)$ on $[0,T-k]$, for all $p$. Also, if
$t^{\prime n}$ is optimal for $V(p,t^{n},\rho^{n})$ and $t^{\prime n}$,
$t^{n}$ converge to $t^{\prime}$, $t<T$ respectively, then $t^{\prime}$ is
optimal for $V(p,t,\rho)$ (see Definition 3 for $t$ optimal).

###### Proof.

Using $(i)$ and $(ii)$ in Section 2, for all $t\in[0,T-k]$, it is, for all
$p\neq\bar{p}$ and $p^{\prime}\in{\cal I}_{p}$, $V(p,t,\rho)\leq
C(p,p^{\prime},t,T,\rho)+\tilde{C}(p^{\prime},T)\leq
C(p,p^{\prime},t,t+k,\rho)+\tilde{C}(p^{\prime},T)$, and this gives the
boundedness. We take $0<h<k$ such that, for all $t\in[0,t_{k}]$,
$p,p^{\prime},\rho$ it is, for $t<\tau\leq t+h$,

$C(p,p^{\prime},t,\tau,\rho)>\left(\max_{p,p^{\prime},t\in[0,T-k],\rho}C(p,p^{\prime},t,t+k,\rho)+\tilde{C}(p^{\prime},T)\right)$

and note that such $h$ exists for hypothesis $(ii)$ in Section 2. We then get
that if the decisional instant $t\in[0,T-k]$ optimally generates the switching
instant $\tau$ then $\tau\geq t+h$. Take $p$ and
$t^{\prime},t^{\prime\prime}\in[0,T-k]$ such that
$|t^{\prime}-t^{\prime\prime}|<h$. For $\varepsilon>0$ let $(r,\sigma,\pi)$ be
such that $V(p,t^{\prime\prime})\geq
J(p,t^{\prime\prime},(r,\sigma,\pi))-\varepsilon$. Hence the control triple
$(r,\sigma,\pi)$ is also admissible for $t^{\prime}$ (all the instants in
$\sigma$ are larger than $t^{\prime}$, because their distance from
$t^{\prime}$ is at least $h$). We have

$\displaystyle V(p,t^{\prime})-V(p,t^{\prime\prime})$
$\displaystyle=V(p,t^{\prime})-V(p,t^{\prime\prime})\leq
J(p,t^{\prime},(r,\sigma,\pi))-J(p,t^{\prime\prime},(r,\sigma,\pi))+\varepsilon$
$\displaystyle=C(p,p_{1},t^{\prime},t_{1})+\sum_{i=2}^{r}C(p_{i-1},p_{i},t_{i-1},t_{i})+\tilde{C}(p_{r},t_{r})$
$\displaystyle\quad-C(p,p_{1},t^{\prime\prime},t_{1})-\sum_{i=2}^{r}C(p_{i-1},p_{i},t_{i-1},t_{i})-\tilde{C}(p_{r},t_{r})+\varepsilon$
$\displaystyle=C(p,p_{1},t^{\prime},t_{1})-C(p,p_{1},t^{\prime\prime},t_{1})+\varepsilon\leq
L|t^{\prime}-t^{\prime\prime}|+\varepsilon,$

where $L$ is the Lipschitz constant of the cost $C$ (see assumption $(i)$),
which is independent of $\rho$. By the arbitrariness of $\varepsilon$, the
compactness of $[0,T-k]$, and changing the role of $t^{\prime}$ and
$t^{\prime\prime}$, we get the Lipschitz continuity of $V$ in $[0,T-k]$,
uniformly in $\rho$.

For the convergence of $V(p,\cdot,\rho^{n})$, note that, by the previous
points and by Ascoli-Arzelà Theorem, at least for a subsequence, we have the
uniform convergence on $[0,T-k]$ to a limit function $\tilde{V}$. Taking $h>0$
as above (and hence, for all $t\in[0,T-k]$, the optimal $t^{\prime}$ belongs
to $[t+h,T]$), by the Lipschitz continuity hypotheses on $C$ and $\tilde{C}$
(in particular the continuity of $C$ with respect to $\rho\in L^{2}$), we get
the point-wise convergence to $V(p,\cdot,\rho)$ in $[0,T-k]$, which then turns
out to be the uniform limit $\tilde{V}$, independently of the subsequence. The
final point on $t^{\prime n},t^{n}$ and $t^{\prime},t$ also comes because,
being $t<T$, there exists $k>0$ such that, for large $n$, both $t,t^{n}$
belong to $[0,T-k]$ and, for example, we can use the characterization of $V$
by Proposition 2 which is independent of Proposition 1. ∎

######  Proposition 2.

The value function $V$ is the unique solution of the following

(3)
$\begin{cases}V(p,t)=\inf_{\begin{subarray}{c}p^{\prime}\in{\mathcal{I}}_{p}\\\
t^{\prime}\in]t,T]\end{subarray}}\\{V(p^{\prime},t^{\prime})+C(p,p^{\prime},t,t^{\prime})\\},&(p,t)\in({\mathcal{I}}\setminus\\{\bar{p}\\})\times[0,T[\\\
V(\bar{p},t)=\tilde{C}(\bar{p},t),&t\in[0,T]\\\
V(p,T)=\tilde{C}(p,T),&p\in{\mathcal{I}}\end{cases}.$

###### Proof.

First of all, let us note that the second and third equalities come from the
definition of $J$ (1). We have to prove the first equality. Suppose that
$p_{r}=\bar{p}$, that is $p_{r}=(1,1,\ldots,1)$.

Case $1.$ Let $p\in{\mathcal{I}}$ be such that $\sum_{i}p^{i}=N-1$, for
instance $p=(1,1,\ldots,1,0)$, so $r=1$, $\pi=(p,\bar{p})$ and
$\sigma=(t,t^{\prime})$ for some arbitrary $t^{\prime}\in]t,T]$. Thus we have
to prove that

(4)
$V(p,t)=\inf_{t^{\prime}\in]t,T]}\\{V(\bar{p},t^{\prime})+C(p,\bar{p},t,t^{\prime})\\}=\inf_{t^{\prime}\in]t,T]}[C(p,\bar{p},t,t^{\prime})+\tilde{C}(\bar{p},t^{\prime})]$

since $V(\bar{p},\cdot)=\tilde{C}(\bar{p},\cdot)$. The last term in the above
equality is

$\inf_{(r,\sigma,\pi)}J(p,t,(r,\sigma,\pi))=V(p,t)$

being the controls $(1,(t,t^{\prime}),(p,\bar{p}))$ the only admissible ones
for $(p,t)$.
Case $2.$ Let $p\in{\mathcal{I}}$ be such that $\sum_{i}p^{i}=N-2$, that is,
for instance, $p=(0,0,1,\ldots,1)$. In this case, the admissible controls must
have either $r=2$ or $r=1$, and so $V$ is the minimum of the infimum of the
cost over the controls with $r=2$ and the infimum of the cost over the
controls with $r=1$. In the first case, setting $t_{r-2}=t$ and $p_{r-2}=p$,
we have

$\begin{split}V(p_{r-2},t_{r-2})&=\inf_{\begin{subarray}{c}(r,\sigma,\pi)\text{
s.t.}\\\ r=2\\\ \sigma=(t_{r-2},t_{r-1},t_{r})\\\
\pi=(p_{r-2},p_{r-1},\bar{p})\end{subarray}}J(p,t,(r,\sigma,\pi))\\\
&=\inf_{\begin{subarray}{c}t_{r-1}\in]t_{r-2},T[\\\ t_{r}\in]t_{r-1},T]\\\
p_{r-1}\in{\mathcal{I}}_{p_{r-2}}\end{subarray}}\left[C(p_{r-2},p_{r-1},t_{r-2},t_{r-1})+C(p_{r-1},\bar{p},t_{r-1},t_{r})+\tilde{C}(\bar{p},t_{r})\right]\\\
&=\inf_{\begin{subarray}{c}t_{r-1}\in]t_{r-2},T[\\\
p_{r-1}\in{\mathcal{I}}_{p_{r-2}}\end{subarray}}\Bigg{[}C(p_{r-2},p_{r-1},t_{r-2},t_{r-1})\\\
&\quad+\inf_{t_{r}\in]t_{r-1},T]}\left[C(p_{r-1},\bar{p},t_{r-1},t_{r})+\tilde{C}(\bar{p},t_{r})\right]\Bigg{]}\\\
&=\inf_{\begin{subarray}{c}t_{r-1}\in]t_{r-2},T[\\\
p_{r-1}\in{\mathcal{I}}_{p_{r-2}}\end{subarray}}\left[V(p_{r-1},t_{r-1})+C(p_{r-2},p_{r-1},t_{r-2},t_{r-1})\right],\end{split}$

where the last equality comes from Case $1)$. The desired result follows.

In the second case, $r=1$, we must necessarily have $p_{r}\neq\bar{p}$ and
$t_{r}=T$. Thus we have only to prove that

$V(p,t)=\inf_{p_{r}\in{\mathcal{I}}_{p}}\\{V(p_{r},T)+C(p,p_{r},t,T)\\}=\inf_{p_{r}\in{\mathcal{I}}_{p}}\\{C(p,p_{r},t,T)+\tilde{C}(p_{r},T)\\}$

since $V(\cdot,T)=\tilde{C}(\cdot,T)$. The last term in the above equality is

$\inf_{(r,\sigma,\pi)}J(p,t,(r,\sigma,\pi))=V(p,t)$

being, in this case, the controls $(1,(t,T),(p,p_{r}))$ the only ones we are
taking account of.

Up to now, we proved the equality for every $(p,t)$ such that
$\sum_{i}p^{i}=N-1$ and $\sum_{i}p^{i}=N-2$. Proceeding backwardly in this way
we then can prove all the other cases with $\sum_{i}p^{i}=N-s$ for
$s=3,\ldots,N$.

Still arguing backwardly, the uniqueness comes from the fact that any other
function satisfying (3), by (4) must coincide with $V$ on the nodes $(p,t)$
with $t\in[0,T[$ and $p$ such that $\sum_{i}p^{i}=N-1$. ∎

######  Remark 2.

The infimum in the first line of (3) is indeed a minimum realized for some
$t^{\prime}$ belonging to $[t+h,T]$, where $h$ is as in the proof of
Proposition 1 for some $k$ such that $t\in[0,T-k]$. Indeed, the quantity
inside the minimization is continuous in $[t+h,T[$ and tends to $+\infty$ for
$t^{\prime}\to T^{-}$.

We also note that, considering $t=0$, any optimal control $(r,\sigma,\pi)$ for
$V(p,0)$ with $p\neq\bar{p}$, is such that $t_{i+1}-t_{i}\geq\bar{h}$ for a
suitable $\bar{h}>0$ independent on $p$ and on $\rho$. This can be seen as in
the proof of Proposition 1, observing that $V(p,0)\leq
C(p,p^{\prime},0,T,\rho)+\tilde{C}(p^{\prime},T)$. The presence of this sort
of minimal waiting time $\bar{h}$ between two consecutive switches, when
starting at $t=0$, will lead to a piecewise continuous/constant feature of the
evolution of the masses $\rho$ with a uniform bounded number of pieces in
$[0,T]$. Also note that, the existence of such $\bar{h}$ gives the conclusion
that for all possible optimal control $(r,\sigma,\pi)$ for an agent at $t=0$,
all the decisional instants will belong in $[0,T-\bar{h}]$. Hence, in the
sequel, we will actually work (see for example (9)) with pairs $(p,t)$ such
that, whenever $p\neq\bar{p}$ and $t<T$ (otherwise the agent would have
finished its evolution), it is necessarily $t\in[0,T-\bar{h}]$, where the
value function is bounded and Lipschitz continuous, by Proposition 1.

Also justified by Remark 2, we define, for $p\neq\bar{p}$ and $t<T$,

(5)
$P(p,t)=\operatorname*{arg\,min}_{\begin{subarray}{c}p^{\prime}\in{\mathcal{I}}_{p}\\\
t^{\prime}\in]t,T]\end{subarray}}\\{V(p^{\prime},t^{\prime})+C(p,p^{\prime},t,t^{\prime})\\}.$

In other words, $P(p,t)$ is the couple $(p^{\prime},t^{\prime})$ of the node
$p^{\prime}$ where it is optimal to switch at the switching instant
$t^{\prime}>t$. As above, we do not display the dependence on $\rho$.

######  Remark 3 (still on assumption $(v)$ in §2).

Assumption $(v)$ may hold for example in the case where the cost $C$, besides
$(ii)$, is derivable w.r.t. the switching time-variable $\tau$ with derivative
$C_{\tau}$ strictly increasing w.r.t. the quantity $\tau-t$. A possible cost
satisfying the previous hypotheses may be for example of the form

(6) $C(p,p^{\prime},t,\tau,\rho)=\frac{\bar{C}(p,p^{\prime},\rho)}{\tau-t}.$

Moreover we assume that $V$ is convex in $[0,T[$ (in Appendix B we give an
explicit example where $V$ is convex). It follows that it is two times
derivable in time almost everywhere (see for example [15], Theorem 1, p. 242).
For the following counterexample, we are going to assume that the first
derivative exists everywhere. By contradiction, let us suppose that if, for
the switching from $p$ to $p^{\prime}$, the decision times $t_{1}$, $t_{2}$
with $t_{1}<t_{2}$ optimally generate the switching times
$\tau_{1},\tau_{2}<T$ respectively, then $\tau_{2}<\tau_{1}$. Hence it follows
that $\tau_{1}>\tau_{2}\geq t_{2}>t_{1}$. This means that

$\inf_{\tau\geq
t_{1}}\left\\{V(p^{\prime},\tau,\rho)+C(p,p^{\prime},t_{1},\tau,\rho)\right\\}=V(p^{\prime},\tau_{1},\rho)+C(p,p^{\prime},t_{1},\tau_{1},\rho),$
$\inf_{\tau\geq
t_{2}}\left\\{V(p^{\prime},\tau,\rho)+C(p,p^{\prime},t_{2},\tau,\rho)\right\\}=V(p^{\prime},\tau_{2},\rho)+C(p,p^{\prime},t_{2},\tau_{2},\rho).$

First order conditions give

$V^{\prime}(p^{\prime},\tau_{1},\rho)+C_{\tau}(p,p^{\prime},t_{1},\tau_{1},\rho)=0,$
$V^{\prime}(p^{\prime},\tau_{2},\rho)+C_{\tau}(p,p^{\prime},t_{2},\tau_{2},\rho)=0.$

Therefore

$V^{\prime}(p^{\prime},\tau_{1},\rho)=-C_{\tau}(p,p^{\prime},t_{1},\tau_{1},\rho)<-C_{\tau}(p,p^{\prime},t_{2},\tau_{2},\rho)=V^{\prime}(p^{\prime},\tau_{2},\rho),$

which contradicts the convexity of $V$ in time.

Recall that assumption $(v)$ implies $(v^{\prime})$: any optimal switching
time less than $T$ originates from a unique decision time. With the same
hypotheses on $C$ as above, $(v^{\prime})$ can be also inferred, without
assuming $(v)$, just assuming that $V$ is derivable w.r.t. the time-variable
without any convexity property. Indeed, suppose that at the decision times
$t_{1},t_{2}$, $t_{1}<t_{2}$, the agents are optimally switching from $p$ to
$p^{\prime}$ with the same switching time $\tau<T$. Arguing as above, with
$\tau_{1}=\tau_{2}=\tau$, we obtain

$V^{\prime}(p^{\prime},\tau,\rho)=-C_{\tau}(p,p^{\prime},t_{1},\tau,\rho)=-C_{\tau}(p,p^{\prime},t_{2},\tau,\rho),$

contradicting $t_{1}\neq t_{2}$.

Without the convexity assumption on $V$, we can infer property $(v)$ by
$(v^{\prime})$ if, besides the derivability of $V$, we assume that the map
$\varphi:t\longmapsto\tau$ is continuous. Note that, by definition of the
optimal switching instant, $\varphi(t)\to T$ as $t\to T$. By contradiction,
suppose that if, for the switching from $p$ to $p^{\prime}$, the decision
times $t_{1},t_{2}$ with $t_{1}<t_{2}$ optimally generate the switching times
$\tau_{1},\tau_{2}<T$ respectively, then
$\varphi(t_{2})=\tau_{2}<\tau_{1}=\varphi(t_{1})<T$. Hence, the function
$\varphi$ is somehow decreasing in $[t_{1},t_{2}]$ but, by continuity and the
limit property above, we must have the existence of $t^{\prime}\neq
t^{\prime\prime}$ such that
$\tau=\varphi(t^{\prime})=\varphi(t^{\prime\prime})$, contradicting
$(v^{\prime})$.

Finally, for what concerns the convexity of $V$, note that if $C$ is strictly
convex in $t$ and $\tilde{C}$ is decreasing in time, due to the decreasingness
of $C$ with respect to $\tau$ ($(ii)$) (and the example in (6) satisfies both
hypotheses), then for all $p$ with one $0$ only (i.e., directly linked to the
destination $\bar{p}$), $V(p,\cdot,\rho)$ is strictly convex, the functions
$\varphi$ are constantly equal to $T$. Proceeding backwardly, we can then
prove that for all the other nodes the value functions are all strictly convex
and, in particular, the function $\varphi$ is single-valued and increasing
(see the example in Appendix B).

######  Remark 4.

Let us note that equation (3) is in some sense the Dynamic Programming
Principle for the value function $V$. However, we can not differentiate it in
the time-variable $t$ and obtain an Hamilton-Jacobi-Bellman equation because
our model does not take account of a continuous dynamic evolution of the
agents.

##  4\. On the continuity equations for the flow

For what concerns the $\rho$ functions for the masses, using the same possible
enumeration of nodes as in §2, for every $j=0,\ldots,2^{N}-1$ we will have, at
least formally, a system of $2^{N}$ continuity equations in the variables
$\rho_{j}^{\text{dm}}$, the mass of decision-making agents (see assumption
$(iv)$ in §2), to be interpreted in a suitable formulation that we will see
later:

(7)
$\begin{cases}(\rho_{j}^{\text{dm}})^{\prime}(t)=\sum_{p_{k}|p_{j}\in{\mathcal{I}}_{p_{k}}}\lambda_{k,j}(s(t),t)\rho_{k}^{\text{dm}}(s(t)){\delta}_{t}\\\
\hskip
150.79968pt-\sum_{p_{h}|p_{h}\in{\mathcal{I}}_{p_{j}}}\lambda_{j,h}(t,\varphi(t))\rho_{j}^{\text{dm}}(t){\delta}_{t},&t\in]0,T]\\\
\rho_{j}^{\text{dm}}(0)=\rho_{j}^{0}\end{cases},$

where $\rho_{j}^{0}$ is fixed for every $j$, $\varphi$ is the (possibly
multivalued) function introduced in Remark 1 and $t\longmapsto s(t)\in[0,T]$
takes into account the decision instant $s$ at which an agent switches from
$p_{i}$ to $p_{j}$ at the switching time $t$. By assumption $(v)$, $s(t)$ is
continuous and non-decreasing (being the inverse of the function $\varphi$ in
Remark 1) and satisfies $s(t)\leq t$ for every $t$ and $s(0)=0$. Formally such
a function $s$ (as well as $\varphi$) should be indexed by $i,j$ but for
simplicity we omit that. The first term in the right-hand side of (7)
represents the mass of decision-making agents arriving to $p_{j}$ at the
switching instant $t$ and the second one, the mass of decision-making agents
leaving $p_{j}$ at the decisional instant $t$. The unknowns are the $2^{N}$
functions $\rho_{j}^{\text{dm}}$ and the functions $\lambda_{k,j}:{\cal
A}\subset[0,T]\times]0,T]\longrightarrow[0,1]$,
$(s,t)\longmapsto\lambda_{k,j}(s,t)$ (${\cal A}=\left\\{(s,t):s<t\right\\}$),
which indicate how many decision-making agents, in $p_{k}$ at time $s$, have
chosen $P(p_{k},s)=(p_{j},t)$, (5), that is the percentage of mass of
decision-making agents which is in $p_{k}$ and at time $s$ optimally decides
to switch to $p_{j}$ at $t>s$. Of course, if $\lambda_{k,j}(s,t)>0$, then, at
time $s$, deciding to switch from $p_{k}$ to $p_{j}$ at time $t$ is optimal,
and we also have
$\sum_{p_{j}|p_{j}\in{\mathcal{I}}_{p_{k}}}\lambda_{k,j}(s,\xi)=1$, where
$\xi\in\varphi(s)$ is any possible selection for the switch from $p_{k}$ to
$p_{j}$. Similarly for $\lambda_{j,h}$.

Note that the previous sum equal to $1$ means that every instant $s$ is a
decisional instant for all the decision-making agents present on the node. The
fact that those $\lambda$ activate a real switch obviously depends on the real
presence of decision-making agents on the node at the time $s$. Indeed,
roughly speaking, the interpretation of (7) is the following one. The
functions $\lambda_{i,j}$, for every $i,j$, give the right way to interpret
it. Such functions are basically values between $0$ and $1$ along the curve
$t\longmapsto(s(t),t)$, that is $\lambda_{i,j}$ is concentrated on the curve
and it is elsewhere null. From a distributional point-of-view, $\lambda_{i,j}$
is a concentration of Dirac deltas on that curve. In other words, if at the
switching instant $t$ the switches from $p_{k}$ to $p_{j}$ and from $p_{j}$ to
$p_{h}$ are both optimal, then $\lambda_{k,j}$ and $\lambda_{j,h}$ are
possibly nonzero at $(s(t),t)$ and consequently activate the Dirac deltas,
which give the corresponding accumulation of mass (of decision-making agents
only) on the arrival node at time $t$. In particular, we stress further that
the functions $\lambda_{.,.}$ are directly linked to the optimization problem,
and hence to the optimal switching function $\varphi$: if to decide at the
time $s$ to switch from $p_{i}$ to $p_{j}$ at the time $t>s$ is not an optimal
choice, then $\lambda_{i,j}(s,t)=0$. See also the fourth line of the system
(8) and point $(v)$ in the next subsection. We also point out that such
functions $\lambda_{.,.}$, as they appear in (7), look like as unknown, but,
as in the standard fixed-point procedure in mean field games, they will be
assumed as known, when one addresses the continuity equation. Indeed, such a
standard fixed point procedure, in our case will be (see the next section):
take $\rho$, derived the corresponding $\lambda_{.,.}$ by the optimization
problem, put such $\lambda_{.,.}$ in (7) and calculate the corresponding
solution $\tilde{\rho}$. Finally, ask $\tilde{\rho}=\rho$ and that will be an
equilibrium. The role of the function $\lambda_{.,.}$ in (7) is the same role
of the optimal field $-\nabla u$ in the Fokker-Planck equation in the standard
mean field game, where $u$ is the value function. Of course in our problem,
due to the possible lacking of the uniqueness of the optimal control (in the
present notation, optimal $p_{j}$ and optimal $t$), we may have different
choices for the functions $\lambda_{.,.}$, but the existence of a suitable
choice for having an equilibrium will be guaranteed by a multi-valued fixed
point procedure after a suitable convexification.

In the case when the function $t\longmapsto\tau=\varphi(t)$ (Remark 1) is
always a singleton, i.e. not multivalued, then system (7) may be also
interpreted as system of impulsive delayed equations (see for instance [22]).
The solutions $\rho_{j}^{\text{dm}}$ are somehow collections of possibly
nonzero values on switching (incoming as well as outgoing) instants, and equal
to zero elsewhere. The real mass evolution $\rho_{j}$, taking into account
both decision-making and non-decision making agents, is just the right-
continuous constant interpolation of those values. In other words, the $2^{N}$
solutions $\rho_{j}$ are constructed node-by-node for every switching time
according to the $\lambda$ functions, and this process gives piecewise
constant functions on $[0,T]$ (see also Remark 2).

In the next section we are going to make a suitable approximation of the
problem, in order to be able to work with piecewise constant functions.
Moreover, in that case, we will see a possible direct construction of such
functions $\lambda$ also explaining their presence and roles in (7), and then
the construction of the functions $\rho$. Actually, we will not use the formal
equations (7) but directly construct step-by-step (switch-by-switch) the
solutions. In Figure 3, §5.1, we graphically represent the construction of a
possible $\rho^{\text{dm}}$ and its constant interpolation $\rho$. The fact
that in the following analysis we will not use directly the equation (7) is
coherent with the theory of the standard first order mean-field game, where,
for the continuity equation one has a natural candidate for the solution: the
push-forward of the initial measure via the optimal field $-\nabla u$. Indeed,
we are going to directly construct a sort of optimal push-forward of the
initial distribution of the agents: an optimal flow inside the network.

##  5\. The approximated mean-field problem

As argued at the end of the previous section, we are going to make a suitable
approximation in order to allow us to look for solutions $\rho$ of (7) in
${\mathcal{P}}{\mathcal{C}}([0,T],[0,1])^{2^{N}}$, where
${\mathcal{P}}{\mathcal{C}}([0,T],[0,1])$ is the set of piecewise constant
functions from $[0,T]$ to $[0,1]$. In order to possibly simplify the notation,
using the same enumeration of the nodes in §2, we consider all the functions
$\rho_{j}$ as forming a unique function in a juxtaposed sequence of $2^{N}$
intervals of length $T$. We then define
${\mathcal{B}}:={\mathcal{P}}{\mathcal{C}}([0,2^{N}T],[0,1])$ whose elements
$\rho$ are still thought as $(\rho_{0},\ldots,\rho_{2^{N}-1})$. The mean-field
game system we are going to study is formally described by

(8)
$\begin{cases}V(p,t,\rho)=\inf_{\begin{subarray}{c}p^{\prime}\in{\mathcal{I}}_{p}\\\
t^{\prime}\in]t,T]\end{subarray}}\\{V(p^{\prime},t^{\prime},\rho)+C(p,p^{\prime},t,t^{\prime},\rho)\\},\hskip
16.50264pt(p,t,\rho)\in{\mathcal{I}}\times[0,T[\times{\mathcal{B}}\\\
V(\bar{p},t,\rho)=\tilde{C}(\bar{p},t),\hskip
178.68326pt(t,\rho)\in[0,T]\times{\mathcal{B}}\\\
V(p,T,\rho)=\tilde{C}(p,T),\hskip
186.36563pt(p,\rho)\in{\mathcal{I}}\times{\mathcal{B}}\\\
\lambda_{i,j}(s,t)=0\ \mbox{if }(p_{j},t)\not\in P(p_{i},s),\\\
(\rho_{j}^{\text{dm}})^{\prime}(t)=\sum_{p_{k}|p_{j}\in{\mathcal{I}}_{p_{k}}}\lambda_{k,j}(s(t),t)\rho_{k}^{\text{dm}}(s(t)){\delta}_{t}\\\
\hskip
141.6946pt-\sum_{p_{h}|p_{h}\in{\mathcal{I}}_{p_{j}}}\lambda_{j,h}(t,\varphi(t))\rho_{j}^{\text{dm}}(t){\delta}_{t},\hskip
8.5359ptt\in[0,T]\\\ \rho_{j}^{\text{dm}}(0)=\rho_{j}^{0},\\\ \rho_{j}\
\text{constant interpolation of }\rho_{j}^{\text{dm}}.\end{cases}$

Note that the fourth line of (8) stands for the fact that if a switch is not
optimal, then the corresponding fraction $\lambda$ is zero: no one is
following that switch. In particular, we point out that the four lines of (8)
take account of the optimization process for the single agent, whereas the
last three are the continuity (flow) equation for the mass of agents through
the network. We also recall here what was said at the end of the last section
for equation (7) that also holds for the last three lines of (8): actually, we
are not directly use the continuity equation, but directly construct step-by-
step the flow, representing the solution.

Next section is devoted to prove the existence of a solution
$(\rho_{j},\lambda_{j,k})$ of an approximated version of (8) and hence of an
$\varepsilon$-approximated equilibrium of the mean-field game. Such an
approximation is mainly consistent in a suitable approximation of the function
$P$ in (5).

###  5.1. Existence of an $\varepsilon$-approximated mean-field equilibrium

As usual, we are going to identify the solution $\rho$ of (8) as a fixed point
of a suitable function. At first sight, given also Remark 2, the space where
to search for a fixed point would seem to be the following one:

$X=\\{\rho\in{\mathcal{B}}:\text{$\rho$ has at most $M$ pieces of
constancy}\\},$

where $M$ is a priori fixed, for example
$M=\left(\frac{2^{N}T}{h}\right)^{2^{N}}$. Note that such a space can be made
compact with respect to a suitable convergence but it is certainly not convex
(every $\rho$ has different pieces from the others) and, to perform a fixed-
point procedure, we need that $X$ satisfies a convexity property. Therefore,
to overcome this difficulty, we fix $\varepsilon>0$ and we consider the
partition ${\mathcal{P}}_{\varepsilon}$ of $[0,2^{N}T]$, given by the nodes
$0<\varepsilon<2\varepsilon<\ldots\leq 2^{N}T$ with $\varepsilon=\frac{T}{m}$
for some $m\in\operatorname{\mathbb{N}}$. We then consider the space

$C_{\varepsilon}=\left\\{\rho\in L^{2}([0,2^{N}T],[0,1]):\right.\\\
\left.\rho\text{ is piecewise constant on the open intervals of
${\mathcal{P}}_{\varepsilon}$ and
$\|\rho\|_{\infty}\leq\|\rho_{0}\|_{\infty}$}\right\\}.$

Now, $C_{\varepsilon}$ is convex and compact with respect to the $L^{2}$
topology. Indeed, since the partition ${\mathcal{P}}_{\varepsilon}$ is fixed
and all the functions $\rho$ are constant on it, from every interval of
${\mathcal{P}}_{\varepsilon}$ we can extract a convergent constant subsequence
whose limit belongs to $L^{2}$.

We then look for a fixed point of a suitable multi-function
$\psi_{\varepsilon}:C_{\varepsilon}\longrightarrow{\mathcal{P}}(C_{\varepsilon})$,
$\rho\longmapsto\psi_{\varepsilon}(\rho)$, that is we look for
$\rho_{\varepsilon}\in C_{\varepsilon}$ such that
$\rho_{\varepsilon}\in\psi_{\varepsilon}(\rho_{\varepsilon})$. Roughly
speaking, the idea is to construct $\psi_{\varepsilon}$ as follows:

  * $(i)$

$\rho$ is put into (3) and the value function $V$ is derived;

  * $(ii)$

$V$ is inserted in (5) and the variable $P$, which is not necessarily unique
(that is, a priori, there may exist more than one optimal switching instant
and more than one admissible subsequent node where it is optimal to switch),
is derived;

  * $(iii)$

We suitably approximate the optimal switching instants given by $P$ at point
$(ii)$ with the nodes of the partition ${\mathcal{P}}_{\varepsilon}$;

  * $(iv)$

With such approximated $\varepsilon$-optimal variables $P_{\varepsilon}$ as in
$(iii)$, we construct all the possible optimal switching paths with their
decision and switching times;

  * $(v)$

For each optimal switching path $\pi$ of point $(iv)$, we construct the
corresponding functions $\lambda$ in (7), as all the agents were following
$\pi$, that is

$\lambda^{\pi,\varepsilon}_{i,j}(s,t)=\begin{cases}1,&(p_{j},t)\in
P_{\varepsilon}(p_{i},s)\cap\pi\\\ 0,&\text{otherwise}\end{cases};$

where the notation $(p_{j},t)\in P_{\varepsilon}(p_{i},s)\cap\pi$ means that,
being at $p_{i}$ at time $s$, the choice of switching to $p_{j}$ at the time
$t>s$ is $\varepsilon$-optimal, in the sense as explained in the previous
point $(iv)$.

  * $(vi)$

For any $\pi$, we insert the functions $\lambda^{\pi}$ into (7), obtaining the
evolution of the mass $\rho^{\pi}\in C_{\varepsilon}$;

  * $(vii)$

By a suitable convexification (interval by interval of the partition
${\mathcal{P}}_{\varepsilon}$) of the functions $\rho^{\pi}$ of $(vi)$, we
construct a set of functions $\psi_{\varepsilon}(\rho)$, which is contained in
${\mathcal{P}}(C_{\varepsilon})$;

  * $(viii)$

By proving that $\psi_{\varepsilon}(\rho)$ is a non-empty and convex subset of
$C_{\varepsilon}$ and that the map $\rho\longmapsto\psi_{\varepsilon}(\rho)$
has closed graph, we can apply the fixed-point Kakutani-Ky Fan Theorem (see
for example [24]) to find a desired $\rho_{\varepsilon}$.

Note that, by construction, $\rho_{\varepsilon}$, together with the
coefficients $\lambda$ of the convex combinations of the extremal $\rho^{\pi}$
as in point $(vii)$, gives what can be considered as an approximated solution
of (8) and hence an $\varepsilon$-mean-field equilibrium.

######  Definition 4.

An $\varepsilon$-mean-field equilibrium of problem (8) is a fixed point
$\rho_{\varepsilon}$ of the multi-valued map $\psi_{\varepsilon}$:
$\rho_{\varepsilon}\in\psi_{\varepsilon}(\rho_{\varepsilon})$.

We divide the construction of $\psi_{\varepsilon}(\rho)$ into some steps. A
general definition for the multi-function $\psi_{\varepsilon}$, covering all
possible cases and, in particular, all possible networks, starting from the
optimal visiting problem with $N$ targets, is beyond the purpose of this paper
and, probably, it is not helpful and even meaningless. In fact, the complexity
of the model increases drastically, both from a notational point-of-view and
for the number of cases and subcases to be considered. Hence we show the
construction of it for some examples. This, however, does not weaken the
proofs of the results. In the following, for simplicity, we suppose $N=3$
(compare with Figure 2) and consider only paths starting from $p_{0}=(0,0,0)$
and that, at the initial time $t=0$, all the agents are in $p_{0}$. Moreover
note that all the paths start at time $t=0$, but this is implicit, in our
model. In Remark 6 below a more general situation is considered. Moreover, the
example in Appendix A may be also somehow enlightening. Anyway, at the end of
Remark 6 we briefly give a possible (certainly non-operative) definition of
$\psi_{\varepsilon}$.

In the sequel, we use the following further notation: $p_{1}=(1,0,0)$,
$p_{2}=(0,1,0)$, $p_{3}=(0,0,1)$, $p_{4}=(1,1,0)$, $p_{5}=(0,1,1)$,
$p_{6}=(1,0,1)$, $p_{7}=\bar{p}=(1,1,1)$. Step 1 (points $(i)-(iv)$). Let
$\rho=(\rho_{p_{0}},\rho_{p_{1}},\rho_{p_{2}},\rho_{p_{3}},\rho_{p_{4}},\rho_{p_{5}},\rho_{p_{6}},\rho_{p_{7}})\in
C_{\varepsilon}$ be fixed. Consider the finite set

$\tilde{P}_{p_{0}}=\\{(p_{1},\tau_{1}),(p_{2},\tau_{2}),(p_{3},\tau_{3}),(p_{4},\tau_{4}),(p_{5},\tau_{5}),(p_{6},\tau_{6}),(p_{7},\tau_{7})\\},$

whose elements are the couples composed by all the possible optimal admissible
nodes $p_{1},\ldots,p_{7}$ (starting from $p_{0}=(0,0,0)$), and the possible
optimal switching instants $\tau_{1},\ldots,\tau_{7}$, as derived in point
$(ii)$, that is, for example, $\tau_{2}$ is the optimal switching instant in
order to switch to $p_{2}=(0,1,0)$ with decision at $t=0$ in $p_{0}=(0,0,0)$
(independently whether the choice of $p_{2}$ is optimal or not).

For point $(iii)$, we argument as follows. At first observe that, at point
$(ii)$, the multiplicity of the variables $P$ lies on the admissible
subsequent node, but may also lie on the optimal switching instant (for a
fixed node), if $\tau^{-}<\tau^{+}$, as in Remark 1. In order to make the
solution $\rho$ consistent with the partition ${\mathcal{P}}_{\varepsilon}$,
and to overcome the possible difficulties of the multivalued feature in time
(making it at most discrete), we approximate the possible optimal switching
instants $\tau_{1},\ldots,\tau_{7}$ with the nodes of
${\mathcal{P}}_{\varepsilon}$. In particular, for a generic switching instant
$\tau_{i}$, we set

$\displaystyle\underline{m}(\tau_{i},\varepsilon):=\max\\{n\in\mathbb{N}:n\varepsilon\leq\tau_{i}\\},$
$\displaystyle\underline{m}(\tau_{i},\varepsilon)\varepsilon=\text{the largest
node not larger than $\tau_{i}$},$
$\displaystyle\overline{m}(\tau_{i},\varepsilon):=\min\\{n\in\mathbb{N}:n\varepsilon\geq\tau_{i}\\},$
$\displaystyle\overline{m}(\tau_{i},\varepsilon)\varepsilon=\text{the smallest
node not smaller than $\tau_{i}$}.$

Then, if in the switching from $p$ to $p^{\prime}$, the optimal switching
instant $\tau_{i}$ belongs to the interval
$[\underline{m}(\tau_{i},\varepsilon)\varepsilon,\overline{m}(\tau_{i},\varepsilon)\varepsilon]$,
we select

(9) $\tilde{\tau}_{i,\varepsilon}\in
F(\tau_{i})=\begin{cases}\\{\underline{m}(\tau_{i},\varepsilon)\varepsilon\\},&\tau_{i}\in[\underline{m}(\tau_{i},\varepsilon)\varepsilon,\underline{m}(\tau_{i},\varepsilon)\varepsilon+\frac{\varepsilon}{2}[\\\
\\{\underline{m}(\tau_{i},\varepsilon)\varepsilon,\overline{m}(\tau_{i},\varepsilon)\varepsilon\\},&\tau_{i}=\underline{m}(\tau_{i},\varepsilon)\varepsilon+\frac{\varepsilon}{2}\\\
\\{\overline{m}(\tau_{i},\varepsilon)\varepsilon\\},&\tau_{i}\in]\underline{m}(\tau_{i},\varepsilon)\varepsilon+\frac{\varepsilon}{2},\overline{m}(\tau_{i},\varepsilon)\varepsilon]\end{cases}.$

In this way, the approximated variables $P_{\varepsilon}$ in $(iii)$ replace
every optimal pair $(p_{i},\tau_{i})\in P\subseteq\tilde{P}_{p_{o}}$ by the
pairs (which we call $\varepsilon$-optimal)
$(p_{i},\tilde{\tau}_{i,\varepsilon})$, $\tilde{\tau}_{i,\varepsilon}\in
F(\tau_{i})$. Therefore, we construct all the possible $\varepsilon$-optimal
switching paths $\pi$ with decision and switching times given by those
approximated $\tilde{\tau}_{i,\varepsilon}$, just taking, switch by switch,
one and only one of the pairs above. For example, if $p_{0}\to p_{1}\to
p_{4}\to p_{7}$ is an optimal path with $\tau_{1},\tau_{4},\tau_{7}$ the
corresponding optimal switching instants, that is

$(p_{1},\tau_{1})\in P(p_{0},0),\ (p_{4},\tau_{4})\in P(p_{1},\tau_{1}),\
(p_{7},\tau_{7})\in P(p_{4},\tau_{4}),$

then we consider all the possible $\varepsilon$-optimal paths $p_{0}\to
p_{1}\to p_{4}\to p_{7}$ with $\varepsilon$-optimal switching instants
$\tilde{\tau}_{j,\varepsilon}\in F(\tau_{j})$, $j=1,4,7$, that is

$(p_{1},\tilde{\tau}_{1,\varepsilon})\in P_{\varepsilon}(p_{0},0),\
(p_{4},\tilde{\tau}_{4,\varepsilon})\in P_{\varepsilon}(p_{1},\tau_{1}),\
(p_{7},\tilde{\tau}_{7,\varepsilon})\in P_{\varepsilon}(p_{4},\tau_{4}),$

where

(10) $P_{\varepsilon}(p_{i},s)=\\{(p_{j},F(\tau_{j})):(p_{j},\tau_{j})\in
P(p_{i},s)\\}.$

In particular, note that, if $\varphi(s)=[\tau_{j}^{-},\tau_{j}^{+}]$ as in
Remark 1, then $P_{\varepsilon}(p_{i},s)$ contains all the pairs
$(p_{j},\tilde{\tau}_{j})$ with $\tilde{\tau}_{j}=$ nodes of
${\mathcal{P}}_{\varepsilon}$ in
$[\underline{m}(\tau_{j}^{-},\varepsilon)\varepsilon,\overline{m}(\tau_{j}^{+},\varepsilon)\varepsilon]$.

Step 2 (points $(v)-(vii)$). The aim is to build a multi-function
$\rho\longmapsto\psi_{\varepsilon}(\rho)\subset C_{\varepsilon}$ with (compact
and) convex images and closed graph, to which we will apply the fixed-point
Kakutani-Ky Fan Theorem.

For each $\varepsilon$-optimal switching path $\pi$ of point $(iv)$, Step 1,
we construct the corresponding evolution of the mass, assuming that all the
agents (which here are assumed to be all at $p_{0}$ at time $t=0$) are
following $\pi$. For example, for the possible $\varepsilon$-optimal path
$p_{0}\to p_{1}\to p_{4}\to p_{7}$ as in Step 1, we would get

$\begin{array}[]{ll}\displaystyle\rho_{0}(t)=\begin{cases}\rho^{0},&0\leq
t<\tilde{\tau}_{1,\varepsilon}\\\ 0,&\tilde{\tau}_{1,\varepsilon}\leq t\leq
T\end{cases},\qquad\rho_{1}(t)=\begin{cases}0,&0\leq
t<\tilde{\tau}_{1,\varepsilon}\\\ \rho^{0},&\tilde{\tau}_{1,\varepsilon}\leq
t<\tilde{\tau}_{4,\varepsilon}\\\ 0,&\tilde{\tau}_{4,\varepsilon}\leq t\leq
T\end{cases},\\\ \rho_{4}(t)=\begin{cases}0,&0\leq
t<\tilde{\tau}_{4,\varepsilon}\\\ \rho^{0},&\tilde{\tau}_{4,\varepsilon}\leq
t<\tilde{\tau}_{7,\varepsilon}\\\ 0,&\tilde{\tau}_{7,\varepsilon}\leq t\leq
T\end{cases},\qquad\rho_{7}(t)=\begin{cases}0,&0\leq
t<\tilde{\tau}_{7,\varepsilon}\\\ \rho^{0},&\tilde{\tau}_{7,\varepsilon}\leq
t\leq T\end{cases},\\\ \rho_{i}\equiv 0,\ i=2,3,5,6,\end{array}$

and note that, by juxtaposition,
$\rho^{\pi,\varepsilon}=(\rho_{0},\rho_{1},\ldots,\rho_{7})\in
C_{\varepsilon}$. Formally, as explained in §4, such an evolution
$\rho^{\pi,\varepsilon}$ can be seen as the constant interpolation of a
decision-making solution $\rho^{\text{dm}}$ of (7), with coefficients
$\lambda$ (to be understood associated to $\pi$, $\varepsilon$ and hence to
the corresponding selection in $P_{\varepsilon}$) satisfying

$\lambda^{\pi,\varepsilon}_{i,j}(s,t)=\begin{cases}1,&(p_{j},t)\in
P_{\varepsilon}(p_{i},s)\cap\pi\\\ 0,&\text{otherwise}\end{cases}.$

The aim is to construct $\psi_{\varepsilon}(\rho)$ as a suitable
convexification of all those “extremal” evolutions $\rho^{\pi,\varepsilon}$.
Such a convexification is constructed by taking into account the decision-
making nodes $(p_{0},0)$ and $(p_{j},\tilde{\tau}_{j,\varepsilon})$. Still
considering an example, suppose that the following paths (nodes $p_{i}$ and
switching time $\tilde{\tau}_{i}$) are $\varepsilon$-optimal

$\begin{array}[]{ll}\displaystyle\pi^{1}:(p_{0},0)\to(p_{1},\tilde{\tau}_{1}^{1})\to(p_{4},\tilde{\tau}_{4}^{1})\to(p_{7},\tilde{\tau}_{7}^{1}),\\\
\displaystyle\pi^{2}:(p_{0},0)\to(p_{1},\tilde{\tau}_{1}^{2})\to(p_{6},\tilde{\tau}_{6}^{2})\to(p_{7},\tilde{\tau}_{7}^{2}),\\\
\displaystyle\pi^{3}:(p_{0},0)\to(p_{3},\tilde{\tau}_{3}^{3})\to(p_{6},\tilde{\tau}_{6}^{3})\to(p_{7},\tilde{\tau}_{7}^{3}),\end{array}$

where we suppose

$0<\tilde{\tau}_{1}^{1}=\tilde{\tau}_{1}^{2}<\tilde{\tau}_{6}^{2}<\tilde{\tau}_{3}^{3}<\tilde{\tau}_{6}^{3}<\tilde{\tau}_{4}^{1}<\tilde{\tau}_{7}^{1}=\tilde{\tau}_{7}^{2}=\tilde{\tau}_{7}^{3}=T.$

We have a first decisional split in $p_{0}$ at $t=0$ between agents switching
to $p_{1}$ and to $p_{3}$, respectively. We then have the convex coefficients
$\lambda_{0,1}(0),\lambda_{0,3}(0)\in[0,1]$ with sum equal to $1$. Then
another decisional split occurs in $p_{1}$ at
$\tilde{\tau}_{1}=\tilde{\tau}_{1}^{1}=\tilde{\tau}_{1}^{2}$, giving the
convex coefficients $\lambda_{1,4}(\tilde{\tau}_{1})$,
$\lambda_{1,6}(\tilde{\tau}_{1})$, and no other decisional split occurs. We
then get the evolutions

(11) $\begin{array}[]{ll}\displaystyle\rho_{0}(t)=\begin{cases}\rho^{0},&0\leq
t<\tilde{\tau}_{1}^{1}\\\ \lambda_{0,3}(0)\rho^{0},&\tilde{\tau}_{1}^{1}\leq
t<\tilde{\tau}_{3}^{3}\\\ 0,&\tilde{\tau}_{3}^{3}\leq t\leq T\end{cases},\ \
\rho_{1}(t)=\begin{cases}0,&0\leq t<\tilde{\tau}_{1}^{1}\\\
\lambda_{0,1}(0)\rho^{0},&\tilde{\tau}_{1}^{1}\leq t<\tilde{\tau}_{6}^{2}\\\
\lambda_{1,4}(\tilde{\tau}_{1})\lambda_{0,1}\rho^{0},&\tilde{\tau}_{2}^{6}\leq
t<\tilde{\tau}_{4}^{1}\\\ 0,&\tilde{\tau}_{4}^{1}\leq t\leq T\end{cases},\\\
\rho_{3}(t)=\begin{cases}0,&0\leq t<\tilde{\tau}_{3}^{3}\\\
\lambda_{0,3}(0)\rho^{0},&\tilde{\tau}_{3}^{3}\leq t<\tilde{\tau}_{6}^{3}\\\
0,&\tilde{\tau}_{6}^{3}\leq t\leq T\end{cases},\\\
\rho_{4}(t)=\begin{cases}0,&0\leq t<\tilde{\tau}_{4}^{1}\\\
\lambda_{1,4}(\tilde{\tau}_{1})\lambda_{0,1}(0)\rho^{0},&\tilde{\tau}_{4}^{1}\leq
t<T\\\ 0,&t=T\end{cases},\\\ \rho_{6}(t)=\begin{cases}0,&0\leq
t<\tilde{\tau}_{6}^{2}\\\
\lambda_{1,6}(\tilde{\tau}_{1})\lambda_{0,1}(0)\rho^{0},&\tilde{\tau}_{6}^{2}\leq
t<\tilde{\tau}_{6}^{3}\\\
(\lambda_{1,6}(\tilde{\tau}_{1})\lambda_{0,1}(0)+\lambda_{0,3}(0))\rho^{0},&\tilde{\tau}_{6}^{3}\leq
t<T\\\ 0,&t=T\end{cases},\\\ \rho_{7}(t)=\begin{cases}0,&0\leq t<T\\\
\rho^{0},&t=T\end{cases},\qquad\rho_{2}=\rho_{5}\equiv 0.\end{array}$

Again, by juxtaposition, we get an element of $C_{\varepsilon}$. The set
$\psi_{\varepsilon}(\rho)\subseteq C_{\varepsilon}$ is then constructed by all
the possible convexifications as above of all sets of extremal evolutions
$\rho^{\pi,\varepsilon}$. See also the discussion after Definition 4 and the
end of Remark 6. See Figure 3 for a graphic representation of
$\rho_{6}^{\text{dm}}$ and its constant interpolation $\rho_{6}$.

######  Remark 5.

The functions $\lambda_{i,j}$ and their products as shown in the example
above, together with the decisional and switching instants, give the
coefficients $\lambda_{i,j}$ in the formal equations (7), for the decision-
making part $\rho^{\text{dm}}$ of the evolution.

$0$$T$$\tilde{\tau}_{6}^{2}$$\tilde{\tau}_{6}^{3}$$t$$\rho_{6}^{\text{dm}}$$\lambda_{1,6}(\tilde{\tau}_{1})\lambda_{0,1}(0)\rho^{0}$$(\lambda_{1,6}(\tilde{\tau}_{1})\lambda_{0,1}(0)+\lambda_{0,3}(0))\rho^{0}$$0$$T$$\tilde{\tau}_{6}^{2}$$\tilde{\tau}_{6}^{3}$$t$$\rho_{6}$

Figure 3. Representation of $\rho_{6}^{\text{dm}}$ and of its constant
interpolation $\rho_{6}$.

######  Lemma 1 (point $(viii)$).

For any $\rho\in C_{\varepsilon}$, the set $\psi_{\varepsilon}(\rho)$ is a
non-empty convex (and compact) subset of $C_{\varepsilon}$. Moreover, the map
$\rho\longmapsto\psi_{\varepsilon}(\rho)$ has closed graph.

###### Proof.

Clearly the set $\psi_{\varepsilon}(\rho)$ is non-empty and moreover it is
convex. Indeed, if $\rho^{1},\rho^{2}\in\psi_{\varepsilon}(\rho)$ and
$\lambda\in[0,1]$, then
$\lambda\rho^{1}+(1-\lambda)\rho^{2}\in\psi_{\varepsilon}(\rho)$. First, note
that the extremal evolutions are a finite quantity
$\\{\rho^{\pi_{1,\varepsilon}},\ldots,\rho^{\pi_{r,\varepsilon}}\\}$, because
the number of $\varepsilon$-optimal paths, $\pi^{k,\varepsilon}$,
$k=1,\ldots,r$, is finite. Hence we can consider both $\rho^{1}$ and
$\rho^{2}$ as a convex combination, decisional node by decisional node (as
described in Step 2), of all extremal evolutions, with convex coefficients
sets $\Lambda^{1}$ and $\Lambda^{2}$ (note that the decisional nodes
$(p_{i},\tilde{\tau}_{i})$ are determined by the fixed $\rho\in
C_{\varepsilon}$ via (5), (10)). This gives that
$\lambda\rho^{1}+(1-\lambda)\rho^{2}$ is a same kind of convex combination of
the extremal evolutions with set of convex coefficients
$\lambda\Lambda^{1}+(1-\lambda)\Lambda^{2}$ (sum performed
$\varepsilon$-optimal path by $\varepsilon$-optimal path,
$\pi^{k,\varepsilon}$, and decisional node by decisional node), and hence it
belongs to $\psi_{\varepsilon}(\rho)$, which turns out to be convex.

Now, we prove that the multifunction $\rho\longmapsto\psi_{\varepsilon}(\rho)$
has closed graph. From this, we also get the closedness of
$\psi_{\varepsilon}(\rho)$ and, since $C_{\varepsilon}$ is compact, it follows
that $\psi_{\varepsilon}(\rho)$ is compact too.

Consider a sequence $\\{\rho^{n}\\}_{n}\subset C_{\varepsilon}$ with
$\rho^{n}\longrightarrow\rho$ in $C_{\varepsilon}$, that is $\rho\in
C_{\varepsilon}$ and the convergence is in $L^{2}$. We want to show that for
every $\rho^{\prime n}\in\psi_{\varepsilon}(\rho^{n})$ with $\rho^{\prime
n}\longrightarrow\rho^{\prime}$ in $C_{\varepsilon}$, we have
$\rho^{\prime}\in\psi_{\varepsilon}(\rho)$.

Let us prove that, up to a subsequence, $\rho^{\prime
n}\longrightarrow\tilde{\rho}^{\prime}$ in $L^{2}$ with
$\tilde{\rho}^{\prime}\in C_{\varepsilon}$ and
$\tilde{\rho}^{\prime}\in\psi_{\varepsilon}(\rho)$. By the uniqueness of the
limit in $L^{2}$, it must hold $\rho^{\prime}=\tilde{\rho}^{\prime}$, ending
the proof. By Proposition 1, we have $V^{n}\longrightarrow V$ uniformly on
$[0,T-k]$ for all $k>0$ (i.e., $V(p,\cdot,\rho^{n})\longrightarrow
V(p,\cdot,\rho)$ uniformly on $[0,T-k]$) and if $t^{\prime n}$ is optimal for
$V(p,t^{n},\rho^{n})$ and $t^{n}\to t$, $t^{\prime n}\to t^{\prime}$, then
$t^{\prime}$ is optimal for $V(p,t,\rho)$. In particular, note that, by Remark
2, since $t^{n}$ is a decisional instant for an optimal path starting at
$t=0$, then $t^{n}\in[0,T-\bar{h}]$. Therefore, denoting by
$P^{n},P_{\varepsilon}^{n},P,P_{\varepsilon}$ the functions (5) and (10)
corresponding to $\rho^{n}$ and $\rho$, respectively, we have

(12) $(p^{\prime n},t^{\prime n})\in P^{n}(p,t^{n})\ \text{and }(p^{\prime
n},t^{\prime n})\to(p^{\prime},t^{\prime})\Rightarrow\
(p^{\prime},t^{\prime})\in P(p,t),$

and hence, by definition of $P_{\varepsilon}$, (10) (see also the comment
below it), in particular by the definition of $F$ in (9), for every choice of
$(p^{\prime n},\tilde{t}^{\prime n})\in P_{\varepsilon}^{n}(p,t^{n})$ there
exists $(p^{\prime},\tilde{t}^{\prime})\in P_{\varepsilon}(p,t)$ such that

(13) $(p^{\prime n},\tilde{t}^{\prime
n})\to(p^{\prime},\tilde{t}^{\prime})\quad\text{up to a subsequence (with
$p^{\prime n},t^{\prime n},p^{\prime},t^{\prime}$ as in \eqref{convPep1})}.$

Moreover, since the nodes are finite, there exists $\bar{n}\in\mathbb{N}$ such
that for every $p$,

(14) $p^{n}\to p\ \Rightarrow\ p^{n}=p\quad\text{for every }n\geq\bar{n}.$

Let $(\rho^{\pi_{1,\varepsilon}},\ldots,\rho^{\pi_{r,\varepsilon}})$ be the
extremal points of $\psi_{\varepsilon}(\rho)$, where $\pi_{1},\ldots,\pi_{r}$
are the $\varepsilon$-optimal paths. By (14), we can assume that for $n$
sufficiently large, also in $\psi_{\varepsilon}(\rho^{n})$ the extremal points
are exactly in the quantity $r$ and their sequences of nodes are the same as
the ones of $\pi_{1},\ldots,\pi_{r}$ and only the decisional and switching
instants may change with $n$. Let us denote by
$\rho^{\pi_{1},n,\varepsilon},\ldots,\rho^{\pi_{r},n,\varepsilon}$ those
extremal points. Then, for $n$ sufficiently large, $\rho^{\prime
n}\in\psi_{\varepsilon}(\rho^{n})$ is a convex combination, constructed as in
Step 2, of the extremal points
$\rho^{\pi_{1},n,\varepsilon},\ldots,\rho^{\pi_{r},n,\varepsilon}$. Let
$\lambda_{i,j}^{n}(\tilde{t}^{n})\in[0,1]$ be the corresponding coefficients
for the generic decisional instant $\tilde{t}^{n}$. Up to a subsequence, we
can assume that $\tilde{t}^{n}\to\tilde{t}$ and
$\lambda_{i,j}^{n}(\tilde{t}^{n})\to\lambda_{i,j}=:\lambda_{i,j}(\tilde{t})\in[0,1]$
and also $\tilde{t}^{\prime n}\to\tilde{t}^{\prime}$ with
$(p^{\prime},\tilde{t}^{\prime n})\in P_{\varepsilon}^{n}(p,\tilde{t}^{n})$
and, by (13), $(p^{\prime},\tilde{t}^{\prime})\in
P_{\varepsilon}(p,\tilde{t})$. Since $\tilde{t}^{\prime n},\tilde{t}^{n}$
assume only discrete values on partition ${\mathcal{P}}_{\varepsilon}$, we can
also assume $\tilde{t}^{\prime n}=\tilde{t}^{\prime}$ and
$\tilde{t}^{n}=\tilde{t}$ for $n$ sufficiently large. Hence the extremal
points $\rho^{\pi_{1},n,\varepsilon},\ldots,\rho^{\pi_{r},n,\varepsilon}$ are
exactly the same as the ones of the limit case $\psi_{\varepsilon}(\rho)$: the
same $\varepsilon$-optimal paths $\pi_{1},\ldots,\pi_{r}$ with the same
decisional and switching instants. The only convergence is in the convex
coefficients.

Now, we construct $\tilde{\rho}^{\prime}$ as the convex combination of the
extremal points with limit coefficients $\lambda_{i,j}$. Obviously
$\tilde{\rho}^{\prime}\in C_{\varepsilon}$ and $\tilde{\rho}^{\prime
n}\longrightarrow\tilde{\rho}^{\prime}$ in $L^{2}$. To conclude, we have to
prove that $\tilde{\rho}^{\prime}\in\psi_{\varepsilon}(\rho)$. In particular,
we have to show that if $(p_{j},\tilde{t}^{\prime})\notin
P_{\varepsilon}(p_{i},\tilde{t})$, then the corresponding
$\lambda_{i,j}(\tilde{t})=0$. This is true because, if
$\lambda_{i,j}(\tilde{t})$ was greater than $0$, then
$\lambda^{n}_{i,j}(\tilde{t}^{n})>0$ by convergence and hence
$(p_{j},\tilde{t}^{\prime n})\in P_{\varepsilon}^{n}(p_{i},\tilde{t}^{n})$,
and this is in contradiction with (13). Therefore
$\tilde{\rho}^{\prime}\in\psi_{\varepsilon}(\rho)$ and we conclude because, by
construction, $\rho^{\prime n}\longrightarrow\tilde{\rho}^{\prime}$ in $L^{2}$
since the convergence of the coefficients $\lambda_{i,j}^{n}$ gives the
convergence of the constant values of $\rho^{\prime n}$ on the partition
${\mathcal{P}}_{\varepsilon}$ to the constant values of
$\tilde{\rho}^{\prime}$. ∎

######  Remark 6.

Observe that the general case $N>3$ works with the same ideas and tools, being
careful that we will have a more complex network (i.e, many more nodes and
paths, that is a more complex topology of the network), which makes the fixed-
point procedure above certainly harder from a computational point-of-view but
even just from a notational one, already for what concerns the analytical
description of $\psi_{\varepsilon}$ (see for example the description of
$\rho_{6}$ in the simple case in (11)). Moreover, here above, for simplicity,
we considered only paths starting from $p_{0}=(0,0,0)$ and that, at the
initial time $t=0$, all the agents are in $p_{0}$, that is $\rho_{i}(0)=0$ for
all $i\neq 0$. The case where at the initial time the mass is possible
distributed to different nodes, up to suitably construct the evolutions as in
Step 2, which will be more knotty, does not change the proof too much (we may
have more involved intersections and overlaps of switches, still in a finite
number, as $\rho_{6}$ in (11) but probably in a more complicated way).

Still considering the network in Figure 2 as in (11), with the same
enumeration of nodes $p_{0},p_{1},\ldots,p_{7}=\bar{p}$, in order to give an
idea of the descriptive and notational complexity of the construction of
$\psi_{\varepsilon}$, already in the case of that simple network, but with a
generic initial distribution
$\rho^{0}=(\rho^{0}_{0},\rho^{0}_{1},\ldots\rho^{0}_{7})$, if we consider, for
instance, the flow $\rho_{6}$ through the node $p_{6}$, we have

$\rho_{6}=\rho^{6,6}+\rho^{1,6}+\rho^{3,6}+\rho^{0,1,6}+\rho^{0,3,6}.$

The term $\rho^{6,6}$ corresponds to the flow of the agents that at time $t=0$
are already in $p_{6}$: all of them, at the decisional instant $t=0$, choose a
switching instant $\tau_{6,7}$ optimally generated as in (9) in order to
switch from $p_{6}$ to $p_{7}$.

The term $\rho^{1,6}$ corresponds to the flow, through $p_{6}$, of the agents
that at $t=0$ were in $p_{1}$: all of them, at the decisional instant $t=0$,
choose a switching instant $\tau_{1,6}$ optimally generated as in (9) in order
to switch from $p_{1}$ to $p_{6}$, together with the corresponding fraction
$\lambda_{1,6}$ of agents performing such a switch. Hence, at the instant
$\tau_{1,6}$, the mass of agents $\lambda_{1,6}\rho^{0}_{1}$ switches from
$p_{1}$ to $p_{6}$. Such a mass of agents, at the (decisional) instant
$\tau_{1,6}$, optimally chooses a switching instant $\tau_{1,6,7}$ in order to
switch from $p_{6}$ to $p_{7}$.

The term $\rho^{3,6}$ is constructed similarly to $\rho^{1,6}$ by replacing
$p_{1}$ with $p_{3}$.

The term $\rho^{0,1,6}$ corresponds to the flow, through $p_{6}$, of the
agents that at $t=0$ were in $p_{0}$: all of them, at the decisional instant
$t=0$, choose a switching instant $\tau_{0,1}$ optimally generated as in (9)
in order to switch from $p_{0}$ to $p_{1}$, together with the corresponding
fraction $\lambda_{0,1}$ of agents performing such a switch. Hence, at the
instant $\tau_{0,1}$, the mass of agents $\lambda_{0,1}\rho^{0}_{0}$ switches
from $p_{0}$ to $p_{1}$. Such a mass of agents, at the (decisional) instant
$\tau_{0,1}$, optimally chooses a switching instant $\tau_{0,1,6}$ in order to
switch from $p_{1}$ to $p_{6}$, together with the fraction $\lambda_{0,1,6}$
of agents performing such a switch. Therefore, at the instant $\tau_{0,1,6}$,
the mass of agents $\lambda_{0,1,6}\lambda_{0,1}\rho^{0}_{0}$, switches from
$p_{1}$ to $p_{6}$. Such a mass of agents, at the (decisional) instant
$\tau_{0,1,6}$, optimally chooses a switching instant $\tau_{0,1,6,7}$ in
order to switch from $p_{6}$ to $p_{7}$.

The term $\rho^{0,3,6}$ is constructed similarly to $\rho^{0,1,6}$ by
replacing $p_{1}$ with $p_{3}$.

Obviously, the coefficients $\lambda$ above must be constrained to have sum
equal to $1$ with the other corresponding coefficients. For instance,
$\lambda_{0,1,6}+\lambda_{0,1,4}=1$. Finally note that in the simple case
(11), $\rho_{6}$ corresponds to $\rho^{0,1,6}+\rho^{0,3,6}$ only, and, in
particular, $\lambda_{3,6}=1$, which means that $\lambda_{3,5}=0$, for the
optimality hypotheses assumed in that example.

As said before, we end this remark with a possible general definition of
$\psi_{\varepsilon}$. Given $\rho\in C_{\varepsilon}$, another element
$\tilde{\rho}\in C_{\varepsilon}$ belongs to $\psi_{\varepsilon}(\rho)$ if and
only if the following holds. We give the list of indices and notation we are
going to use.

  * 1)

$j$: Index of the node of the network, $0\leq j\leq 2^{N}-1$;

  * 2)

$\ell_{j}$: Index of the optimal path starting from the node $p_{j}$,
$1\leq\ell_{j}\leq\mu_{j}$, for some $\mu_{j}\in\mathbb{N}\setminus\\{0,\\}$;

  * 3)

$\pi_{j,\ell_{j}}$: $\ell_{j}$-th optimal path starting from $p_{j}$;

  * 4)

$\nu_{j,\ell_{j}}$: Ordering number of the switch in the path
$\pi_{j,\ell_{j}}$, $1\leq\nu_{j,\ell_{j}}\leq\xi_{j,\ell_{j}}$, for some
$\xi_{j,\ell_{j}}\in\mathbb{N}\setminus\\{0\\}$;

  * 5)

$\left(p_{j,\ell_{j},\nu_{j,\ell_{j}}},t_{j,\ell_{j},\nu_{j,\ell_{j}}}\right)$:
$\nu_{j,\ell_{j}}$-th pair (node/time) of $\pi_{j,\ell_{j}}$;

  * 6)

$\kappa_{j,\ell_{j},\nu_{j,\ell_{j}}}$: Number of nodes in ${\cal
I}_{p_{j,\ell_{j},\nu_{j,\ell_{j}}}}$ such that there exists
$t>t_{j,\ell_{j},\nu_{j,\ell_{j}}}$ such that, being in
$p_{j,\ell_{j},\nu_{j,\ell_{j}}}$ at the time
$t_{j,\ell_{j},\nu_{j,\ell_{j}}}$, it is optimal to decide to switch on that
node at the time $t$;

  * 7)

For all $(j,\ell_{j},\nu_{j,\ell_{j}})$ and for all
$1\leq\kappa\leq\kappa_{j,\ell_{j},\nu_{j,\ell_{j}}}$ we take
$\lambda_{j,\ell_{j},\nu_{j,\ell_{j}},k}\in[0,1]$, such that

$\sum_{\kappa=1}^{\kappa_{j,\ell_{j},\nu_{j,\ell_{j}}}}\lambda_{j,\ell_{j},\nu_{j,\ell_{j}},\kappa}=1,$

and we denote by $p_{j,\ell_{j},\nu_{j,\ell_{j}},\kappa}$ the corresponding
node in ${\cal I}_{p_{j,\ell_{j},\nu_{j,\ell_{j}}}}$;

  * 8)

For $0\leq\nu\leq\nu_{j,\ell_{j}}-1$ let $i_{\nu}$ such that
$p_{j,\ell_{j},\nu,i_{\nu}}=p_{j,\ell_{j},\nu+1}$.

The statement is then: $\tilde{\rho}\in\psi_{\varepsilon}(\rho)$ if and only
if we can choose the numbers $\lambda_{j,\ell_{j},\nu_{j,\ell_{j}},\kappa}$ as
in 7) such that, for all $0\leq k\leq 2^{N}-1$ and $t\in[0,T[$ we have

$\tilde{\rho}_{k}(t)=\sum_{(j,\ell_{j},\nu_{j,\ell_{j}})\Big{|}p_{j,\ell_{j},\nu_{j,\ell_{j}}}=p_{k},\
t_{j,\ell_{j},\nu_{j,\ell_{j}}}\leq
t<t_{j,\ell_{j},\nu_{j,\ell_{j}}+1}}\left(\left(\prod_{\nu=0}^{\nu_{j,\ell_{j}}-1}\lambda_{j,\ell_{j},\nu,i_{\nu}}\right)\rho_{j}^{0}\right).$

######  Theorem 5.1.

Under all the hypotheses stated in §2, there exists an $\varepsilon$-mean-
field equilibrium of system (8) (see Definition 4).

###### Proof.

The proof follows from Lemma 1, Remark 6 and the fixed-point Kakutani-Ky Fan
Theorem. ∎

##  6\. On the limit $\varepsilon\to 0$ and the existence and uniqueness of a
mean-field equilibrium

In the sequel, we denote by $\rho_{\varepsilon}$ a fixed point for
$\psi_{\varepsilon}(\rho)$, i.e., a total mass satisfying
$\rho_{\varepsilon}\in\psi_{\varepsilon}(\rho_{\varepsilon})$. The existence
of such fixed points is proved in the previous section and now we will perform
the limit procedure as $\varepsilon\to 0$, obtaining as limit $\rho\in
L^{2}([0,T],[0,1])^{2^{N}}$ such that $\rho\in\psi(\rho)$, where $\psi$ is
constructed as in the previous points $(i)$–$(viii)$ with the only difference
that we do not perform the approximation $P_{\varepsilon}$ in $(iii)$, but we
just consider the function $P$, (5). Hence $\rho$, together with its convexity
coefficients, will be a solution of (8) and a mean-field equilibrium. Recall
that, see Remark 2, in the non-approximated case (i.e., no
$\varepsilon$-partition) the mass flow of the agents is still piecewise
constant with pieces of length at least $\bar{h}>0$, but not necessarily based
on the $\varepsilon$-partition. Hence, the construction of the multifunction
$\psi$ is similar to the one of $\psi_{\varepsilon}$. The only difference is
that in the construction of $\psi_{\varepsilon}$, in the switching
optimization procedure, we first use the function $P$ (5) and then adjust the
switching time by $P_{\varepsilon}$ as described in Subsection 5.1, whereas,
in the general non-approximated case, we just take the switching instant given
by the function $P$.

######  Definition 5.

A mean field equilibrium for (8), in the case of no $\varepsilon$-partition,
is a function $\rho$ such that $\rho\in\psi(\rho)$.

One of the main problems in performing such a limit is the fact that the
functions $t\longmapsto\tau=\varphi(t)$ (see Remark 1) may be multivalued,
and, in particular, with a continuum (an interval, see Remark 1) as image of
$t$. This problem was bypassed in the previous section using the time-
discretizetion given by the partition $\mathcal{P}_{\varepsilon}$. We first
assume that the functions $\varphi$ are not multivalued and we prove, in such
a case, the existence of a mean-field equilibrium, that is of a function
$\rho\in L^{2}$ such that $\rho\in\psi(\rho)$.

######  Theorem 6.1.

Under all the hypotheses stated in §2 and assuming the single-valued feature
of $\varphi$, there exists a mean-field equilibrium of system (8), that is
there exists $\rho\in L^{2}$ such that $\rho\in\psi(\rho)$ (see Definition 5).

###### Proof.

First of all note that, fixed $\rho$, under the hypothesis on $\varphi$, for
every decisional instant $t$ and node $p_{i}$, there exists a unique optimal
switching instant $\tau$ for the switch to $p_{j}$, that is $(p_{j},\tau)\in
P(t,p_{i})$. This fact gives that the mass evolution
$\rho^{\prime}\in\psi(\rho)$ is also piecewise constant and similarly
constructed as in Step 2, §5.1, with the only difference that now the pieces
of constancy are not fixed a priori (we do not have the partition
$\mathcal{P}_{\varepsilon}$). Moreover, for all $\varepsilon>0$, the function
$P_{\varepsilon}$, (10), evaluated at $(t,p_{i})$, generates at most two
$\varepsilon$-approximated switching instants for the switch to $p_{j}$: the
possible approximation $\tilde{\tau}_{\varepsilon}$ of $\tau$ by the function
$F$ in (9) (and not the whole intersection of the nodes of the partition with
the interval $\varphi(t)$ in the case of multivalued feature). Finally,
$\tilde{\tau}_{\varepsilon}\to\tau$ as $\varepsilon\to 0$. Note that, see
Definition 1, the function $\varphi$, the optimally generated switching time,
depends on $p_{i}$ and $p_{j}$. Here for simplicity we do not display such a
dependence. The proof is made by a generic pair $(p_{i},p_{j})$ with
$p^{\prime}\in{\cal I}_{p_{i}}$, and of course, being such a pairs in a finite
quantity, we have the uniformity of the convergence, with respect to the pair.

Now, recall that (see the beginning of §5.1) the fixed points
$\rho_{\varepsilon}$ are piecewise constant with at most a fixed number $M$ of
pieces of constancy. Hence, possibly extracting a subsequence, we can make
such intervals of constancy converge as well as the corresponding values of
the constants. We then get a function $\rho$ such that, up to a subsequence,
$\rho_{\varepsilon}\to\rho$ in $L^{2}$. The convergence of the constant values
is obviously constructed by the convergence, up to a subsequence, of the
convex coefficients $\lambda_{i,j}^{\varepsilon}\in\mathbb{R}$ evaluated on
the decisional instants and implemented at the corresponding
$\varepsilon$-approximated instants as in Step 2, §5.1. Note that the
decisional and switching instants are the extremal points of the intervals of
constancy, and also that, being the number of possible cases finite, we can
assume, up to a subsequence, that those ones are decisional and switching
instants for the same switch from $p_{i}$ to $p_{j}$, i.e. for the same $i$
and $j$ for all $\varepsilon$. Finally note that $\rho_{\varepsilon}$, being a
fixed point of $\psi_{\varepsilon}$, is exactly constructed by its
coefficients $\lambda_{i,j}^{\varepsilon}$ implemented on the nodes that are
generated by $\rho_{\varepsilon}$ itself via $P_{\varepsilon}$.

Arguing as in the proof of Lemma 1, using Proposition 1 and similar
convergence for $\varepsilon\to 0$ as in (12) and (13), we get that
$\rho\in\psi(\rho)$ (i.e.: $\rho$ is constructed by the coefficients
$\lambda_{i,j}$ implemented on the nodes that are generated by $\rho$ itself
via $P$, and moreover if the switch is not optimal, then $\lambda_{i,j}=0$). ∎

In Appendix B, we give an explicit example of possible costs that guarantee
the single-valued feature of $\varphi$.

###  6.1. The general case: $\varphi$ multivalued

Without the single-valued hypothesis on $\varphi$, the passage to the limit as
$\varepsilon\to 0$ is more involved. Indeed, if the image of the decisional
time $t$ is an interval $[\tau^{-},\tau^{+}]$, in the
$\varepsilon$-approximation case we discretize it through the partition
${\mathcal{P}}_{\varepsilon}$ and, on every node, we get a value
$\lambda_{i,j}^{\varepsilon}(t,\cdot)$ which composes with the others.
Formally, we have a sum of weighted delta functions on the nodes of
${\mathcal{P}}_{\varepsilon}$ inside $[\tau^{-},\tau^{+}]$. In the the limit
as $\varepsilon\to 0$, we obtain instead a possible sum of functions
$\lambda_{i,j}(t,\cdot)$, defined on the whole interval $[\tau^{-},\tau^{+}]$
and other sums of delta functions. Hence the situation is more complex,
including the interpretation of system (7). A rigorous investigation of this
situation is going to be the subject of future works. Again considering a
particular case, where $\rho_{\varepsilon}\longrightarrow\rho$ in $L^{2}$ and
$\rho$, via the functions $P$, generates functions $\varphi$ not multivalued,
then $\rho$ may be a mean-field equilibrium because the proof of Theorem 6.1
can be probably adapted. Also for this case the details have not been checked.
However, in Appendix B, we give an explicit example of possible costs that
guarantee the single-valued feature of $\varphi$.

###  6.2. On the uniqueness of the equilibrium

As we said in the Introduction, the uniqueness of the equilibrium is often
proved by assuming the Lasry-Lions monotonicity condition on the cost (see
[21]). Our problem does not immediately fit into such a property because of
its deterministic and network-type features and the presence of two kinds of
time-variables. Anyway, in Appendix A, we try to show, by two simple examples,
how a monotonicity-type condition can be promising in order to study the
uniqueness of the equilibrium but the real implementation of that condition in
our model is completely left to future studies.

##  Appendix A On the uniqueness of the equilibrium

We first recall that, as in §6, a mean-field equilibrium is a function
$\rho\in L^{2}$ such that $\rho\in\psi(\rho)$, which means that $\rho$ is a
juxtaposed convex combination of the extremal evolutions generated by $\rho$
itself via the optimization functions $P$ (5).

The examples we are going to show do not necessarily meet in all their aspects
our model studied in previous sections. They are just inspiring examples about
the possible use of the monotonicity property.

######  Example 2.

$p_{0}$$p_{3}$$p_{2}$$p_{1}$$p_{4}$ Figure 4. The network of Example 2.

Consider the network in Figure 4, where the goal is to start from $p_{0}$ and
to arrive to $p_{4}$, along the three possible paths: $p_{0}\to p_{1}\to
p_{4}$, $p_{0}\to p_{2}\to p_{4}$ and $p_{0}\to p_{3}\to p_{4}$. Moreover, we
suppose that all the agents at the time $t=0$ are in $p_{0}$, that at the time
$t=1$ they are all forced to switch to one of the three nodes $p_{1}$, $p_{2}$
and $p_{3}$, and that at the time $t=T=2$ they are all forced to switch to
$p_{4}$, ending the game. Since the switching instants are fixed and the
significant nodes are just $p_{1}$, $p_{2}$ and $p_{3}$, we only give the cost
of stay on such nodes respectively, independently of time:
$C_{1}(\rho_{1})=\rho_{1},C_{2}(\rho_{2})=2\rho_{2},C_{3}(\rho_{3})=3\rho_{3}$,
where $\rho_{i}$ is the mass in the node $p_{i}$. In this case a mean-field
equilibrium is given by
$(\lambda_{1},\lambda_{2},\lambda_{3})=(6/11,3/11,2/11)$, which means that,
denoted by $\rho_{0}$ the initial distribution in $p_{0}$, at time $t=1$ the
fraction $\lambda_{i}\rho_{0}$ switches to the node $p_{i}$, $i=1,2,3$.
Indeed, with these fractions all the costs $C_{1},C_{2},C_{3}$ are equal to
$(6/11)\rho_{0}$. Hence if all the agents in $p_{0}$ conjecture such a
distribution, then all the possible generated extremal distributions are the
following ones: $(\rho_{0},0,0),(0,\rho_{0},0),(0,0,\rho_{0})$, that is all
the switches are optimal. The actual mass
$(\lambda_{1}\rho_{0},\lambda_{2}\rho_{0},\lambda_{3}\rho_{0})$ is then a
convex combination of the generated extremal distributions with convex
coefficients $(\lambda_{1},\lambda_{2},\lambda_{3})$, and hence it is a mean
field equilibrium. By linearity of the costs, the coefficients $\lambda_{i}$
are easily calculated by imposing
$C_{1}(\lambda_{1})=C_{2}(\lambda_{2})=C_{3}(\lambda_{3})$ with the constraint
$\lambda_{i}\in[0,1]$ and $\lambda_{1}+\lambda_{2}+\lambda_{3}=1$, and they
are the only ones satisfying the system and the constraint. Note that if, for
example, we are looking for a possible equilibrium using just the nodes
$p_{1}$ and $p_{2}$, that is we look for $\lambda_{1},\lambda_{2}\geq 0$,
$\lambda_{1}+\lambda_{2}=1$ and $C_{1}(\lambda_{1})=C_{2}(\lambda_{2})$, we
find $\lambda_{1}=2/3,\lambda_{2}=1/3$ and then we have the distribution
$(\lambda_{1}\rho_{0},\lambda_{2}\rho_{0},0)$. But such a distribution is not
an equilibrium because it gives the costs
$\left((2/3)\rho_{0},(2/3)\rho_{0},0\right)$, which generates the only
extremal distribution $(0,0,\rho_{0})$: all agents switch to $p_{3}$. And
$(\lambda_{1}\rho_{0},\lambda_{2}\rho_{0},0)$ is not a convex combination of
(i.e., is not equal to) the singleton $\\{(0,0,\rho_{0})\\}$. The problem then
has a unique equilibrium which is given by
$((6/11)\rho_{0},(3/11)\rho_{0},(2/11)\rho_{0})$.

Note that, whenever we find a triple of convex coefficients
$(\lambda_{1},\lambda_{2},\lambda_{3})$ such that
$C_{1}(\lambda_{1})=C_{2}(\lambda_{2})=C_{3}(\lambda_{3})$, then the
corresponding distribution
$(\lambda_{1}\rho_{0},\lambda_{2}\rho_{0},\lambda_{3}\rho_{0})$ is an
equilibrium because it gives the same costs along any path, and then generates
all the extremal distributions $(\rho_{0},0,0),(0,\rho_{0},0),(0,0,\rho_{0})$
of which it is a convex combination. The question about uniqueness is then:
given three functions $C_{i}:[0,1]\to\mathbb{R}$, $i=1,2,3$, under which
condition there exists at most one triple of convex coefficients
$(\lambda_{1},\lambda_{2},\lambda_{3})$ such that

(15)
$C_{1}(\lambda_{1}\rho_{0})=C_{2}(\lambda_{2}\rho_{0})=C_{3}(\lambda_{3}\rho_{0})\text{?}$

A condition that guarantees such a uniqueness is the following monotonicity
property which is, in our discrete case, the condition in [21]:

(16)
$\begin{array}[]{ll}\displaystyle\sum_{i=1}^{3}\left(C_{i}(\lambda^{\prime}_{i}\rho_{0})-C_{i}(\lambda_{i}^{\prime\prime}\rho_{0})\right)(\lambda_{i}^{\prime}-\lambda_{i}^{\prime\prime})>0\\\
\displaystyle\text{for all
}(\lambda^{\prime}_{1},\lambda^{\prime}_{2},\lambda^{\prime}_{3})\neq(\lambda^{\prime\prime}_{1},\lambda^{\prime\prime}_{2},\lambda^{\prime\prime}_{3})\
\mbox{convex triples and for any }\rho_{0}>0.\end{array}$

Indeed, let us suppose that there are two convex triples

$(\lambda_{1}^{\prime},\lambda_{2}^{\prime},\lambda_{3}^{\prime})=(\lambda_{1}^{\prime},\lambda_{2}^{\prime},1-\lambda^{\prime}_{1}-\lambda_{2}^{\prime}),\
(\lambda_{1}^{\prime\prime},\lambda_{2}^{\prime\prime},\lambda_{3}^{\prime\prime})=(\lambda_{1}^{\prime\prime},\lambda_{2}^{\prime\prime},1-\lambda^{\prime\prime}_{1}-\lambda_{2}^{\prime\prime})$

satisfying (15), and denoting by $C^{\prime},C^{\prime\prime}$ the common
costs, for the single triple respectively, we obtain

$\sum_{i=1}^{3}(C_{i}^{\prime}-C_{i}^{\prime})(\lambda_{i}^{\prime}-\lambda_{i}^{\prime\prime})=(C^{\prime}-C^{\prime\prime})\sum_{i=1}^{2}(\lambda^{\prime}_{i}-\lambda^{\prime\prime}_{i})+(C^{\prime}-C^{\prime\prime})(1-\lambda_{1}^{\prime}-\lambda_{2}^{\prime}-1+\lambda_{1}^{\prime\prime}+\lambda_{2}^{\prime\prime})=0$

and hence, by (16),
$(\lambda_{1}^{\prime},\lambda_{2}^{\prime},\lambda_{3}^{\prime})=(\lambda_{1}^{\prime\prime},\lambda_{2}^{\prime\prime},\lambda_{3}^{\prime\prime})$.

$p_{0}$$p_{4}$$p_{3}$$p_{1}$$p_{2}$$p_{5}$ Figure 5. The network of Example 3.

######  Example 3.

Consider the network in Figure 5. The goal is to start from $p_{0}$ and to
reach $p_{5}$ among one of the possible paths $p_{0}\to p_{1}\to p_{5}$,
$p_{0}\to p_{2}\to p_{3}\to p_{5}$ and $p_{0}\to p_{2}\to p_{4}\to p_{5}$.
Again, the agents at $t=0$ are all in $p_{0}$, with distribution $\rho_{0}$,
at time $t=1$ they are forced to switch to $p_{1}$ or to $p_{2}$, at time
$t=3/2$ the agents in $p_{2}$ are forced to switch to $p_{3}$ or $p_{4}$ and
at the time $t=T=2$ they are all forced to switch to $p_{5}$. The costs are
$C_{1}(\rho_{1})=\rho_{1}$, $C_{2}(\rho_{2})=4\rho_{2}$,
$C_{3}(\rho_{3})=3\rho_{3}$, $C_{4}(\rho_{4})=2\rho_{4}$. Moreover, the costs
are also multiplied by the amount of the time spent on the node. We denote by
$(\lambda_{1},\lambda_{2},\lambda_{2,3},\lambda_{2,4})$ the coefficients of a
possible equilibrium, that is: at $t=1$ the fraction given by
$\lambda_{1}\rho_{0}$ switches to $p_{1}$ and the fraction given by
$\lambda_{2}\rho_{0}$ switches to $p_{2}$; at time $t=3/2$, the fraction
$\lambda_{2}\lambda_{2,3}\rho_{0}$ switches from $p_{2}$ to $p_{3}$ and the
fraction $\lambda_{2}\lambda_{2,4}\rho_{0}$ switches from $p_{2}$ to $p_{4}$.
Still by linearity of the costs, such coefficients are founded by solving

(17)
$\begin{cases}2\lambda_{2}+\frac{3}{2}\lambda_{2}\lambda_{2,3}=\lambda_{1}\\\
2\lambda_{2}+\lambda_{2}\lambda_{2,4}=\lambda_{1}\\\
\lambda_{1}+\lambda_{2}=\lambda_{2,3}+\lambda_{2,4}=1\end{cases},$

which corresponds to, taking also account of the time spent on the node,

(18)
$\begin{cases}\frac{C_{2}(\lambda_{2}\rho_{0})}{2}+\frac{C_{3}(\lambda_{2}\lambda_{2,3}\rho_{0})}{2}=C_{1}(\lambda_{1}\rho_{0})\\\
\frac{C_{2}(\lambda_{2}\rho_{0})}{2}+\frac{C_{4}(\lambda_{2}\lambda_{2,4}\rho_{0})}{2}=C_{1}(\lambda_{1}\rho_{0})\\\
\lambda_{1}+\lambda_{2}=\lambda_{2,3}+\lambda_{2,4}=1\end{cases}.$

From (17), we obtain the unique solution

$(\lambda_{1},\lambda_{2},\lambda_{2,3},\lambda_{2,4})=\left(\frac{13}{18},\frac{5}{18},\frac{2}{5},\frac{3}{5}\right).$

This is an equilibrium because it generates the distribution

(19)
$\left(\frac{13}{18}\rho_{0},\frac{5}{18}\rho_{0},\frac{1}{9}\rho_{0},\frac{1}{6}\rho_{0}\right),$

which gives the cost, for each one of the three paths, equal to $13/18$. Hence
all the paths are equivalent and the distribution generates all the possible
extremal evolutions $(\rho_{0},0,0,0)$, $(0,\rho_{0},\rho_{0},0)$,
$(0,\rho_{0},0,\rho_{0})$ of which (19) is a juxtaposed convex combination.

Similarly as in (16), the uniqueness of the solution of (18) is guaranteed by
the following monotonicity conditions

(20)
$\begin{array}[]{ll}\displaystyle\left\\{\begin{array}[]{ll}\displaystyle\sum_{i=3}^{4}\left(C_{i}(\lambda\lambda^{\prime}_{2,i}\rho_{0})-C_{i}(\lambda\lambda_{2,i}^{\prime\prime}\rho_{0})\right)(\lambda_{2,i}^{\prime}-\lambda_{2,i}^{\prime\prime})>0\quad\text{for
every }\lambda>0,\\\ \displaystyle\end{array}\right.\\\
\displaystyle\left\\{\begin{array}[]{ll}\displaystyle\left(C_{1}(\lambda^{\prime}_{1}\rho_{0})-C_{1}(\lambda^{\prime\prime}_{1}\rho_{0})\right)(\lambda_{1}^{\prime}-\lambda_{1}^{\prime\prime})\\\
\displaystyle+\frac{1}{2}\left(C_{2}(\lambda^{\prime}_{2}\rho_{0})+C_{3}(\lambda_{2}^{\prime}\lambda_{2,3}^{\prime}\rho_{0})-C_{2}(\lambda_{2}^{\prime\prime}\rho_{0})-C_{3}(\lambda_{2}^{\prime\prime}\lambda_{2,3}^{\prime\prime}\rho_{0})\right)(\lambda_{2}^{\prime}-\lambda_{2}^{\prime\prime})>0\end{array}\right.\\\
\displaystyle\ \
\forall(\lambda^{\prime}_{1},\lambda^{\prime}_{2})\neq(\lambda^{\prime\prime}_{1},\lambda^{\prime\prime}_{2}),\
(\lambda_{2,3}^{\prime},\lambda_{2,4}^{\prime})\neq(\lambda_{2,3}^{\prime\prime},\lambda_{2,4}^{\prime\prime})\
\mbox{convex pairs and }\rho_{0}>0.\end{array}$

Indeed, by the second inequality we have the uniqueness of the pair of convex
coefficients $(\lambda_{1},\lambda_{2})$, which, putting $\lambda=\lambda_{2}$
in the first inequality, gives the uniqueness of the pair
$(\lambda_{2,3},\lambda_{2,4})$.

######  Remark 7.

Similarly as in Example 2 (see Figure 4) when the number of the nodes is $n$
instead of $3$, the uniqueness of the $n$-string of convex coefficients
satisfying $C_{i}(\lambda_{i}\rho_{0})=C_{j}(\lambda_{j}\rho_{0})$ for all
$i,j=1,\ldots,n$ is guaranteed by the monotonicity conditions as (16),
replacing $n=3$ by the generic $n$. As seen in Example 3 (see Figure 5), in
the case of more complex networks, the conditions are much more involved and
less treatable, because of the peculiar characteristics of the problem. The
topology of the network in fact strongly affects the monotonicity property,
the way of representing it and, ultimately, its applicability. However, we
point out that if all the single costs $C_{i}$ are strictly monotone, then
they will certainly satisfy the corresponding monotonicity property.

######  Remark 8.

In the two examples here presented, the switching instants are a-priori fixed
for all agents, and hence they do not enter in the optimization process
performed by the single agent. In our model, in the previous sections, we
instead consider also the switching time as well as the decisional time as
part of the control for the agents, and the costs also depend on them. This
fact obviously makes the situation much more complicated in order to establish
a reasonable condition for the uniqueness of the mean-field game.

######  Remark 9.

The monotonicity conditions (16) and (20) and their possible generalization to
more complicated networks, only guarantee the uniqueness of the possible
$n$-string of convex coefficients but not, in general, its existence. Note
that, if the (unique) solution presents some $\lambda_{i}=0$, then it means
that the corresponding node will be not reached by the equilibrium, but
anyway, even with zero mass, that node produces the same cost as the others.
Moreover, we may not have existence of the $n$-string convex solution. Looking
at Example 2 (generalized to $n$ intermediate nodes), this means that we do
not have a $n$-string which gives the fraction of mass switching to the $n$
nodes. This means that there is at least a node which must be not considered
in the game from the beginning. For example, a node $p_{i}$ such that
$C_{i}(\lambda_{i}\rho_{0})>C_{j}(\lambda_{j}\rho_{0})$ for all $j\neq i$ and
$\lambda_{i},\lambda_{j}$: it is a too expensive node, no one will switch to
it. In this situation, the actual game is with just $n-1$ nodes and not with
$n$. Hence, one must look for a possible unique $(n-1)$-string of convex
combination solving the corresponding problem without that node. Proceeding in
this way, one can find a possible unique $m$-string, and will set the other
components to $0$: no flow through such nodes. However note that in our model,
in the previous sections, we have also the time spent on the node at our
disposal, which possibly modulate the paid cost, and hence the situation is
more flexible but less prone to have a good condition for uniqueness.

The points and the questions of these last remarks are certainly worth
investigating and may be the argument of future studies.

##  Appendix B On the convexity of $V$ and single-valued feature of $\varphi$

Let us assume

$C(p,p^{\prime},t,\tau,\rho)=\frac{\bar{C}(p,p^{\prime},\rho)}{\tau-t},\quad\tau\longmapsto\tilde{C}(\bar{p},\tau)\
\text{strictly decreasing}.$

In particular, $\bar{C}$ does not explicitly depend on $t$ and $\tau$, for
example

$\bar{C}(p,p^{\prime},\rho)=\frac{a(p)}{T}\int_{0}^{T}\rho_{p}(s)ds+\frac{a(p^{\prime})}{T}\int_{0}^{T}\rho_{p^{\prime}}(s)ds$

for some weight $p\longmapsto a(p)$. A possible strictly non-decreasing
$\tilde{C}$ is $\tilde{C}(\bar{p},\tau)=T-\tau$.

Let $p_{1}$ be a node directly linked to $\bar{p}$, i.e.
$\sum_{i}p_{1}^{i}=N-1$, and let $t<T$. Hence we have

$V(p_{1},t)=\inf_{\tau\in]t,T]}\left\\{\frac{\bar{C}(p_{1},\bar{p},\rho)}{\tau-t}+\tilde{C}(\bar{p},\tau)\right\\}=\frac{\bar{C}(p_{1},\bar{p},\rho)}{T-t}+\tilde{C}(\bar{p},T).$

Therefore, $t\longmapsto V(p_{1},t)$ is strictly convex and $\varphi(t)=T$ is
single-valued.

Now, let $p_{2}$ be a node linked to $\bar{p}$ with two switches, i.e.
$\sum_{i}p_{2}^{i}=N-2$, and let $p_{1}\in{\cal I}_{p_{2}}$ and $t<T$. We
consider the function

$\psi_{p_{2},p_{1}}:]t,T[\ni\tau\longmapsto
V(p_{1},\tau)+\frac{\bar{C}(p_{2},p_{1},\rho)}{\tau-t}=\frac{\bar{C}(p_{1},\bar{p},\rho)}{T-\tau}+\tilde{C}(\bar{p},T)+\frac{\bar{C}(p_{2},p_{1},\rho)}{\tau-t}.$

Note that $\lim_{\tau\to t^{+}}\psi_{p_{2},p_{1}}(\tau)=\lim_{\tau\to
T^{-}}\psi_{p_{2},p_{1}}(\tau)=+\infty$. Hence, the minimization problem

$\inf_{\tau\in]t,T[}\psi_{p_{2},p_{1}}(\tau)$

has a solution $\varphi_{p_{2},p_{1}}(t)\in]t,T[$ and it must be

(21)
$\frac{\bar{C}(p_{1},\bar{p},\rho)}{(T-\varphi_{p_{2},p_{1}}(t))^{2}}-\frac{\bar{C}(p_{2},p_{1},\rho)}{(\varphi_{p_{2},p_{1}}(t)-t)^{2}}=0,$

which gives a unique possible point of minimum

$\varphi_{p_{2},p_{1}}(t)=\frac{\sqrt{\frac{\bar{C}(p_{2},p_{1},\rho)}{\bar{C}(p_{1},\bar{p},\rho)}}T+t}{\sqrt{\frac{\bar{C}(p_{2},p_{1},\rho)}{\bar{C}(p_{1},\bar{p},\rho)}}+1}\in]t,T[,$

and note that $\varphi$ is strictly increasing and linear and hence derivable.
Moreover, its derivative satisfies

(22) $0<\varphi^{\prime}_{p_{2},p_{1}}(t)<1.$

We now consider the function

$V_{p_{2},p_{1}}:t\longmapsto\psi_{p_{2},p_{1}}(\varphi_{p_{2},p_{1}}(t))=\frac{\bar{C}(p_{1},\bar{p},\rho)}{T-\varphi_{p_{2},p_{1}}(t)}+\tilde{C}(\bar{p},T)+\frac{\bar{C}(p_{2},p_{1},\rho)}{\varphi_{p_{2},p_{1}}(t)-t},$

which represents the optimum when, being in $p_{2}$ at time $t$, the agent
decides that it will switch to $p_{1}$ before $T$, that is it will perform the
path $p_{2}\to p_{1}\to\bar{p}$. Such a function is then twice derivable and
it is strictly convex in $]0,T[$. Indeed, taking account of (21) and (22), it
is

$V^{\prime\prime}_{p_{2},p_{1}}(t)=\frac{2\bar{C}(p_{2},p_{1},\rho)(\varphi_{p_{2},p_{1}}(t)-t)(1-\varphi^{\prime}_{p_{2},p_{1}}(t))}{(\varphi_{p_{2},p_{1}}(t)-t)^{4}}>0.$

Note that we do not need the second derivative of $\varphi_{p_{2},p_{3}}$
(even if it exists, in our example) because in the calculation of
$V^{\prime}_{p_{2},p_{1}}$ it cancels in view of (21). Finally, note that
$\lim_{t\to T^{-}}V_{p_{2},p_{1}}(t)=+\infty$.

Now, we take $p_{3}$ such that $p_{2}\in{\cal I}_{p_{3}}$ and consider the
function

$V_{p_{3},p_{1},p_{1}}:t\longmapsto\inf_{\tau\in]t,T[}\left\\{V_{p_{2},p_{1}}(\tau)+\frac{\bar{C}(p_{3},p_{2},\rho)}{\tau-t}\right\\},$

which represents the optimum when, being in $p_{3}$ at time $t$, the agent
decides that it will perform the path $p_{3}\to p_{2}\to p_{1}\to\bar{p}$.
Note that the function $]t,T[\ni\tau\longmapsto\psi_{p_{3},p_{2},p_{1}}$,
inside the minimization, is twice derivable and satisfies $\lim_{\tau\to
t^{+}}\psi_{p_{3},p_{2},p_{1}}(\tau)=\lim_{\tau\to
T^{+}}\psi_{p_{3},p_{2}.p_{4}}(\tau)=+\infty$. Hence the minimization process
has a solution $\varphi_{p_{3},p_{2},p_{1}}(t)\in]t,T[$, and such a solution
is unique. Indeed, again, it must be

(23)
$V^{\prime}_{p_{2},p_{1}}(\varphi_{p_{3},p_{2},p_{1}}(t))=\frac{\bar{C}(p_{3},p_{2},\rho)}{(\varphi_{p_{3},p_{2},p_{1}}(t)-t)^{2}}.$

Whereas $\tau\longmapsto V^{\prime}_{p_{2},p_{1}}(\tau)$ is strictly
increasing (being $V_{p_{2},p_{1}}$ strictly convex) and
$\tau\longmapsto\bar{C}(p_{3},p_{2},\rho)/(\tau-t)^{2}$ is strictly
decreasing, the solution $\varphi_{p_{3},p_{2},p_{1}}(t)\in]t,T[$ is unique.
Moreover, by the Implicit Function Theorem, $\varphi_{p_{3},p_{2},p_{1}}$ is
derivable. Differentiating the equality (23), we get (we write $\varphi$ for
$\varphi_{p_{3},p_{2},p_{1}}$)

$\left(V^{\prime\prime}_{p_{2},p_{1}}(\varphi(t)+\frac{2\bar{C}(p_{3},p_{1},\rho)(\varphi(t)-t)}{(\varphi(t)-t)^{4}}\right)\varphi^{\prime}(t)=\frac{2\bar{C}(p_{3},p_{2},\rho)(\varphi(t)-t)}{(\varphi(t)-t)^{4}},$

from which, being $V^{\prime\prime}_{p_{2},p_{1}}>0$ and $\varphi(t)>t$, we
get

(24) $0<\varphi^{\prime}_{p_{3},p_{2},p_{1}}(t)<1$

and in particular $\varphi_{p_{1},p_{2},p_{3}}$ is strictly increasing. Now,
we prove that (still denoting $\varphi_{p_{3},p_{2},p_{1}}$ by $\varphi$)

$t\longmapsto
V_{p_{3},p_{2},p_{1}}(t)=V_{p_{2},p_{1}}(\varphi(t))+\frac{\bar{C}(p_{3},p_{2},\rho)}{\varphi(t)-t}$

is strictly convex. Indeed, differentiating two times, taking account of (23)
and (24), we get again

$V^{\prime\prime}_{p_{3},p_{2},p_{1}}(t)=\frac{2\bar{C}(p_{3},p_{2},\rho)(\varphi(t)-t)(1-\varphi^{\prime}(t))}{(\varphi(t)-t)^{4}}>0.$

Again, note that we do not need the second derivative of $\varphi$ (even if it
exists, in our example) because in the calculation of
$V^{\prime}_{p_{3},p_{2},p_{1}}$ it cancels in view of (23). Finally note that
$\lim_{t\to T^{-}}V_{p_{3},p_{2},p_{1}}(t)=+\infty$.

Proceeding in this way we obtain that, for every path $p_{n}\to
p_{n-1}\to\cdots\to p_{1}\to\bar{p}$, the function

$V_{p_{n},p_{n-1},\ldots,p_{1}}(t)=\inf_{\tau\in]t,T[}\left\\{V_{p_{n-1},\ldots,p_{1}}(t)+\frac{\bar{C}(p_{n},p_{n-1},\rho)}{\tau-t}\right\\}$

is realized by a unique $\tau=\varphi_{p_{n},\ldots,p_{1}}(t)\in]t,T[$, it is
strictly convex, and $\varphi_{p_{n},\ldots,p_{1}}$ is strictly increasing
with derivative less than $1$.

We finally obtain that the value function, for all $p\neq\bar{p}$ and $t<T$,

$V(p,t)=\inf_{\begin{subarray}{c}\tau\in]t,T]\\\ p^{\prime}\in{\cal
I}_{p}\end{subarray}}\left\\{V(p^{\prime},\tau)+\frac{\bar{C}(p,p^{\prime},\rho)}{\tau-t}\right\\},$

is realized by a unique, strictly increasing (for $t$ such that
$\varphi(t)>T$) single-valued function $t\longmapsto\tau=\varphi(t)\in]t,T]$,
giving the optimal instant $\tau\in]t,T]$ for switching to the optimal node
$p^{\prime}\in{\cal I}_{p}$.

## References

  * 1. F. Al Saleh, T. Bakaryan, D. A. Gomes and R. Ribeiro,  First-order mean-field games on networks and Wardrop equilibrium,  https://arxiv.org/abs/2207.01397, (2022).
  * 2. F. Bagagiolo, S. Faggian, R. Maggistro and R. Pesenti,  Optimal Control of the Mean Field Equilibrium for a Pedestrian Tourists’ Flow Model,  _Networks and Spatial Economics_ , (2019).
  * 3. F. Bagagiolo, A. Festa and L. Marzufero,  A hybrid control framework for an optimal visiting problem,  _IFAC-PapersOnLine_ , 54(5) (2021), 241-246.
  * 4. F. Bagagiolo, A. Festa and L. Marzufero  Hybrid control for optimal visiting problems for a single player and for a crowd,  _Nonlinear Differential Equations and Applications_ , 29(1), 4 (2022).
  * 5. F. Bagagiolo, A. Festa and L. Marzufero,  The orienteering problem: a hybrid control formulation,  _IFAC-PapersOnLine_ , 54(5) (2021), 175-180.
  * 6. F. Bagagiolo, R. Maggistro and R. Pesenti,  Origin-to-destination network flow with path preferences and velocity controls: a mean field game-like approach,  _Journal of Dynamics and Games_ , 8(4) (2021), 359-380.
  * 7. C. Bertucci,  Fokker-Planck equations of jumping particles and mean field games of impulse control,  _Annales de l’Institut Henri Poincaré C, Analyse Non Linéaire_ , 37(5) (2020), 1211-1244.
  * 8. C. Bertucci,  Optimal stopping in mean field games, an obstacle problem approach,  _Journal de Mathématiques Pures et Appliquées_ , 120 (2018), 165-194.
  * 9. P. H. L. Bovy and S. P. Hoogendoorn,  Pedestrian Travel Behavior Modeling,  _Networks and Spatial Economics_ , 5(2) (2005), 139-216.
  * 10. F. Camilli, E. Carlini and C. Marchi,  A model problem for Mean Field Games on networks,  _Discrete and Continuous Dynamical Systems_ , 35(9) (2015), 4173-4192.
  * 11. F. Camilli, R. De Maio and A. Tosin,  Transport of measures on networks,  _Networks and Heterogeneous Media_ , 12(2) (2017), 191-215.
  * 12. P. Cardaliaguet and P. J. Graber,  Mean field games systems of first order,  _ESAIM Control, Optimisation and Calculus of Variations_ , 21(3) (2015), 690-722.
  * 13. P. Centorrino, A. Corbetta, E. Cristiani and E. Onofri,  Managing crowded museums: Visitors flow measurement, analysis, modeling, and optimization,  Journal of Computational Science, 53 (2021).
  * 14. M. Chowdhury, S. Yang, S. Khuller, J. You and M. Purohit,  Near Optimal Coflow Scheduling in Networks,  _SPAA ’19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures_ , (2019), 123-134.
  * 15. L. C. Evans and R. F. Gariepy,  _Measure theory and fine properties of functions_ ,  Revised edition, CRC press, USA, 2015.
  * 16. A. Festa and S. Göttlich,  A mean field game approach for multi-lane traffic management,  _IFAC-PapersOnLine_ , 5(32) (2018), 793-798.
  * 17. D. A. Gomes and J. Saùde,  Mean Field Games Models – A Brief Survey,  _Dynamic Games and Applications_ , 4(2) (2014), 110-154.
  * 18. T. Gonzalez and S. Sahni,  Open Shop Scheduling to Minimize Finish Time,  _Journal of the ACM_ , 23(4) (1976), 665-679.
  * 19. M. Huang, R. P. Malhamé and P. E. Caines,  Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainly equivalence principle,  _Communications in Information and Systems_ , 6(3) (2006), 221-252.
  * 20. J. M. Lasry and P. L. Lions,  Juex à champ moyen. II – Horizon fini et contrôle optimal,  _Comptes Rendus Mathematique_ , 343(10) (2006), 679-684.
  * 21. J. M. Lasry and P. L. Lions,  Mean field games,  _Japanese Journal of Mathematics_ , 2(1) (2007), 229-260.
  * 22. X. Li, S. Song,  _Impulsive Systems with Delays: Stability and Control_ ,  Springer, Singapore, 2022.
  * 23. M. Morandotti and F. Solombrino,  Mean-field Analysis of Multipopulation Dynamics with Label Switching,  _SIAM Journal on Mathematical Analysis_ , 52(2) (2020), 1427-1462.
  * 24. V. Pata,  _Fixed Point Theorems and Applications_ ,  Springer, 2019.
  * 25. M. L. Pinedo,  _Scheduling: Theory, Algorithms, and Systems_ ,  5rd Edition, Springer, Boston, 2012.