-
Previous Article
Spatial competitive games with disingenuously delayed positions
- JDG Home
- This Issue
-
Next Article
Social networks and global transactions
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 |
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.
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. |
[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. 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. |
[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. 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. |
[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. |
[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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
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. |
[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. 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. |
[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. 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. |
[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. |
[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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]