Discrete mean field games: Existence of equilibria and convergence

Josu Doncel; Nicolas Gast; Bruno Gaujal

doi:10.3934/jdg.2019016

Previous Article
Spatial competitive games with disingenuously delayed positions
JDG Home
This Issue
Next Article
Social networks and global transactions

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]	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
[2]	Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[3]	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
[4]	Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[5]	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
[6]	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
[7]	Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[8]	Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020027
[9]	Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[10]	Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190
[11]	Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[12]	Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[13]	Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[14]	Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[15]	Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[16]	Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623
[17]	Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[18]	Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341
[19]	Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195

American Institute of Mathematical Sciences

Discrete mean field games: Existence of equilibria and convergence

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Discrete mean field games: Existence of equilibria and convergence

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors