Zi 字媒體

編者按：在，「田忌賽馬」的故事可謂家喻戶曉（故事出自《史記》，講的是戰國時期，齊國大將田忌經常與人賽馬，一次，在孫臏的建議下，用和之前同樣的馬匹，只是通過調換在比賽中的出場順序而反敗為勝）。不過，很多人可能並不知道，這個故事和著名數學家吳文俊院士還有一段鮮為人知的聯繫。吳院士是最早提出「田忌賽馬」屬於博弈論的數學家，除了在拓撲學等方面的突出成就，吳院士也是最早研究博弈論的數學家。而關於他與博弈論的故事，歷史上卻是長期被忽視的。在2010年姜伯駒、李邦河、高小山、李文林主編的為慶祝吳文俊先生九十華誕而出版的《吳文俊與數學》一書中，曹志剛、楊曉光、俞建等三位學者合作撰寫了《吳文俊關於納什均衡穩定性的工作及其影響》一文，詳細地介紹了吳院士在博弈論方面的貢獻，今科學大院經授權刊載（有刪減，小標題為編者新加），緬懷這位博弈論研究的先驅。與博弈論結緣吳文俊院士是最早從事博弈論研究的數學家。1958年大躍進時期，國內的政治氣氛要求數學面嚮應用，包括華羅庚在內的一批頂尖數學家開始從事運籌學的研究。博弈論屬於運籌學的一個分支。由於經典博弈論的一個重要工具是拓撲學中熟知的布勞威爾不動點定理，而吳文俊院士是拓撲學研究的大家，因此他選擇了博弈論作為他從事運籌學研究的切入點。1959年，吳文俊院士發表了第一篇博弈論研究論文《關於博弈理論基本定理的一個註記》（科學記錄（《科學通報》的前身），1959，10）。1960年，他還寫了一篇普及性文章《博弈論雜談：（一）二人博弈》（數學通報，1960，10），深入淺出地介紹了基本定理的證明。在這篇文章中，第一次明確提出「田忌賽馬」的故事屬於博弈論範疇，使得古代思想寶庫中的博弈論思想重放光輝。同年，吳文俊院士等出版了《對策論（博弈論）講義》（人民教育出版社出版，1960），這是最早一本有關博弈論的教材。提出「本質均衡」吳文俊院士在博弈論方面的最大貢獻，是他與他的學生江嘉禾先生合作於1962年對於有限非合作博弈提出了本質均衡(essential equilibrium)的概念，並給出了它的一個重要性質和存在性定理[1]。本質均衡是這樣一個特殊的納什均衡：如果對支付函數作一個足夠小的擾動，那麼擾動后的博弈總存在一個與該均衡距離也足夠小的納什均衡。文章證明了如下性質：給定每個參與者的有限策略集，則所有本質博弈構成的集合是相應空間上的稠密剩餘集（即一列稠密開集的交集）。其中本質博弈是指所有納什均衡都為本質均衡的博弈。因為稠密剩餘集是第二綱的，所以在Baire分類意義上幾乎所有的博弈都是本質博弈。文章還給出了如下存在性定理：一個有限策略的策略型博弈(strategic-form game)，如果其納什均衡的個數有限，則這些納什均衡中至少有一個是本質均衡。本質性很好地刻畫了納什均衡的穩定性或魯棒性(robustness)，所以有的文獻經常把本質性和魯棒性替換使用。吳文俊院士和江嘉禾先生的結果實際上告訴了我們，無論是從Baire分類意義上還是從測度論意義上來說，幾乎所有的博弈都是穩定的。這是數學家在博弈論領域最早的貢獻之一，也是迄今為止數學家在博弈論領域取得的最具國際影響的成就之一。為證明其結果，吳文俊院士及時找到了當時最新的數學工具——福特（M.K. Fort）的本質不動點定理[2]。福特的本質不動點是具有某種穩定性的特殊不動點，其存在性定理今天已成為博弈論穩定性分析的標準工具，而吳文俊院士則是國際上最早意識到福特定理重要性的學者之一。對納什均衡精鍊研究的意義吳文俊和江嘉禾先生結果的意義還遠不局限上述介紹，更重要的是它開創了納什均衡精鍊研究的先河。納什均衡，作為博弈論最核心的概念，其最嚴重的缺點是非唯一性，且經常包含非理性解。如何剔除非理性解對納什均衡進行精鍊以使得它儘可能合理，是上世紀七八十年代博弈論最核心的研究課題。德國博弈論學家澤爾騰(R. Selten)[3]正是憑藉這方面的著名工作獲得了1994年度的諾貝爾經濟學獎。納什均衡精鍊方面的研究工作是針對擴展型博弈(extensive-form game)和策略型博弈分別進行的。前一方面的研究思路是要求參與人在博弈不斷推進的時候始終具有理性，最著名的工作是澤爾騰在1965年提出的子博弈精鍊納什均衡(sub-game perfect equilibrium,[4]）；后一方面的研究思路是要求均衡在各種擾動下保持穩定。納什均衡在參與人策略擾動的時候應保持穩定，這是澤爾騰1975年提出的顫抖手均衡(trembling hand equilibrium,[5])的主要思想。參與人的策略為什麼會出現擾動呢？澤爾騰的解釋是任何人做決策的時候都有至少非常微小的概率犯任何錯誤，這正是該均衡名稱的由來。而納什均衡在支付函數擾動時應保持穩定，則是吳文俊院士1962文章中率先開闢的思想。同樣是均衡在擾動下應保持穩定的思想，吳文俊院士要早於澤爾騰13年正式提出。博弈論研究成果逐漸被關注吳文俊院士在本質均衡方面的工作是關於納什均衡精鍊研究方面最早的結果，但是由於歷史的原因，改革開放以前的學術界與世界學術界處於一種隔絕的狀態，一直到上個世紀八十年代吳文俊院士的這一結果才逐步得到了國際博弈論學界的關注，並帶動著相關研究的發展：1、1981年，荷蘭學者琴生(M.J.M. Jansen)針對雙矩陣博弈，即只有兩個參與者的策略型博弈，避開了福特定理，只利用基本的博弈分析重新證明了吳文俊院士的結果。這也是國際上首次對吳文俊院士結果的正式關注[6]；2、1984年，前蘇聯博弈論研究的奠基人沃羅比約夫（N. N. Vorobev）在其專著《博弈論基礎：非合作博弈》中多次引用了吳文俊院士的結果，並在該書第二章對其1962年的結果作了如此評價，「有限非合作博弈的穩定性，即均衡解對博弈的連續依賴性，很顯然首先是由吳文俊和江嘉禾在文章中研究的」 。[7]；3、1985年，日本學者小島(M. Kojima)等提出了強穩定均衡的概念（strongly stable equilibrium），對本質均衡進行了進一步的精鍊[8]；4、1986年，哈佛大學商學院教授科爾伯格（E. Kohlberg）等在著名論文《關於均衡的策略穩定性》中引用了吳先生的工作，指出本質均衡只對策略型博弈有意義[9]；5、1987年，荷蘭學者范德蒙在研究納什均衡精鍊的經典專著《納什均衡的穩定性與精鍊》中[10]，對本質均衡給予了高度評價，並在該書第二章第四節對其進行了專門介紹。由於此書第一章為概述，第二章第一節為基礎知識介紹，吳文俊院士的工作被放在了僅次于澤爾騰的顫抖手均衡和邁爾森(R.Myerson)[11]的恰當均衡（proper equilibrium）的重要位置。又由於恰當均衡是顫抖手均衡的進一步精鍊，與顫抖手均衡的的研究思路是相同的，更加可以看出作者對吳文俊院士工作的重視。范德蒙還在此章第六節中利用正則均衡（regular equilibrium）的性質進一步加強了吳文俊先生的結果；6、1991年，弗登伯格(D.Fudenberg)[12]和梯若爾(J. M. Tirole)[13]合著的世界流行的教科書《博弈論》也在該書第十二章對本質均衡及其理論淵源——福特定理進行了專門介紹，也指出了本質均衡只對策略型博弈有意義[14]；7、上個世紀九十年代以來，博弈論學者俞建教授對吳文俊院士的本質均衡結果進行了一系列推廣，不僅將本質均衡推廣到線性賦范空間以及線性賦范空間上的廣義博弈、多目標博弈和連續博弈，而且進一步研究了平衡點集本質連通區的存在性等問題[15]；8、2009年，美國學者卡博奈爾-尼科拉(O. Carbonell-Nicolau)在其即將發表於著名的Journal of Economic Theory上的文章中在俞建教授結果的基礎上對吳文俊院士的結果進行了進一步的推廣[16]；……佳話永傳雖然經過二十多年的苦苦探索，博弈論學者並沒有找到一個完美的均衡精鍊概念，各種均衡精鍊概念層出不窮，然而在令人眼花繚亂的均衡精鍊概念中，本質均衡是除子博弈精鍊納什均衡和顫抖手均衡以外屈指可數的幾個存活下來的概念之一。更為難能可貴的是，在近半個世紀后的今天，吳文俊院士在本質均衡方面的主要思想及結果，依然被包括馬斯金(E. Maskin)、梯若爾[17、18]，威布爾[19、20]等在內的世界一流的博弈論學者在最頂尖的刊物上持續引用，而且近幾年的引用頻次越來越高。多少有些令我們感到慨嘆的是，吳文俊院士當時工作的出發點更多的是純數學，文章主要是穩定性研究而沒有意識到納什均衡精鍊研究的必要性以及本質均衡與納什均衡精鍊的密切聯繫。又由於吳文俊院士的研究興趣很快轉至他處而沒能將此工作持續下去（江嘉禾先生有後續的幾篇工作，但也都是從純數學角度研究的），更沒有從事擴展型博弈納什均衡精鍊的研究——這是比策略型博弈納什均衡精鍊重要得多的研究方向，其代表性成果子博弈精鍊納什均衡在擴展型博弈中已完全取代了納什均衡的位置，滲透到其研究的各個角落，並被寫入任何一本博弈論教材。由於與國際博弈論學界溝通的不足，吳文俊院士的成果直到1981年才在國際上被首次注意，八十年代末才被更多的主流學者所知曉，而此時納什均衡精鍊方面的研究的高潮已經過去。由於這種種的原因，吳文俊院士的研究在博弈論發展的黃金時期並沒有起到按一般邏輯起應該起到的引領潮流的作用，其工作的影響力不僅無法與澤爾騰、范德蒙等人的相關工作相比肩，甚至在納什均衡精鍊方面的研究塵埃落定的今天也並沒有得到完全公正的評價。一個代表性的例子是，在新帕爾格雷夫大辭典「納什均衡精鍊」詞條中，儘管支付函數擾動的思想被高度認可並做了大篇幅的介紹，吳文俊院士的名字及文章都未被提及[21]。幸運的是，吳文俊院士的結果在今天依然充滿了令人驚異的活力，2007年至今一直被頻繁引用，顯示了一個數學思想生命力的頑強。而吳文俊院士從事博弈論研究曲曲折折的故事，也必將成為數學界和博弈論學界的一段佳話，給我們以永遠的啟迪。註釋：[1] W.T. Wu and J.H. Jiang: Essential equilibrium points of n-person non-cooperative games, Scientia Sinica, 11, 1962, 1307-1322.[2] M.K. Fort, Jr.: Essential and nonessential fixed points. American Journal of Math, 72, 1950, 315-322.[3] 澤爾騰（Reinhard Selten），1930——，德國波恩大學（Bonn）教授，著名的博弈論學家，1994年度諾貝爾經濟學獎得主。澤爾騰教授不僅在納什均衡精鍊領域有舉世公認的成就，還是實驗博弈理論的開拓者之一，在有限理性領域也有深刻的研究。南開大學的澤爾騰實驗室就是以澤爾騰教授命名的。澤爾騰教授還以喜歡將文章發表到無需同行評議的非正規學術刊物從而避免他認為對其文章不應有的任何修改而聞名博弈論學界。[4] R. Selten: Spieltheorethische Behandlung eines Oligopolmodells mit Nachfragetra gheit, Z. Ges. Staats. 12 , 1965, 301-324.[5] R. Selten: Reexamination of the perfectness concept for equilibrium points in extensive games, International Journal of Game Theory, 4(1) , 1975, 25-55.[6] M.J.M. Jansen: Regularity and stability of equilibrium points of bimatrix games. Mathematics of Operations Research, 6(4), 1981, 530-550. [7] N. N. Vorobev，Foundations of Game Theory：noncooperative games，Birkhauser, 1994 (翻譯自1984年俄文版). 沃羅比約夫1960年曾來講學，並受到周恩來總理的接見。吳文俊院士等編寫的《對策論（博弈論）講義》一書的序言中曾對沃羅比約夫來的講學表示感謝。[8] M. Kojima, A. Okada & S. Shindoh: Strongly stable equilibrium points of n-person non-cooperative games. Mathematics of Operations Research, 10(4), 1985, 650-663.[9] E. Kohlberg, J.F. Mertens : On the strategic stability of equilibria. Econometrica: Journal of the Econometric Society, 54(5), 1986, 1003-1037。這是博弈論著名論文之一，google scholar顯示已被引用達851次。[10] E. van Damme: Stability and Perfection of Nash Equilibria, Springer-Verlag, 1987.[11] 邁爾森（Roger Myerson）， 1951——，美國芝加哥大學教授，當今最活躍最有影響力的博弈論學家和經濟學家之一，因其在機制設計方面的著名工作而獲得了2007年度的諾貝爾經濟學獎。[12] 弗登伯格（Drew Fudenberg），1957——，美國哈佛大學教授，著名的博弈論學家，美國科學與藝術院院士。[13] 梯若爾（Jean Marcel Tirole），1953——，法國圖盧茲大學（Toulouse）教授，美國科學與藝術院外籍院士，曾任國際經濟學會主席，在博弈論、合同理論、產業組織學、認知心理學、政治經濟學及貨幣銀行學等多個領域都有建樹，並有多本風靡全球的教材，是當今少有的經濟學通才及最有影響力的經濟學家之一。[14] D.Fudenberg & J. Tirole: Game Theory. MIT Press, 1991. 有中譯本：黃濤等譯，《博弈論》，人民大學出版社，2003.[15] 俞建，貴州大學教授。他在本質博弈方面的系列性工作，絕大多數都反應在他的專著《博弈論與非線性分析》（科學出版社，2008）。[16] O. Carbonell-Nicolau: Essential equilibria in normal-form games, Journal of Economic Theory, 2009 (available online).[17] 馬斯金（Eric Maskin），1950——，美國普林斯頓大學高等研究中心教授，當今最德高望重的博弈論學家和經濟學家之一，以其機制設計方面的理論而獲得了2007年度的諾貝爾經濟學獎。[18] E.Maskin & J. Tirole: Markov Perfect Equilibrium: I. Observable Actions. Journal of Economic Theory, 100(2), 2001, 191-219.[19] 威布爾（Jörgen Weibull），1948——，瑞典斯德哥爾摩經濟學院教授，著名的演化博弈論大師，瑞典皇家科學院院士，曾任諾貝爾經濟學獎委員會主席。[20] J. Weibull: Robust set-valued solutions in games. 2009 (available online).[21] S. Govindan & R. Wilson: Refinements of Nash equilibrium, The New Palgrave Dictionary of Economics, 2nd Edition.大院熱門文章top榜即刻關注