Iterative strategies for solving  linearized discrete mean field games systems

Yves Achdou; Victor Perez; Yves Achdou; Victor Perez

doi:10.3934/nhm.2012.7.197

Networks and Heterogeneous Media

2012, Volume 7, Issue 2: 197-217. doi: 10.3934/nhm.2012.7.197

Previous Article Next Article

Iterative strategies for solving linearized discrete mean field games systems

Yves Achdou ^{1
,},
Victor Perez ^{1
,}

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

Received: 01 November 2011 Revised: 01 March 2012
Primary: 91-08, 91A23, 65N22; Secondary: 65M06, 65F10.

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.
- Mean field games,
- numerical methods,
- iterative solvers,
- multigrid methods
Citation: Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems[J]. Networks and Heterogeneous Media, 2012, 7(2): 197-217. doi: 10.3934/nhm.2012.7.197

Related Papers:

Abstract

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.

References

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

Reader Comments

Your name:*

Email:*
© 2012 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)