American Institute of Mathematical Sciences

Advanced
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

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-109. 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-1162. 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-271. 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, 2001), Internat. J. Numer. Methods Fluids, 40 (2002), 21-30.  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-1730. 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-328.  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 "Paris-Princeton Lectures on Mathematical Finance 2010," Lecture Notes in Math., 2003, Springer, Berlin, (2011), 205-266.  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-849 (electronic). 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-588. 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-625. 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-684. 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-260.  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, P. Oswald and K. Stüben, Academic Press, Inc., San Diego, CA, 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-644. 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-109. 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-1162. 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-271. 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, 2001), Internat. J. Numer. Methods Fluids, 40 (2002), 21-30.  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-1730. 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-328.  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 "Paris-Princeton Lectures on Mathematical Finance 2010," Lecture Notes in Math., 2003, Springer, Berlin, (2011), 205-266.  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-849 (electronic). 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-588. 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-625. 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-684. 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-260.  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, P. Oswald and K. Stüben, Academic Press, Inc., San Diego, CA, 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-644. 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]

Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete & 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 & Games, 2021  doi: 10.3934/jdg.2021014
[4]

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
[5]

Emmanuel Frénod. Homogenization-based numerical methods. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : i-ix. doi: 10.3934/dcdss.201605i
[6]

Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006
[7]

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
[8]

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
[9]

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
[10]

Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173
[11]

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
[12]

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
[13]

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
[14]

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
[15]

Neil K. Chada, Yuming Chen, Daniel Sanz-Alonso. Iterative ensemble Kalman methods: A unified perspective with some new variants. Foundations of Data Science, 2021  doi: 10.3934/fods.2021011
[16]

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
[17]

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
[18]

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
[19]

Yue Qiu, Sara Grundel, Martin Stoll, Peter Benner. Efficient numerical methods for gas network modeling and simulation. Networks & Heterogeneous Media, 2020, 15 (4) : 653-679. doi: 10.3934/nhm.2020018
[20]

Abdon Atangana, José Francisco Gómez-Aguilar, Jordan Y. Hristov, Kolade M. Owolabi. Preface on "New trends of numerical and analytical methods". Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : i-ii. doi: 10.3934/dcdss.20203i

2020 Impact Factor: 1.213

Tools

Metrics

  • PDF downloads (143)
  • HTML views (0)
  • Cited by (20)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences