Learning discrete-time major-minor mean field games
AUTHORs: 
Kai Cui, Gökçe Dayanıklı, Mathieu Laurière, Matthieu Geist, Olivier Pietquin, Heinz KoepplAuthors Info & Claims
Article No.: 1070, Pages 9616 - 9625
Abstract
Recent techniques based on Mean Field Games (MFGs) allow the scalable analysis of multi-player games with many similar, rational agents. However, standard MFGs remain limited to homogeneous players that weakly influence each other, and cannot model major players that strongly influence other players, severely limiting the class of problems that can be handled. We propose a novel discrete time version of major-minor MFGs (M3FGs), along with a learning algorithm based on fictitious play and partitioning the probability simplex. Importantly, M3FGs generalize MFGs with common noise and can handle not only random exogeneous environment states but also major players. A key challenge is that the mean field is stochastic and not deterministic as in standard MFGs. Our theoretical investigation verifies both the M3FG model and its algorithmic solution, showing firstly the well-posedness of the M3FG model starting from a finite game of interest, and secondly convergence and approximation guarantees of the fictitious play algorithm. Then, we empirically verify the obtained theoretical results, ablating some of the theoretical assumptions made, and show successful equilibrium learning in three example problems. Overall, we establish a learning framework for a novel and broad class of tractable games.
References
[1]
Aurell, A.; Carmona, R.; Dayanikli, G.; and Laurière, M. 2022. Optimal incentives to mitigate epidemics: a Stackelberg mean field game approach. SIAM J. Control Optim., 60(2): S294—S322.
[2]
Bensoussan, A.; Chau, M. H.; and Yam, S. C. 2016. Mean field games with a dominating player. Appl. Math. Optim., 74: 91-128.
[3]
Cabannes, T.; Laurière, M.; Pérolat, J.; Marinier, R.; Girgin, S.; Perrin, S.; Pietquin, O.; Bayen, A. M.; Goubault, E.; and Elie, R. 2022. Solving N-Player Dynamic Routing Games with Congestion: A Mean-Field Approach. In Proc. AAMAS, volume 21, 1557-1559.
[4]
Cardaliaguet, P.; Cirant, M.; and Porretta, A. 2020. Remarks on Nash equilibria in mean field game models with a major player. Proc. Am. Math. Soc., 148(10): 4241-4255.
[5]
Carmona, R. 2020. Applications of Mean Field Games in Financial Engineering and Economic Theory. arXiv:2012.05237.
[6]
Carmona, R.; and Dayanikli, G. 2021. Mean field game model for an advertising competition in a duopoly. International Game Theory Review, 23(04): 2150024.
[7]
Carmona, R.; Dayanikli, G.; and Laurière, M. 2022. Mean field models to regulate carbon emissions in electricity production. Dynamic Games and Applications, 12(3): 897-928.
[8]
Carmona, R.; Delarue, F.; and Lacker, D. 2016. Mean field games with common noise. Ann. Probab., 44(6): 3740-3803.
[9]
Carmona, R.; Delarue, F.; et al. 2018. Probabilistic theory of mean field games with applications I-II. Springer.
[10]
Carmona, R.; and Wang, P. 2017. An alternative approach to mean field game with major and minor players, and applications to herders impacts. Appl. Math. Optim., 76: 5-27.
[11]
Carmona, R.; and Wang, P. 2021. Finite-state contract theory with a principal and a field of agents. Management Science, 67(8): 4725-4741.
[12]
Carmona, R. A.; and Zhu, X. 2016. A probabilistic approach to mean field games with major and minor players. Ann. Appl. Probab., 26(3): 1535-1580.
[13]
Chaintron, L.-P.; and Diez, A. 2022. Propagation of chaos: A review of models, methods and applications. I. Models and methods. Kinetic and Related Models, 15(6): 895-1015.
[14]
Cui, K.; Dayanikli, G.; Laurière, M.; Geist, M.; Pietquin, O.; and Koeppl, H. 2023. Learning Discrete-Time Major-Minor Mean Field Games. arXiv:2312.10787.
[15]
Cui, K.; Fabian, C.; and Koeppl, H. 2023. Multi-Agent Reinforcement Learning via Mean Field Control: Common Noise, Major Agents and Approximation Properties. arXiv:2303.10665.
[16]
Cui, K.; and Koeppl, H. 2021. Approximately solving mean field games via entropy-regularized deep reinforcement learning. In Proc. AISTATS, 1909-1917.
[17]
Daskalakis, C.; Goldberg, P. W.; and Papadimitriou, C. H. 2009. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1): 195-259.
[18]
Djehiche, B.; Tcheukam, A.; and Tembine, H. 2017. Mean-Field-Type Games in Engineering. AIMS Electron. Electr. Eng., 1(1): 18-73.
[19]
Elie, R.; Mastrolia, T.; and Possamaï, D. 2019. A tale of a principal and many, many agents. Mathematics of Operations Research, 44(2): 440-467.
[20]
Geist, M.; Pérolat, J.; Laurière, M.; Elie, R.; Perrin, S.; Bachem, O.; Munos, R.; and Pietquin, O. 2022. Concave Utility Reinforcement Learning: The Mean-field Game Viewpoint. In Proc. AAMAS, 489-497.
[21]
Gu, H.; Guo, X.; Wei, X.; and Xu, R. 2021. Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis. SIAM J. Math. Data Sci., 3(4): 1168-1196.
[22]
Guo, X.; Hu, A.; Xu, R.; and Zhang, J. 2019. Learning mean-field games. In Proc. NeurIPS, 4966-4976.
[23]
Guo, X.; Hu, A.; and Zhang, J. 2022. Optimization frameworks and sensitivity analysis of Stackelberg mean-field games. arXiv:2210.04110.
[24]
Guo, X.; Hu, A.; and Zhang, J. 2023. MF-OMO: An Optimization Formulation of Mean-Field Games. arXiv:2206.09608.
[25]
Guo, X.; Li, L.; Nabi, S.; Salhab, R.; and Zhang, J. 2023. MESOB: Balancing Equilibria & Social Optimality. arXiv:2307.07911.
[26]
Guo, X.; Xu, R.; and Zariphopoulou, T. 2022. Entropy regularization for mean field games with learning. Math. Oper. Res.
[27]
Harris, C. 1998. On the rate of convergence of continuous-time fictitious play. Games Econ. Behav., 22(2): 238-259.
[28]
Hernández-Lerma, O.; and Lasserre, J. B. 2012. Discrete-time Markov control processes: basic optimality criteria, volume 30. Springer Science & Business Media.
[29]
Hofbauer, J.; and Sandholm, W. H. 2002. On the global convergence of stochastic fictitious play. Econometrica, 70(6): 2265-2294.
[30]
Huang, J.; and Wang, S. 2016. Dynamic optimization of large-population systems with partial information. J. Optim. Theory Appl., 168: 231-245.
[31]
Huang, M. 2010. Large-population LQG games involving a major player: the Nash certainty equivalence principle. SIAM J. Control Optim., 48(5): 3318-3353.
[32]
Huang, M.; Caines, P. E.; Malhame, R. P.; et al. 2006. Distributed multi-agent decision-making with partial observations: asymptotic Nash equilibria. In Proc. 17th Internat. Symp. MTNS, 2725-2730.
[33]
Huang, M.; Malhamé, R. P.; and Caines, P. E. 2006. Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle. Commun. Inf. Syst., 6(3): 221-252.
[34]
Lasry, J.-M.; and Lions, P.-L. 2007. Mean field games. Japanese J. Math., 2(1): 229-260.
[35]
Lasry, J.-M.; and Lions, P.-L. 2018. Mean-field games with a major player. Comptes Rendus Mathematique, 356(8): 886-890.
[36]
Laurière, M.; Perrin, S.; Girgin, S.; Muller, P.; Jain, A.; Cabannes, T.; Piliouras, G.; Pérolat, J.; Elie, R.; Pietquin, O.; et al. 2022. Scalable deep reinforcement learning algorithms for mean field games. In Proc. ICML, 12078-12095. PMLR.
[37]
Lauriere, M.; Perrin, S.; Geist, M.; and Pietquin, O. 2022. Learning Mean Field Games: A Survey. arXiv:2205.12944.
[38]
Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015. Human-level control through deep reinforcement learning. Nature, 518(7540): 529-533.
[39]
Mondal, W. U.; Agarwal, M.; Aggarwal, V.; and Ukkusuri, S. V. 2022. On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC). JMLR, 23(129): 1-46.
[40]
Motte, M.; and Pham, H. 2022. Mean-field Markov decision processes with common noise and open-loop controls. Ann. Appl. Probab., 32(2): 1421-1458.
[41]
Nguyen, S. L.; and Huang, M. 2012. Linear-quadratic-Gaussian mixed games with continuum-parametrized minor players. SIAM J. Control Optim., 50(5): 2907-2937.
[42]
Nourian, M.; and Caines, P. E. 2013. e-Nash mean field game theory for nonlinear stochastic dynamical systems with major and minor agents. SIAM J. Control Optim., 51(4): 3302-3331.
[43]
Pásztor, B.; Krause, A.; and Bogunovic, I. 2023. Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning. Trans. Mach. Learn. Res.
[44]
Pérolat, J.; Perrin, S.; Elie, R.; Laurière, M.; Piliouras, G.; Geist, M.; Tuyls, K.; and Pietquin, O. 2022. Scaling Mean Field Games by Online Mirror Descent. In Proc. AAMAS, 1028-1037.
[45]
Perrin, S.; Perolat, J.; Laurière, M.; Geist, M.; Elie, R.; and Pietquin, O. 2020. Fictitious play for mean field games: continuous time analysis and applications. In Proc. NeurIPS, 13199-13213.
[46]
Saldi, N.; Başar, T.; and Raginsky, M. 2018. Markov-Nash equilibria in mean-field games with discounted cost. SIAM J. Control Optim., 56(6): 4256-4287.
[47]
Sen, N.; and Caines, P. E. 2016. Mean field game theory with a partially observed major agent. SIAM J. Control Optim., 54(6): 3174-3224.
[48]
Sutton, R. S.; and Barto, A. G. 2018. Reinforcement Learning: An Introduction. Cambridge, MA, USA: MIT press.
[49]
Vasal, D.; and Berry, R. 2022. Master Equation for Discrete-Time Stackelberg Mean Field Games with a Single Leader. In Proc. CDC, 5529-5535. IEEE.
[50]
Yang, Y.; and Wang, J. 2021. An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspective. arXiv:2011.00583.
[51]
Yardim, B.; Cayci, S.; Geist, M.; and He, N. 2023. Policy mirror ascent for efficient and independent learning in mean field games. In Proc. ICML, 39722-39754. PMLR.
[52]
Zhang, K.; Yang, Z.; and Başar, T. 2021. Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms. In Vamvoudakis, K. G.; Wan, Y.; Lewis, F. L.; and Cansever, D., eds., Handbook of Reinforcement Learning and Control, 321-384. Cham: Springer International Publishing.
Index Terms
- Learning discrete-time major-minor mean field games
Index terms have been assigned to the content through auto-classification.
Recommendations
Planarity, Colorability, and Minor Games
Let $m$ and $b$ be positive integers, and let $F$ be a hypergraph. In an $(m,b)$ Maker-Breaker game $F$ two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of $F$. Maker selects $m$ vertices per move, and Breaker ...
Waiter-Client and Client-Waiter planarity, colorability and minor games
For a finite set X , a family of sets F 2 X and a positive integer q , we consider two types of two player, perfect information games with no chance moves. In each round of the ( 1 : q ) Waiter-Client game ( X , F ) , the first player, called Waiter, ...
Nonzero-Sum Stochastic Games and Mean-Field Games with Impulse Controls
We consider a general class of nonzero-sum N-player stochastic games with impulse controls, where players control the underlying dynamics with discrete interventions. We adopt a veri?cation approach and provide su?cient conditions for the Nash equilibria (...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2024
23861 pages
ISBN:978-1-57735-887-9
Copyright © 2024 Association for the Advancement of Artificial Intelligence.
Sponsors
- Association for the Advancement of Artificial Intelligence
Publisher
AAAI Press
Publication History
Published: 20 February 2024
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Jan 2025