紀念 | 「博弈論里的上帝」去了天堂

封面圖：勞埃德·沙普利（Lloyd Shapley，1980年）

編者按：

這是作者為本周辭世的現代合作博弈論奠基人勞埃德·沙普利撰寫的紀念文章。因提出「蓋爾-沙普利」演算法和穩定匹配理論，沙普利獲得了2012年經濟學獎。他和去年相繼離世的哈羅德·庫恩與約翰·納什同為普林斯頓大學1950屆博士畢業生，被稱為「普林斯頓博弈論學派三巨星」。他自稱是從來沒有修過一門經濟學課程的數學家。作者認為，與其不如說他是一位運籌學家，或者說經濟學中的工程師。沙普利主要藉助其運籌學或工程師的思維方式獲得了舉世矚目的成就。作者從運籌學與數學、博弈論和經濟學關係的角度，梳理沙普利的主要學術貢獻。

文 | 曹志剛（中國科學院數學與系統科學研究院）

●　●　●

繼哈羅德·庫恩（Harold W. Kuhn）和約翰·納什（John Nash）於2014年相繼離世後，又一位博弈論大師駕鶴西去。現代合作博弈論的奠基人和市場設計理論的開拓者勞埃德·沙普利於2016年3月12日在睡夢中去世，享年93歲。至此，普林斯頓博弈論學派1950屆博士畢業生中的三位巨星悉數隕落。

加州大學洛杉磯分校教授沙普利由於在「匹配理論」(Matching Theory)方面的貢獻獲得2012年的諾貝爾經濟學獎。沙普利的主要貢獻是1962年和數學家蓋爾在共同提出了「蓋爾-沙普利演算法」 （the Gale–Shapley algorithm），提出並發展了穩定匹配理論，其研究重點是如何使雙方不願打破當前的匹配狀態，以保持匹配的穩定性。

在這樣一個特殊的時刻寫一篇小文章紀念這位大師有很多選擇。比如可以全面回顧一下他的學術貢獻，這對我來說比較吃力，但在前人系統性總結的基礎上大體上還能勝任；或者可以八卦一下他的生平和逸聞趣事——沙普利也是一個有故事的人，儘管不像納什那樣傳奇；也可以講講為什麼獲諾獎的不是沙普利值（Shapley Value），而是在很多人看來不起眼的一個小模型(Toy Model )。沙普利的長期合作者Shubik教授說，他能舉出沙普利十項比穩定匹配(Stable Matching)更重要的工作,我當然不能完全贊同這種觀點; 還可以講講合作博弈論與非合作博弈論相比有哪些優勢以及其可能的復興方向（劣勢很明顯且容易說清楚）；甚至可以從女權主義的視角來科普一下和穩定匹配相關的「求婚演算法」（編者註：蓋爾和沙普利1962年在《高校招生和婚姻穩定性》一文中利用求婚的模型，提出了蓋爾-沙普利演算法），整天拒絕渣男的女王們其實有天然的系統性劣勢，真正的贏家是屢敗屢戰不斷降低要求的求婚者。但是思來想去，我還是藉此機會來談一談我對運籌學以及它與數學、博弈論和經濟學關係的一些粗淺認識。

科學家通常有著職業性的傲慢與偏見，眾多的學科分支中存在著不成文的「鄙視鏈」。大致來說，數學和經濟學分別位於自然科學和社會科學鄙視鏈的最頂端。數學家和經濟學家都驕傲得很。有趣的是，他們之間則經常相互鄙視。經濟學家如果說哪位同行是一位數學家，這通常是非常負面的評價。數學家則會說，「用上一點簡單的微積分，就能搞出一場所謂邊際革命，也太小兒科了吧？數學定理一萬年也不會錯，外星人那裡的數學估計跟我們也沒差別。可是除了比較優勢理論外，經濟學中還有其它既特別靠譜又有一定的普適性和深度的理論嗎？比如說需求定律那也好意思叫一個定律？」這當然都是玩笑話。學科歧視遠沒有種族歧視那麼「政治不正確」，需要辯證地來看。在對其他學科做出可能不公正評價的同時也不斷加深了對本學科的認識。這個問題按下不表。

儘管獲得諾貝爾經濟學獎是眾望所歸，沙普利從不把自己看成是經濟學家——他一直宣稱自己是數學家。當然，沒有經濟學家因此而鄙視他。這在一流的博弈論和經濟學家中比較少見。數學對於經濟學的重要性無須贅述。但他們畢竟是兩門不同的學科，有著差別巨大的研究範式和評判標準。儘管沙普利開創的隨機博弈近些年受到越來越多的數學家關注，Shapley-KKM引理和 Shapley-Folkman引理等也都是很重要的數學貢獻，毫無疑問他在數學領域的影響遠沒有在經濟學領域大。

但與其說沙普利是一位數學家，不如說他是一位運籌學家，或者說經濟學中的工程師。沙普利主要藉助其運籌學或工程師的思維方式獲得了舉世矚目的成就。我提醒讀者工程師這個稱呼對沙普利絕對沒有任何不敬。和沙普利分享2012年諾貝爾經濟學獎的埃爾文·羅斯（Alvin Roth） 在接受採訪的時候，就自稱是經濟學中的工程師，其成就得益於其運籌學背景。當然，無需多言，他們都不是普通的工程師。

運籌學或管理學背景的讀者可能會認為我小題大做，博弈論不就是運籌學的一個分支嗎？但是經濟學背景的讀者不見得了解我下面要講的內容，甚至最終不見得同意我的觀點。

博弈論在經濟學中找到了最廣泛而深入的成功應用，目前仍不斷滲透到政治學等幾乎所有的社會科學和生物學等自然科學。隨著其不斷發展壯大，博弈論有了一定的獨立性。但是它還沒有壯大到一級學科的程度（比如沒有博弈論本科專業，正如沒有運籌學本科專業），必須依附於其它學科才能生存。目前最一流的博弈論學家多數都是而且承認自己是經濟學家，但是或承認自己是數學家或運籌學家的一流博弈論學家相對較少，這其中包含沙普利。沙普利認為自己是數學家，但我覺得他更合適或更確切的身份是運籌學家。

運籌學（Operations Research）在台灣又被翻譯成「作業研究」，是在二戰中跟控制論、博弈論和計算機等共同發展起來的一門應用型基礎學科。台灣的這個直譯，跟很多其它學術名詞的翻譯一樣，儘管遠沒有「運籌學」那麼高大上，卻道出了這門學科的核心：跟數學和理論經濟學相比，運籌學都是比較形而下的。

總體而言，運籌學不像數學那麼抽象，不致力於研究抽象結構而是解決相對具體的問題；其思想性也不像經濟學那麼強，運籌學研究中很少見經濟學中那種天馬行空的模型。

按照我的理解，運籌學中的優化理論位於經濟學的上游，而它們都是數學的下遊學科。運籌學中偏重於建模的部分位於經濟學的下游，這部分運籌學家就是經濟學家中的工程師。比如經濟學家更多地對工業組織感興趣，運籌學家則更多地對工業工程感興趣，當然這種區分並不絕對，而博弈論則遊走於運籌學和經濟學等多門學科。

從歷史上看，運籌學和博弈論是共同成長起來的兩門學科，他們最早期的研究者高度重合；從學科關係上來講，博弈論是決策科學的一個分支，而決策科學同時是運籌學和經濟學的重要內容。

歷史上博弈論與數學關係也曾非常密切。看看Luce & Raiffa或者Owen等比較早期的博弈論教科書，引用的參考文獻大量來自Annals等一流的純數學期刊。但是再看看上世紀90年代初期Myerson等那幾本目前認為最重要的教科書，發表於純數學期刊的那些結果能活下來的已經寥寥可數。科學研究的殘酷性令人不勝唏噓，甚至連馮諾依曼這種量級的人物也只有極大極小定理等極少數成果能活下來。這說明按照純數學的品味去研究博弈論，至少目前來看，是沒有前途的。雖然沙普利自稱數學家，我下面將稍微展開說明，他的研究風格恰恰不是純數學品味而是運籌學品味。主流博弈論學家目前最認可的刊物，多數來自經濟學，少數來自運籌學、生物學等。博弈論與純數學早已漸行漸遠。

我對沙普利幾個著名的工作進行了簡單分析，說明這些成果的確有鮮明的運籌學特色，跟運籌學精神以及運籌學其他分支密不可分。運籌學家可以理直氣壯地說，曾獲得過運籌學界最高獎項馮諾依曼獎的沙普利是我們的人。

（1）獲得諾獎的穩定匹配（Stable Matching）模型。

對這項工作的歷史通常的演繹如下：1962年蓋爾首先想到了這個模型，苦苦思索沒有答案，於是給他的好朋友沙普利寫信求助。沙普利利用一個下午的時間解決了這個問題，隨後投稿。該結果經過兩輪拒稿，最終發表於《美國數學月報》。半個世紀以後這篇「靈機一動」的小文章幫助沙普利獲得了諾獎。

我想特別說明的是，沙普利能夠一個下午就解決這個問題，並不是簡單的靈機一動，而是與他長期思考相關的問題密不可分。沙普利早在1955年就系統性地思考過這種雙邊結構的博弈。我們現在熟知的手套博弈和指派博弈（1971年正式發表於IJGT的創刊號上），核心思想在1955年蘭德公司的工作論文中就有了。而指派博弈是穩定匹配問題的一個姊妹模型，很多性質都是平行的。指派博弈來源於指派問題，後者是運籌學和組合優化中的一個經典模型。

當然，沙普利研究穩定匹配問題的時候不見得能意識到這篇論文將來會有如此大的影響。這與羅斯等將這套理論發揚光大並開發出很多軟體系統的實際工作密不可分。可以說沙普利和羅斯成全了彼此。2008年金融危機後公眾對經濟學普遍質疑。在這樣的背景下，諾獎委員會把2012年的諾貝爾經濟學獎頒給了沙普利和羅斯這樣一項工程性的成果是比較容易理解的——經濟學家也可以從事毫無爭議實實在在改變世界的工作。

我認為跟博弈論領域其它的一流工作相比，沙普利和羅斯的工作在思想上或技術上的確沒有特別高深的東西。但就是有用——這就是頂級的運籌學成果。值得指出的是，穩定匹配的後續工作，除了經濟學家在大批跟進以外，也始終是計算機學家和運籌學家的研究熱點。目前依然如此。

（2）凸博弈。

這是合作博弈論中的一類重要博弈，有非常漂亮的性質，並且在各種背景的問題中廣泛存在。儘管這個想法現在來看非常自然，沙普利能夠設計出這樣一類博弈，與他精深的凸分析造詣應該是分不開的。事實上，他在凸分析方面有重要貢獻。從論文中可以看出，沙普利對當時很前沿的組合優化專家Edmonds的工作非常熟悉。

事實上，合作博弈論，尤其是凸博弈及後續研究，是由博弈論專家和組合優化專家共同發展起來的。遺憾的是，儘管沙普利對雙方早期的工作都非常熟悉，後續的研究者很快分道揚鑣了，長期相互不引用。沙普利也很早就注意到了Choquet積分與凸博弈的密切關係，後續的多數研究者卻只認可Lovasz extension。

令人讚歎的是，在Topkis、Milgrom、Roberts和Vives等人的努力下，非合作博弈論里也發展出來一套類似的優美理論——超模博弈。超模博弈和位勢博弈是目前最廣泛的可以保證純策略納什均衡存在的兩類博弈。沙普利對這兩類博弈都有開創性貢獻。這也是一個經濟學家和運籌學家共同作出的重要成果（沙普利既是經濟學家又是運籌學家，Topkis是運籌學家，Milgrom、Roberts和Vives都是經濟學家）。

更令人讚歎的是，組合優化領域裡，在Edmonds、Lovasz、Fujishige和Murota等眾多一流科學家的帶領下，已經建立起了從擬陣到次模分析到離散凸分析的一整套優美理論。這套理論不僅可以把合作博弈論里的凸博弈與非合作博弈論里的超模博弈統一起來，同時處理很多連續問題和離散問題，還有望類似於凸分析跟連續優化的關係，為組合優化建立一個統一框架。

（3）沙普利值和Shapley-Shubik指數。

沙普利值大概是沙普利最著名的工作，但並沒有因此獲諾獎。我個人認為這個概念的重要性不僅無法跟納什均衡（Nash Equilibrium）相提並論，大概也比不上Core）。沙普利和Shubik將沙普利值應用於政治科學中票數的權力度量問題，創立了著名的Shapley-Shubik指數，成為該領域最重要的幾個指標之一。當然，這個指標，跟任何其它指標一樣，遠不是完美的，這裡不展開介紹。做評估和度量，是運籌學和決策科學裡的重要課題，也是經濟學中相對比較工程性的問題。

（4）位勢博弈。

這是沙普利和Monderer合作的重要成果。前面已經介紹，位勢函數法是博弈論里證明純策略納什均衡存在性最常用的兩種方法之一。這在博弈論里也屬於比較技術性而非思想性問題。值得一提的是，位勢函數的思想主要來自物理學。即便在博弈論領域，Rosenthal和Slade也分別早於Monderer和沙普利提出了這種思想（後者對前兩者有引用）。但是很多研究者都「方便起見」將此簡單歸功於後者。這是學術領域裡典型的（有失公平但不見得不合理的）馬太效應。

（5）隨機博弈。

數學上來說，這是馬氏決策的推廣。後者是運籌學中的重要內容。所知有限，不去詳述。

（6）演算法博弈論。

學術界最近十多年才開始對博弈論里的演算法問題真正感興趣並發展出演算法博弈論這個分支。這是計算機科學對經濟學的一次入侵。儘管該方向正勢不可擋地被經濟學主流接納，目前依然有一些經濟學家對它的研究範式有「偏見」。沙普利不僅在1962年就研究穩定匹配中的演算法問題，還很早就對納什均衡求解的Lemke-Howson演算法感興趣。前面介紹的凸博弈研究中，沙普利也很注意演算法問題；而位勢函數不僅可以用來證明納什均衡的存在，還可以用很簡單的演算法來找到一個（特殊）均衡。沙普利毫無疑問是演算法博弈論的先驅。

從前面的討論可以看出，沙普利始終對運籌學的前沿非常熟悉，他的博弈論研究帶有濃厚的運籌學色彩。他自己也研究過運籌學裡的一些非博弈論課題，比如網路流問題。始終關注演算法問題，是沙普利跟很多博弈論學家和經濟學家所不同的，也是我們稱其為運籌學家的強有力證據。這與運籌學和博弈論共同發源於以馮諾依曼為首的普林斯頓學派是密不可分的。比如馮諾依曼就是線性規劃對偶理論的發明者之一，Kuhn就是指派問題中著名匈牙利演算法的命名者，沙普利對這些怎麼能不熟悉呢！

沙普利對博弈論的貢獻是全面的。跟同樣量級的博弈論學家和經濟學家相比，沙普利的學術風格具有濃厚的運籌學家的務實色彩。對比於Aumann等對知識和理性的充滿哲學性的探討，對比於目前仍然在研究的前向歸納與後向歸納的關係，沙普利的工作或許顯得沒有那麼深刻那麼迷人。但是事實證明，將工程師的精神發揮到極致依然可以做出超一流的工作。

有人告訴我說，天堂里沒有飢餓沒有寒冷沒有痛苦，所有的人每天都傻傻地快樂著。我完全無法想像那種生活狀態。天堂里的人還需要做選擇和決策嗎？天堂里的男女還需要做匹配嗎？天堂里還投票嗎？天堂里需要博弈論和運籌學專家嗎？Aumann眼中博弈論里的上帝去了天堂，我不知道沙普利到了那裡是否真的能成為上帝，只願他能找到永恆的安寧和快樂。

（責任編輯 徐可）

知識分子，為更好的智趣生活。

關注請加微信號:the-intellectual或長按下方二維碼。投稿、授權事宜請聯繫：zizaifenxiang@163.com。

推薦閱讀：