Iterative strategies for solving linearized discrete mean field games systems

Previous Article
Preface
NHM Home
This Issue
Next Article
From discrete to continuous Wardrop equilibria

June 2012, 7(2): 197-217. doi: 10.3934/nhm.2012.7.197

Iterative strategies for solving linearized discrete mean field games systems

1.	Université Paris Diderot, UMR 7598, Laboratoire Jacques-Louis Lions, Paris, France, France

Received November 2011 Revised March 2012 Published June 2012

Abstract
Related Papers

Mean fields games (MFG) describe the asymptotic behavior of stochastic differential games in which the number of players tends to $+\infty$. Under suitable assumptions, they lead to a new kind of system of two partial differential equations: a forward Bellman equation coupled with a backward Fokker-Planck equation. In earlier articles, finite difference schemes preserving the structure of the system have been proposed and studied. They lead to large systems of nonlinear equations in finite dimension. A possible way of numerically solving the latter is to use inexact Newton methods: a Newton step consists of solving a linearized discrete MFG system. The forward-backward character of the MFG system makes it impossible to use time marching methods. In the present work, we propose three families of iterative strategies for solving the linearized discrete MFG systems, most of which involve suitable multigrid solvers or preconditioners.

Keywords: multigrid methods., numerical methods, Mean field games, iterative solvers.

Mathematics Subject Classification: Primary: 91-08, 91A23, 65N22; Secondary: 65M06, 65F1.

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

References:

[1]	, UMFPACK., Available from: \url{http://www.cise.ufl.edu/research/sparse/umfpack/current/}., (). Google Scholar
[2]	Y. Achdou, F. Camilli, and I. Capuzzo Dolcetta, Mean field games: numerical methods for the planning problem,, SIAM J. Control Optim., 50 (2012), 77. doi: 10.1137/100790069. Google Scholar
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods,, SIAM J. Numer. Anal., 48 (2010), 1136. doi: 10.1137/090758477. Google Scholar
[4]	J.-D. Benamou and Y. Brenier, Mixed $L^2$-Wasserstein optimal mapping between prescribed density functions,, J. Optim. Theory Appl., 111 (2001), 255. doi: 10.1023/A:1011926116573. Google Scholar
[5]	J.-D. Benamou, Y. Brenier and K. Guittet, The Monge-Kantorovitch mass transfer and its computational fluid mechanics formulation,, ICFD Conference on Numerical Methods for Fluid Dynamics (Oxford, 40 (2002), 21. Google Scholar
[6]	A. Brandt, Rigorous quantitative analysis of multigrid. I. Constant coefficients two-level cycle with $L_2$-norm,, SIAM J. Numer. Anal., 31 (1994), 1695. doi: 10.1137/0731087. Google Scholar
[7]	D. A. Gomes, J. Mohr and R. R. Souza, Discrete time, finite state space mean field games,, J. Math. Pures Appl. (9), 93 (2010), 308. Google Scholar
[8]	O. Guéant, Mean field games equations with quadratic hamiltonian: A specific approach,, \arXiv{1106.3269}, (2011). Google Scholar
[9]	O. Guéant, J.-M. Lasry and P.-L. Lions, Mean field games and applications,, in, 2003 (2011), 205. Google Scholar
[10]	S. Henn, A multigrid method for a fourth-order diffusion equation with application to image processing,, SIAM J. Sci. Comput., 27 (2005), 831. doi: 10.1137/040611124. Google Scholar
[11]	A. Lachapelle, J. Salomon and G. Turinici, Computation of mean field equilibria in economics,, Math. Models Methods Appl. Sci., 20 (2010), 567. doi: 10.1142/S0218202510004349. Google Scholar
[12]	J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. I. Le cas stationnaire,, C. R. Math. Acad. Sci. Paris, 343 (2006), 619. doi: 10.1016/j.crma.2006.09.019. Google Scholar
[13]	J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. II. Horizon fini et contrôle optimal,, C. R. Math. Acad. Sci. Paris, 343 (2006), 679. doi: 10.1016/j.crma.2006.09.018. Google Scholar
[14]	J.-M. Lasry and P.-L. Lions, Mean field games,, Jpn. J. Math., 2 (2007), 229. Google Scholar
[15]	P.-L. Lions, Cours du Collège de France, 2007-2011., Available from: \url{http://www.college-de-france.fr/default/EN/all/equ_der/}., (). Google Scholar
[16]	U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid,", With contributions by A. Brandt, (2001). Google Scholar
[17]	H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems,, SIAM J. Sci. Statist. Comput., 13 (1992), 631. doi: 10.1137/0913035. Google Scholar

show all references

References:

[1]	, UMFPACK., Available from: \url{http://www.cise.ufl.edu/research/sparse/umfpack/current/}., (). Google Scholar
[2]	Y. Achdou, F. Camilli, and I. Capuzzo Dolcetta, Mean field games: numerical methods for the planning problem,, SIAM J. Control Optim., 50 (2012), 77. doi: 10.1137/100790069. Google Scholar
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods,, SIAM J. Numer. Anal., 48 (2010), 1136. doi: 10.1137/090758477. Google Scholar
[4]	J.-D. Benamou and Y. Brenier, Mixed $L^2$-Wasserstein optimal mapping between prescribed density functions,, J. Optim. Theory Appl., 111 (2001), 255. doi: 10.1023/A:1011926116573. Google Scholar
[5]	J.-D. Benamou, Y. Brenier and K. Guittet, The Monge-Kantorovitch mass transfer and its computational fluid mechanics formulation,, ICFD Conference on Numerical Methods for Fluid Dynamics (Oxford, 40 (2002), 21. Google Scholar
[6]	A. Brandt, Rigorous quantitative analysis of multigrid. I. Constant coefficients two-level cycle with $L_2$-norm,, SIAM J. Numer. Anal., 31 (1994), 1695. doi: 10.1137/0731087. Google Scholar
[7]	D. A. Gomes, J. Mohr and R. R. Souza, Discrete time, finite state space mean field games,, J. Math. Pures Appl. (9), 93 (2010), 308. Google Scholar
[8]	O. Guéant, Mean field games equations with quadratic hamiltonian: A specific approach,, \arXiv{1106.3269}, (2011). Google Scholar
[9]	O. Guéant, J.-M. Lasry and P.-L. Lions, Mean field games and applications,, in, 2003 (2011), 205. Google Scholar
[10]	S. Henn, A multigrid method for a fourth-order diffusion equation with application to image processing,, SIAM J. Sci. Comput., 27 (2005), 831. doi: 10.1137/040611124. Google Scholar
[11]	A. Lachapelle, J. Salomon and G. Turinici, Computation of mean field equilibria in economics,, Math. Models Methods Appl. Sci., 20 (2010), 567. doi: 10.1142/S0218202510004349. Google Scholar
[12]	J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. I. Le cas stationnaire,, C. R. Math. Acad. Sci. Paris, 343 (2006), 619. doi: 10.1016/j.crma.2006.09.019. Google Scholar
[13]	J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. II. Horizon fini et contrôle optimal,, C. R. Math. Acad. Sci. Paris, 343 (2006), 679. doi: 10.1016/j.crma.2006.09.018. Google Scholar
[14]	J.-M. Lasry and P.-L. Lions, Mean field games,, Jpn. J. Math., 2 (2007), 229. Google Scholar
[15]	P.-L. Lions, Cours du Collège de France, 2007-2011., Available from: \url{http://www.college-de-france.fr/default/EN/all/equ_der/}., (). Google Scholar
[16]	U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid,", With contributions by A. Brandt, (2001). Google Scholar
[17]	H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems,, SIAM J. Sci. Statist. Comput., 13 (1992), 631. doi: 10.1137/0913035. Google Scholar

[1]	Olivier Guéant. New numerical methods for mean field games with quadratic costs. Networks & Heterogeneous Media, 2012, 7 (2) : 315-336. doi: 10.3934/nhm.2012.7.315
[2]	Lori Badea. Multigrid methods for some quasi-variational inequalities. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1457-1471. doi: 10.3934/dcdss.2013.6.1457
[3]	Pierre Cardaliaguet, Jean-Michel Lasry, Pierre-Louis Lions, Alessio Porretta. Long time average of mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 279-301. doi: 10.3934/nhm.2012.7.279
[4]	Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173
[5]	Martin Burger, Marco Di Francesco, Peter A. Markowich, Marie-Therese Wolfram. Mean field games with nonlinear mobilities in pedestrian dynamics. Discrete & Continuous Dynamical Systems - B, 2014, 19 (5) : 1311-1333. doi: 10.3934/dcdsb.2014.19.1311
[6]	Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks & Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021
[7]	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
[8]	Emmanuel Frénod. Homogenization-based numerical methods. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : i-ix. doi: 10.3934/dcdss.201605i
[9]	Victoria Martín-Márquez, Simeon Reich, Shoham Sabach. Iterative methods for approximating fixed points of Bregman nonexpansive operators. Discrete & Continuous Dynamical Systems - S, 2013, 6 (4) : 1043-1063. doi: 10.3934/dcdss.2013.6.1043
[10]	Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[11]	Victoria Martín-Márquez, Simeon Reich, Shoham Sabach. Iterative methods for approximating fixed points of Bregman nonexpansive operators. Discrete & Continuous Dynamical Systems - S, 2013, 6 (4) : 1043-1063. doi: 10.3934/dcdss.2013.6.1043
[12]	Ching-Shan Chou, Yong-Tao Zhang, Rui Zhao, Qing Nie. Numerical methods for stiff reaction-diffusion systems. Discrete & Continuous Dynamical Systems - B, 2007, 7 (3) : 515-525. doi: 10.3934/dcdsb.2007.7.515
[13]	Emmanuel Frénod. An attempt at classifying homogenization-based numerical methods. Discrete & Continuous Dynamical Systems - S, 2015, 8 (1) : i-vi. doi: 10.3934/dcdss.2015.8.1i
[14]	Sebastián J. Ferraro, David Iglesias-Ponte, D. Martín de Diego. Numerical and geometric aspects of the nonholonomic SHAKE and RATTLE methods. Conference Publications, 2009, 2009 (Special) : 220-229. doi: 10.3934/proc.2009.2009.220
[15]	Timothy Blass, Rafael de la Llave. Perturbation and numerical methods for computing the minimal average energy. Networks & Heterogeneous Media, 2011, 6 (2) : 241-255. doi: 10.3934/nhm.2011.6.241
[16]	Joseph A. Connolly, Neville J. Ford. Comparison of numerical methods for fractional differential equations. Communications on Pure & Applied Analysis, 2006, 5 (2) : 289-307. doi: 10.3934/cpaa.2006.5.289
[17]	Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243
[18]	Diogo A. Gomes, Gabriel E. Pires, Héctor Sánchez-Morgado. A-priori estimates for stationary mean-field games. Networks & Heterogeneous Media, 2012, 7 (2) : 303-314. doi: 10.3934/nhm.2012.7.303
[19]	Juan Pablo Maldonado López. Discrete time mean field games: The short-stage limit. Journal of Dynamics & Games, 2015, 2 (1) : 89-101. doi: 10.3934/jdg.2015.2.89
[20]	Jitraj Saha, Nilima Das, Jitendra Kumar, Andreas Bück. Numerical solutions for multidimensional fragmentation problems using finite volume methods. Kinetic & Related Models, 2019, 12 (1) : 79-103. doi: 10.3934/krm.2019004

2018 Impact Factor: 0.871

American Institute of Mathematical Sciences