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/}., ().
[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.
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods,, SIAM J. Numer. Anal., 48 (2010), 1136. doi: 10.1137/090758477.
[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.
[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.
[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.
[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.
[8]	O. Guéant, Mean field games equations with quadratic hamiltonian: A specific approach,, \arXiv{1106.3269}, (2011).
[9]	O. Guéant, J.-M. Lasry and P.-L. Lions, Mean field games and applications,, in, 2003 (2011), 205.
[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.
[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.
[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.
[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.
[14]	J.-M. Lasry and P.-L. Lions, Mean field games,, Jpn. J. Math., 2 (2007), 229.
[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/}., ().
[16]	U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid,", With contributions by A. Brandt, (2001).
[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.

show all references

References:

[1]	, UMFPACK., Available from: \url{http://www.cise.ufl.edu/research/sparse/umfpack/current/}., ().
[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.
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods,, SIAM J. Numer. Anal., 48 (2010), 1136. doi: 10.1137/090758477.
[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.
[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.
[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.
[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.
[8]	O. Guéant, Mean field games equations with quadratic hamiltonian: A specific approach,, \arXiv{1106.3269}, (2011).
[9]	O. Guéant, J.-M. Lasry and P.-L. Lions, Mean field games and applications,, in, 2003 (2011), 205.
[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.
[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.
[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.
[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.
[14]	J.-M. Lasry and P.-L. Lions, Mean field games,, Jpn. J. Math., 2 (2007), 229.
[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/}., ().
[16]	U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid,", With contributions by A. Brandt, (2001).
[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.

[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]	Emmanuel Frénod. Homogenization-based numerical methods. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : i-ix. doi: 10.3934/dcdss.201605i
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	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
[19]	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
[20]	Giacomo Albi, Lorenzo Pareschi, Mattia Zanella. Opinion dynamics over complex networks: Kinetic modelling and numerical methods. Kinetic & Related Models, 2017, 10 (1) : 1-32. doi: 10.3934/krm.2017001

2017 Impact Factor: 1.187

American Institute of Mathematical Sciences