Iterative strategies for solving linearized discrete mean field games systems

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

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

Iterative strategies for solving linearized discrete mean field games systems

Yves Achdou ^1, and Victor Perez ^1,

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 and Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197

References:

[1]	, UMFPACK. Available from: 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-109. doi: 10.1137/100790069.
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods, SIAM J. Numer. Anal., 48 (2010), 1136-1162. 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-271. 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, 2001), Internat. J. Numer. Methods Fluids, 40 (2002), 21-30.
[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-1730. 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-328.
[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 "Paris-Princeton Lectures on Mathematical Finance 2010," Lecture Notes in Math., 2003, Springer, Berlin, (2011), 205-266.
[10]	S. Henn, A multigrid method for a fourth-order diffusion equation with application to image processing, SIAM J. Sci. Comput., 27 (2005), 831-849 (electronic). 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-588. 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-625. 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-684. 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-260.
[15]	P.-L. Lions, Cours du Collège de France, 2007-2011. Available from: 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, P. Oswald and K. Stüben, Academic Press, Inc., San Diego, CA, 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-644. doi: 10.1137/0913035.

show all references

References:

[1]	, UMFPACK. Available from: 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-109. doi: 10.1137/100790069.
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods, SIAM J. Numer. Anal., 48 (2010), 1136-1162. 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-271. 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, 2001), Internat. J. Numer. Methods Fluids, 40 (2002), 21-30.
[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-1730. 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-328.
[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 "Paris-Princeton Lectures on Mathematical Finance 2010," Lecture Notes in Math., 2003, Springer, Berlin, (2011), 205-266.
[10]	S. Henn, A multigrid method for a fourth-order diffusion equation with application to image processing, SIAM J. Sci. Comput., 27 (2005), 831-849 (electronic). 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-588. 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-625. 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-684. 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-260.
[15]	P.-L. Lions, Cours du Collège de France, 2007-2011. Available from: 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, P. Oswald and K. Stüben, Academic Press, Inc., San Diego, CA, 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-644. doi: 10.1137/0913035.

[1]	Olivier Guéant. New numerical methods for mean field games with quadratic costs. Networks and Heterogeneous Media, 2012, 7 (2) : 315-336. doi: 10.3934/nhm.2012.7.315
[2]	Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4905-4923. doi: 10.3934/dcdsb.2020132
[3]	Siting Liu, Levon Nurbekyan. Splitting methods for a class of non-potential mean field games. Journal of Dynamics and Games, 2021, 8 (4) : 467-486. doi: 10.3934/jdg.2021014
[4]	Lori Badea. Multigrid methods for some quasi-variational inequalities. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1457-1471. doi: 10.3934/dcdss.2013.6.1457
[5]	Emmanuel Frénod. Homogenization-based numerical methods. Discrete and Continuous Dynamical Systems - S, 2016, 9 (5) : i-ix. doi: 10.3934/dcdss.201605i
[6]	Pierre Cardaliaguet, Jean-Michel Lasry, Pierre-Louis Lions, Alessio Porretta. Long time average of mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 279-301. doi: 10.3934/nhm.2012.7.279
[7]	Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics and Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016
[8]	Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks and Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021
[9]	Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173
[10]	Martin Burger, Marco Di Francesco, Peter A. Markowich, Marie-Therese Wolfram. Mean field games with nonlinear mobilities in pedestrian dynamics. Discrete and Continuous Dynamical Systems - B, 2014, 19 (5) : 1311-1333. doi: 10.3934/dcdsb.2014.19.1311
[11]	Adriano Festa, Diogo Gomes, Francisco J. Silva, Daniela Tonon. Preface: Mean field games: New trends and applications. Journal of Dynamics and Games, 2021, 8 (4) : i-ii. doi: 10.3934/jdg.2021025
[12]	Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics and Games, 2021, 8 (4) : 445-465. doi: 10.3934/jdg.2021006
[13]	Lucio Boccardo, Luigi Orsina. The duality method for mean field games systems. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1343-1360. doi: 10.3934/cpaa.2022021
[14]	Victoria Martín-Márquez, Simeon Reich, Shoham Sabach. Iterative methods for approximating fixed points of Bregman nonexpansive operators. Discrete and Continuous Dynamical Systems - S, 2013, 6 (4) : 1043-1063. doi: 10.3934/dcdss.2013.6.1043
[15]	Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[16]	Victoria Martín-Márquez, Simeon Reich, Shoham Sabach. Iterative methods for approximating fixed points of Bregman nonexpansive operators. Discrete and Continuous Dynamical Systems - S, 2013, 6 (4) : 1043-1063. doi: 10.3934/dcdss.2013.6.1043
[17]	Neil K. Chada, Yuming Chen, Daniel Sanz-Alonso. Iterative ensemble Kalman methods: A unified perspective with some new variants. Foundations of Data Science, 2021, 3 (3) : 331-369. doi: 10.3934/fods.2021011
[18]	Dang Van Hieu, Le Dung Muu, Pham Kim Quy. New iterative regularization methods for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021185
[19]	Ching-Shan Chou, Yong-Tao Zhang, Rui Zhao, Qing Nie. Numerical methods for stiff reaction-diffusion systems. Discrete and Continuous Dynamical Systems - B, 2007, 7 (3) : 515-525. doi: 10.3934/dcdsb.2007.7.515
[20]	Emmanuel Frénod. An attempt at classifying homogenization-based numerical methods. Discrete and Continuous Dynamical Systems - S, 2015, 8 (1) : i-vi. doi: 10.3934/dcdss.2015.8.1i

2021 Impact Factor: 1.41

Tools

Metrics

Other articles
by authors

on AIMS
Yves Achdou Victor Perez
on Google Scholar
Yves Achdou Victor Perez

[Back to Top]