Particle approximation of one-dimensional Mean-Field-Games with local interactions

Marco Di Francesco; Serikbolsyn Duisembay; Diogo Aguiar Gomes; Ricardo Ribeiro

doi:10.3934/dcds.2022025

Article Contents

2022, Volume 42, Issue 7: 3569-3591. Doi: 10.3934/dcds.2022025

This issue Previous Article On decomposition of ambient surfaces admitting

$ A $

-diffeomorphisms with non-trivial attractors and repellers Next Article On information gain, Kullback-Leibler divergence, entropy production and the involution kernel

Particle approximation of one-dimensional Mean-Field-Games with local interactions

1.
University of L'Aquila, Department of Information Engineering, Computer Science, and Mathematics (DISIM), Via Vetoio 1, Coppito, I-67100 L'Aquila, Italy
2.
King Abdullah University of Science and Technology (KAUST), CEMSE Division, KAUST SRI, Center for Uncertainty Quantification in Computational Science and Engineering, Thuwal 23955-6900, Saudi Arabia

^*Corresponding author: Serikbolsyn Duisembay
^*Corresponding author: Serikbolsyn Duisembay

M. Di Francesco was supported by KAUST during his visit in 2020

Received: September 2021

Revised: January 2022

Early access: March 2022

Published: July 2022

S. Duisembay, D. A. Gomes and R. Ribeiro were partially supported by King Abdullah University of Science and Technology (KAUST) baseline funds and KAUST OSR-CRG2021-4674

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

Abstract

We study a particle approximation for one-dimensional first-order Mean-Field-Games (MFGs) with local interactions with planning conditions. Our problem comprises a system of a Hamilton-Jacobi equation coupled with a transport equation. As we deal with the planning problem, we prescribe initial and terminal distributions for the transport equation. The particle approximation builds on a semi-discrete variational problem. First, we address the existence and uniqueness of a solution to the semi-discrete variational problem. Next, we show that our discretization preserves some previously identified conserved quantities. Finally, we prove that the approximation by particle systems preserves displacement convexity. We use this last property to establish uniform estimates for the discrete problem. We illustrate our results for the discrete problem with numerical examples.

Keywords:

Mathematics Subject Classification: Primary: 91A16, 49N80; Secondary: 65C35.

Citation:

Full Text(HTML)

Figure 1. Periodic case: $ \Omega = \mathbb{T} $, $ g(m) = m^2/2 $ (hence, $ G(r) = r^2/6 $) and $ V(x,t) $ is given by (32). (A) Optimal trajectories of the $ N = 50 $ particles minimizing (31). (B) Exact and approximate CDFs for $ N = 50 $ at $ t = T/2 $

Download: Full-size image PowerPoint slide

Figure 2. $ \Omega = \mathbb{R} $, $ g(m) = m $ (hence, $ G(r) = r/2 $) and $ V(x,t) $ is given by (34). (A) Optimal trajectories of the $ N = 50 $ particles minimizing (31). (B) Exact and approximate CDFs for $ N = 50 $ at $ t = T/2 $

Download: Full-size image PowerPoint slide

Figure 3. $ \Omega = \mathbb{R} $, $ g(m) = m $ (hence, $ G(r) = r/2 $) and $ V(x,t) $ is given by (35). (A) Optimal trajectories of the $ N = 50 $ particles minimizing (31). (B) Exact and approximate CDFs for $ N = 50 $ at $ t = T/2 $

Download: Full-size image PowerPoint slide

Figure 4. $ L(v) = v^2/2 $. (A) Optimal trajectories of the particles. (B) Discrete conserved quantity $ \sum_{i = 1}^{N} L'\left(\frac{x_i^{m+1}-x_i^m}{\Delta t}\right)R_i $. (C) Discrete approximation of the semi-discrete quantity $ \sum_{i = 1}^N (L'(u_i)u_i-L(u_i)-G(R_i))R_i $ given by (21)

Download: Full-size image PowerPoint slide

Figure 5. Displacement convexity illustration for $ \sum_{i = 1}^{N} U(R_i(t)) (x_i(t) - x_{i-1}(t)) $ with $ U(z) = e^{-z} $, $ N = 5, \Delta t = \frac{1}{20} $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	Y. Achdou, Finite difference methods for mean field games, in Hamilton-Jacobi Equations: Approximations, Numerical Analysis and Applications, 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: Numerical methods for the planning problem, SIAM Journal on Control and Optimization, 50 (2012), 77-109. doi: 10.1137/100790069.
[3]	Y. Achdou and I. Capuzzo-Dolcetta, Mean field games: Numerical methods, SIAM Journal on Numerical Analysis, 48 (2010), 1136-1162. doi: 10.1137/090758477.
[4]	Y. Achdou and M. Laurière, Mean field type control with congestion (II): An augmented Lagrangian method, Applied Mathematics and Optimization, 74 (2016), 535-578. doi: 10.1007/s00245-016-9391-z.
[5]	Y. Achdou and V. Perez, Iterative strategies for solving linearized discrete mean field games systems, Networks and Heterogeneous Media, 7 (2012), 197-217. doi: 10.3934/nhm.2012.7.197.
[6]	Y. Achdou and A. Porretta, Convergence of a finite difference scheme to weak solutions of the system of partial differential equations arising in mean field games, SIAM Journal on Numerical Analysis, 54 (2016), 161-186. doi: 10.1137/15M1015455.
[7]	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.
[8]	T. Bakaryan, R. Ferreira and D. Gomes, Some estimates for the planning problem with potential, NoDEA. Nonlinear Differential Equations and Applications, 28 (2021), Paper No. 20, 23 pp. doi: 10.1007/s00030-021-00681-z.
[9]	L. Briceño-Arias, D. Kalise, Z. Kobeissi, M. Laurière, Á 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, (2019), 330–348. doi: 10.1051/proc/201965330.
[10]	L. M. Briceño-Arias, D. Kalise and F. J. Silva, Proximal methods for stationary mean field games with local couplings, SIAM Journal on Control and Optimization, 56 (2018), 801-836. doi: 10.1137/16M1095615.
[11]	A. Cesaroni and M. Cirant, One-dimensional multi-agent optimal control with aggregation and distance constraints: Qualitative properties and mean-field limit, Nonlinearity, 34 (2021), 1408-1447. doi: 10.1088/1361-6544/abc795.
[12]	M. Di Francesco, S. Fagioli and M. D. Rosini, Deterministic particle approximation of scalar conservation laws, Bollettino dell'Unione Matematica Italiana, 10 (2017), 487-501. doi: 10.1007/s40574-017-0132-2.
[13]	M. Di Francesco, S. Fagioli and E. Radici, Deterministic particle approximation for nonlocal transport equations with nonlinear mobility, Journal of Differential Equations, 266 (2019), 2830-2868. doi: 10.1016/j.jde.2018.08.047.
[14]	M. Di Francesco, S. Fagioli, M. D. Rosini and G. Russo, Follow-the-leader approximations of macroscopic models for vehicular and pedestrian flows, in Active Particles. Vol. 1. Advances in Theory, Models, and Applications, Birkhäuser/Springer, Cham, (2017), 333–378.
[15]	M. Di Francesco, S. Fagioli, M. D. Rosini and G. Russo, A deterministic particle approximation for non-linear conservation laws, in Theory, Numerics and Applications of Hyperbolic Problems. I, Springer, Cham, (2018), 487–499. doi: 10.1007/978-3-319-91545-6_37.
[16]	M. Di Francesco and G. Stivaletta, Convergence of the follow-the-leader scheme for scalar conservation laws with space dependent flux, Discrete and Continuous Dynamical Systems. Series A, 40 (2020), 233-266. doi: 10.3934/dcds.2020010.
[17]	L. C. Evans, Partial Differential Equations, American Mathematical Society, 1998.
[18]	D. A. Gomes, L. Nurbekyan and M. Sedjro, One-dimensional forward-forward mean-field games, Applied Mathematics and Optimization, 74 (2016), 619-642. doi: 10.1007/s00245-016-9384-y.
[19]	D. A. Gomes and J. Saúde, Numerical methods for finite-state mean-field games satisfying a monotonicity condition, Applied Mathematics & Optimization, 83 (2021), 51–82. doi: 10.1007/s00245-018-9510-0.
[20]	D. A. Gomes and T. Seneci, Displacement convexity for first-order mean-field games, Minimax Theory Appl., 3 (2018), 261-284.
[21]	D. A. Gomes and X. Yang, The Hessian Riemannian flow and Newton's method for effective Hamiltonians and Mather measures, ESAIM. Mathematical Modelling and Numerical Analysis, 54 (2020), 1883-1915. doi: 10.1051/m2an/2020036.
[22]	L. Gosse and G. Toscani, Identification of asymptotic decay to self-similarity for one-dimensional filtration equations, SIAM Journal on Numerical Analysis, 43 (2006), 2590-2606. doi: 10.1137/040608672.
[23]	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, Calculus of Variations and Partial Differential Equations, 58 (2019), Paper No. 115, 28 pp. doi: 10.1007/s00526-019-1561-9.
[24]	M. Huang, P. E. Caines and R. P. Malhamé, Large-population cost-coupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized $ \varepsilon$-Nash equilibria, Institute of Electrical and Electronics Engineers. Transactions on Automatic Control, 52 (2007), 1560-1571. doi: 10.1109/TAC.2007.904450.
[25]	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, Communications in Information and Systems, 6 (2006), 221-251. doi: 10.4310/CIS.2006.v6.n3.a5.
[26]	J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. I. Le cas stationnaire, Comptes Rendus Mathématique. Académie des Sciences. Parisl, 343 (2006), 619-625. doi: 10.1016/j.crma.2006.09.019.
[27]	J.-M. Lasry and P.-L. Lions, Jeux à champ moyen. II. Horizon fini et contrôle optimal, Comptes Rendus Mathématique. Académie des Sciences. Parisl, 343 (2006), 679-684. doi: 10.1016/j.crma.2006.09.018.
[28]	J.-M. Lasry and P.-L. Lions, Mean field games, Japanese Journal of Mathematics, 2 (2007), 229-260. doi: 10.1007/s11537-007-0657-8.
[29]	H. Lavenant and F. Santambrogio, Optimal density evolution with congestion: $L^\infty$ bounds via flow interchange techniques and applications to variational mean field games, Communications in Partial Differential Equations, 43 (2018), 1761-1802. doi: 10.1080/03605302.2018.1499116.
[30]	P.-L. Lions, Cours au Collège de France, http://www.college-de-france.fr, (lectures on November 27th, December 4th-11th, 2009).
[31]	R. J. McCann, A convexity principle for interacting gases, Advances in Mathematics, 128 (1997), 153-179. doi: 10.1006/aima.1997.1634.
[32]	C. Orrieri, A. Porretta and G. Savaré, A variational approach to the mean field planning problem, Journal of Functional Analysis, 277 (2019), 1868-1957. doi: 10.1016/j.jfa.2019.04.011.
[33]	A. Porretta, On the planning problem for the mean field games system, Dyn. Games Appl., 4 (2014), 231-256. doi: 10.1007/s13235-013-0080-0.
[34]	G. Russo, Deterministic diffusion of particles, Communications on Pure and Applied Mathematics, 43 (1990), 697-733. doi: 10.1002/cpa.3160430602.
[35]	B. Schachter, A new class of first order displacement convex functionals, SIAM Journal on Mathematical Analysis, 50 (2018), 1779-1789. doi: 10.1137/17M1131817.