1

Collective Stochastic Discrete Choice
Problems:

arXiv:1604.08136v3 [] 17 Aug 2017

A Min-LQG Game Formulation
Rabih Salhab, Roland P. Malhamé and Jerome Le Ny

Abstract
We consider a class of dynamic collective choice models with social interactions, whereby a large
number of non-uniform agents have to individually settle on one of multiple discrete alternative choices,
with the relevance of their would-be choices continuously impacted by noise and the unfolding group
behavior. For example, a large collection of geographically dispersed micro robots might need to gather,
in a self organized mode and with least energy expenditure, at various known potential sites of interest,
where groups of sufficient size would be required to perform collective tasks, such as search and
rescue. This class of problems is modeled here as a so-called Min-LQG game, i.e., a linear quadratic
Gaussian dynamic and non-cooperative game, with an additional combinatorial aspect in that it includes
a final choice-related minimization in its terminal cost. The presence of this minimization term is key
to enforcing some specific discrete choice by each individual agent. The theory of mean field games is
invoked to generate a class of decentralized agent feedback control strategies which are then shown to
converge to an exact Nash equilibrium of the game as the number of players increases to infinity. A key
building block in our approach is an explicit solution to the problem of computing the best response
of a generic agent to some arbitrarily posited smooth mean field trajectory. Ultimately, an agent is
shown to face a continuously revised discrete choice problem, where greedy choices dictated by current
conditions must be constantly balanced against the risk of the future process noise upsetting the wisdom
of such decisions. Even though an agent’s ultimately chosen alternative is random and dictated by its
entire noise history and initial state, the limiting infinite population macroscopic behavior can still be
predicted. It is shown that any Nash equilibrium of the game is defined by an a priori computable
This work was supported by NSERC under Grants 6820-2011 and 435905-13. The authors are with the department of
Electrical Engineering, Polytechnique Montreal and with GERAD, Montreal, QC H3T-1J4, Canada {rabih.salhab,

roland.malhame, jerome.le-ny}@polymtl.ca.

August 21, 2017

DRAFT

2

probability matrix characterizing the manner in which the agent population ultimately splits among the
available alternatives. For the scalar binary choice case with uniform dynamics and cost functions, we
propose a numerical scheme to compute this probability matrix and the associated decentralized Nash
strategies. The results are illustrated through simulations.

Index Terms
Mean Field Games, Stochastic Optimal Control, Discrete Choice Models.

I. I NTRODUCTION
Discrete choice problems arise in situations where an individual makes a choice among a
discrete set of alternatives, such as modes of transportation [1], entry and withdrawal from
the labor market, or residential locations [2]. In some situations, the individuals’ choices are
considerably influenced by the social behavior. For example, in schools, teenagers’ decisions to
smoke are affected by some personal factors, as well as by their peers’ behavior [3].
In this paper, we study a discrete choice problem for a large population of agents in a dynamic
setting, capturing in particular the influence of the population’s state and the efforts that must
be exerted over time by an individual before reaching a decision. For example, as in [4]–[6], a
group of robots exploring an unknown terrain might need to move within a finite time horizon
from their initial positions towards one of multiple sites of interest. While moving, each robot
optimizes its efforts to remain close to the group and to arrive at the end of the time horizon in the
vicinity of one of the predefined sites. The group may split, but the size of the subgroups should
remain large enough to perform some collective tasks, such as search and rescue. Our model
could also be used to study a mechanistic representation of opinion crystallization in elections
[7], [8], where voters continuously update their opinions until forming a final decision regarding
who they should vote for. Along the path to choose a candidate, changing one’s decision requires
an effort, but at the same time, deviations from the others’ opinions involve a discomfort.
McFadden laid in [9] the theoretical foundations of static discrete choice models, where an
agent chooses among a finite set of alternatives the one that maximizes its utility. This utility
depends on some potentially observable attributes (such as the agent’s financial status in the
example of residential location choice) that dictate a deterministic trend in the choice, and other
attributes idiosyncratic to that agent, which are not known by the economist or social planner
August 21, 2017

DRAFT

3

carrying out the macroscopic analysis, although they may influence the choice. As a result,
utility is defined as the sum of a known deterministic term plus a random term. Later, Rust [10]
introduced a dynamic discrete choice model involving a Markov decision process for each agent.
While peer pressure effects are absent in Rust’s and McFadden’s models, Brock and Durlauf [11]
discuss a discrete choice problem with social interactions modeled as a static noncooperative
game, where a large number of agents have to choose between two alternatives while being
influenced by the average of the choices. The authors analyze the model using an approach
similar to that of a static Mean Field Game (MFG), and inspired by statistical mechanics.
The Brock-Durlauf model includes peer influence but is static, and in Rust’s model, the
agents are required to make a choice repeatedly at each discrete time period but under no
social influence. In our model, the agents are instead continuously reassessing the adequacy of
their would-be choices and current actions along their random state-space path, up until the
end of the control horizon, at which point their ultimate choice of alternative becomes fully
crystallized. Thus, our formulation helps in modeling situations where alternative choices are
identified as potential destination points in a suitable state space (e.g., physical space in the
robotics example, or opinion space in the election example), and implementation of a given choice
involves movement towards a final destination state, requiring control effort and constrained by
specific dynamics.
Recently, we introduced a related dynamic collective choice model with social interactions in
[12]–[14]. In these articles, we study using the MFG methodology a dynamic game involving a
large number of players choosing between multiple destination points. The agents’ dynamics are
deterministic with random initial conditions. We show that multiple approximate (epsilon) Nash
equilibria may exist, each characterized by a vector describing the way the population splits
between the alternatives. The strategies developed in these papers are open loop decentralized
policies, in the sense that to make its choice of trajectory and destination, an agent needs to know
only its initial state and the initial distribution of the population. In particular, in this formulation
each agent can commit from the start to its final choice, which implies that the model with
deterministic dynamics is not sufficiently rich to fully capture opinion change phenomena. In
contrast, we consider here the fully stochastic case where a large number of players moving
according to a set of controlled diffusion processes should lie at time T in the vicinity of one
of multiple predefined destination points. Along their path, they are influenced by the average
August 21, 2017

DRAFT

4

state of the population and try to develop as little effort as possible to approach one of these
destinations. By introducing noise in the dynamics we can model for example the unexpected
events that influence a voter’s opinion during electoral campaigns or the random forces that
perturb a robot’s trajectory while choosing a site to visit. The presence of this noise requires
the agents to use bona fide feedback strategies and prevents them from committing to a choice
before the final time. However, one can still anticipate asymptotically the manner in which an
infinite population splits among the set of alternatives.
A. Mean Field Game Methodology and Contributions of This Paper
The MFG methodology that we again follow in this paper was introduced in a series of
papers by Huang et al. [15]–[17], and independently by Lions and Lasry [18]–[20]. It is a
powerful technique to analyze dynamic games involving a large number of agents anonymously
interacting through their mean field, i.e., the empirical distributions of the agents’ states. Analysis
starts by considering the limiting case of a continuum of agents. For agents evolving according to
diffusion processes, the equilibrium of the game can be shown to be characterized by the solution
of two coupled partial differential equations (PDE), a Hamilton-Jacobi-Bellman (HJB) equation
propagating backwards and a Fokker-Planck (FP) equation propagating forwards. Indeed, the
former characterizes the agents’ best response to some posited candidate mean field trajectory,
while the latter propagates the would-be resulting mean field when all agents implement the
computed best responses. Consistency requires that sustainable mean field trajectories, if they
exist, be replicated in the process. Limiting equilibria are thus required to satisfy a system of
fixed point equations, herein given by the coupled HJB-FP equations. The corresponding best
responses, when applied to the finite population, constitute approximate Nash equilibria (-Nash
equilibria) [16], [17], in the following sense.
Definition 1: Consider N agents, a set of strategy profiles S = S1 × . . . × SN , and for each
agent i, a cost function Ji (u1 , . . . , uN ), for (u1 , . . . , uN ) ∈ S. A strategy profile (u∗1 , . . . , u∗N ) ∈ S
is called an -Nash equilibrium with respect to the costs Ji if there exists an  > 0 such that,
for any fixed 1 ≤ i ≤ N , for all ui ∈ Si , we have Ji (ui , u∗−i ) ≥ Ji (u∗i , u∗−i ) − .
The main contributions and structure of the paper are described next. In Section II, we present
the mathematical formulation of our multi-agent dynamic discrete choice problem. Then in
Section III, we postulate a known trajectory for the agents population mean state, and compute
August 21, 2017

DRAFT

5

the best response strategy of a generic agent. This involves solving a modified version of the
standard Linear Quadratic Gaussian (LQG) optimal tracking problem, which we call the MinLQG optimal tracking problem, where the final cost is replaced by a minimum of l distances to
capture the discrete choice between l alternatives. We give an explicit expression for the generic
agent’s best response (Min-LQG optimal control law), and show that at each instant, it can be
interpreted as a static discrete choice model [9], where the cost for the agent of choosing one
of the alternatives includes an additional term that increases with the risk of being driven to the
other alternatives by the process noise.
In Section IV we introduce the mean field equations, which allow us to compute the admissible
population distribution trajectories. By exploiting the relationship between dynamic programming
and the stochastic maximum principle, we establish a one-to-one map between the solutions of
the mean field equations and the fixed points of a finite dimensional map. The latter characterizes
the way the population splits between the alternatives. We show the existence of a fixed point for
this map and propose in the binary choice case a numerical scheme to compute it. Our model
lies somewhere between the MFG LQG models studied in [15], [16] and the fully nonlinear
MFGs considered in [17]–[20]. On the one hand, in the LQG case the optimal strategies are
linear feedback policies, whereas in our case they are nonlinear. On the other hand, an explicit
solution in the general nonlinear case is not possible, while we provide in this paper an explicit
form of the optimal strategies. Moreover, the existence and uniqueness of solutions of the mean
field equations are shown in the general case under some strong regularity and boundedness
conditions on the dynamics and cost coefficients [17]–[20]. In this paper, however, the quadratic
running cost and linear dynamics make it possible to relax these assumptions.
Finally, Section V discusses some numerical simulations illustrating the results, and Section
VI presents our conclusions. Overall, the paper develops a set of decentralized closed-loop
strategies forming an approximate Nash equilibrium for our multi-agent dynamic discrete choice
problem. This equilibrium converges to an exact Nash equilibrium as the size of the population
increases to infinity. To compute its optimal control at each time, an agent only needs to know
its current individual state and the initial distribution of the population, which could be learned
by a consensus-like algorithm for example [21]. The rationality assumption in MFGs allows us
to drastically reduce the amount of coordination needed between the players, by predicting the
evolution of the population distribution. In practice, with a finite number of players, errors in
August 21, 2017

DRAFT

6

this prediction build up over time, but could be corrected by periodic communication between
agents to re-estimate their current distribution.
B. Notation
Given an Euclidean space X, B(c, r) denotes the ball of radius r centered at c, xk the k-th
element of x ∈ X, and x−i the vector (x1 , . . . , xi−1 , xi+1 , . . . , xN ). ⊗ denotes the Kronecker
product. The n×n identity matrix is In , M 0 denotes the transpose of a matrix M , Tr(M ) its trace
and |M | its determinant. The notations M  0 and M  0 stand respectively for M positive
q
definite and positive semi-definite. Given an n×n matrix Q  0 and x ∈ Rn , 12 x0 Qx is denoted
by kxkQ . The minimum and maximum eigenvalues of a square matrix Q are written λmin (Q)
and λmax (Q). Let X and Y be two subsets of Euclidean spaces. The set of functions from X to
Y is denoted by Y X . ∂A, Int(A) and Ā denote respectively the boundary, interior and closure
of a subset A ⊂ X. C(X) refers to the set of Rn -valued continuous functions on X with the
standard supremum norm k.k∞ , and C i,j (X × Y ) to the set of real-valued continuous functions
f (x, y) on X × Y such that the first i partial derivatives with respect to the x variable and the
first j partial derivatives with respect to the y variable are continuous. The normal distribution
of mean µ and covariance matrix Σ is denoted by N (µ, Σ).
II. M ATHEMATICAL M ODEL
We present in this section the dynamic collective choice model with social interactions. We
consider a dynamic noncooperative game involving a large number N of players with the
following stochastic dynamics:
dxi (t) = (Ai xi (t) + Bi ui (t)) dt + σi dwi (t),

(1)

for 1 ≤ i ≤ N , where Ai ∈ Rn×n , Bi ∈ Rn×m , σi ∈ Rn×n , and {wi , 1 ≤ i ≤ N } are
N independent Brownian motions in Rn on a probability space (Ω, F, P, {Ft }t∈[0,T ] ), where
{Ft }t∈[0,T ] is the Brownian filtration generated by {wi , 1 ≤ i ≤ N } [22, Section 2.7]. In the
remaining of the paper, P(A) denotes the probability of an event A, E(X) the expectation of a
random variable X and M([0, T ], Rn ) the set of progressively measurable Rn -valued functions
with respect to the filtration {Ft }t∈[0,T ] . We assume that the matrices σi , 1 ≤ i ≤ N , are invertible
and that the initial conditions {xi (0), 1 ≤ i ≤ N } are independent and identically distributed
August 21, 2017

DRAFT

7

(i.i.d.) and also independent of {wi , 1 ≤ i ≤ N }. Moreover, we assume that Ekxi (0)k2 < ∞.
The vector xi (t) ∈ Rn is the state of player i at time t and ui (t) ∈ Rm its control input. Let
pj , 1 ≤ j ≤ l, be l points in Rn . Each player is associated with the following individual cost
functional:
Z
Ji (xi (0), ui , u−i ) = E
0

T



kxi −

x̄k2Qi +kui k2Ri

dt + min kxi (T ) −
1≤j≤l

pj k2Mi


xi (0) ,

(2)

where T > 0, Qi  0, Ri  0 and Mi  0. Along the path, the running cost encourages the
P
players to remain grouped around the average of the population x̄(t) := N
i=1 xi (t)/N , which
captures the social effect, and to develop as little effort as possible. The form of the final cost
captures the discrete choice aspect, if we assume Mi large. That is, a player i at time T should
be close to one of the destination points pj ∈ Rn , otherwise it is strongly penalized. Hence,
the overall individual cost captures the problem faced by each agent of deciding between l
alternatives, while trying to remain close to the mean population trajectory.
The players interact through the average x̄ of the population. Even though the running cost
is linear and quadratic, the minimum term in the final cost changes drastically the analysis of
the game with respect to the standard LQG MFG problems [15], [16]. In fact, as shown later
in (14), the optimal strategies are nonlinear feedback policies, whereas they are linear in the
standard LQG MFG problems. Moreover, to anticipate the mean trajectory x̄, the players need
in the LQG case to know only the initial mean of the population. In our case, they need to know
the full initial distribution in order to compute a solution of the nonlinear mean field equations
defined later in (24).
Let us denote the individual parameters θi := (Ai , Bi , σi , Qi , Ri , Mi ). We assume that there
are k types of agents, that is, θi takes values in a finite set {Θ1 , . . . , Θk }, which does not
depend on the size of the population N . As N tends to infinity, it is convenient to represent
the limiting sequence of (θi )i=1,...,N by realizations of a random vector θ, which takes values
in the same finite set {Θ1 , . . . , Θk }. Let us denote the empirical measure of the sequence θi
P
N
as PθN (Θs ) = 1/N N
i=1 1{θi =Θs } for s = 1, . . . , k. We assume that Pθ has a weak limit
Pθ = (α1 , . . . , αk ) as N → ∞ For further discussions about this assumption, one can refer to
[24].
We define the set of admissible control laws for each agent as follows


Z T
m
2
U = u ∈ M([0, T ], R ) E
ku(s)k ds < ∞, .

(3)

0
August 21, 2017

DRAFT

8

We define the set of admissible Markov policies
n
n
L = u ∈ (Rm )[0,T ]×R |∃L1 > 0, ∀(t, x) ∈ [0, T ] × Rn , ku(t, x)k≤ L1 (1 + kxk), and
o (4)
∀r > 0, T 0 ∈ (0, T ), ∃L2 > 0, ∀k(x, y)k≤ r, t ∈ [0, T 0 ], ku(t, x) − u(t, y)k≤ L2 kx − yk .
If u ∈ L, then the stochastic differential equation (SDE) (1), with ui equal to u(t, xi ), has a unique
strong solution [22, Section 5.2]. As shown below in Theorem 6, the developed strategies form
−Nash equilibria with respect to the space of admissible actions U. Moreover, these strategies
can be expressed as Markov policies (feedback policies), see (14).
III. T HE “M IN -LQG” O PTIMAL T RACKING P ROBLEM
AND THE

G ENERIC AGENT ’ S B EST R ESPONSE

Following the MFG approach, we start by assuming a continuum of agents for which one
can ascribe a deterministic macroscopic behavior x̄ (posited mean population state), which is
supposed known in this section. The problem of determining x̄ is treated in Section IV. In order
to compute its best response to x̄, a generic agent with parameters θ = (A, B, σ, Q, R, M ) ∈
{Θ1 , . . . , Θk } solves the following optimal control problem, which we call the “Min-LQG”
optimal tracking problem:
T

Z



inf J (x(0), u, x̄) = inf E

u∈U

u∈U

kx −

x̄k2Q +kuk2R

0

dt + min kx(T ) −
j=1,...,l

pj k2M


x(0)
(5)

s.t. dx(t) = (Ax(t) + Bu(t)) dt + σdw(t),
where w is a Brownian motion in Rn on the probability space (Ω, F, P) and x(0) is a random
vector independent of w and distributed according to the known distribution of the agents’ initial
and
states. Herein, ∂h(t,x)
∂x

∂ 2 h(t,x)
∂x2

will denote respectively the gradient and Hessian matrix of the

real function h with respect to x ∈ Rn . The optimal cost-to-go function of (5) satisfies the
following HJB equation [25]
∂V
∂V
1
−
= x0 A0
−
∂t
∂x
2
V (T, x) = min kx −
1≤j≤l



∂V
∂x

pj k2M ,

0

 2

1
0∂ V
BR B
+ Tr σ
σ + kx − x̄k2Q
2
∂x
2
∂x
−1

0 ∂V

(6)

n

∀x ∈ R .

In the following, we linearize equation (6) under appropriate conditions, using a generalized
Hopf-Cole transformation [26, Section 4.4]. Moreover, we derive an explicit formula for the

August 21, 2017

DRAFT

9

solution of (6) and the min-LQG optimal control law. The results of this section are proved in
Appendix A.
The following notation is used in the remaining of the paper. We define x(j) , u(j) and Vj to
be the optimal state trajectory, optimal control law and optimal cost-to-go of the LQG tracking
problem that the generic agent must solve when pj is the only available alternative, that is, (5)
with pk = pj , for all k ∈ {1, . . . , l}. Recall that [27, Chapter 6]
1
Vj (t, x) = x0 Π(t)x + x0 βj (t) + δj (t)
2
u(j) (t, x) = −R−1 B 0 (Π(t)x + βj (t))

dx(j) (t) = Ax(j) (t) + Bu(j) t, x(j) (t) dt + σdw(j) (t),

(7)
(8)
(9)

where Π, βj and δj are the unique solutions of
d
Π(t) = Π(t)BR−1 B 0 Π(t) − A0 Π(t) − Π(t)A − Q,
dt
0
d
βj (t) = − A − BR−1 B 0 Π(t) βj (t) + Qx̄(t),
dt
d
1
1
δj (t) = βj (t)0 BR−1 B 0 βj (t) − Tr(σ 0 Π(t)σ) − kx̄(t)k2Q ,
dt
2
2

(10)

with Π(T ) = M, βj (T ) = −M pj and δj (T ) = kpj k2M .
Remark 1: The final cost in (5) is non-smooth. Hence, the corresponding HJB equation (6) and
its transformed parabolic equation (30) below have non-smooth terminal conditions. However, as
shown later in Lemma 8, these partial differential equations (PDEs) smooth out their solutions,
i.e., the only non-smoothness occurs at the terminal time. Hence, all the PDE solutions in the
remaining sections are to be understood in the strong sense.
In the following, we denote by Wj , for j ∈ {1, . . . , l}, the Voronoi cell associated with pj ,
that is, Wj = {x ∈ Rn such that kx − pj kM ≤ kx − pk kM , for all 1 ≤ k ≤ l}. We define for all
j ∈ {1, . . . , l} the following notation for the conditional probability of an agent following the
control law u(j) to be in the Voronoi cell j at time T if its state at time t is x


gj (t, x) , P x(j) (T ) ∈ Wj x(j) (t) = x ,

(11)

where x(j) is defined in (9). To linearize and solve the HJB equation (6) using the Hopf-Cole
transformation (see Appendix A), we make the following assumption.
Assumption 1: We assume that there exists a scalar η > 0 such that BR−1 B 0 = ησσ 0 .
August 21, 2017

DRAFT

10

Remark 2: Note the following:
i. Assumption 1 always holds in the scalar case (n = m = 1).
ii. If η exists, then it is strictly positive.
iii. If η exists, since we assumed that σ is invertible, so is BR−1 B 0 , and thus ker B 0 = {0}.
In particular, the dimension of control space is greater or equal to that of the state space
(m ≥ n). Then we must choose R = η1 B 0 (σσ 0 )−1 B, for some η > 0.
iv. Assumption 1 is satisfied in particular if B = R = σ = In , a situation that has been studied
previously in the context of other mean-field games (with A = 0) using the Hopf-Cole
transformation, see [28, Chapter 2] and the references therein.
We now state the main result of this section.
Theorem 1: Under Assumption 1, the HJB equation (6) has a unique solution (t, x) 7→ V (t, x)
in C 1,2 ([0, T ) × Rn ) ∩ C([0, T ] × Rn ), defined as
!
l
X
1
exp (−ηVj (t, x)) gj (t, x) , ∀(t, x) ∈ [0, T ) × Rn
V (t, x) = − log
η
j=1

(12)

V (T, x) = min kx − pj k2M , ∀x ∈ Rn ,
j=1,...,l

where Vj and x(j) are defined in (7) and (9).
Having solved the HJB equation related to the Min-LQG optimal control problem (5), we
now prove the existence of a unique optimal control law. We define the following function:
u∗ (t, x) = −R−1 B 0

∂V
,
∂x

t ∈ [0, T )
(13)

u∗ (T, x) = 0.
Theorem 2: The following statements hold:
i. The function u∗ defined in (13) has on [0, T ) × Rn the following form:
u∗ (t, x) =

l
X

exp (−ηVj (t, x)) gj (t, x)
Pl

j=1

k=1

exp (−ηVk (t, x)) gk (t, x)

u(j) (t, x),

(14)

with Vj , u(j) defined in (7) and (8).
ii. u∗ is an admissible Markov policy.
iii. u∗ (t, x∗ (t, w)) is the unique optimal control law of (5), where x∗ (t, w) is the unique strong
solution of the SDE in (5) with u equal to u∗ (t, x).
August 21, 2017

DRAFT

11

In the degenerate case with σ = 0, it is shown in [12]–[14] that the optimal strategy of an
agent i in the Min-LQG problem is equal to u(j) (the optimal strategy in the presence of only
one alternative pj ) if the Linear Quadratic Regulator (LQR) control problem associated with pj
is the least costly starting from xi (0). Therefore, a generic agent commits from the start to its
final choice based on its initial state. When σ 6= 0, the generic agent can no longer be “decisive”.
Its optimal control law (14) is a convex combination of the optimal policies u(j) , j = 1, . . . , l.
The weights of u(j) form a spatio-temporal Gibbs distribution [29], which puts more mass on
the less costly and risky destinations. A destination pj is considered riskier in state x at time t if
the Brownian motion has a higher chance of driving the state of an agent closer to a destination
different from pj at time T , when this agent implements u(j) from (x, t) onwards.
We claim in Section II that the final cost forces the agents to be close to one of the destination
points at time T . In the following Lemma, we show in fact that in the scalar case, the probability
that an agent is close to one of the desitnation points increases with the final cost’s coefficient
M . The result is proved for paths x̄ that are uniformly bounded with respect to M , a property
that is shown to hold later in Theorem 5 for the fixed point paths x̄.
Lemma 3: Suppose that the paths x̄ are uniformly bounded with respect to M for the norm
 12
R
T
2
. Then, for any  > 0,
k.k
dt
0


σ 2 log M
1
+
P (|x∗ (T ) − pj |> , ∀1 ≤ j ≤ l) = o
.
M
2 M
In the rest of this section, we discuss the relation between our solution to the Min-LQG optimal
control problem in the scalar binary choice case and the solution of static discrete choice models.
We start by recalling some facts about the static models. In the standard binary discrete choice
models, a generic person chooses between two alternatives 1 and 2. The cost paid by this person
when choosing an alternative j is defined by vj = k(j) + ν, where k(j) is a deterministic
function that depends on personal publicly observable attributes and on alternative j, while ν
is a random variable accounting for personal idiosyncrasies unobservable by the social planner.
When ν is distributed according to the extreme value distribution [9], then the probability that
a cost-minimizing generic person chooses an alternative j is equal to Pj =

August 21, 2017

exp(−k(j))
.
exp(−k(1))+exp(−k(2))

DRAFT

12

Now, the Min-LQG optimal control law (14) can be written as follows:


exp −η Ṽ1 (t, x)



 u(1) (t, x)
u∗ (t, x) =
exp −η Ṽ1 (t, x) + exp −η Ṽ2 (t, x)


exp −η Ṽ2 (t, x)



 u(2) (t, x),
+
exp −η Ṽ1 (t, x) + exp −η Ṽ2 (t, x)

(15)

where
Ṽj (t, x) = Vj (t, x) −

1
log (gj (t, x)) ,
η

j = 1, 2.

(16)

Here Vj (t, x) is the expected cost paid by a generic agent if pj is the only available alternative,
and u(j) (t, x) is the corresponding optimal policy. In the presence of two alternatives, the optimal
policy at time t is given by (15), which can be interpreted as a mixed strategy between two
pure strategies u(1) (t, x) (picking alternative p1 ) and u(2) (t, x) (picking alternative p2 ). Within
this framework, denoting by −j the alternative other than j, a generic agent at time t chooses
the alternative pj with probability


exp −η Ṽj (t, x)



.
P rj =
exp −η Ṽj (t, x) + exp −η Ṽ−j (t, x)
Thus, the Min-LQG problem can be viewed at each time t ∈ [0, T ] as a static discrete choice
problem, where the cost of choosing alternative pj includes an additional term − η1 log (gj (t, x))
which goes to zero when the probability gj (t, x) of landing inside of the Voronoi cell Wj
associated with alternative j at time T approaches one. In effect, this additional term measures
the expected cost due to the risk inherent to an early choice, i.e., one based on a premature
decision at time t < T in favor of one alternative, for example alternative pj , thus applying all
the way the pure strategy u(j) (t, x), while ignoring the possibility that by time T , the Brownian
motion could drive the agent’s state toward the −j alternative.
IV. T HE M EAN F IELD E QUATIONS AND T HE F IXED P OINT P ROBLEM
In Section III, we assumed the mean trajectory x̄ known and we computed the generic agent’s
best response to it, which is given by (14). In the following, a superscript s refers to an agent
with parameters Θs ∈ {Θ1 , . . . , Θk }. We write us∗ (t, x, x̄) instead of us∗ (t, x) to emphasize the
dependence on x̄. We now seek a sustainable macroscopic behavior x̄, in the sense that it
August 21, 2017

DRAFT

13

is replicated by the mean of the generic agent’s state under its best response to it. Thus, an
admissible x̄ satisfies the following Mean Field equations:
x̄(t) =

k
X

αs x̄s (t), with x̄s = E[xs∗ ], 1 ≤ s ≤ k,

(17)

s=1

dxs∗ (t) = (As xs∗ (t) + B s us∗ (t, xs∗ (t), x̄)) dt + σ s dws (t),
where xs∗ (0), 1 ≤ s ≤ k, are independent and identically distributed according to the initial
distribution of the players, i.e., the distribution of xi (0), αs are defined in Section II and
{w1 , . . . , wk } are k independent Brownian motions, assumed independent of {x1∗ (0), . . . , xk∗ (0)}.
Solving (17) directly is no easy task. Indeed, this is an n × k nonlinear Mckean-Vlasov
equation [17], where the drift term depends on the joint probability law of the k types of generic
agents through the mean trajectory x̄. However, we derive in Lemma 4 below an equivalent
representation for a solution x̄ of (17), based on the solution of a deterministic optimal control
problem, consisting of two linear forward-backward ODEs (see (19a)-(19b) below), with a
nonlinear coupling in the boundary condition (see (20a)-(20b)) through what we call a “Choice
Distribution Matrix” (CDM). A CDM is a k × l row stochastic matrix with its (s, j) entry equal
to the probability that the generic agent of type s is at time T closer (in the sense of the M weighted l2 norm) to pj than any of the other alternatives when it optimally responds to x̄.
Equations (19a)-(19b) are respectively the expectations of the generic agents’ state (see (1)) and
co-state equations (see (34)), together with that of their boundary conditions (see (35)), when
the input in (1) associated with the agents’ best response is expressed in terms of the co-state.
The state and co-state equations follow from the stochastic maximum principle of the Min-LQG
problem, which we derive in Lemma 9 in Appendix B. The advantage of this new representation
is that if one considers the CDM in the q̄(T ) boundary condition as a parameter (say any k × l
row stochastic matrix), then equations (19a)-(19b) become totally linear. As a result, they have
under Assumption 2 below an explicit solution (the term that multiplies P1 in (22)) parametrized
by the stochastic matrix. This implies that the solutions x̄ of the mean field equations lies in the
family of paths (22) parametrized by the k × l row stochastic matrices. Conversely, in order to
have a path x̄Λ parametrized by some candidate Λ be a solution of (17), consistency requires
that Λ be equal to the associated CDM as expressed in (20a) when the generic agents optimally
respond to x̄Λ . This is equivalent to requiring that Λ be a fixed point of the finite dimensional
August 21, 2017

DRAFT

14

map F defined by (23). Indeed, F maps a row stochastic matrix Λ to the CDM when the generic
agents optimally respond to x̄Λ .
In effect, we establish that there is a one to one map between the solutions x̄ of (17) and
the fixed points of the finite dimensional map F . Theorem 5 below summarizes the related
results: point (i) of the theorem states the existence of the one-to-one map in question, while
point (ii) states that there is at least one fixed point of F . Thus, a Nash equilibrium CDM exists
(equivalently a solution of (17)) characterizing the way an infinite population, with the same
distribution of heterogeneous parameters as the original large but finite population, would split
between the destination points. The above results are proved in Appendix B.
In the following, we adopt the following notations. Let X̄ = (x̄1 , . . . , x̄k ), X∗ = (x1∗ , . . . , xk∗ ),
U∗ = (u1∗ , . . . , uk∗ ), W = (w1 , . . . , wk ), and p = (p1 , . . . , pl ). Let A, B, Q, R, M and σ be the
block-diagonal matrices diag(A1 , . . . , Ak ), diag(B 1 , . . . , B k ), diag(Q1 , . . . , Qk ), diag(R1 , . . . , Rk ),
diag(M 1 , . . . , M k ) and diag(σ 1 , . . . , σ k ) respectively. Define L = Ink − 1k ⊗ P1 , where 1k is a
column of k ones and P1 = Pθ0 ⊗ In where Pθ is defined in Section II. The following assumption
guarantees the existence and uniqueness of a solution for (19a)-(19b) whenever the CDM in the
q̄(T ) boundary condition is considered as a parameter.
Assumption 2: We assume the existence of a solution on [0, T ] to the following (nonsymmetric)
Riccati equation:
d
π = −A0 π − πA + πBR−1 B 0 π + QL,
dt

π(T ) = M.

(18)

Note that if Assumption 2 is satisfied, the solution of (18) is unique as a consequence of the
smoothness of the right-hand side of (18) with respect to π [30, Section 2.4, Lemma 1]. For a
uniform population, i.e., k = 1, we have L = 0 and hence Assumption 2 is always satisfied [31,
Section 2.3]. For more details about Assumption 2, one can refer to [32].
Lemma 4: Under Assumption 2, x̄ satisfies (17) if and only if it satisfies the following equations

d
X̄(t) = AX̄(t) − BR−1 B 0 q̄(t),
dt
d
q̄(t) = −A0 q̄(t) + QLX̄(t),
dt
x̄(t) = P1 X̄(t),

August 21, 2017

(19a)
(19b)
(19c)

DRAFT

15


with X̄(0) = EX(0) and q̄(T ) = M X̄(T ) − Λ ⊗ In p , where the CDM Λ is defined as follows:

Λsj = P(xs∗ (T ) ∈ Wj ),

1 ≤ s ≤ k, 1 ≤ j ≤ l

dX∗ (t) = (AX∗ (t) + BU∗ (t, X∗ (t), x̄)) dt + σdW (t).

(20a)
(20b)

We are now ready to state the main result of this paper, which asserts that there exists an
admissible mean trajectory x̄ satisfying (17). Moreover, it characterizes each admissible x̄ by a
matrix Λ, where Λsj given in (20a) is the probability that an agent of type s optimally tracking
x̄ is at time T closer to pj than any of the other destination points. This matrix is a fixed point
of a well defined finite dimensional map.
The following functions are used to compute the solution of (19a)-(19b), where Λ is considered
as a parameter. Under Assumption 2, we define R1 and R2 such that, for all s ≥ 0,

d
R1 (t, s) = A − BR−1 B 0 π(t) R1 (t, s),
dt

d
R2 (t) = A − BR−1 B 0 π(t) R2 (t)
dt

(21)

+ BR−1 B 0 R1 (T, t)0 M,
with R1 (s, s) = Ink and R2 (0) = 0, where π is the unique solution of (18). We denote by S
the set of k × l row stochastic matrices. For Λ ∈ S, define the function x̄Λ : [0, T ] → Rn by
x̄Λ (t) := P1 (R1 (t, 0)X̄(0) + R2 (t)Λ ⊗ In p).

(22)

Next, define the finite dimensional map F from S into itself such that for all Λ ∈ S,
F (Λ)sj = P(xs,Λ
∗ (T ) ∈ Wj ),

(23)

k,Λ
where X∗Λ = (x1,Λ
∗ , . . . , x∗ ) is the unique strong solution of the following SDE parameterized

by Λ
dX∗Λ (t) = AX∗Λ (t) + BU∗ t, X∗Λ (t), x̄Λ



dt + σdW (t),

with X∗Λ (0) = X∗ (0).

(24)

The map F involves the probability distribution of the process X∗Λ . Hence, to find the value of
F (Λ), one needs to solve the Fokker-Planck equation associated with (24).
Theorem 5: Under Assumption 2, the following statements hold:
(i) x̄ satisfies (17) if and only if
x̄ = x̄Λ
August 21, 2017

(25)
DRAFT

16

where x̄Λ is defined in (22) and Λ is a fixed point of F .
(ii) F is continuous and has at least one fixed point. Equivalently, (17) has at least one solution
x̄.
(iii) For a uniform population, i.e, k=1, the admissible paths x̄ are uniformly bounded with
R
 21
T
2
respect to M and Λ ∈ S for the standard L2 norm
k.k dt .
0
Remark 3: In [17], [33], which consider the general MFG theory, the authors show the existence
and uniqueness of solutions for the Mckean-Vlasov equation describing the mean field behavior
via Banach’s [17] or Schauder’s fixed point theorem [33]. In [17], it is assumed that the optimal
control law is regular enough (Lipschitz continuous with respect to the state and the distribution)
in order to define a contraction, while in [33] the result is proved under the assumption of smooth
and convex final cost. In our case, the control law (14) is not Lipschitz continuous with respect
to x̄. Moreover, the final cost is neither smooth nor convex. Hence, the Mckean-Vlasov equation
(17) might have multiple solutions. Indeed, (17) has a number of solutions equal to the number
of fixed points of F .
Having solved the game for a continuum of players, we now return to the practical case of a
finite population of players. Using arguments similar to those in [16, Theorem 5.6], one can
show that the MFG-based decentralized strategies (14), when applied by a finite population,
constitute an −Nash equilibrium.
Theorem 6: The decentralized feedback strategies u∗ defined in (14) for a fixed point path x̄
of (17), when applied by N players with dynamics (1), constitute an N -Nash equilibrium with
respect to the costs (2), where N converges to zero as N increases to infinity.
The set of fixed points of the finite dimensional map F characterizes the game in terms of
the number of distinct −Nash equilibria and the distribution of the choices for each of them. In
fact, Theorem 5 establishes a one to one map between the solutions of the mean field equations
(17) and the set of fixed point CDMs. If Λ is a fixed point of F and the players optimally
respond to the corresponding x̄Λ given by (22), then Λsj is the fraction of agents of type s that
P
go towards pj , and ks=1 αs Λsj is the total fraction of players choosing this alternative. Thus,
to compute a path x̄ satisfying (17), a player computes a fixed point Λ of F and then computes
(22).
Let us now briefly illustrate how to compute a fixed point of F in the scalar binary choice
case for a population with uniform dynamics and cost functions, i.e., n = m = k = 1 and
August 21, 2017

DRAFT

17

l = 2, and initial probability density function p0 . In this case, a pair (r, 1 − r) for r ∈ [0, 1] is a
fixed point of F if and only if r is a fixed point of G, where G(r) = [F (r, 1 − r)]1 . Following
the second point of Theorem 5, F is continuous. As a result, G is a continuous function from
[0, 1] into itself. Thus, we can apply the bisection method to G(r) − r to find a fixed point of
Rc
G, if we can compute the value of G at any r ∈ [0, 1]. But G(r) = −∞ pr (T, x)dx, where
c = (p1 + p2 )/2 and pr (t, x) is the probability density of X (r,1−r) (t) defined by (24), which can
be computed numerically by solving the following Fokker-Planck equation associated to (24),
e.g., via an implicit finite difference scheme [34]
∂ (µ(t, x, r)pr (t, x)) σ 2 ∂ 2 pr (t, x)
∂pr (t, x)
=−
+
,
∂t
∂x
2
∂x2

(26)


with pr (0, x) = p0 (x), ∀x ∈ R. Here µ(t, x, r) = Ax + Bu∗ t, x, x̄(r,1−r) for x̄(r,1−r) (t) =
R1 (t, 0)x̄(0) + R2 (t) (rp1 + (1 − r)p2 ), see (22).
V. S IMULATION R ESULTS
To illustrate the dynamics of our collective decision mechanism, we consider a group of agents
with parameters A = 0.1, B = 0.2, R = 5, M = 500, T = 2 and σ = 1.5. The agents, initially
drawn from the normal distribution N (0.3, 1), choose between the alternatives p1 = −10 and
p2 = 10. At first, we consider a weak social effect (Q = 0.1). Following the numerical scheme
at the end of Section IV, we find a fixed point r = 0.39. Accordingly, a player applying its
decentralized MFG-based strategy is at time T closer to p1 with probability 0.39. Equivalently, if
we draw independently from the initial distribution a large number of players with independent
Wiener processes, then the percentage of players that will be at time T closer to p1 converges to
39% as the size of the population increases to infinity. Thus, the majority of the players choose
p2 . Figure 1 shows the distribution at time t = 0, t = 0.5T and t = T , the mean of a generic
agent, the tracked path (admissible path (25)), and the sample paths of 10 players choosing
between −10 and 10 under the weak social effect. As shown in this figure, the mean replicates
the tracked path computed using the fixed point r = 0.39 and (25).
Figure 2 shows that for sufficiently small values of Q (Q < 21) the fixed points of F are
unique. When the social effect Q exceeds 21, F has three fixed points, where two of them
correspond to consensus on one alternative. Indeed as Q increases arbitrarily, agents essentially
forget temporarily about the final cost, and the problem becomes a classical rendez-vous MFG
August 21, 2017

DRAFT

18

0.4
0.2
0
-20

-15

-10

-5

0

5

10

15

20

4
2
0

0

0.5

1

1.5

2

0

0.5

1

1.5

2

20
10
0
-10
-20

Fig. 1. Distribution evolution, mean trajectory, tracked path and sample paths for a weak social effect (Q = 0.1). Here r = 0.39.

where they tend to merge towards each other rapidly. If this occurs around the middle of the
destinations segment, then this is clearly an unstable situation where most of the time, they
end up splitting classically according to initial conditions; however, some large deviations are
possible whereby a significant fraction decides to choose one destination, thus pulling everyone
else towards it, which may help explain the non uniqueness of outcomes. Figure 3 illustrates the
evolution of the distributions that correspond to the first fixed point with Q = 10 and Q = 20.
1
0.8
0.6
0.4
0.2
0
0

5

10

15

20

25

30

Fig. 2. Influence of the coefficient Q on the multiplicity of the fixed points

August 21, 2017

DRAFT

19

0.5
0.4
0.3
0.2
0.1
0
-20

-15

-10

-5

0

5

10

15

20

-15

-10

-5

0

5

10

15

20

0.5
0.4
0.3
0.2
0.1
0
-20

Fig. 3. Influence of the social effect on the distribution of the agents. Distribution evolution for medium (Q = 10) and strong
(Q = 20) social effects. In the first case, r = 0.2, while in second case, r = 0.02.

To illustrate the effect of the noise intensity on the behavior of the group, we fix Q = 20 and
we increase σ from 1.5 to 5. For σ = 1.5, r = 0.02 (Figure 3), but for σ = 3, r increases to
0.28 (Figure 4) and for σ = 5, r = 0.46 (Figure 4). Thus, the higher the noise the more evenly
distributed the players are between the alternatives.
VI. C ONCLUSION
We study within the framework of mean field game theory a dynamic collective choice model
with social interactions. We introduce the Min-LQG optimal control problem and give an explicit
form of a generic agent’s best response (Min-LQG optimal control law). The Min-LQG problem
can be interpreted at each time step as a static discrete choice model where the cost of choosing
one of the alternatives has an additional term that increases with the risk of being driven by
the process noise to the other alternatives. We show the existence of closed loop decentralized
−Nash strategies. Moreover, we characterize these strategies by a CDM describing the way
August 21, 2017

DRAFT

20

0.4

0.3

0.2

0.1

0
-30

-20

-10

0

10

20

30

-20

-10

0

10

20

30

0.4

0.3

0.2

0.1

0
-30

Fig. 4. Influence of the noise on the distribution of the agents. Distribution evolution for σ = 3 and σ = 5. In the first case,
r = 0.28, while in the second case, r = 0.46.

the population splits between the alternatives, which is a fixed point of a well defined finite
dimensional map.
A PPENDIX A
In this appendix, we provide the proofs of lemmas and theorems related to a generic agent’s
best response.
Proof of Theorem 1
We start with a technical result on the mean-square convergence of random variables.
Lemma 7: Let I be a closed subset of Rn . Let Xk ∈ Rn be a sequence of random variables
with finite first and second moments. If E[Xk ] =: µk → µ for some vector µ not in I, and
E[kXk − µk k2 ] → 0, then lim P (Xk ∈ I) = 0.
k→∞

August 21, 2017

DRAFT

21

Proof: I ⊂ Rn is a closed set and µ ∈
/ I, so the distance d between µ and I is strictly
positive. Since, µk converges to µ, there exists k0 > 0 such that for all k ≥ 0 and for all x in I
we have kx − µk k≥ d/2. Hence, using Chevyshev’s inequality [35, Theorem 1.6.4],
P (Xk ∈ I) ≤ P (kXk − µk k≥ d/2) ≤

4
E[kXk − µk k2 ],
d2

for all k ≥ k0 . The result follows since the right-hand side of the inequality is assumed to
converge to 0.
The following lemma concerns the regularity of the solution provided in Theorem 1.
Lemma 8: V defined in (12) is in C 1,2 ([0, T ) × Rn ) ∩ C([0, T ] × Rn ).
Proof: Note that for gj defined in (11), we can write


gj (t, x) = P x(j) (T ) ∈ Wj x(j) (t) = x
Z
Z T
1
p
=
exp − y − α(T, t)x +
α(T, τ )BR−1 B 0 βj (τ )dτ
|2πΣt | Wj
t
Z T
α(T, τ )σσ 0 α(T, τ )0 dτ,
for Σt =

2
Σ−1
t

!
dy (27)

t
(j)

where x , Π and βj are defined in (9) and (10), and the matrix-valued function α(t, s) is the
unique solution of

d
α(t, s) = A − BR−1 B 0 Π(t) α(t, s),
dt

(28)

with α(s, s) = In . The expression (27) follows from the fact that the solution of a linear SDE with
deterministic initial condition has a normal distribution [22, Section 2.5]. In view of (12), (27),
and Σt  0 for all t ∈ [0, T ), V is in C 1,2 ([0, T )×Rn ). It remains to show the continuity on {T }×
Rn . We start by considering x ∈ Rn \ ∪lj=1 ∂Wj , and (tk , xk ) ∈ [0, T ) × Rn converging to (T, x).
We have x ∈ Int(Wj0 ) for some j0 ∈ {1, . . . , l}, and x 6∈ Wj for j 6= j0 . In view of (27), gj (tk , xk )
RT
is the probability that a Gaussian vector of mean α(T, tk )xk − tk α(T, τ )BR−1 B 0 βj (τ )dτ (which
converges to x with k) and covariance Σtk (which converges to 0 with k) is in the closed set
Wj . In this way, each j defines a distinct sequence of random variables associated with the
(tk , xk )’s. Now if one considers the closed set I of Lemma 7 to be any of the closed sets Wj ’s
for j 6= j0 , one can conclude from this lemma that gj (tk , xk ) must converge to 0 for j 6= j0 and,
as a consequence, to 1 for j = j0 since the Wj ’s form a partition of the state space. Therefore,

V (tk , xk ) converges to V (T, x). Thus, V is continuous on [0, T ] × Rn \ ∪lj=1 ∂Wj . Finally,
consider a sequence (tk , xk ) ∈ [0, T )×Rn converging to (T, c), with c ∈ ∪lj=1 ∂Wj . We show that
August 21, 2017

DRAFT

22

V (tk , xk ) converges to V (T, c). Up to renumbering the Voronoi cells, we can assume without
loss of generality that c ∈ ∂Wj for all j in {1, . . . , z} and c ∈
/ ∪lj=z+1 Wj , for some 1 ≤ z ≤ l.
We have,
I0 =

l
X

exp (−ηVj (tk , xk )) gj (tk , xk )

j=1

=

z
X

l
X

exp (−ηVj (tk , xk )) gj (tk , xk ) +

j=1

exp (−ηVj (tk , xk )) gj (tk , xk ).

j=z+1

Since c ∈
/ ∪lj=z+1 Wj , one can use an argument similar to that above to show that the second
term of the right-hand side of the second equality converges to 0.
Next, let  > 0 and fix r > 0 small enough so that B̄(c, r) ⊂ ∩lj=z+1 Wj

C

. The value of r

will be determined later. The first term can be written
z
X
exp (−ηVj (tk , xk )) gj (tk , xk ) = I1 + I2 ,
j=1

where
I1 =

z
X



(j)

(j)

exp (−ηVj (tk , xk )) P x (T ) ∈ Wj ∩ B̄(c, r) x (tk ) = xk



j=1

I2 =

z
X



exp (−ηVj (tk , xk )) P x(j) (T ) ∈ Wj \ B̄(c, r) x(j) (tk ) = xk .

j=1

By Lemma 7, I2 converges to zero. Next, by solving the linear differential equations in (10) and
replacing the expressions of βj and δj in the expression (27) of gj , one can show that under
Assumption 1
I1 = exp (−ηV0 (tk , xk ))

z Z
X
j=1


fk (y) exp η(kyk2M −ky − pj k2M ) dy,

Wj ∩B̄(c,r)

where fk (y) is the probability density function of the Gaussian distribution of mean α(T, tk )xk −
RT
α(T, τ )BR−1 B 0 β0 (τ )dτ and variance Σtk , and V0 and β0 are equal to Vj and βj defined in
tk
(7)-(10) but for pj = 0. By the definition of c, kc − p1 k2M = · · · = kc − pz k2M . Hence,
z Z
X
2
2
I1 = exp −η(V0 (tk , xk ) − kckM +kc − pj kM )
fk (y)dy
j=1

+ exp (−ηV0 (tk , xk ))

z Z
X
j=1

Wj ∩B̄(c,r)

fk (y)f (y)dy

Wj ∩B̄(c,r)

, I3 + I4 ,
August 21, 2017

DRAFT

23

where f (y) = exp (η(kyk2M −ky − pj k2M )) − exp (η(kck2M −kc − pj k2M )). V0 (tk , xk ) converges to
V0 (T, c) = kck2M fk converges in distribution to a point mass at c, and Wj ∩ B̄(0, c), j = 1, . . . , z,
is a partition of B̄(0, c). Therefore, I3 converges to exp(−ηkc − pj k2M ) = exp(−ηV (T, c)). f
is continuous, and f (c) = 0. Hence, one can choose r small enough so that |f (y)|<  for
all y ∈ B̄(c, r). Thus, |I4 |≤ , and lim sup|I0 − exp(−ηV (T, c))|≤ . Since  is arbitrary, I0
k

converges to exp(−ηV (T, c)). This proves the result.
To finish the proof of Theorem 1, it remains to show that V satisfies the HJB equation
(6). We define the transformations by a generalized Hopf-Cole transformation [26, Chapter 4Section 4.4] of Vj (t, x), ψj (t, x) = exp (−ηVj (t, x)), for j = 1, . . . , l. Recall [27, Chapter 6]
that the optimal cost-to-go Vj satisfies the HJB equation (6), but with the boundary condition
equal to Vj (T, x) = kx − pj k2M . By multiplying the right-hand and left-hand sides of (6) by
−η exp (−ηVj (t, x)), one obtain that
 2

1
∂ψj
0 0 ∂ψj
0 ∂ ψj
=xA
+ Tr σ
σ − ηkx − x̄k2Q ψj
−
∂t
∂x
2
∂x2

0
 ∂Vj
1 ∂Vj
+ η exp (−ηVj (t, x))
.
BR−1 B 0 − ησσ 0
2 ∂x
∂x
Thus, under Assumption 1, we get
 2

∂ψj
1
0 0 ∂ψj
0 ∂ ψj
−
=xA
+ Tr σ
σ − ηkx − x̄k2Q ψj
2
∂t
∂x
2
∂x

ψj (T, x) = exp −ηkx − pj k2M , ∀x ∈ Rn .

(29)

Define ψ(t, x) = exp (−ηV (t, x)) the transformation of V (t, x) defined in (12). Hence, we
Pl
∂ψj
have ψ(t, x) =
j=1 ψj (t, x)gj (t, x). Equation (29), Assumption 1 and the identity ∂x =
−η (Πx + βj ) ψj , where Π and βj are defined in (10), imply
 2 
∂ψ
1
∂ ψ
0 0 ∂ψ
+xA
+ Tr σ 0 2 σ − ηkx − x̄k2Q ψ
∂t
∂x 2
∂x
 2

l 
X
0 ∂gj 1
∂gj
−1 0
−1 0
0 ∂ gj
=
+ Ax − BR B Πx − BR B βj
+ Tr σ
σ
ψj .
∂t
∂x
2
∂x2
j=1
The process x(j) satisfies the SDE (9). Therefore, by Kolmogorov’s backward equation [22,
Section 5.B],
 2

0 ∂gj 1
∂gj
−1 0
−1 0
0 ∂ gj
+ Ax − BR B Πx − BR B βj
+ Tr σ
σ = 0.
∂t
∂x
2
∂x2

August 21, 2017

DRAFT

24

Hence,
 2 
∂ ψ
1
∂ψ
0 0 ∂ψ
+xA
+ Tr σ 0 2 σ − ηkx − x̄k2Q ψ = 0.
∂t
∂x 2
∂x
By multiplying the right and left-hand sides of (30) by

1
η

(30)

exp(ηV (t, x)), V (t, x) satisfies (6). The

uniqueness of the solution follows from the uniqueness of solutions to the uniform parabolic
PDE (30) [22, Theorem 7.6].
Proof of Theorem 2
We have
−1

u∗ (t, x) = −R B

+

0 ∂V

∂x

=

l
X

ψj (t, x)gj (t, x)
Pl

j=1

k=1 ψk (t, x)gk (t, x)

1
η

Pl

k=1

ψk (t, x)gk (t, x)

−1

R B

0

l
X
j=1

u(j) (t, x)

ψj (t, x)

∂gj
(t, x).
∂x

In the following we show that the second summand is zero. By the change of variable z =
RT
y − α(T, t)x + t α(T, τ )BR−1 B 0 βj (τ )dτ in (27) and Leibniz integral rule, we have
Z


−α(T, t)
∂gj
2
(t, x) = p
exp − kzkΣ−1
~nj (z)ds(z)
t
∂x
|2πΣt | ∂Wj −α(T,t)x+RtT α(T,τ )BR−1 B 0 βj (τ )dτ
!
Z
Z T
2
−α(T, t)
~nj (y)ds(y),
exp − y − α(T, t)x +
α(T, τ )BR−1 B 0 βj (τ )dτ
=p
|2πΣt | ∂Wj
t
Σ−1
t
where α is defined in (28) and ~nj (y) is the unit normal component of ∂Wj and its translation
RT
∂Wj − α(T, t)x + t α(T, τ )BR−1 B 0 βj (τ )dτ . By solving for βj and δj in (10) and replacing
the solutions in the expressions of the costs Vj defined in (7) and in the derivatives

∂gj
,
∂x

one can

show that under Assumption 1,
l
X

l Z
X

∂gj
ψj (t, x)
(t, x) = K1 (t, x)
exp K2 (t, x, y) + ηky − pj k2M −ηkyk2M ~nj (y)ds(y).
∂x
j=1
j=1 ∂Wj

(31)
where K1 and K2 are functions that do not depend on pj , ∀j ∈ {1, . . . , l}. Note that ∂Wj =
k

k

j
j
∪i=1
Oi , where the disjoint subsets (up to a subset of measure zero) {Oi }i=1
are the common

boundaries of Wj and the adjacent Voronoi cells. If Oi is the common boundary of Wj and some
adjacent Voronoi Cell Wk , then ~nj (y) = −~nk (y) for all y ∈ Oi . Moreover, by the definition of
the Voronoi cells, ky − pj kM = ky − pk kM for all y ∈ Oi . Therefore, the right-hand side of (31)
is equal to zero. Thus, the optimal control u∗ satisfies (14).
August 21, 2017

DRAFT

25

Next, we show that u∗ is an admissible Markov policy, i.e. u∗ ∈ L defined in (4). In view
of (14), the function

∂u∗
∂x

is continuous on [0, T ) × Rn . Therefore, the local Lipschitz condition

holds. Moreover, for all (t, x) ∈ [0, T ] × Rn , we have
ku∗ (t, x)k≤

l
X

l
X
−1 0
(j)
u∗ (t, x) ≤ kR B k lkΠk∞ kxk+
kβj k∞

j=1

!
.

(32)

j=1

Hence, the linear growth condition is satisfied and this proves the result. As a result, sufficient
conditions are satisfied for the SDE defined in (5) and controlled by u∗ (t, x) to have unique
strong solution denoted x∗ (.) [22, Section 5.2].
Finally, by the verification theorem [25, Theorem 4.3.1], we know that u∗ is the unique
optimal control law of (5) if it is the unique minimizer (up to a set of measure 0) of the
, u, t) = (Ax + Bu)0 ∂V
+ kx − x̄k2Q +kuk2R , and if the cost-to-go V (t, x)
Hamiltonian H(x, ∂V
∂x
∂x
has a polynomial growth in x and satisfies (6). For the first condition, we have for Lebesgue×Pa.e (t, ξ) ∈ [0, T ] × Ω (P is the probability measure defined at the beginning of Section II),
∂V
(t, x∗ (t, ξ))
∂x


∂V
= argmin H x∗ (t, ξ),
(t, x∗ (t, ξ)), u, t .
∂x
u∈Rn

u∗ (t, x∗ (t, ξ)) = −R−1 B 0

In fact, the control law defined in (13) minimizes H except on the set {T } × Ω, which has a
Lebesgue × P measure zero. Next, in view of (32), we have for all (t, x) ∈ [0, T ) × Rn
Z kxk
∂V
(t, y) dy ≤ K1 (1 + kxk2 ),
kV (t, x)k≤
∂x
0
for some K1 > 0. Moreover, kV (T, x)k≤ K2 (1 + kxk2 ), for some K2 > 0. Hence, for all
(t, x) ∈ [0, T ] × Rn , kV (t, x)k≤ K (1 + kxk2 ), for some K > 0. Moreover, as established in
Theorem 3, V ∈ C 1,2 ([0, T ) × Rn ) ∩ C([0, T ] × Rn ) satisfies the HJB equation (6). This proves
the result.
A. Proof of Lemma 3
To prove the result, it is sufficient to show that the expectation of the optimal cost EJ∗ (x(0)) ≤
K+

σ2
2

log M , for some K > 0 independent of M . The result is then a direct consequence of

Chebyshev’s inequality


2
1
P min |x∗ (T ) − pj |>  ≤ 2 E min |x∗ (T ) − pj |2 ≤
EJ∗ (x(0)).
1≤j≤l
 1≤j≤l
M 2
August 21, 2017

DRAFT

26

To prove the boundedness of the cost, we start by the special case where x̄ = 0 and p1 = · · · =
2 RT
pl = 0. The optimal cost is then J∗ (x(0)) = 21 Π(0)x2 (0) + σ2 0 Π(τ )dτ . We now show that
RT
Π(0) is uniformly bounded with M and that 0 Π(τ )dτ is of the order log M for large M . To
prove the uniform boundness of Π(0), we consider the LQR problem

Z T
Q 2 R 2
M
inf JM (y(0) = 1, v(.)) = inf
y + v dt + |y(T )|2
v
v
2
2
2
0
(33)
dy
s.t.
= Ay + Bv,
y(0) = 1.
dt
∗
The optimal cost is JM
= 21 Π(0), where Π is defined in (10). By controllability of (A, B), one can
find a continuous control law v10 that does not depend on M and such that the corresponding
∗
state y10 is at time T at 0. We have 12 Π(0) = JM
≤ JM (1, v10 ). The right hand side of the

inequality is finite and does not depend on M . Hence, Π(0) is uniformly bounded w.r.t. M .
RT
We now prove that 0 Π(τ )dτ is of the order log M for large M . We have for all M ≥ 1,
1
Π(0)
2

∗
∗
≥ JM
= JM
=1 := C > 0. The constant C is independent of M , whenever M > 1.

Moreover, for large, M min Π(t) = Π(0) > C. By dividing by Π(t) on both sides of the
t∈[0,T ]

Riccati equation in (10) and integrating on [0, T ] the right and left hand sides, we get
Z
Z T
b2 T
1
log M − log Π(0) =
Π(τ )dτ − 2aT − q
dτ.
r 0
0 Π(τ )
RT 1
RT
1
By the boundedness of Π(0) and 0 Π(τ
dτ
≤
,
we
have
Π(τ )dτ /log M converges to 1
)
CT
0
as M goes to infinity. Having shown the result for the special case, the case where x̄ 6= 0 and
A
p1 = · · · = pl = p can be proved by making the change of variables x̃ = x − p and ũ = u + B
p

and noting the uniform boundedness of x̄ and that
 Z T
Z T
RA2 T 2
M 2
2
2
Q(x̄ − p)2 dt +
p.
EJ∗ (x(0)) ≤ E inf E
{Qx̃ + Rũ }dt + x̃ (T )|x(0) +
ũ
2
B2
0
0
Finally, we conclude the general case by the following inequality
Z T

R 2
M
Q
2
2
EJ∗ (x(0)) ≤ E inf E
{ (x − x̄) + u }dt + (x(T ) − p1 ) |x(0) .
u
2
2
2
0
A PPENDIX B
This appendix includes the proofs of lemmas and theorems related to the existence of a solution
of the mean field equations.

August 21, 2017

DRAFT

27

Proof of Lemma 4
First, we provide in the following lemma a stochastic maximum principle [36] for the “minLQG” optimal control problem. Because of the non-smooth final cost, this result is derived
using the relationship between dynamic programming and the stochastic maximum principle
rather than the variational method used in [36].


2 s
Lemma 9: The processes q s (t), ∂∂xV2 (t, xs∗ (t) , 1 ≤ s ≤ k, with q s (t) =

∂V s
(t, xs∗ (t)),
∂x

the following backward linear SDE:


∂ 2V s
0
− dq s (t) = (As ) q s (t) + Qs (xs∗ (t) − x̄(t)) dt −
((t, xs∗ (t)) σ s dws (t),
∂x2


P
with q s (T ) = M s xs∗ (T ) − lj=1 1Wj (xs∗ (T ))pj .
Proof: The function
Section 3.3.A] to

∂V s
∂x

∂V s
(t, x)
∂x

∂V s
∂x

(34)

is smooth on [0, T ) × Rn . By applying Itô’s formula [22,

(t, xs∗ (t)), and by noting that V s satisfies the HJB equation (6), we have

−dq s (t) = ((As )0 q s (t) + Qs (xs∗ (t) − x̄(t))) dt −
with q s (0) =

satisfy

∂ 2V s
((t, xs∗ (t)) σ s dws (t),
2
∂x

(0, xs∗ (0)). It remains to show that P-a.s
∂V s
lim
(t, xs∗ (t)) = M s
t→T ∂x

xs∗ (T ) −

l
X

!
1Wj (xs∗ (T ))pj

.

(35)

j=1

By Theorem 2, we have on [0, T ) × Rn

l
X
exp −η s Vjs (t, x) gjs (t, x) ∂Vjs
∂V s
(t, x) =
(t, x).
Pl
s
s s
∂x
∂x
k=1 exp (−η Vk (t, x)) gk (t, x)
j=1
Fix j ∈ {1, . . . , l}. By Lemma 7, we have on {xs∗ (T ) ∈ Int(Wj )}, lim gjs (t, xs∗ (t)) = 1 and

t→T
s
s
s
s
lim gk (t, x∗ (t)) = 0, for all k 6= j. Hence, on {x∗ (T ) ∈ Int(Wj )}, we have lim ∂V
(t, xs∗ (t)) =
∂x
t→T
t→T
∂V s
lim ∂xj (t, xs∗ (t)) = M s (xs∗ (T ) − pj ). But, xs∗ is the solution of an SDE with non degenerate
t→T
noise. Therefore, P (xs∗ (T ) ∈ ∂Wj ) = 0. Hence, (35) holds.

Remark 4: The backward SDE (34) is the adjoint equation [36] for the min-LQG optimal
control problem.
We now prove Lemma 4. By taking the expectations on the right and the left hand sides of
P
(34) and the SDE in (17), and in view of ks=1 αs x̄s (t) = x̄, we get the necessary condition. To
prove the sufficient condition, we consider (X̄, x̄, q̄) satisfying (19a)-(20b). We define (x̂s , q̂ s ) =
(Exs∗ , Eq s ), where (xs∗ , q s ) are the s-type generic agent’s optimal state and co-state when tracking

August 21, 2017

DRAFT

28

x̄. We define e = (x̂1 , . . . , x̂k ) − X̄ and q̄e = (q̂ 1 , . . . , q̂ k ) − q̄. By taking expectations on the
right and the left hand sides of (34) and the generic agent’s dynamics, we obtain that
d
e(t) = Ae(t) − BR−1 B 0 q̄e (t),
e(0) = 0
dt
(36)
d
0
q̄e (t) = −A q̄e (t) + QLe(t),
q̄e (T ) = M e(T ).
dt
Under Assumption 2, we define qe0 (t) = π(t)e(t), where π(t) is the unique solution of (18). We
have

d(q̄e −qe0 )
dt

= −(A0 −π(t)BR−1 B 0 )(q̄e −qe0 ), with (q̄e (T )−qe0 (T )) = 0. Hence, q̄e (t) = π(t)e(t).

By replacing q̄e (t) = π(t)e(t) in the forward equation in (36), we obtain that e = 0. Hence, x̄
satisfies (17).
Proof of Theorem 5
Let x̄ be a path satisfying (17). Then, by Lemma 4, x̄ satisfies (19a)-(20b). Under Assumption
2, using arguments similar to those used in Lemma 4 we obtain that (19a) and (19b) has a
unique solution (X̄, q̄). Moreover, q̄ = π X̄ + γ, where π is the unique solution of (18), and γ
is the unique solution of γ̇ = −(A − BR−1 B 0 π)0 γ with γ(T ) = −M Λ ⊗ In p. By replacing,
q̄ = π X̄ + γ in (19a), we get that x̄ is of the form (22). Next, by implementing this new form
of x̄ in the expression of (20b) and by noting that Λ satisfies (20a), Λ is a fixed point of F .

Conversely, we consider Λ to be a fixed point of F , X̄ = R1 (t, 0)X̄(0) + R2 (t)Λ ⊗ In p and
x̄ = P1 X̄. We define q̄(t) = −(BR−1 B 0 )−1 ( dtd X̄(t) − AX̄(t)). (X̄, q̄) satisfies (19a)-(19b). We
s,Λ
have Λsj = F (Λ)sj = P(xs,Λ
is defined in (24). But x̄ is of the form
∗ (T ) ∈ Wj ), where x∗

(25), hence xλ∗ is the unique strong solution of (20b). Therefore, x̄ satisfies (19a)-(20b), and by
Lemma 4, it satisfies (17). This proves the first point.
Next, to show the existence of a fixed point of F , it is sufficient to show that F is continuous,
in which case Brouwer’s fixed point theorem [37, Section V.9] ensures the existence of a fixed
point. Equation (24) is a stochastic differential equation depending on the parameter Λ. By [38,
Theorem 1], the joint distribution of X∗Λ and the Brownian motion W is weakly continuous in
Λ. Consider a sequence of stochastic matrices {Λn }n≥0 converging to the stochastic matrix Λ.
The distribution of X∗Λn (T ) converges weakly to the distribution of X∗λ (T ) Moreover, X∗λ is the
solution of a non-degenerate SDE. Hence, Wj , j = 1, . . . , l, is a continuity set of the distribution
of X∗λ . Therefore, lim F (Λn )sj = lim P(x∗s,Λn (T ) ∈ Wj ) = P(xs,Λ
∗ (T ) ∈ Wj ) = F (Λ)sj , and so
n

August 21, 2017

n

DRAFT

29

F is continuous. Finally, using arguments similar to those used in [14, Lemma 9], one can show
the third point.
R EFERENCES
[1] F. Koppelman and V. Sathi, “Incorporating variance and covariance heterogeneity in the generalized nested logit model:
an application to modeling long distance travel choice behavior,” Transportation Research, vol. 39, pp. 825–853, 2005.
[2] C. Bhat and J. Guo, “A mixed spatially correlated logit model: formulation and application to residential choice modeling,”
Transportation Research, vol. 38, pp. 147–168, 2004.
[3] R. Nakajima, “Measuring peer effects on youth smoking behaviour,” The Review of Economic Studies, vol. 74, no. 3, pp.
897–935, 2007.
[4] D. Vail and M. Veloso, “Multi-robot dynamic role assignment and coordination through shared potential fields,” Multi-robot
systems, pp. 87–98, 2003.
[5] A. Halász, M. A. Hsieh, S. Berman, and V. Kumar, “Dynamic redistribution of a swarm of robots among multiple sites,”
in 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems.

IEEE, 2007, pp. 2320–2325.

[6] M. A. Hsieh, Á. Halász, S. Berman, and V. Kumar, “Biologically inspired redistribution of a swarm of robots among
multiple sites,” Swarm Intelligence, vol. 2, no. 2-4, pp. 121–141, 2008.
[7] S. Merrill and B. Grofman, A Unified Theory of Voting: Directional and Proximity Spatial Models. Cambridge University
Press, 1999.
[8] G. B. Markus and P. E. Converse, “A dynamic simultaneous equation model of electoral choice,” American Political
Science Review, vol. 73, no. 04, pp. 1055–1070, 1979.
[9] D. McFadden, “Conditional logit analysis of qualitative choice behavior,” in Frontiers in Econometrics, P. Zarembka, Ed.
New York: New York: Academic Press, 1974, ch. 4, pp. 105–142.
[10] J. Rust, “Structural estimation of markov decision processes,” Handbook of econometrics, vol. 4, pp. 3081–3143, 1994.
[11] W. Brock and S. Durlauf, “Discrete choice with social interactions,” Review of Economic Studies, pp. 147–168, 2001.
[12] R. Salhab, R. P. Malhamé, and J. Le Ny, “Consensus and disagreement in collective homing problems: A mean field games
formulation,” in Proceedings of the 53rd IEEE Conference on Decision and Control, Dec 2014, pp. 916–921.
[13] ——, “A dynamic game model of collective choice in multi-agent systems,” in Proceedings of the 54th IEEE Conference
on Decision and Control, Dec 2015, pp. 4444–4449.
[14] R. Salhab, R. P. Malhamé, and J. Le Ny, “A dynamic game model of collective choice in multi-agent systems,” IEEE
Transactions on Automatic Control, 2017, In Press, available at http://ieeexplore.ieee.org/document/7970149/.
[15] M. Huang, P. E. Caines, and R. P. Malhamé, “Individual and mass behaviour in large population stochastic wireless power
control problems: centralized and Nash equilibrium solutions,” in Proceedings of the 42nd IEEE Conference on Decision
and Control, 2003, pp. 98–103.
[16] ——, “Large-population cost-coupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized
epsilon-Nash equilibria,” IEEE Transactions on Automatic Control, vol. 52, no. 9, pp. 1560–1571, 2007.
[17] M. Huang, R. P. Malhamé, and P. E. Caines, “Large population stochastic dynamic games: closed-loop McKean-Vlasov
systems and the Nash certainty equivalence principle,” Communications in Information & Systems, vol. 6, no. 3, pp.
221–252, 2006.
[18] J. M. Lasry and P. L. Lions, “Jeux à champ moyen. I–le cas stationnaire,” Comptes Rendus Mathématique, vol. 343, no. 9,
pp. 619–625, 2006.
August 21, 2017

DRAFT

30

[19] ——, “Jeux à champ moyen. II–horizon fini et contrôle optimal,” Comptes Rendus Mathématique, vol. 343, no. 10, pp.
679–684, 2006.
[20] ——, “Mean field games,” Japanese Journal of Mathematics, vol. 2, pp. 229–260, 2007.
[21] F. Fagnani and S. Zampieri, “Randomized consensus algorithms over large scale networks,” IEEE Journal on Selected
Areas in Communications, vol. 26, no. 4, pp. 634–649, 2008.
[22] I. Karatzas and S. Shreve, Brownian motion and stochastic calculus. Springer Science & Business Media, 2012, vol. 113.
[23] R. Salhab, R. P. Malhamé, and J. Le Ny, “A dynamic game model of collective choice: Stochastic dynamics and closed
loop solutions,” arXiv preprint arXiv:1604.08136, 2016.
[24] M. Huang, P. E. Caines, and R. P. Malhamé, “Social optima in mean field LQG control: centralized and decentralized
strategies,” IEEE Transactions on Automatic Control, vol. 57, no. 7, pp. 1736–1751, 2012.
[25] W. H. Fleming and H. M. Soner, Controlled Markov processes and viscosity solutions.

Springer Science & Business

Media, 2006, vol. 25.
[26] L. Evans, Partial Differential Equations, ser. Graduate studies in mathematics.

American Mathematical Society, 1998.

[27] J. Yong and X. Y. Zhou, Stochastic controls: Hamiltonian systems and HJB equations.

Springer Science & Business

Media, 1999, vol. 43.
[28] D. Gomes, E. Pimentel, and V. Voskanyan, Regularity Theory for Mean-Field Game Systems, ser. SpringerBriefs in
Mathematics.

Springer, 2016.

[29] T. Liggett, Interacting particle systems.

Springer Science & Business Media, 2012, vol. 276.

[30] L. Perko, Differential equations and dynamical systems.

Springer Science & Business Media, 2013, vol. 7.

[31] B. D. Anderson and J. B. Moore, Optimal control: linear quadratic methods.

Dover Publications, 2007.

[32] G. Freiling, “A survey of nonsymmetric Riccati equations,” Linear algebra and its applications, vol. 351, pp. 243–270,
2002.
[33] R. Carmona and F. Delarue, “Probabilistic analysis of mean-field games,” SIAM Journal on Control and Optimization,
vol. 51, no. 4, pp. 2705–2734, 2013.
[34] L. Pichler, A. Masud, and L. Bergman, “Numerical solution of the Fokker–Planck equation by finite difference and finite
element methods - A comparative study,” in Computational Methods in Stochastic Dynamics. Springer, 2013, pp. 69–85.
[35] R. Durrett, Probability: theory and examples.

Cambridge university press, 2010.

[36] S. Peng, “A general stochastic maximum principle for optimal control problems,” SIAM Journal on control and optimization,
vol. 28, no. 4, pp. 966–979, 1990.
[37] J. B. Conway, A Course in Functional Analysis, ser. Graduate Texts in Mathematics.

Springer-Verlag, 1985.

[38] A. V. Skorokhod, “Stochastic differential equations depending on a parameter,” Theory of Probability & Its Applications,
vol. 25, no. 4, pp. 659–666, 1981.

August 21, 2017

DRAFT

31

Rabih Salhab is currently pursuing the Ph.D. degree in Electrical Engineering in the Department of
Electrical Engineering, Ecole Polytechnique de Montreal, Canada. He received the B.S. degree in Electrical
Engineering from Ecole Supérieure d’Ingénieurs de Beyrouth (E.S.I.B), Lebanon, in 2008. From 2008 to
2013 he was an Electrical Engineer with Dar al Handasah Shair and Partners, Lebanon. His current
research interests are in stochastic control, game theory and mean field games theory and its applications.

Roland Malhamé received the Bachelors, Masters and Ph.D. degrees in Electrical Engineering from the
American University of Beirut, the University of Houston, and the Georgia Institute of Technology in
1976, 1978 and 1983 respectively.
After single year stays at University of Quebec , and CAE Electronics Ltd (Montreal), he joined in
1985 École Polytechnique de Montréal, where he is Professor of Electrical Engineering. In 1994, 2004,
and 2012 he was on sabbatical leave respectively with LSS CNRS (France), École Centrale de Paris, and
University of Rome Tor Vergata. His interest in statistical mechanics inspired approaches to the analysis and control of large
scale systems has led him to contributions in the area of aggregate electric load modeling, and to the early developments of
the theory of mean field games. His current research interests are in collective decentralized decision making schemes, and
the development of mean field based control algorithms in the area of smart grids. From june 2005 to june 2011, he headed
GERAD, the Group for Research on Decision Analysis. He is an Associate Editor of International Transactions on Operations
Research.

Jerome Le Ny (S’05-M’09-SM’16) received the Engineering Degree from the École Polytechnique,
France, in 2001, the M.Sc. degree in Electrical Engineering from the University of Michigan, Ann
Arbor, in 2003, and the Ph.D. degree in Aeronautics and Astronautics from the Massachusetts Institute
of Technology, Cambridge, in 2008. He is currently an Associate Professor with the Department of
Electrical Engineering, Polytechnique Montreal, Canada. He is a member of GERAD, a multi-university
research center on decision analysis. From 2008 to 2012 he was a Postdoctoral Researcher with the
GRASP Laboratory at the University of Pennsylvania. His research interests include robust and stochastic control, mean-field
control, privacy and security in large-scale networked control systems, dynamic resource allocation and active perception, with
applications to autonomous multi-robot systems and intelligent infrastructures.

August 21, 2017

DRAFT

