American Institute of Mathematical Sciences

Advanced
July  2019, 6(3): 221-239. doi: 10.3934/jdg.2019016

Discrete mean field games: Existence of equilibria and convergence

Josu Doncel 1,, , Nicolas Gast 2, and  Bruno Gaujal 2,

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.

Keywords: Mean field game, discrete state-space.
Mathematics Subject Classification: Primary: 91A13, 91A15; Secondary: 93A20.
Citation: Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics & Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016
References:
[1]

S. Adlakha, R. 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. Basna, A. 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, arXiv: 1707.02648. 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.   Google Scholar
[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. Carmona, D. 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. Doncel, N. 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. Gomes, J. 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. Gomes, E. 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. Gomes, E. 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.   Google Scholar
[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. Wang, C. T. Bauch, S. Bhattacharyya, A. d'Onofrio, P. Manfredi, M. Perc, N. Perra, M. 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. Adlakha, R. 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. Basna, A. 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, arXiv: 1707.02648. 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.   Google Scholar
[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. Carmona, D. 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. Doncel, N. 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. Gomes, J. 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. Gomes, E. 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. Gomes, E. 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.   Google Scholar
[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. Wang, C. T. Bauch, S. Bhattacharyya, A. d'Onofrio, P. Manfredi, M. Perc, N. Perra, M. 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]

René Aïd, Roxana Dumitrescu, Peter Tankov. The entry and exit game in the electricity markets: A mean-field game approach. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021012
[2]

Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006
[3]

Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011
[4]

Siting Liu, Levon Nurbekyan. Splitting methods for a class of non-potential mean field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021014
[5]

Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021026
[6]

Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021074
[7]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[8]

Tobias Geiger, Daniel Wachsmuth, Gerd Wachsmuth. Optimal control of ODEs with state suprema. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021012
[9]

Akio Matsumoto, Ferenc Szidarovszky. Stability switching and its directions in cournot duopoly game with three delays. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021069
[10]

Mrinal K. Ghosh, Somnath Pradhan. A nonzero-sum risk-sensitive stochastic differential game in the orthant. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021025
[11]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[12]

Rafael López, Óscar Perdomo. Constant-speed ramps for a central force field. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3447-3464. doi: 10.3934/dcds.2021003
[13]

Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301
[14]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[15]

Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675
[16]

Pengfei Wang, Mengyi Zhang, Huan Su. Input-to-state stability of infinite-dimensional stochastic nonlinear systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021066
[17]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061
[18]

Chloé Jimenez. A zero sum differential game with correlated informations on the initial position. A case with a continuum of initial positions. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021009
[19]

Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973
[20]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

 Impact Factor: 

Tools

Metrics

  • PDF downloads (196)
  • HTML views (503)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences