Advanced Search
Article Contents
Article Contents

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

  • *Corresponding author: Levon Nurbekyan

    *Corresponding author: Levon Nurbekyan
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
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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

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

    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\} $

    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

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

    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
  • [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. AchdouF. 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. AlmullaR. 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 AriasD. 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. CardaliaguetP. J. GraberA. 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. HuangP. 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. HuangR. 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. JacobsF. LégerW. 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.
  • 加载中




Article Metrics

HTML views(702) PDF downloads(176) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint