Fictitious Play for Mixed Strategy Equilibria in Mean Field Games: Conclusion and References

cover
25 Sept 2024

Authors:

(1) Chengfeng Shen, School of Mathematical Sciences, Peking University, Beijing;

(2) Yifan Luo, School of Mathematical Sciences, Peking University, Beijing;

(3) Zhennan Zhou, Beijing International Center for Mathematical Research, Peking University.

Abstract and 1. Introduction

2 Model and 2.1 Optimal Stopping and Obstacle Problem

2.2 Mean Field Games with Optimal Stopping

2.3 Pure Strategy Equilibrium for OSMFG

2.4 Mixed Strategy Equilibrium for OSMFG

3 Algorithm Construction and 3.1 Fictitious Play

3.2 Convergence of Fictitious Play to Mixed Strategy Equilibrium

3.3 Algorithm Based on Fictitious Play

3.4 Numerical Analysis

4 Numerical Experiments and 4.1 A Non-local OSMFG Example

4.2 A Local OSMFG Example

5 Conclusion, Acknowledgement, and References

5 Conclusion

In conclusion, this paper proposes a novel generalized fictitious play algorithm for computing mixed strategy equilibria in OSMFGs. The key innovations include leveraging an iterative process of solving pure strategy systems to approximate mixed equilibria, as well as expanding the design flexibility for the learning rate parameter. Rigorous convergence results are provided, and finite difference schemes are constructed to efficiently solve the obstacle and Fokker-Planck equations during each iteration.

Future work includes extensions to problems with common noise, where the equilibria consist of randomized stopping times that depend on the realized common noise path. The generalized fictitious play framework could also be applied to other competitive games involving optimal stopping decisions. Additionally, further analysis on quantifying the convergence rate and computational complexity could provide deeper theoretical insights. Overall, this paper introduces a novel algorithm and analysis to overcome the limitations of current OSMFG methods, opening the door for handling broader classes of large-scale dynamic games with optimal stopping.

Acknowledgement

ZZ is supported by the National Key R&D Program of China, Project Number 2021YFA1001200, and the NSFC, grant Number 12031013, 12171013. YL is supported by the NSFC, grant Number 12090022. We thank Xu’an Dou, Jian-Guo Liu and Jiajun Tong for helpful discussions.

References

[1] Y. Achdou, F. Camilli, and I. C. Dolcetta, Mean field games: Convergence of a finite difference method, SIAM J. Numer. Anal., 51 (2012), pp. 2585–2612.

[2] ________, Mean field games: Numerical methods for the planning problem, SIAM J. Control. Optim., 50 (2012), pp. 77–109.

[3] Y. Achdou and I. C. Dolcetta, Mean field games: Numerical methods, SIAM J. Numer. Anal., 48 (2010), pp. 1136–1162.

[4] R. Aid, R. Dumitrescu, and P. Tankov, The entry and exit game in the electricity markets: A mean-field game approach, Journal of Dynamics & Games, (2020).

[5] C. Bertucci, Optimal stopping in mean field games, an obstacle problem approach, Journal de Math´ematiques Pures et Appliqu´ees, (2017).

[6] ________, A remark on uzawa’s algorithm and an application to mean field games systems, ESAIM: Mathematical Modelling and Numerical Analysis, (2018).

[7] G. Bouveret, R. Dumitrescu, and P. Tankov, Mean-field games of optimal stopping: A relaxed solution approach, SIAM J. Control. Optim., 58 (2018), pp. 1795–1821.

[8] L. Brugnano and A. Sestini, Iterative solution of piecewise linear systems for the numerical solution of obstacle problems 12, arXiv: Numerical Analysis, (2009).

[9] P. Cardaliaguet and S. Hadikhanloo, Learning in mean field games: The fictitious play, ESAIM: Control, Optimisation and Calculus of Variations, 23 (2015), pp. 569–591.

[10] R. Dumitrescu, M. Leutscher, and P. Tankov, Linear programming fictitious play algorithm for mean field games with optimal stopping and absorption, ESAIM: Mathematical Modelling and Numerical Analysis, (2022).

[11] X. Fernandez-Real and X. Ros-Oton ´ , Regularity theory for elliptic pde, 2022.

[12] R. H. W. Hoppe, Multigrid algorithms for variational inequalities, SIAM Journal on Numerical Analysis, 24 (1987), pp. 1046–1065.

[13] J. Huang and T. Xie, A class of mean-field games with optimal stopping and its applications, Asian Journal of Control, (2023).

[14] J. M. Lasry and P. L. Lions, Jeux `a champ moyen. i – le cas stationnaire, Comptes Rendus Mathematique, 343 (2006), pp. 619–625.

[15] ________, Jeux `a champ moyen. ii – horizon fini et contrˆole optimal, Comptes Rendus Mathematique, 343 (2006), pp. 679–684.

[16] ________, Mean field games, Japanese Journal of Mathematics, 2 (2007), pp. 229–260.

[17] M. Lauri`ere, Numerical methods for mean field games and mean field type control, ArXiv, abs/2106.06231 (2021).

[18] P. Lee, T. W. Kim, and S. Kim, Accurate and efficient numerical solutions for elliptic obstacle problems, Journal of Inequalities and Applications, 2017 (2017).

[19] S. Perrin, J. P´erolat, M. Lauri`ere, M. Geist, R. Elie, and O. Pietquin ´ , Fictitious play for mean field games: Continuous time analysis and applications, ArXiv, abs/2007.03458 (2020).

[20] G. Tran, H. Schaeffer, W. M. Feldman, and S. Osher, An l1 penalty method for general obstacle problems, SIAM J. Appl. Math., 75 (2014), pp. 1424–1444.

[21] X. Yang, G. Wang, and X. Gu, Numerical solution for a parabolic obstacle problem with nonsmooth initial data, Numerical Methods for Partial Differential Equations, 30 (2014).

This paper is available on arxiv under CC 4.0 license.