平均場博奕應用淺談


平均場博奕（mean field game，MFG）理論專門探討數量龐大的智能體（agent）在競爭環境下所使用的策略。每個智能體都會因應身邊其他智能體所採取的行動而隨之應變，務求令自可獲得最大利益。例如，在股票市場，每位交易者為追求最高回報率，都會先留意其他交易者所採取的策略，再決定買入或賣出若干數量的股票。「平均場」（mean field）一詞本來是物理學術語，意思是大群體裏的單一智能體行為對系統的影響微不足道。在典型的MFG裏，智能體的行為是基於其他智能體的狀態分佈而作出反應，而非個別地針對其他智能體的行為而行動。例如，在購物市場裏，某位客人可以在得知其他客人及賣家的交易資訊後才去購買商品，然而這種做法現實幾乎不可能做到，而且費時失事。相反，在平均場的情境之下，他/她可以只看商品的價格就作決定，令決定的流程變得簡單。在市場裏，價格是由買賣雙方經過互動而得出，因此，它蘊含了市場內所有智能體的狀態及策略的概率分佈。將價格視為平均場，能大大節省決策時間，而它本身亦可算是一種平均場。

MFG理論是由JM Lasry及PL Lions引入數學領域[1、2]，並由PE Caines、M Huang及RP Malhamé在工程界獨立開發[3、4]。在有N人參與的博奕裏，MFG就是當N趨向無限大時博奕的極限。在連續時間裏，典型MFG的組成部分包括描述單一智能體之成本函數動態的Hamilton-Jacobi-Bellman方程式，以及描述所有智能體之聚合分佈發展的Fokker-Planck方程式。到目前為止，MFG已派入多項用途，例如經濟學[5、6]、社交網絡[7、8]、機械學習 [9、10]等。

本文將探討MFG的幾種應用場合，包括機械學習、行人流量、流行病模型、婚姻領域。

1. MFG與機械學習

MFG與機械學習的交集可分為兩個方向，第一是利用機械學習來有效率地解決高維的MFG，見[11、12、13]以及[14]對MFG數值方法的探討。第二是運用MFG理論為機械學習提供解釋及發展所需用到的見解[15]。本文將介紹MFG在聚類（cluster）分析及強化學習上的應用。

1.1 聚類分析

聚類分析是機械學習裏一個經典問題。其中的難題是如何將一組數據點細分為子組，從而令同一組裏的點彼此靠近，而非靠近其他組的點，見[20、21]。在[18、19]裏，MFG模型被開發用於聚類分析，它們分別為K平均演算法[21]以及期望最大化演算法[22]的連續版本。

在[19]裏，作者利用一個限定混合模型（概率密度函數的凸組合）來描述特定的數據集，視每個數據點為其中一個群體的一個智能體；每個群體則相當於混合模型的一個成分。每個群體的每個智能體均會依照自己的動態而移動，並儘量將一項無限時間成本泛函數降至最小；這項泛函數蘊含了智能體所在位置與群體重心（barycenter）之間的距離。作者在以上操作裏得到的是一個多重群體MFG系統。[19]裏其中一項應用就是處理顏色量化的問題，其目的是將特定圖像裏的顏色總數減到固定數量K，從而令得出的圖像盡可能與原來圖像相似。圖1為原來灰度圖以及顏色分佈。圖2顯示K=2、3、5個聚類時的結果，可見當聚類增加時，結果圖像會越來越接近原圖。


圖1﹕黑白圖像（a）及其灰度分佈（b）（來源：[19]）

1.2 多智能體強化學習（multi-agent reinforcement learning，MARL）

現時，強化學習 (reinforcement learning，RL) 是深度學習裏最熱門的研究範疇之一。AlphaGo以及許多著名的強化學習應用個案，大體上均是以單一智能體或少數智能體的群體為基礎。當中的智能體會因應環境而作決定並獲得回報；而MARL則出現在更複雜的情境，例如，在交通網絡裏，司機的行為會受到環境及周圍其他司機的影響，因此，在交通車流裏要顧及大量智能體的行為。最近，MARL在某些應用場合裏已運用成功。


圖2﹕當K = 2、3、5（由上至下）時，透過MFG聚類（左）及相應的混合（右）進行顏色量化（來源：[19]）

例如，OpenAI建立了一個可以攻破Dota2的系統，而DeepMind亦在Quake III遊戲裏破關。 一般而言，由於直接打破納殊均衡點（Nash equalibrium）需要複雜的計算，因此當智能體數量增加時，MARL在處理上會更加吃力，此時MFG正好可用來簡化包含大量智能體的複雜MARL情境。在MFG裏，每個智能體不會逐一回應其他智能體的動作，而是因應其他智能體的分佈而行動；分佈圖集合了其他智能體的動作及狀態。

在[16、17]裏，作者提出結合MFG及MARL裏的不同技巧。[16、17]其中一項實驗的主題是合作-競爭交戰混合博奕，當中，兩方軍隊要在劃分成網格的世界裏對抗；每邊軍隊由不同的RL演算法驅動。在圖3a的設置下，每支軍隊包含64個同質智能體。每支軍隊可以與隊友合作摧毀所有成分，從而獲得更多回報。在示例中，演算法、Q-learning（QL）及有利演員(advantageous actor，AC)均依照其各自的平均場對應物、平均場Q-learning (MF-Q)及平均場有利演員(MF-AC)接受了測試。作者安排了二千輪自我對弈來訓練四個模型。訓練期間，智能體迅速掌握了追擊及合作的擊殺對手技能。圖4為二千輪交叉比較實驗的勝率及總回報結果。我們見到MF-Q大體上比其他演算法出色，顯示平均場MARL演算法有其效用。

(a) 交戰博奕場景

(b) 學習曲線

圖3﹕交戰博奕﹕64比64（來源:[16]）


(a) 平均勝率

(b) 平均總回報

圖4﹕交戰博奕表現比較（來源﹕[16]）。

MFG在學習上尚有其他有意思的應用，本文無法一一列舉。例如，[24]提出了一套通用的MFG框架，可同時執行學習及決策，並就重複廣告競價問題進行實驗。MFG與機械學習兩者相結合目前仍然只處於純綷理論的層面，業界並未廣泛應用，然而在初試啼聲之後，所展示出的潛力令人難以置信。MFG可以為學習任務訂立嚴格的框架，又能利用無限個智能體將大規模的系統簡化。

2. 行人流

行人的流動是由大量智能體的決定所組成。我們通常都要考慮人流裏的擁塞效應，當中每一個智能體的成本取決於眾多智能體的移動速度非線性組合，以及整個群體的分佈，因此，以在非常擠塞的區域為例，智能體情願以慢速移動。PL Lions於2011年在[25]裏引入並研究帶有擁塞效應的MFG，另見[14、26、27、28]的幾項數值模擬。

本文會介紹[14、28]的示例。在[14，28]裏，作者模擬的處境是行人被趕離設有數個長方形障礙物的特定正方形大堂，如圖5所示。


圖5﹕左﹕平面圖（障礙物為紅色）；右﹕密度（當t=0）（來源:[14]）

圖5裏，大堂有紅色障礙物；底下有兩個出口。我們想像封閉的建築物發生恐慌時，行人爭相走向出口；紅色的障礙物是坐椅。當t=0時，所有人都坐在椅上，如圖5右所示。圖6顯示t=1、5、15分鐘時，人群的概率密度。我們見到行人衝向最靠近自己的大堂兩側窄走廊，然後跑向出口，我們又留意到，走廊交匯處的人群密度為最高。在研究[14、28]裏，作者亦留意到擁塞效應，即在密度高的區域速度會變低。


圖6﹕兩個模型在不同日期所計算到的密度，t=1、5、15分鐘（由上至下）（來源:[14]）

3. 流行病模型

2019冠狀病毒病（COVID-19）大流行至今仍然肆虐，影響全球每個角落，關於COVID-19模型的研究論文的大量出版。對於涉及龐大群眾行動的流行病，MFG理論是有效的研究工具；已有幾篇論文為COVID-19提供多個MFG模型，見[29、30、31]。在[29]裏，作者提出一個能夠控制流行病在空間域（spatial domain）上傳播的平均場控制模型。[29]的模型是建基於已為人熟知的SIR模型[32]；S、I、R分別代表健康（susceptible）、感染（infected）、康復（recovered）的人數。這個經典的SIR模型只包含與隨時間變化有關的普通微分系統。由於諸如COVID-19的嚴重流行病會在全球各地傳播，因此在量度疾病的傳播以及人員的感染及移動時必須考慮空間類型的SIR模型。在[29]裏，作者在建立病毒在空間域裏的傳播時，結合了源自SIR模型及MFG模型的構思。這個模型的目標，是將受感染的智能體數量以及群體的移動量降至最低。

[29]其中一項實驗是研究不同康復率的影響。


圖7﹕低康復率時，各個群體於不同時間的變化。第一行代表健康，第二行代表感染，最後一行代表康復。（來源:[29]）

圖7顯示低康復率時t=0至t=1各個群體的概率密度。圖7裏第一行是健康者的變化，第二行是感染者的移動，最後一行是康復群體的變化。隨著時間發展，我們會看到健康群體與感染人群分開；由此可以推斷，當康復率較低時，最佳策略是防止健康群體受感染。

圖8顯示高康復率時各個群體的變化，代表疫苗推出市面時的情況。由圖8可見，隨著時間發展，健康群體並無太大變動；受感染的人變少，康復的人漸多。實驗顯示，當康復率較高時，減少感染人數的最佳策略是專注於令感染者康復，而非調動健康群體。


圖8﹕高康復率時，各個群體於不同時間的變化。第一行代表健康，第二行代表感染，最後一行代表康復。（來源:[29]）

4. MFG在婚姻的應用

在以下最後的一個例子，我們會介紹MFG在婚姻上的有趣應用。在[33]裏，作者使用了隨機微分方程式來模擬夫妻的感情狀態。影響感情狀態的因素有隨機事件、父母、子女、朋友，以及婚姻狀況的社會分佈。數學模型可幫助我們更加了解感情的動態變化，並為夫妻提出合適的干預或治療方案。[33]之前的研究均無考慮無法預測因素、噪訊、隨機事件，以及感情狀況的社會分佈，而平均場模型正是此類問題的理想模型，因為社會、朋友、夫妻的父母可能會聯合影響他們。[33]模型的平均場描述了在社會裏夫妻感情狀況的分佈。

在[33]裏，多位作者所考慮的是一套平均場感情博奕，他們一致認為，朋友、父母、朋友的朋友、社會環境裏的感情狀況均會對夫妻有影響。例如，當某對夫妻有很多朋友均處於較低的感情狀況時，離婚機會就會提高。另外，夫妻感情狀況亦會傳播並影響朋友的朋友，以至更遠，因此，作者將社會裏的社會性質影響及外部影響引入婚姻博奕。

從數字結果而言，[33]的研究顯示，如果努力的成本並非太高而且最初感情狀況並非太低，夫妻努力修復婚姻仍可能有助於維持婚姻。研究又顯示，自己認識太多已離婚的人，可能會適得其反，對婚姻狀況帶來不良影響，即是認識離婚的人越多，自己婚姻就越大可能破裂。然而這樣並不表示，某對夫妻會因為他們的朋友婚姻正在破裂而離婚。婚姻狀況亦取決於夫妻的努力及社會環境。這項研究有助我們從理論上明白與婚姻相關的過程，從而有助我們設計或評估對婚姻的介入措施。

上述的應用層面還遠遠未達完成階段。而從以上的例子我們亦可以見到，當要處理涉及大量智能體的系統時，MFG理論是有效率的模型建立工具。如今「大數據」大行其道，相信MFG與其他領域交集的機會將越來越多。

參考文獻


  1. J. M. Lasry and P. L. Lions, Jeux à champ moyen. I. Le cas stationnaire. C. R. Math. Acad. Sci. Paris, 343(9):619–625, 2006.
  2. J. M. Lasry and P. L. Lions, Jeux à champ moyen. II. Horizon fini et contrôle optimal. C. R. Math. Acad. Sci. Paris, 343(10):679–684, 2006.
  3. M. Huang, P. E. Caines, and R. P. Malhamé. Large-population cost-coupled LQG problems with nonuniform agents: individual-mass behavior and decentralized ϵ-Nash equilibria. IEEE Trans. Automat. Control, 52(9):1560–1571, 2007.
  4. 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(3):221–251, 2006.
  5. Y. Achdou, J. Han, J. M. Lasry, P. L. Lions, and B. Moll. Income and wealth distribution in macroeconomics: A continuous-time approach. Technical report, National Bureau of Economic Research, 2017.
  6. G. Olivier, J. M. Lasry, and P. L. Lions. Mean field games and applications. In Paris-Princeton lectures on mathematical finance 2010, pp. 205-266. Springer, Berlin, Heidelberg, 2011.
  7. B. Dario, H. Tembine, and T. Basar. Opinion dynamics in social networks through mean-field games. SIAM Journal on Control and Optimization 54, no. 6 (2016).
  8. L. Jian, B. Xia, X. Geng, H. Ming, S. Shakkottai, V. Subramanian, and L. Xie. Mean field games in nudge systems for societal networks. ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS) 3, no. 4, 2018.
  9. C. Haoyang, X. Guo, and M. Laurière. Connecting GANs, MFGs, and OT. arXiv e-prints (2020): arXiv-2002.
  10. S. Jayakumar, and A. Mahajan. Reinforcement learning in stationary mean-field games. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 251-259. 2019.
  11. C. René, and M. Laurière. Convergence Analysis of Machine Learning Algorithms for the Numerical Solution of Mean Field Control and Games: II--The Finite Horizon Case. arXiv preprint arXiv:1908.01613 (2019).
  12. C. René, and M. Laurière. Convergence Analysis of Machine Learning Algorithms for the Numerical Solution of Mean Field Control and Games: II--The Finite Horizon Case. arXiv preprint arXiv:1908.01613 (2019).
  13. R. Lars, S. J. Osher, W. Li, L. Nurbekyan, and S. W. Fung. A machine learning framework for solving high-dimensional mean field game and mean field control problems. Proceedings of the National Academy of Sciences 117, no. 17, 2020.
  14. A. Yves, and M. Laurière. Mean field games and applications: Numerical aspects. arXiv preprint arXiv:2003.04444, 2020.
  15. W. E, J. Han, and Q. Li. A mean-field optimal control formulation of deep learning. Research in the Mathematical Sciences 6, no. 1 (2019): 1-41.
  16. Y. Yang, R. Luo, M. Li, M. Zhou, W. Zhang, and J. Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 5571-5580. PMLR, 2018.
  17. M. David, J. Jennings, S. V. Macua, E. Sison, S. Ceppi, and E. M. D. Cote. Coordinating the crowd: Inducing desirable equilibria in non-cooperative systems. arXiv preprint arXiv:1901.10923, 2019.
  18. J. L. Coron. Quelques exemples de jeux à champ moyen, Ph.D. thesis, Universite Paris-Dauphiné, 2018.
  19. A. Laura, S. Cacace, F. Camilli, and R. D. Maio. A mean field games approach to cluster analysis. Applied Mathematics & Optimization (2020): 1-25.
  20. B. Christopher M. Pattern recognition and machine learning. springer, 2006.
  21. S. Amit, M. Prasad, A. Gupta, N. Bharill, O. P. Patel, A. Tiwari, M. J. Er, W. Ding, and C. Lin. A review of clustering techniques and developments. Neurocomputing 267 (2017): 664-681.
  22. B. Leon, and Y. Bengio. Convergence properties of the k-means algorithms. In Advances in neural information processing systems, pp. 585-592. 1995.
  23. J. A. Bilmes. A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models. International Computer Science Institute 4, no. 510 (1998): 126.
  24. X. Guo, A. Hu, R. Xu, and J. Zhang. Learning mean-field games. arXiv preprint arXiv:1901.09585 (2019).
  25. P. L. Lions, Cours du Collège de France, http://www.College-de-france.fr/default/EN/all/equ−der/, 2007-2011.
  26. Y. Achdou. Finite difference methods for mean field games. In Hamilton-Jacobi equations: approximations, numerical analysis and applications, pp. 1-47. Springer, Berlin, Heidelberg, 2013.
  27. Y. Achdou, and J. M. Lasry. Mean field games for modeling crowd motion. In Contributions to partial differential equations and applications, pp. 17-42. Springer, Cham, 2019.
  28. Y. Achdou, and M. Lauriere. On the system of partial differential equations arising in mean field type control. arXiv preprint arXiv:1503.05044 (2015).
  29. W. Lee, S. Liu, H. Tembine, W. Li, and S. Osher. Controlling Propagation of epidemics via mean-field control. SIAM Journal on Applied Mathematics 81, no. 1 (2021): 190-207.
  30. S. Cho. Mean-field game analysis of SIR model with social distancing. arXiv preprint arXiv:2005.06758 (2020).
  31. A. Alexander, R. Carmona, G. Dayanikli, and M. Lauriere. Optimal incentives to mitigate epidemics: a Stackelberg mean field game approach. arXiv preprint arXiv:2011.03105 (2020).
  32. W. O. Kermack, and M. G. Anderson G. A contribution to the mathematical theory of epidemics. Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character115, no. 772 (1927): 700-721.
  33. B. Dario, B. M. Dia, B. Djehiche, H. Tembine, and R. Tempone. Mean-field games for marriage. PloS one 9, no. 5 (2014): e94933.

作者：
香港城市大學數學系助理教授牟宸辰博士

2021年7月