doi: 10.3934/jdg.2019016

Discrete mean field games: Existence of equilibria and convergence

1. 

University of the Basque Country, UPV/EHU, Spain

2. 

Univ. Grenoble Alpes, Inria, CNRS, LIG, F-38000 Grenoble, France

* Corresponding author: Josu Doncel

Received  November 2018 Revised  May 2019 Published  June 2019

We consider mean field games with discrete state spaces (called discrete mean field games in the following) and we analyze these games in continuous and discrete time, over finite as well as infinite time horizons. We prove the existence of a mean field equilibrium assuming continuity of the cost and of the drift. These conditions are more general than the existing papers studying finite state space mean field games. Besides, we also study the convergence of the equilibria of N -player games to mean field equilibria in our four settings. On the one hand, we define a class of strategies in which any sequence of equilibria of the finite games converges weakly to a mean field equilibrium when the number of players goes to infinity. On the other hand, we exhibit equilibria outside this class that do not converge to mean field equilibria and for which the value of the game does not converge. In discrete time this non- convergence phenomenon implies that the Folk theorem does not scale to the mean field limit.

Citation: Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics & Games, doi: 10.3934/jdg.2019016
References:
[1]

S. AdlakhaR. Johari and G. Y. Weintraub, Equilibria of dynamic games with many players: Existence, approximation, and market structure, Journal of Economic Theory, 156 (2015), 269-316. doi: 10.1016/j.jet.2013.07.002. Google Scholar

[2]

N. I. Al-Najjar and R. Smorodinsky, Large nonanonymous repeated games, Games and Economic Behavior, 37 (2001), 26-39. doi: 10.1006/game.2000.0826. Google Scholar

[3]

D. M. Ambrose, Strong solutions for time-dependent mean field games with non-separable hamiltonians, Journal de Mathématiques Pures et Appliquées, 113 (2018), 141-154. doi: 10.1016/j.matpur.2018.03.003. Google Scholar

[4]

R. BasnaA. Hilbert and V. N. Kolokoltsov, An epsilon-nash equilibrium for non-linear markov games of mean-field-type on finite spaces, Commun. Stoch. Anal, 8 (2014), 449-468. doi: 10.31390/cosa.8.4.02. Google Scholar

[5]

E. Bayraktar and A. Cohen, Analysis of a finite state many player game using its master equation, SIAM J. Control Optim., 56 (2018), 3538–3568. doi: 10.1137/17M113887X. Google Scholar

[6]

M. Benaim and J.-Y. Le Boudec, A class of mean field interaction models for computer and communication systems, Performance Evaluation, 65 (2008), 823-838. Google Scholar

[7]

A. Bensoussan, J. Frehse and P. Yam, Mean Field Games and Mean Field Type Control Theory, Springer, 2013. doi: 10.1007/978-1-4614-8508-7. Google Scholar

[8] K. C. Border, Fixed Point Theorems with Applications to Economics and Game Theory, Cambridge university press, 1989.
[9]

P. Cardaliaguet, F. Delarue, J.-M. Lasry and P.-L. Lions, The master equation and the convergence problem in mean field games, arXiv preprint, arXiv: 1509.02505, 2015.Google Scholar

[10]

R. Carmona and F. Delarue, Probabilistic analysis of mean-field games, SIAM Journal on Control and Optimization, 51 (2013), 2705-2734. doi: 10.1137/120883499. Google Scholar

[11]

R. CarmonaD. Lacker and et al., A probabilistic weak formulation of mean field games and applications, The Annals of Applied Probability, 25 (2015), 1189-1231. doi: 10.1214/14-AAP1020. Google Scholar

[12]

R. Carmona and P. Wang, Finite state mean field games with major and minor players, arXiv preprint, arXiv: 1610.05408.Google Scholar

[13]

A. Cecchin and M. Fischer, Probabilistic approach to finite state mean field games, Applied Mathematics & Optimization, 2018, 1–48. doi: 10.1007/s00245-018-9488-7. Google Scholar

[14]

P. Dasgupta and E. Maskin, The existence of equilibrium in discontinuous economic games, i: Theory, Review of Economic Studies, 53 (1986), 1-26. doi: 10.2307/2297588. Google Scholar

[15]

J. DoncelN. Gast and B. Gaujal, Are mean-field games the limits of finite stochastic games?, SIGMETRICS Perform. Eval. Rev., 44 (2016), 18-20. doi: 10.1145/3003977.3003984. Google Scholar

[16]

A. M. Fink, Equilibrium in a stochastic $n$-person game, J. Sci. Hiroshima Univ. Ser. A-I Math., 28 (1964), 89-93. doi: 10.32917/hmj/1206139508. Google Scholar

[17]

D. Fudenberg and E. Maskin, The folk theorem in repeated games with discounting or with incomplete information, Econometrica, 54 (1986), 533-554. doi: 10.2307/1911307. Google Scholar

[18]

N. Gast and B. Gaujal, A mean field approach for optimization in discrete time, Discrete Event Dynamic Systems, 21 (2011), 63-101. doi: 10.1007/s10626-010-0094-3. Google Scholar

[19]

D. A. Gomes, J. Mohr and R. R. Souza, Discrete time, finite state space mean field games, Journal de Mathématiques Pures et Appliquées, 93 (2010), 308–328. doi: 10.1016/j.matpur.2009.10.010. Google Scholar

[20]

D. A. GomesJ. Mohr and R. R. Souza, Continuous time finite state mean field games, Applied Mathematics & Optimization, 68 (2013), 99-143. doi: 10.1007/s00245-013-9202-8. Google Scholar

[21]

D. A. Gomes and E. Pimentel, Time-dependent mean-field games with logarithmic nonlinearities, SIAM Journal on Mathematical Analysis, 47 (2015), 3798-3812. doi: 10.1137/140984622. Google Scholar

[22]

D. A. GomesE. Pimentel and H. Sánchez-Morgado, Time-dependent mean-field games in the superquadratic case, ESAIM: Control, Optimisation and Calculus of Variations, 22 (2016), 562-580. doi: 10.1051/cocv/2015029. Google Scholar

[23]

D. A. Gomes and E. A. Pimentel, Regularity for mean-field games systems with initial-initial boundary conditions: The subquadratic case, In Dynamics, Games and Science, 2015,291–304. Google Scholar

[24]

D. A. GomesE. A. Pimentel and H. Sánchez-Morgado, Time-dependent mean-field games in the subquadratic case, Communications in Partial Differential Equations, 40 (2015), 40-76. doi: 10.1080/03605302.2014.903574. Google Scholar

[25]

A. Granas and J. Dugundji, Fixed Point Theory, Springer Monographs in Mathematics. Springer-Verlag, New York, 2003. doi: 10.1007/978-0-387-21593-8. Google Scholar

[26]

O. Guéant, Existence and uniqueness result for mean field games with congestion effect on graphs, Applied Mathematics & Optimization, 72 (2014), 291-303. Google Scholar

[27]

O. Guéant, J.-M. Lasry and P.-L. Lions, Mean field games and applications, In Paris-Princeton Lectures on Mathematical Finance 2010, volume 2003 of Lecture Notes in Mathematics, pages 205–266. Springer Berlin Heidelberg, 2011. doi: 10.1007/978-3-642-14660-2_3. Google Scholar

[28]

M. Huang, Mean field stochastic games with discrete states and mixed players, In Game Theory for Networks, Springer, 2012,138–151. doi: 10.1007/978-3-642-35582-0_11. Google Scholar

[29]

M. Huang, R. Malhame and P. Caines, Large population stochastic dynamic games: Closed-loop mckean vlasov systems and the nash certainty equivalence principle, Communications in Information and Systems, 6 (2006), 221–252, Special issue in honor of the 65th birthday of Tyrone Duncan. doi: 10.4310/CIS.2006.v6.n3.a5. Google Scholar

[30]

D. Lacker, A general characterization of the mean field limit for stochastic differential games, Probability Theory and Related Fields, 165 (2016), 581-648. doi: 10.1007/s00440-015-0641-9. Google Scholar

[31]

J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. i–le cas stationnaire, Comptes Rendus Mathématique, 343 (2006), 619–625. doi: 10.1016/j.crma.2006.09.019. Google Scholar

[32]

J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. ii–horizon fini et contrôle optimal, Comptes Rendus Mathématique, 343 (2006), 679–684. doi: 10.1016/j.crma.2006.09.018. Google Scholar

[33]

J.-M. Lasry and P.-L. Lions, Mean field games, Japanese Journal of Mathematics, 2 (2007), 229-260. doi: 10.1007/s11537-007-0657-8. Google Scholar

[34]

H. Sabourian, Anonymous repeated games with a large number of players and random outcomes, Journal Of Economic Theory, 51 (1990), 92-110. doi: 10.1016/0022-0531(90)90052-L. Google Scholar

[35] W. Sandholm, Population Games and Evolutinary Dynamics, MIT Press, 2010.
[36]

H. Tembine, Mean field stochastic games: Convergence, q/h-learning and optimality, In American Control Conference (ACC), 2011, IEEE, 2011, 2423–2428. doi: 10.1109/ACC.2011.5991087. Google Scholar

[37]

H. Tembine, J.-Y. L. Boudec, R. El-Azouzi and E. Altman, Mean field asymptotics of markov decision evolutionary games and teams, In Game Theory for Networks, 2009. GameNets' 09. International Conference on, IEEE, 2009,140–150. doi: 10.1109/GAMENETS.2009.5137395. Google Scholar

[38]

Z. WangC. T. BauchS. BhattacharyyaA. d'OnofrioP. ManfrediM. PercN. PerraM. Salathé and D. Zhao, Statistical physics of vaccination, Physics Reports, 664 (2016), 1-113. doi: 10.1016/j.physrep.2016.10.006. Google Scholar

show all references

References:
[1]

S. AdlakhaR. Johari and G. Y. Weintraub, Equilibria of dynamic games with many players: Existence, approximation, and market structure, Journal of Economic Theory, 156 (2015), 269-316. doi: 10.1016/j.jet.2013.07.002. Google Scholar

[2]

N. I. Al-Najjar and R. Smorodinsky, Large nonanonymous repeated games, Games and Economic Behavior, 37 (2001), 26-39. doi: 10.1006/game.2000.0826. Google Scholar

[3]

D. M. Ambrose, Strong solutions for time-dependent mean field games with non-separable hamiltonians, Journal de Mathématiques Pures et Appliquées, 113 (2018), 141-154. doi: 10.1016/j.matpur.2018.03.003. Google Scholar

[4]

R. BasnaA. Hilbert and V. N. Kolokoltsov, An epsilon-nash equilibrium for non-linear markov games of mean-field-type on finite spaces, Commun. Stoch. Anal, 8 (2014), 449-468. doi: 10.31390/cosa.8.4.02. Google Scholar

[5]

E. Bayraktar and A. Cohen, Analysis of a finite state many player game using its master equation, SIAM J. Control Optim., 56 (2018), 3538–3568. doi: 10.1137/17M113887X. Google Scholar

[6]

M. Benaim and J.-Y. Le Boudec, A class of mean field interaction models for computer and communication systems, Performance Evaluation, 65 (2008), 823-838. Google Scholar

[7]

A. Bensoussan, J. Frehse and P. Yam, Mean Field Games and Mean Field Type Control Theory, Springer, 2013. doi: 10.1007/978-1-4614-8508-7. Google Scholar

[8] K. C. Border, Fixed Point Theorems with Applications to Economics and Game Theory, Cambridge university press, 1989.
[9]

P. Cardaliaguet, F. Delarue, J.-M. Lasry and P.-L. Lions, The master equation and the convergence problem in mean field games, arXiv preprint, arXiv: 1509.02505, 2015.Google Scholar

[10]

R. Carmona and F. Delarue, Probabilistic analysis of mean-field games, SIAM Journal on Control and Optimization, 51 (2013), 2705-2734. doi: 10.1137/120883499. Google Scholar

[11]

R. CarmonaD. Lacker and et al., A probabilistic weak formulation of mean field games and applications, The Annals of Applied Probability, 25 (2015), 1189-1231. doi: 10.1214/14-AAP1020. Google Scholar

[12]

R. Carmona and P. Wang, Finite state mean field games with major and minor players, arXiv preprint, arXiv: 1610.05408.Google Scholar

[13]

A. Cecchin and M. Fischer, Probabilistic approach to finite state mean field games, Applied Mathematics & Optimization, 2018, 1–48. doi: 10.1007/s00245-018-9488-7. Google Scholar

[14]

P. Dasgupta and E. Maskin, The existence of equilibrium in discontinuous economic games, i: Theory, Review of Economic Studies, 53 (1986), 1-26. doi: 10.2307/2297588. Google Scholar

[15]

J. DoncelN. Gast and B. Gaujal, Are mean-field games the limits of finite stochastic games?, SIGMETRICS Perform. Eval. Rev., 44 (2016), 18-20. doi: 10.1145/3003977.3003984. Google Scholar

[16]

A. M. Fink, Equilibrium in a stochastic $n$-person game, J. Sci. Hiroshima Univ. Ser. A-I Math., 28 (1964), 89-93. doi: 10.32917/hmj/1206139508. Google Scholar

[17]

D. Fudenberg and E. Maskin, The folk theorem in repeated games with discounting or with incomplete information, Econometrica, 54 (1986), 533-554. doi: 10.2307/1911307. Google Scholar

[18]

N. Gast and B. Gaujal, A mean field approach for optimization in discrete time, Discrete Event Dynamic Systems, 21 (2011), 63-101. doi: 10.1007/s10626-010-0094-3. Google Scholar

[19]

D. A. Gomes, J. Mohr and R. R. Souza, Discrete time, finite state space mean field games, Journal de Mathématiques Pures et Appliquées, 93 (2010), 308–328. doi: 10.1016/j.matpur.2009.10.010. Google Scholar

[20]

D. A. GomesJ. Mohr and R. R. Souza, Continuous time finite state mean field games, Applied Mathematics & Optimization, 68 (2013), 99-143. doi: 10.1007/s00245-013-9202-8. Google Scholar

[21]

D. A. Gomes and E. Pimentel, Time-dependent mean-field games with logarithmic nonlinearities, SIAM Journal on Mathematical Analysis, 47 (2015), 3798-3812. doi: 10.1137/140984622. Google Scholar

[22]

D. A. GomesE. Pimentel and H. Sánchez-Morgado, Time-dependent mean-field games in the superquadratic case, ESAIM: Control, Optimisation and Calculus of Variations, 22 (2016), 562-580. doi: 10.1051/cocv/2015029. Google Scholar

[23]

D. A. Gomes and E. A. Pimentel, Regularity for mean-field games systems with initial-initial boundary conditions: The subquadratic case, In Dynamics, Games and Science, 2015,291–304. Google Scholar

[24]

D. A. GomesE. A. Pimentel and H. Sánchez-Morgado, Time-dependent mean-field games in the subquadratic case, Communications in Partial Differential Equations, 40 (2015), 40-76. doi: 10.1080/03605302.2014.903574. Google Scholar

[25]

A. Granas and J. Dugundji, Fixed Point Theory, Springer Monographs in Mathematics. Springer-Verlag, New York, 2003. doi: 10.1007/978-0-387-21593-8. Google Scholar

[26]

O. Guéant, Existence and uniqueness result for mean field games with congestion effect on graphs, Applied Mathematics & Optimization, 72 (2014), 291-303. Google Scholar

[27]

O. Guéant, J.-M. Lasry and P.-L. Lions, Mean field games and applications, In Paris-Princeton Lectures on Mathematical Finance 2010, volume 2003 of Lecture Notes in Mathematics, pages 205–266. Springer Berlin Heidelberg, 2011. doi: 10.1007/978-3-642-14660-2_3. Google Scholar

[28]

M. Huang, Mean field stochastic games with discrete states and mixed players, In Game Theory for Networks, Springer, 2012,138–151. doi: 10.1007/978-3-642-35582-0_11. Google Scholar

[29]

M. Huang, R. Malhame and P. Caines, Large population stochastic dynamic games: Closed-loop mckean vlasov systems and the nash certainty equivalence principle, Communications in Information and Systems, 6 (2006), 221–252, Special issue in honor of the 65th birthday of Tyrone Duncan. doi: 10.4310/CIS.2006.v6.n3.a5. Google Scholar

[30]

D. Lacker, A general characterization of the mean field limit for stochastic differential games, Probability Theory and Related Fields, 165 (2016), 581-648. doi: 10.1007/s00440-015-0641-9. Google Scholar

[31]

J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. i–le cas stationnaire, Comptes Rendus Mathématique, 343 (2006), 619–625. doi: 10.1016/j.crma.2006.09.019. Google Scholar

[32]

J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. ii–horizon fini et contrôle optimal, Comptes Rendus Mathématique, 343 (2006), 679–684. doi: 10.1016/j.crma.2006.09.018. Google Scholar

[33]

J.-M. Lasry and P.-L. Lions, Mean field games, Japanese Journal of Mathematics, 2 (2007), 229-260. doi: 10.1007/s11537-007-0657-8. Google Scholar

[34]

H. Sabourian, Anonymous repeated games with a large number of players and random outcomes, Journal Of Economic Theory, 51 (1990), 92-110. doi: 10.1016/0022-0531(90)90052-L. Google Scholar

[35] W. Sandholm, Population Games and Evolutinary Dynamics, MIT Press, 2010.
[36]

H. Tembine, Mean field stochastic games: Convergence, q/h-learning and optimality, In American Control Conference (ACC), 2011, IEEE, 2011, 2423–2428. doi: 10.1109/ACC.2011.5991087. Google Scholar

[37]

H. Tembine, J.-Y. L. Boudec, R. El-Azouzi and E. Altman, Mean field asymptotics of markov decision evolutionary games and teams, In Game Theory for Networks, 2009. GameNets' 09. International Conference on, IEEE, 2009,140–150. doi: 10.1109/GAMENETS.2009.5137395. Google Scholar

[38]

Z. WangC. T. BauchS. BhattacharyyaA. d'OnofrioP. ManfrediM. PercN. PerraM. Salathé and D. Zhao, Statistical physics of vaccination, Physics Reports, 664 (2016), 1-113. doi: 10.1016/j.physrep.2016.10.006. Google Scholar

[1]

Fabio Camilli, Francisco Silva. A semi-discrete approximation for a first order mean field game problem. Networks & Heterogeneous Media, 2012, 7 (2) : 263-277. doi: 10.3934/nhm.2012.7.263

[2]

John R. Tucker. Attractors and kernels: Linking nonlinear PDE semigroups to harmonic analysis state-space decomposition. Conference Publications, 2001, 2001 (Special) : 366-370. doi: 10.3934/proc.2001.2001.366

[3]

Kai Du, Jianhui Huang, Zhen Wu. Linear quadratic mean-field-game of backward stochastic differential systems. Mathematical Control & Related Fields, 2018, 8 (3&4) : 653-678. doi: 10.3934/mcrf.2018028

[4]

Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks & Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197

[5]

Juan Pablo Maldonado López. Discrete time mean field games: The short-stage limit. Journal of Dynamics & Games, 2015, 2 (1) : 89-101. doi: 10.3934/jdg.2015.2.89

[6]

Martin Burger, Alexander Lorz, Marie-Therese Wolfram. Balanced growth path solutions of a Boltzmann mean field game model for knowledge growth. Kinetic & Related Models, 2017, 10 (1) : 117-140. doi: 10.3934/krm.2017005

[7]

Elisabetta Carlini, Francisco J. Silva. A semi-Lagrangian scheme for a degenerate second order mean field game system. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4269-4292. doi: 10.3934/dcds.2015.35.4269

[8]

Carmen G. Higuera-Chan, Héctor Jasso-Fuentes, J. Adolfo Minjárez-Sosa. Control systems of interacting objects modeled as a game against nature under a mean field approach. Journal of Dynamics & Games, 2017, 4 (1) : 59-74. doi: 10.3934/jdg.2017004

[9]

Haiyan Zhang. A necessary condition for mean-field type stochastic differential equations with correlated state and observation noises. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1287-1301. doi: 10.3934/jimo.2016.12.1287

[10]

Hayato Chiba, Georgi S. Medvedev. The mean field analysis of the kuramoto model on graphs Ⅱ. asymptotic stability of the incoherent state, center manifold reduction, and bifurcations. Discrete & Continuous Dynamical Systems - A, 2019, 39 (7) : 3897-3921. doi: 10.3934/dcds.2019157

[11]

Franco Flandoli, Matti Leimbach. Mean field limit with proliferation. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3029-3052. doi: 10.3934/dcdsb.2016086

[12]

Oleksandr Misiats, Nung Kwan Yip. Convergence of space-time discrete threshold dynamics to anisotropic motion by mean curvature. Discrete & Continuous Dynamical Systems - A, 2016, 36 (11) : 6379-6411. doi: 10.3934/dcds.2016076

[13]

Andrew Comech. Weak attractor of the Klein-Gordon field in discrete space-time interacting with a nonlinear oscillator. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2711-2755. doi: 10.3934/dcds.2013.33.2711

[14]

Alexander V. Rezounenko, Petr Zagalak. Non-local PDEs with discrete state-dependent delays: Well-posedness in a metric space. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 819-835. doi: 10.3934/dcds.2013.33.819

[15]

Pierre Cardaliaguet, Jean-Michel Lasry, Pierre-Louis Lions, Alessio Porretta. Long time average of mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 279-301. doi: 10.3934/nhm.2012.7.279

[16]

Patrick Gerard, Christophe Pallard. A mean-field toy model for resonant transport. Kinetic & Related Models, 2010, 3 (2) : 299-309. doi: 10.3934/krm.2010.3.299

[17]

Chang-Shou Lin. An expository survey on the recent development of mean field equations. Discrete & Continuous Dynamical Systems - A, 2007, 19 (2) : 387-410. doi: 10.3934/dcds.2007.19.387

[18]

Pierre-Emmanuel Jabin. A review of the mean field limits for Vlasov equations. Kinetic & Related Models, 2014, 7 (4) : 661-711. doi: 10.3934/krm.2014.7.661

[19]

Manuel Núñez. The long-time evolution of mean field magnetohydrodynamics. Discrete & Continuous Dynamical Systems - B, 2004, 4 (2) : 465-478. doi: 10.3934/dcdsb.2004.4.465

[20]

Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173

 Impact Factor: 

Metrics

  • PDF downloads (30)
  • HTML views (116)
  • Cited by (0)

Other articles
by authors

[Back to Top]