Splitting methods for a class of non-potential mean field games

Siting Liu; Levon Nurbekyan

doi:10.3934/jdg.2021014

Article Contents

2021, Volume 8, Issue 4: 467-486. Doi: 10.3934/jdg.2021014

This issue Previous Article On some singular mean-field games Next Article

Splitting methods for a class of non-potential mean field games

Siting Liu and
Levon Nurbekyan^,

Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095, USA

^*Corresponding author: Levon Nurbekyan
^*Corresponding author: Levon Nurbekyan

Received: May 31, 2020

Early access: March 2021

Published: October 2021

This work was supported by AFOSR MURI FA9550-18-1-0502, AFOSR Grant No. FA9550-18-1-0167, ONR Grant No. N00014-18-1-2527, ONR N00014-20-1-2093

Abstract Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by

Abstract

We extend the methods from [39, 37] to a class of non-potential mean-field game (MFG) systems with mixed couplings. Up to now, splitting methods have been applied to potential MFG systems that can be cast as convex-concave saddle-point problems. Here, we show that a class of non-potential MFG can be cast as primal-dual pairs of monotone inclusions and solved via extensions of convex optimization algorithms such as the primal-dual hybrid gradient (PDHG) algorithm. A critical feature of our approach is in considering dual variables of nonlocal couplings in Fourier or feature spaces.

Keywords:

Mathematics Subject Classification: Primary: 49N80, 35Q89, 35A15; Secondary: 35Q91, 35Q93, 65M70, 93A16.

Citation:

Full Text(HTML)

Figure 1. Plot of approximated kernels for example 5.1 case B. From left to right: approximated kernel with $ r = 5^2 $; approximated kernel with $ r = 15^2 $; the exact kernel

Download: Full-size image PowerPoint slide

Figure 2. MFG solution $ \rho(x,0.3), \rho(x,0.6), \rho(x,1) $ for density splitting examples

Download: Full-size image PowerPoint slide

Figure 3. MFG solution $ \rho(x,0.3), \rho(x,0.6), \rho(x,1) $ for static obstacles examples, where the obstacle (yellow) is located at $ \Omega_{obs} = \left\{\|x-[0,0.2]\|^2\leq 0.15^2\right\} \cup \left\{ |x_1|\geq 0.1, |x_2+0.15|\leq 0.05 \right\} $

Download: Full-size image PowerPoint slide

Figure 4. $ 3 $D plots of example 5.2. From left to right: initial density distribution; final density distribution for Case A; final density distribution for Case B

Download: Full-size image PowerPoint slide

Figure 5. MFG solution $ \rho(x,0.3), \rho(x,0.6), \rho(x,1) $ for dynamic obstacles examples

Download: Full-size image PowerPoint slide

Table 1. Comparison of adaptive PDHG and PDHG

$ \epsilon $	1.00e-3	1.00e-4	1.00e-5	1.00e-6	1.00e-7
PDHG	393	955	3030	9108	$> $2e4
adaptive PDHG	295	701	2033	6200	17842

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Y. Achdou, Finite difference methods for mean field games, in Hamilton-Jacobi Equations: Approximations, Numerical Analysis and Applications, Lecture Notes in Math., 2074, Springer, Heidelberg, 2013, 1-47. doi: 10.1007/978-3-642-36433-4_1.
[2]	Y. Achdou, F. Camilli and I. Capuzzo-Dolcetta, Mean field games: Convergence of a finite difference method, SIAM J. Numer. Anal., 51 (2013), 2585-2612. doi: 10.1137/120882421.
[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]	N. Almulla, R. Ferreira and D. Gomes, Two numerical approaches to stationary mean-field games, Dyn. Games Appl., 7 (2017), 657-682. doi: 10.1007/s13235-016-0203-5.
[5]	J.-D. Benamou and G. Carlier, Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations, J. Optim. Theory Appl., 167 (2015), 1-26. doi: 10.1007/s10957-015-0725-9.
[6]	J. -D. Benamou, G. Carlier and F. Santambrogio, Variational mean field games, in Active Particles. Vol. 1. Advances in Theory, Models, and Applications doi: 10.1007/978-3-319-49996-3_4.
[7]	L. M. Briceño-Arias and P. L. Combettes, Monotone operator methods for Nash equilibria in non-potential games, in Computational and Analytical Mathematics, Springer Proc. Math. Stat., 50, Springer, New York, 2013, 143-159. doi: 10.1007/978-1-4614-7621-4_9.
[8]	L. Briceño Arias, D. Kalise, Z. Kobeissi, M. Laurière, A. Mateos González and F. J. Silva, On the implementation of a primal-dual algorithm for second order time-dependent mean field games with local couplings, in CEMRACS 2017-Numerical Methods for Stochastic Models: Control, Uncertainty Quantification, Mean-Field, ESAIM Proc. Surveys, 65, EDP Sci., Les Ulis, 2019, 330-348. doi: 10.1051/proc/201965330.
[9]	L. M. Briceño Arias, D. Kalise and F. J. Silva, Proximal methods for stationary mean field games with local couplings, SIAM J. Control Optim., 56 (2018), 801-836. doi: 10.1137/16M1095615.
[10]	F. Camilli and F. Silva, A semi-discrete approximation for a first order mean field game problem, Netw. Heterog. Media, 7 (2012), 263-277. doi: 10.3934/nhm.2012.7.263.
[11]	P. Cardaliaguet, Long time average of first order mean field games and weak KAM theory, Dyn. Games Appl., 3 (2013), 473-488. doi: 10.1007/s13235-013-0091-x.
[12]	P. Cardaliaguet, Notes on Mean Field Games, (2013)., Available from: Https://www.ceremade.dauphine.fr/ cardaliaguet/.
[13]	P. Cardaliaguet, P. J. Graber, A. Porretta and D. Tonon, Second order mean field games with degenerate diffusion and local coupling, NoDEA Nonlinear Differential Equations Appl., 22 (2015), 1287-1317. doi: 10.1007/s00030-015-0323-4.
[14]	P. Cardaliaguet and S. Hadikhanloo, Learning in mean field games: The fictitious play, ESAIM Control Optim. Calc. Var., 23 (2017), 569-591. doi: 10.1051/cocv/2016004.
[15]	E. Carlini and F. J. Silva, A fully discrete semi-Lagrangian scheme for a first order mean field game problem, SIAM J. Numer. Anal., 52 (2014), 45-67. doi: 10.1137/120902987.
[16]	E. Carlini and F. J. Silva, A semi-Lagrangian scheme for a degenerate second order mean field game system, Discrete Contin. Dyn. Syst., 35 (2015), 4269-4292. doi: 10.3934/dcds.2015.35.4269.
[17]	E. Carlini and F. J. Silva, On the discretization of some nonlinear Fokker-Planck-Kolmogorov equations and applications, SIAM J. Numer. Anal., 56 (2018), 2148-2177. doi: 10.1137/17M1143022.
[18]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.
[19]	A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159 (2016), 253-287. doi: 10.1007/s10107-015-0957-3.
[20]	R. Ferreira and D. Gomes, Existence of weak solutions to stationary mean-field games through variational inequalities, SIAM J. Math. Anal., 50 (2018), 5969-6006. doi: 10.1137/16M1106705.
[21]	R. Ferreira, D. Gomes and T. Tada, Existence of weak solutions to time-dependent mean-field games, preprint, arXiv: 2001.03928.
[22]	T. Goldstein, M. Li, X. Yuan, E. Esser and R. Baraniuk, Adaptive primal-dual hybrid gradient methods for saddle-point problems, preprint, arXiv: 1305.0546.
[23]	D. A. Gomes and J. Saúde, Mean field games models-A brief survey, Dyn. Games Appl., 4 (2014), 110-154. doi: 10.1007/s13235-013-0099-2.
[24]	D. A. Gomes and J. Saúde, Numerical methods for finite-state mean-field games satisfying a monotonicity condition, Appl. Math. Optim., 83 (2021), 51-82. doi: 10.1007/s00245-018-9510-0.
[25]	P. J. Graber and A. R. Mészáros, Sobolev regularity for first order mean field games, Ann. Inst. H. Poincaré Anal. Non Linéaire, 35 (2018), 1557-1576. doi: 10.1016/j.anihpc.2018.01.002.
[26]	P. J. Graber, A. R. Mészáros, F. J. Silva and D. Tonon, The planning problem in mean field games as regularized mass transport, Calc. Var. Partial Differential Equations, 58 (2019), 28pp. doi: 10.1007/s00526-019-1561-9.
[27]	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. doi: 10.1007/978-3-642-14660-2_3.
[28]	S. Hadikhanloo, Learning in anonymous nonatomic games with applications to first-order mean field games, preprint, arXiv: 1704.00378.
[29]	S. Hadikhanloo and F. J. Silva, Finite mean field games: Fictitious play and convergence to a first order continuous mean field game, J. Math. Pures Appl. (9), 132 (2019), 369-397. doi: 10.1016/j.matpur.2019.02.006.
[30]	M. Huang, P. E. Caines and R. P. Malhamé, Large-population cost-coupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized $\epsilon$-Nash equilibria, IEEE Trans. Automat. Control, 52 (2007), 1560-1571. doi: 10.1109/TAC.2007.904450.
[31]	M. Huang, R. P. Malhamé and P. E. Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6 (2006), 221-251. doi: 10.4310/CIS.2006.v6.n3.a5.
[32]	M. Jacobs and F. Léger, A fast approach to optimal transport: The back-and-forth method, Numer. Math., 146 (2020), 513-544. doi: 10.1007/s00211-020-01154-8.
[33]	M. Jacobs, F. Léger, W. Li and S. Osher, Solving large-scale optimization problems with a convergence rate independent of grid size, SIAM J. Numer. Anal., 57 (2019), 1100-1123. doi: 10.1137/18M118640X.
[34]	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.
[35]	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.
[36]	J.-M. Lasry and P.-L. Lions, Mean field games, Jpn. J. Math., 2 (2007), 229-260. doi: 10.1007/s11537-007-0657-8.
[37]	S. Liu, M. Jacobs, W. Li, L. Nurbekyan and S. J. Osher, Computational methods for nonlocal mean field games with applications, preprint, arXiv: 2004.12210.
[38]	L. Nurbekyan, One-dimensional, non-local, first-order stationary mean-field games with congestion: A Fourier approach, Discrete Contin. Dyn. Syst. Ser. S, 11 (2018), 963-990. doi: 10.3934/dcdss.2018057.
[39]	L. Nurbekyan and J. Saúde, Fourier approximation methods for first-order nonlocal mean-field games, Port. Math., 75 (2018), 367-396. doi: 10.4171/PM/2023.
[40]	B. C. Vũ, A variable metric extension of the forward-backward-forward algorithm for monotone operators, Numer. Funct. Anal. Optim., 34 (2013), 1050-1065. doi: 10.1080/01630563.2013.763825.