Multi-population Mean Field Games systems with aversion

Multi-population Mean Field Games systems
with aversion
Marco Cirant
` Degli Studi di Milano
Universita
7 October 2014
joint work with M. Bardi and Y. Achdou
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
1 / 26
Statement of the problem
Two-populations Mean Field Games: describe rational behavior of
populations with a very large number of players, such that
Players of
have distribution
move according to
pay a cost
Population 1
m1
Population 2
m2
dXt = αt dt + νdBt in Ω ⊆ Rd ,
1
γ∗
γ ∗ |α| ,
γ∗ > 1
V 1 (m1 , m2 )
V 2 (m1 , m2 )
decreasing w.r.t m1
decreasing w.r.t m2
increasing w.r.t m2
increasing w.r.t m1
Every player aim at minimizing his own cost.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
2 / 26
If the overall cost of every player has the long-time average form
Z T
∗
1
|αt |γ
i
i
J (α) = lim
E
+ V (m1 (Xt ), m2 (Xt )) dt, i = 1, 2
T →∞ T
γ∗
0
Nash equilibria of the game with large number of players can be
approximated by the Mean Field Games system

1
γ
i
 −ν∆ui + γ |Dui | + λi = V (m1 , m2 ), in Ω,
−ν∆mi − div(|Dui |γ−2 Dui mi ) = 0,
 R
i = 1, 2.
Ω mi = 1,
(MFG)
where (m1 , m2 ) is the vector of equilibrium distributions and
−|Dui |γ−2 Dui provides the ()-Nash strategy for players of the i-th
population ([Lasry, Lions] and [Huang, Caines, Malhame], 2005 ).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
3 / 26
Two Models
LINEAR model:
VL1 (m1 (x), m2 (x)) = m2 (x),
VL2 (m1 (x), m2 (x)) = m1 (x).
SCHELLING model:

−
m1 (x)
 V 1 (m1 (x), m2 (x)) =
−
a
,
S
m1 (x)+m2 (x)
−
m2 (x)
 V 2 (m (x), m (x)) =
,
1
2
S
m1 (x)+m2 (x) − a
a ∈ (0, 1].
V i (m1 , m2 ) are decreasing w.r.t mi and increasing w.r.t m−i .
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
4 / 26
Schelling’s model
In the late ’60 Schelling proposed a simple model of two populations that
interact. Blue people and red people live in a chessboard:
Each individual wants to make sure that he lives near someone of his own
population.
He is happy if the percentage of same-color individuals among his neighbors is
above some happines threshold a.
If he’s not happy, he moves to another free house.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
5 / 26
If we run a simulation starting from a random initial distribution of
individuals (so, some of them are unhappy), after some time we always
notice that ethnic clusters form.
a = 35%
a = 70%
Segregation shows up (even from mild ethnocentric attitude).
[Schelling, 1969]
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
6 / 26
What happens if we add a random noise? i.e. a small percentage of
individuals moves in any case at every time step.
a = 35%
a = 70%
Interfaces become more regular.
If the noise is increased the two populations remain mixed.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
7 / 26
Existence & Uniqueness
Theorem (C., 2014)
For all ν > 0, γ > 1, there exists a solution
(u, m, λ) ∈ [C 2 (Ω)]2 × [W 1,p (Ω)]2 × R2 of (MFG).
Schelling model (bounded costs V i ), standard arguments.
Linear model (unbounded costs V i ), trickier.
Uniqueness: forget it! (in both cases).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
8 / 26
Questions (unsolved by the previous thm.)
What kind of behavior do we expect?
SEGREGATION, namely m1 and m2 concentrating in different parts of Ω.
In both models.
What happens if ν is close to zero (small noise regime)?
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
9 / 26
Another interpretation of the MFG system...
Consider now the linear case.
We may think of our MFG as a differential game with two players: the two
populations.
The state of each population is his own distribution mi .
Given two controls (α1 , α2 ), the two states satisfy the Kolmogorov
equations
−ν∆mi − div(αi mi ) = 0,
and the costs paid by the two populations are
Z
Z
1
γ∗
1
J (α1 , α2 ) = ∗ m1 |α1 | + m1 m2
γ
Z
Z
1
∗
J 2 (α1 , α2 ) = ∗ m2 |α2 |γ + m1 m2
γ
Nash equilibria of this game provide solutions of (MFG).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
10 / 26
...which leads to a control problem!
If we set
J
TOT
1
(α1 , α2 ) = ∗
γ
Z
m1 |α1 |
γ∗
1
+ ∗
γ
Z
m2 |α2 |
γ∗
Z
+
m1 m2 ,
i.e. J TOT is some overall cost paid by the “world” population,
then its global minima (α1∗ , α2∗ )
J TOT (α1∗ , α2∗ ) ≤ J TOT (α1 , α2 )
∀α1 , α2
are Nash equilibria for the MFG
(and local minima are local Nash equilibria for the MFG).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
11 / 26
Some numerical experiments.
In collaboration with Y. Achdou, we look for approximate solutions of our
(MFG). How? By a long time approximation method:
consider a finite-difference version of the forward-forward system

Ω × (0, T )
 ∂t ui − νi ∆ui + H i (x, Dui ) = V i [m],
∂t mi − νi ∆mi − div(Dp H i (x, Dui )mi ) = 0,

ui = 0, m = mi0
Ω × {0}.
and let T → ∞.
Remarks:
Switch to a time-dependent problem to remove the unknowns λi .
backward-forward system is more natural but computationally harder.
Mimic the strategy used for homogenization of HJB eq.
Expect: u(x, T ) − λT → U(x) and m(x, T ) → M(x).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
12 / 26
The two models compared.
From a qualitative point of view, solutions do not change “so much”:
Schelling (a = 0.4)
Linear
ν=1
ν = 0.1
ν = 0.01
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
13 / 26
Some solutions in 1D
Ω = (0, 1), γ = 2, T ≈ 1000.
Using the long-time approximation (works for both models)
ν large (≈ 1)
mixing
ν small (<< 1)
segregation
Other solutions??
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
14 / 26
Some other solutions
Minimizing J TOT associated to the linear model
(using MATLAB’s fmincon on its finite difference version):
ν large (≈ 1)
mixing
ν small (<< 1)
segregation
...
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
15 / 26
A bifurcation diagram
(we are still focusing on the linear model)
Every solid line corresponds to a branch of solutions.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
16 / 26
A bifurcation diagram
(we are still focusing on the linear model)
Every solid line corresponds to a branch of solutions.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
16 / 26
The answer is NO.
In the following sense:
Theorem
Suppose that (α1∗ , α2∗ ) is (one of) the best possible strategy, i.e.
J TOT (α1∗ , α2∗ ) ≤ J TOT (α1 , α2 )
Then,
Z
m1∗ m2∗ → 0
∀α1 , α2 .
as ν → 0.
Moreover, m1∗ and m2∗ are nonincreasing or nondecreasing.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
17 / 26
Given m1 , m2 we consider the decreasing and increasing rearrangements
m1,& , m2,% :
Rearranging preserves the total mass of m1 , m2 , and
J TOT (m1,& , m2,% ) ≤ J TOT (m1 , m2 ),
so a global minimizer of J TOT is such that
J TOT (m1,& , m2,% ) = J TOT (m1 , m2 ).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
18 / 26
Given m1 , m2 we consider the decreasing and increasing rearrangements
m1,& , m2,% :
Rearranging preserves the total mass of m1 , m2 , and
J TOT (m1,& , m2,% ) ≤ J TOT (m1 , m2 ),
so a global minimizer of J TOT is such that
J TOT (m1,& , m2,% ) = J TOT (m1 , m2 ).
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
18 / 26
Outside Lineland...
What happens in space dimension two?
Exploiting the control problem point of view (the functional J TOT ), it is
possible to prove the existence of solutions of (MFG) that segregate:
Z
m1 m2 → 0 as ν → 0,
Yet no proof of monotonicity properties (or other qualitative result) of
optimal distributions is available.
Nor, analogous results are available for the Schelling model.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
19 / 26
Numerically (finite elements approximation), we observe that if the domain
has an axis of symmetry, then there exist solutions (m1 , m2 ) that
“segregate” along that axis.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
20 / 26
Numerically (finite elements approximation), we observe that if the domain
has an axis of symmetry, then there exist solutions (m1 , m2 ) that
“segregate” along that axis.
But there might be others
Conjecture: “best solutions” minimize the perimeter of the free boundary
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
20 / 26
The non-stationary case.
So far we considered the infinite-time horizon case. How about finite-time
problems? Namely, when players’ cost has the form
J i (α) = E
Z
T
0
∗
|αt |γ
+ V i (m1 (Xt ), m2 (Xt )),
γ∗
i = 1, 2, T > 0
Nash equilibria of the game with large number of players can be
approximated by the Mean Field Games system

−∂t ui − ν∆ui + γ1 |Dui |γ = V i (m1 , m2 ),
in Ω × (0, T ),



γ−2
∂
R t mi − ν∆mi − div(|Dui | Dui mi ) = 0,

m = 1,

 Ω i
mi |t=0 = m0 , ui |t=T = 0, i = 1, 2.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
(MFGe)
7/10/2014
21 / 26
Existence of smooth solutions for (MFGe) in general (γ 6= 2) is an open
problem.
How to deal numerically with the backward-forward time structure?
Define the (usual) fixed point operator
mi 7→
ui
solution of HJB
7→
µi
solution of FKP
(1)
Approximate solutions of discrete mi via Newton’s method.
Positivity of m is preserved; ν ≥ 0.01 is ok.
Initial guess m0 (x, t) for fixed point of (1) is extremely important.
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
22 / 26
Schelling model, a = 0.4, (x, t) ∈ [0, 1] × [0, 4]
ν = 0.15
ν = 0.05
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
23 / 26
a = 0.4
ν = 0.05
a = 0.7 same behavior as a = 0.4, PLUS...
ν = 0.01
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
24 / 26
Final Remarks
Stationary case.
What happens in 1-D is quite well understood. Numerical methods
work well for small ν.
2-D is still ok from the numerical viewpoint, theoretical results on the
shape of free boundary are still missing.
Non-stationary case.
Convergence if ν ≥ 0.01.
“Crossing” phenomena to be studied.
What if ν = 0?
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
25 / 26
Thanks for your attention !
Marco Cirant (Universit`
a di Milano)
Multi-population MFG with aversion
7/10/2014
26 / 26

Download Report