[PDF] Notes on Mean Field Games 20 Apr 2013 For this

View - Download Notes on Mean Field Games

Previous PDF

Next PDF

Notes on Mean Field Games

(from P.-L. Lions' lectures at College de France)

Pierre Cardaliaguet

y

September 27, 2013

Contents

1 Introduction2

2 Nash equilibria in games with a large number of players 4

2.1 Symmetric functions of many variables . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Limits of Nash equilibria in pure strategies . . . . . . . . . . . . . . . . . . . . . 5

2.3 Limit of Nash equilibria in mixed strategies . . . . . . . . . . . . . . . . . . . . . 6

2.4 A uniqueness result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.5 Example: potential games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.6 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Analysis of second order MFEs 10

3.1 On the Fokker-Planck equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2 Proof of the existence Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.3 Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.4 Application to games with nitely many players . . . . . . . . . . . . . . . . . . . 15

3.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4 Analysis of rst order MFEs 18

4.1 Semi-concavity estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2 On the continuity equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.3 Proof of the existence Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.4 The vanishing viscosity limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5 The space of probability measures 33

5.1 The Monge-Kantorovich distances . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.2 The Wasserstein space of probability measures onRd. . . . . . . . . . . . . . . . 39

5.3 Polynomials onP(Q) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.4 Hewitt and Savage Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

CEREMADE, UMR CNRS 7534, Universite de PARIS - DAUPHINE, Place du Marechal De Lattre De Tassigny 75775 PARIS CEDEX 16 - FRANCE. e-mail : cardaliaguet@ceremade.dauphine.fr

yLecture given at Tor Vergata, April-May 2010. The author wishes to thank the University for its hospitality

and INDAM for the kind invitation. These notes are posted with the authorization of Pierre-Louis Lions.

1

6 Hamilton-Jacobi equations in the space of probability measures 43

6.1 Derivative in the Wasserstein space . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2 First order Hamilton-Jacobi equations . . . . . . . . . . . . . . . . . . . . . . . . 46

6.3 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

7 Heuristic derivation of the mean eld equation 49

7.1 The dierential game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

7.2 Derivation of the equation inP2. . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7.3 From the equation inP2to the mean eld equation . . . . . . . . . . . . . . . . . 51

8 Appendix53

8.1 Nash equilibria in classical dierential games . . . . . . . . . . . . . . . . . . . . 53

8.2 Desintegration of a measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

8.3 Ekeland's and Stegall's variational principles . . . . . . . . . . . . . . . . . . . . 54

1 Introduction

Mean eld game theory is devoted to the analysis of dierential games with a (very) larger number of \small" players. By \small" player, we mean a player who has very little in uence on the overall system. This theory has been recently developed by J.-M. Lasry and P.-L. Lions in a series of papers [48, 49, 50, 51] and presented though several lectures of P.-L. Lions at the College de France. Its name comes from the analogy with the mean eld models in mathematical physics which analyses the behavior of many identical particles (see for instance Sznitman's notes [58]). Related ideas have been developed independently, and at about the same time, by

Huang-Caines-Malhame [38, 39, 40, 41].

The aim of these notes is to present in a simplied framework some of the ideas developed

in the above references. It is not our intention to give a full picture of this fast growing area: we

will only select a few topics, but will try to provide an approach as self content as possible. We strongly advise the interested reader to go back to the original works by J.-M. Lasry and P.-L. Lions for further and sharper results. Let us also warn the reader that these note only partially re ect the state of the art by 2008: for lack of time we did not cover the lectures of Pierre-Louis Lions at College de France for the years 2009 and 2010. The typical model for Mean Field Games (FMG) is the following system 8< :(i)@tuu+H(x;m;Du) = 0 inRd(0;T) (ii)@tmmdiv(DpH(x;m;Du)m) = 0 inRd(0;T) (iii)m(0) =m0; u(x;T) =G(x;m(T))(1) In the above system,is a nonnegative parameter. The rst equation has to be understood backward in time and the second on is forward in time. There are two crucial structure conditions for this system: the rst one is the convexity ofH=H(x;m;p) with respect to the last variable. This condition implies that the rst equation (a Hamilton-Jacobi equation) is associated with an optimal control problem. This rst equation shall be the value function associated with a 2 typical small player. The second structure condition is thatm0(and thereforem(t)) is (the density of) a probability measure. The heuristic interpretation of this system is the following. An average agent controls the stochastic dierential equation dX t=tdt+p2Bt where (Bt) is a standard Brownian motion. He aims at minimizing the quantity E ZT 012

L(Xs;m(s);s)ds+G(XT;m(T))

whereLis the Fenchel conjugate ofHwith respect to thepvariable. Note that in this cost the evolution of the measuremsenters as a parameter. The value function of our average player is then given by (1-(i)). His optimal control is|at least heuristically|given in feedback form by(x;t) =DpH(x;m;Du). Now, if all agents argue in this way, their repartition will move with a velocity which is due, on the one hand, to the diusion, and, one the other hand, on the drift termDpH(x;m;Du). This leads to the

Kolmogorov equation (1-(ii)).

The mean eld game theory developed so far has been focused on two main issues: rst investigate equations of the form (1) and give an interpretation (in economics for instance) of such systems. Second analyze dierential games with a nite but large number of players and link their limiting behavior as the number of players goes to innity and equation (1). So far the rst issue is well understood and well documented. The original works by Lasry and Lions give a certain number of conditions under which equation (1) has a solution, discuss its uniqueness and its stability (see also Huang-Caines-Malhame [38, 39, 40, 41]). Several papers also study the numerical approximation of the solution of (1): see Achdou and Capuzzo Dolcetta [1], Achdou, Camilli and Capuzzo Dolcetta [2], Gomes, Mohr and Souza [32], Lachapelle, Salomon and Turinici [46]. The mean eld games theory seem also paticularly adapted to modelize problems in economics: see Gueant [34], [35], Lachapelle [45], Lasry, Lions, Gueant [52], and the references therein. As for the second part of the program, the limiting behavior of dierential games when the number of players tend to innity has been understood only for ergodic dierential games [51].

The general case remains largely open.

The largest part of this paper is dedicated to the rst issue, and we only consider the second one in an oversimplied framework. These notes are organized as follows. We rst study as a toy example classical (one-shot) games with a very large number of identical players: this allows to present some typical phenomena for functions of many variables. We start the analysis of mean eld games with the second order case (i.e. when= 1). If we assume (to x the ideas) thatFandGare regularizing, then existence of a solution of (1) is fairly easy. As a byproduct, we provide an interpretation of the mean-eld system for a large (but nite) number of players. Then we turn to rst order mean eld equation (= 0): in this case existence of a solution is more involved and strongly relies on the regularizing properties ofFandG. Then we summarize some typical results on the space of probability measures needed for the rest of the presentation. The end of the notes is devoted on the one hand to an approach of Hamilton-Jacobi in the Wasserstein space and, on another hand, to some heuristic derivation of the mean eld equation from a system of Nash equilibria for a large number of players. 3

2 Nash equilibria in games with a large number of players

Before starting the analysis of dierential games with a large number of players, it is not unin- teresting to have a look at this question for classical (one-shot) games. The general framework is the following: letNbe a (large) number of players. We assume that the players are symmetric. In particular, the set of strategiesQis the same for all players. We denote byFNi=FNi(x1;:::;xN) the payo (= the cost) of playeri2 f1;:::;Ng. Our symmetry assumption means that F

N(i)(x(1);:::;x(N)) =Fi(x1;:::;xN)

for all permutationonf1;:::;Ng. We consider Nash equilibria for this game and want to analyze their behavior asN!+1. For this we rst describe the limit of maps of many variable. We proceed with the analysis of the limit of Nash equilibria in pure, and then in mixed, strategies. We nally discuss the uniqueness of the solution of the limit equation and present some examples.

2.1 Symmetric functions of many variables

LetQbe a compact metric space anduN:QN!Rbe a symmetric function: u N(x1;:::;xN) =uN(x(1);:::;x(n)) for any permutationonf1;:::;ng:

Our aim is to dene a limit for theuN.

For this let us introduce the setP(Q) of Borel probability measures onQ. This set is endowed with the topology of weak-* convergence: a sequence (mN) ofP(Q) converges tom2 P(Q) if lim NZ Q '(x)dmN(x) =Z Q '(x)dm(x)8'2 C0(Q): Let us recall thatP(Q) is a compact metric space for this topology, which can be metrized by the distance (often called the Kantorowich-Rubinstein distance) d

1(;) = supfZ

Q fd() wheref:Q!Ris 1Lipschitz continuousg: Other formulations for this distance will be given later (section 5). In order to show that the (uN) have a limit, we assume the following:

1. (Uniform bound) there is someC >0 with

kuNkL1(Q)C(2)

2. (Uniform continuity) there is a modulus of continuity!independent ofnsuch that

juN(X)uN(Y)j !(d1(mNX;mNY))8X;Y2QN;8N2N;(3) wheremNX=1N P N i=1xiandmNY=1N P N i=1yiifX= (x1;:::;xN) andY= (y1;:::;yN). Theorem 2.1If theuNare symmetric and satisfy (2) and (3), then there is a subsequence (unk)of(uN)and a continuous mapU:P(Q)!Rsuch that lim k!+1sup

X2Qnkjunk(X)U(mnkX)j= 0:

4 Proof of Theorem 2.1:Without loss of generality we can assume that the modulus!is concave. Let us dene the sequence of mapsUN:P(Q)!Rby U

N(m) = inf

X2QNuN(X) +!(d1(mNX;m))8m2 P(Q):

Then, by condition (3),UN(mNX) =uN(X) for anyX2QN. Let us show that theUNhave! for modulus of continuity onP(Q): indeed, ifm1;m22 P(Q) and ifX2QNisoptimal in the denition ofUN(m2), then U

N(m1)uN(X) +!(d1(mNX;m1))

UN(m2) ++!(d1(mNX;m2) +d1(m1;m2))!(d1(mNX;m2))

UN(m2) +!(d1(m1;m2)) +

because!is concave. Hence theUNare equicontinuous on the compact setP(Q) and uniformly bounded. We complete the proof thanks to Ascoli Theorem. Remark 2.2Some uniform continuity condition is needed: for instance ifQis a compact subset ofRdanduN(X) = maxijxij, thenuN\converges" toU(m) = supx2spt(m)jxjwhich is not continuous. Of course the convergence is not uniform. Remark 2.3IfQis a compact subset of some nite dimensional spaceRd, a typical condition which ensures (3) is the existence of a constantC >0, independent ofN, such that sup i=1;:::;NkDxiuNk1CN 8N :

2.2 Limits of Nash equilibria in pure strategies

LetQbe a compact metric space andP(Q) be the set of Borel probability measures onQ. We consider a one-shot game with a large numberNof players. Our main assumption is that the payosFN1;:::;FNNof the players are symmetric. In particular, under suitable bounds and uniform continuity, we know from Theorem 2.1 that theFNihave a limit, which has the formF(x;m) (the dependence onxis here to keep track of the fact of the dependence iniof the functionFNi). So the payos of the players are very close to payos of the form

F(x1;1N1P

j2xj);:::;F(xN;1N1P jN1xj). In order to keep the presentation as simple as possible, we suppose that the payos have already this form. That is, we suppose that there is a continuous mapF:Q P(Q)!Rsuch that, for anyi2 f1;:::;Ng F

Ni(x1;:::;xN) =F0

xi;1N1X j6=i xj1 A

8(x1;:::;xN)2QN:

Let us recall that a Nash equilibrium for the game (FN1;:::;FNN) is an element (xN1;:::;xNN)2 Q

Nsuch that

F Ni(xN1;:::;xNi1;yi;xNi+1;:::;xNN)FNi(xN1;:::;xNN)8yi2Q :

We set

X

N= (xN1;:::;xNN) and mN=1N

N X i=1 xNi: 5 Theorem 2.4Assume that, for anyN,XN= (xN1;:::;xNN)is a Nash equilibrium for the game F N1;:::;FNN. Then up to a subsequence, the sequence of measures(mN)converges to a measure m2 P(Q)such that Z Q

F(y;m)dm(y) = infm2P(Q)Z

Q

F(y;m)dm(y):(4)

Remark 2.5The \mean eld equation" (4) is equivalent to saying that the support of mis contained in the set of minima ofF(y;m). Indeed, if Sptmargminy2QF(y;m), then clearly msatises (4). Conversely, if (4) holds, then choosingm=xshows thatR

QF(y;m)dm(y)F(x;m) for anyx2Q. ThereforeR

QF(y;m)dm(y)minx2QF(x;m), which implies that mis supported in argminy2QF(y;m). Remark 2.6The result is not completely satisfying because it requires the existence of Nash equilibria in theNplayer game, which does not always hold. However there always exists Nash equilibria in mixed strategies, i.e., when the player are allowed to randomize their behavior by playing strategies inP(Q) instead ofQ. We discuss this issue below. Proof :Without loss of generality we can assume that the sequence (mN) converges to some m. Let us check that msatises (4). For this we note that, by denition, the measurexNiis a minimum of the problem inf m2P(Q)Z Q

F(y;1N1X

j6=i xNj)dm(y): Since d0 1N1X j6=i xNj;mN1 A 2N and sinceFis continuous, the measurexNiis alsooptimal for the problem inf m2P(Q)Z Q

F(y;mN)dm(y)

as soon asNis suciently large. By linearity, so is mN: Z Q

F(y;mN)dmN(y)infm2P(Q)Z

Q

F(y;mN)dm(y) + :

LettingN!+1gives the result.

2.3 Limit of Nash equilibria in mixed strategies

We now assume that the players play the same gameFN1;:::;FNNas before, but there are allowed to play inmixed strategies, i.e., they minimize over elements ofP(Q) instead of minimizing over elements ofQ(which are now viewed aspure strategies). If the players play the mixed strategies

1;:::;N2 P(Q), then the outcome of Playeri(still denoted, by abuse of notation,FiN) is

F iN(1;:::;N) =Z Q

NFiN(x1;:::;xN)d1(x1):::dN(xN);

6 or, recalling the denition ofFN1;:::;FNN, F iN(1;:::;N) =Z Q NF0 xi;1N1X j6=i xj1 A d1(x1):::dN(xN): The notion of Nash equilibria in mixted strategies can be dened as before: (1;:::;N)2 (P(Q))Nis a Nash equilibrium if, for anyi2 f1;:::;Ng, F iN(1;:::;N)FNi((j)j6=i;i)8i2 P(Q):

Note that the above inequality is equivalent to

F iN(1;:::;N)FNi((j)j6=i;xi)8xi2Q : Nash Theorem states that Nash equilibria in mixted strategies do exist (see Theorem 8.3 below). In fact, because of the special struture of the game, there also exists symmetric Nash equilibria, i.e., equilibria of the form (;:::;), where 2 P(Q) (Theorem 8.4). Theorem 2.7We assume thatFis Lipschitz continuous. Let, for anyN,(N;:::;N)be a symmetric Nash equilibrium in mixed strategies for the gameFN1;:::;FNN. Then, up to a subsequence,(N)converges to a measuremsatisfying (4). Remark 2.8In particular the above Theorem proves the existence of a solution to the \mean eld equation" (4). Proof:Let mbe a limit, up to subsequences, of the (N). Since the mapxj!F(y;1N1P j6=ixj) is Lip(F)=(N1)Lipschitz continuous, we have, by denition of the distanced1, Z Q

N1F(y;1N1X

j6=i xj)Y j6=idN(xj)Z Q

N1F(y;1N1X

j6=i xj)Y j6=idm(xj) (Lip(F) +kFk1)d1(N;m)8y2Q :(5) A direct application of the Hewitt and Savage Theorem (see Theorem 5.10 below) gives lim N!+1Z Q

N1F(y;1N1X

j6=i xj)Y j6=idm(xj) =F(y;m);(6) where the convergence is uniform with respect toy2Qthanks to the (Lipschitz) continuity of F. Since (1;:::;N) is a Nash equilibrium, inequality (5) implies that, for any >0 and if we can chooseNlarge enough, Z Q

NF(y;1N1X

j6=i xj)Y j6=idm(xj)dm(xi)Z Q

NF(y;1N1X

j6=i xj)Y j6=idm(xj)dm(xi) + ; for anym2 P(Q). LettingN!+1on both sides of the inequality gives, in view of (6), Z Q

F(xi;m)dm(xi)Z

Q

F(xi;m)dm(xi) +8m2 P(Q);

which gives the result, sinceis arbitrary. 7

2.4 A uniqueness result

One obtains the full convergence of the measure mN(orN) if there is a unique measure m satisfying the condition (4). This is the case under the following assumption:

Proposition 2.9Assume thatFsatises

Z Q (F(y;m1)F(y;m2))d(m1m2)(y)>08m16=m2:(7)

Then there is at most one measure satisfying (4).

Remark 2.10Requiring at the same time the continuity ofFand the above monotonicity condition seems rather restrictive for applications. Condition (7) is more easily fullled for mapping dened on strict subsets ofP(Q). For instance, ifQis a compact subset ofRdof positive measure andPac(Q) is the set of absolutely continuous measures onQ(absolutely continuous with respect to the Lebesgue measure), then

F(y;m) =G(m(y)) ifm2 Pac(Q)

+1otherwise satises (7) as soon asG:R!Ris continuous and increasing. If we assume thatQis the closure of some smooth open bounded subset ofRd, another example is given by

F(y;m) =um(y) ifm2 Pac(Q)\L2(Q)

+1otherwise whereumis the solution inH1(Q) of um=min u m= 0 on@ Note that in this case the mapy!F(y;m) is continuous. Proof of Proposition 2.9:Let m1;m2satisfying (4). Then Z Q

F(y;m1)dm1(y)Z

Q

F(y;m1)dm2(y)

and Z Q

F(y;m2)dm2(y)Z

Q

F(y;m2)dm1(y):

Therefore

Z Q (F(y;m1)F(y;m2))d(m1m2)(y)0; which implies that m1= m2thanks to assumption (7). 8

2.5 Example: potential games

The heuristic idea is that, ifF(x;m) can somehow be represented as the derivative of some mapping (x;m) with respect to themvariable, and if the problem inf m2P(Q)Z Q (x;m)dx has a minimum m, then Z Q

0(x;m)(mm)08m2 P(Q):

So Z Q

F(x;m)dmZ

Q

F(x;m)dm8m2 P(Q);

which shows that mis an equilibrium.

For instance let us assume that

F(x;m) =V(x)m(x) +G(m(x)) ifm2 Pac(Q)

+1otherwise whereV:Q!Ris continuous andG: (0;+1)!Ris continuous, strictly increasing, with

G(0) = 0 andG(s)csfor somec >0. Then let

(x;m) =V(x)m(x) +H(m(x)) ifmis a.c. whereHis a primitive ofGwithH(0) = 0. Note thatGis strictly convex withG(s)c2 s2ds.

Hence the problem

inf m2Pac(Q)Z Q

V(x)m(x) +H(m(x))dx

has a unique solution m2L2(Q). Then we have, for anym2 Pac(Q), Z Q (V(x) +G(m(x)))m(x)dxZ Q (V(x) +G(m(x)))m(x)dx ;quotesdbs_dbs46.pdfusesText_46

[PDF] alors jacques les jambes brisées commentaire PDF Cours,Exercices ,Examens

[PDF] Alors je dois rédigez sous une forme théâtrale ceci 3ème Autre

[PDF] Alors svp c'est a rendre pr demain et j'arrive absolument pas svp :x 3ème Mathématiques

[PDF] Alors svp c'est a rendre pr demain et j'arrive absolument pas svp :x 4ème Français

[PDF] Alors voila moi plus tard j'aimerais travaillé dans les finances es ce que vous licéen ou autre pouvé me conseillé un bac a prendre 6ème Autre

[PDF] ALORS, PETiT EXERCiCE EN ESPAGNOL :D 3ème Espagnol

[PDF] aloysius bertrand gaspard de la nuit pdf PDF Cours,Exercices ,Examens

[PDF] alpha centauri distance de la terre PDF Cours,Exercices ,Examens

[PDF] alpha volumes PDF Cours,Exercices ,Examens

[PDF] alphabet anglais phonétique tableau PDF Cours,Exercices ,Examens

[PDF] alphabet chinois traduit en français pdf PDF Cours,Exercices ,Examens

[PDF] Alphabet des vacances - O, X et Ä 5ème Allemand

[PDF] Alphabet des vacances - vous pouvez toujours répondre ! - O, U, X et Ä 5ème Allemand

[PDF] alphabet et qualité 6ème Français

[PDF] alphabet exercise workout PDF Cours,Exercices ,Examens