July  2019, 6(3): 221-239. 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 and Games, 2019, 6 (3) : 221-239. 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.

[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.

[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.

[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.

[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, arXiv: 1707.02648. doi: 10.1137/17M113887X.

[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. 

[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.

[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.

[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.

[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.

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[26]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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.

[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.

[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.

[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.

[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, arXiv: 1707.02648. doi: 10.1137/17M113887X.

[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. 

[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.

[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.

[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.

[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.

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[26]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[1]

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

[2]

Thi Tuyet Trang Chau, Pierre Ailliot, Valérie Monbet, Pierre Tandeo. Comparison of simulation-based algorithms for parameter estimation and state reconstruction in nonlinear state-space models. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022054

[3]

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

[4]

César Barilla, Guillaume Carlier, Jean-Michel Lasry. A mean field game model for the evolution of cities. Journal of Dynamics and Games, 2021, 8 (3) : 299-329. doi: 10.3934/jdg.2021017

[5]

René Aïd, Roxana Dumitrescu, Peter Tankov. The entry and exit game in the electricity markets: A mean-field game approach. Journal of Dynamics and Games, 2021, 8 (4) : 331-358. doi: 10.3934/jdg.2021012

[6]

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

[7]

Shuhua Zhang, Junying Zhao, Ming Yan, Xinyu Wang. Modeling and computation of mean field game with compound carbon abatement mechanisms. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3333-3347. doi: 10.3934/jimo.2020121

[8]

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

[9]

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

[10]

Theresa Lange, Wilhelm Stannat. Mean field limit of Ensemble Square Root filters - discrete and continuous time. Foundations of Data Science, 2021, 3 (3) : 563-588. doi: 10.3934/fods.2021003

[11]

Stamatios Katsikas, Vassilli Kolokoltsov. Evolutionary, mean-field and pressure-resistance game modelling of networks security. Journal of Dynamics and Games, 2019, 6 (4) : 315-335. doi: 10.3934/jdg.2019021

[12]

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

[13]

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

[14]

Kuang Huang, Xuan Di, Qiang Du, Xi Chen. A game-theoretic framework for autonomous vehicles velocity control: Bridging microscopic differential games and macroscopic mean field games. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4869-4903. doi: 10.3934/dcdsb.2020131

[15]

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 and Games, 2017, 4 (1) : 59-74. doi: 10.3934/jdg.2017004

[16]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control and Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[17]

Fabio Bagagiolo, Rosario Maggistro, Raffaele Pesenti. Origin-to-destination network flow with path preferences and velocity controls: A mean field game-like approach. Journal of Dynamics and Games, 2021, 8 (4) : 359-380. doi: 10.3934/jdg.2021007

[18]

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 and Continuous Dynamical Systems, 2019, 39 (7) : 3897-3921. doi: 10.3934/dcds.2019157

[19]

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

[20]

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

 Impact Factor: 

Metrics

  • PDF downloads (354)
  • HTML views (509)
  • Cited by (2)

Other articles
by authors

[Back to Top]