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 & 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.  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, 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. 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.   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. 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, 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. 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.   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. 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]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[2]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[3]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

[4]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[5]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[6]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[7]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

[8]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[9]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[10]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[11]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[12]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[13]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[14]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[15]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

 Impact Factor: 

Metrics

  • PDF downloads (156)
  • HTML views (499)
  • Cited by (2)

Other articles
by authors

[Back to Top]