逝者 | “博弈論里的上帝”去了天堂
勞埃德·沙普利（Lloyd Shapley，1980年）
編者按：
這是作者為本周辭世的現(xiàn)代合作博弈論奠基人勞埃德·沙普利撰寫的紀(jì)念文章。因提出“蓋爾-沙普利”算法和穩(wěn)定匹配理論，沙普利獲得了2012年經(jīng)濟(jì)學(xué)獎(jiǎng)。他和去年相繼離世的哈羅德·庫(kù)恩與約翰·納什同為普林斯頓大學(xué)1950屆博士畢業(yè)生，被稱為“普林斯頓博弈論學(xué)派三巨星”。他自稱是從來(lái)沒(méi)有修過(guò)一門經(jīng)濟(jì)學(xué)課程的數(shù)學(xué)家。作者認(rèn)為，與其不如說(shuō)他是一位運(yùn)籌學(xué)家，或者說(shuō)經(jīng)濟(jì)學(xué)中的工程師。沙普利主要借助其運(yùn)籌學(xué)或工程師的思維方式獲得了舉世矚目的成就。作者從運(yùn)籌學(xué)與數(shù)學(xué)、博弈論和經(jīng)濟(jì)學(xué)關(guān)系的角度，梳理沙普利的主要學(xué)術(shù)貢獻(xiàn)。
文 | 曹志剛（中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院）
● ● ●
繼哈羅德·庫(kù)恩（Harold W. Kuhn）和約翰·納什（John Nash）于2014年相繼離世后，又一位博弈論大師駕鶴西去。現(xiàn)代合作博弈論的奠基人和市場(chǎng)設(shè)計(jì)理論的開拓者勞埃德·沙普利于2016年3月12日在睡夢(mèng)中去世，享年93歲。至此，普林斯頓博弈論學(xué)派1950屆博士畢業(yè)生中的三位巨星悉數(shù)隕落。
加州大學(xué)洛杉磯分校教授沙普利由于在“匹配理論”(Matching Theory)方面的貢獻(xiàn)獲得2012年的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。沙普利的主要貢獻(xiàn)是1962年和數(shù)學(xué)家蓋爾在共同提出了“蓋爾-沙普利算法” （the Gale–Shapley algorithm），提出并發(fā)展了穩(wěn)定匹配理論，其研究重點(diǎn)是如何使雙方不愿打破當(dāng)前的匹配狀態(tài)，以保持匹配的穩(wěn)定性。
在這樣一個(gè)特殊的時(shí)刻寫一篇小文章紀(jì)念這位大師有很多選擇。比如可以全面回顧一下他的學(xué)術(shù)貢獻(xiàn)，這對(duì)我來(lái)說(shuō)比較吃力，但在前人系統(tǒng)性總結(jié)的基礎(chǔ)上大體上還能勝任；或者可以八卦一下他的生平和逸聞趣事——沙普利也是一個(gè)有故事的人，盡管不像納什那樣傳奇；也可以講講為什么獲諾獎(jiǎng)的不是沙普利值（Shapley Value），而是在很多人看來(lái)不起眼的一個(gè)小模型(Toy Model )。沙普利的長(zhǎng)期合作者Shubik教授說(shuō)，他能舉出沙普利十項(xiàng)比穩(wěn)定匹配(Stable Matching)更重要的工作,我當(dāng)然不能完全贊同這種觀點(diǎn); 還可以講講合作博弈論與非合作博弈論相比有哪些優(yōu)勢(shì)以及其可能的復(fù)興方向（劣勢(shì)很明顯且容易說(shuō)清楚）；甚至可以從女權(quán)主義的視角來(lái)科普一下和穩(wěn)定匹配相關(guān)的“求婚算法”（編者注：蓋爾和沙普利1962年在《高校招生和婚姻穩(wěn)定性》一文中利用求婚的模型，提出了蓋爾-沙普利算法），整天拒絕渣男的女王們其實(shí)有天然的系統(tǒng)性劣勢(shì)，真正的贏家是屢敗屢戰(zhàn)不斷降低要求的求婚者。但是思來(lái)想去，我還是借此機(jī)會(huì)來(lái)談一談我對(duì)運(yùn)籌學(xué)以及它與數(shù)學(xué)、博弈論和經(jīng)濟(jì)學(xué)關(guān)系的一些粗淺認(rèn)識(shí)。
科學(xué)家通常有著職業(yè)性的傲慢與偏見(jiàn)，眾多的學(xué)科分支中存在著不成文的“鄙視鏈”。大致來(lái)說(shuō)，數(shù)學(xué)和經(jīng)濟(jì)學(xué)分別位于自然科學(xué)和社會(huì)科學(xué)鄙視鏈的最頂端。數(shù)學(xué)家和經(jīng)濟(jì)學(xué)家都驕傲得很。有趣的是，他們之間則經(jīng)常相互鄙視。經(jīng)濟(jì)學(xué)家如果說(shuō)哪位同行是一位數(shù)學(xué)家，這通常是非常負(fù)面的評(píng)價(jià)。數(shù)學(xué)家則會(huì)說(shuō)，“用上一點(diǎn)簡(jiǎn)單的微積分，就能搞出一場(chǎng)所謂邊際革命，也太小兒科了吧？數(shù)學(xué)定理一萬(wàn)年也不會(huì)錯(cuò)，外星人那里的數(shù)學(xué)估計(jì)跟我們也沒(méi)差別?？墒浅吮容^優(yōu)勢(shì)理論外，經(jīng)濟(jì)學(xué)中還有其它既特別靠譜又有一定的普適性和深度的理論嗎？比如說(shuō)需求定律那也好意思叫一個(gè)定律？”這當(dāng)然都是玩笑話。學(xué)科歧視遠(yuǎn)沒(méi)有種族歧視那么“政治不正確”，需要辯證地來(lái)看。在對(duì)其他學(xué)科做出可能不公正評(píng)價(jià)的同時(shí)也不斷加深了對(duì)本學(xué)科的認(rèn)識(shí)。這個(gè)問(wèn)題按下不表。
盡管獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)是眾望所歸，沙普利從不把自己看成是經(jīng)濟(jì)學(xué)家——他一直宣稱自己是數(shù)學(xué)家。當(dāng)然，沒(méi)有經(jīng)濟(jì)學(xué)家因此而鄙視他。這在一流的博弈論和經(jīng)濟(jì)學(xué)家中比較少見(jiàn)。數(shù)學(xué)對(duì)于經(jīng)濟(jì)學(xué)的重要性無(wú)須贅述。但他們畢竟是兩門不同的學(xué)科，有著差別巨大的研究范式和評(píng)判標(biāo)準(zhǔn)。盡管沙普利開創(chuàng)的隨機(jī)博弈近些年受到越來(lái)越多的數(shù)學(xué)家關(guān)注，Shapley-KKM引理和 Shapley-Folkman引理等也都是很重要的數(shù)學(xué)貢獻(xiàn)，毫無(wú)疑問(wèn)他在數(shù)學(xué)領(lǐng)域的影響遠(yuǎn)沒(méi)有在經(jīng)濟(jì)學(xué)領(lǐng)域大。
但與其說(shuō)沙普利是一位數(shù)學(xué)家，不如說(shuō)他是一位運(yùn)籌學(xué)家，或者說(shuō)經(jīng)濟(jì)學(xué)中的工程師。沙普利主要借助其運(yùn)籌學(xué)或工程師的思維方式獲得了舉世矚目的成就。我提醒讀者工程師這個(gè)稱呼對(duì)沙普利絕對(duì)沒(méi)有任何不敬。和沙普利分享2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)的埃爾文·羅斯（Alvin Roth） 在接受采訪的時(shí)候，就自稱是經(jīng)濟(jì)學(xué)中的工程師，其成就得益于其運(yùn)籌學(xué)背景。當(dāng)然，無(wú)需多言，他們都不是普通的工程師。
運(yùn)籌學(xué)或管理學(xué)背景的讀者可能會(huì)認(rèn)為我小題大做，博弈論不就是運(yùn)籌學(xué)的一個(gè)分支嗎？但是經(jīng)濟(jì)學(xué)背景的讀者不見(jiàn)得了解我下面要講的內(nèi)容，甚至最終不見(jiàn)得同意我的觀點(diǎn)。
博弈論在經(jīng)濟(jì)學(xué)中找到了最廣泛而深入的成功應(yīng)用，目前仍不斷滲透到政治學(xué)等幾乎所有的社會(huì)科學(xué)和生物學(xué)等自然科學(xué)。隨著其不斷發(fā)展壯大，博弈論有了一定的獨(dú)立性。但是它還沒(méi)有壯大到一級(jí)學(xué)科的程度（比如沒(méi)有博弈論本科專業(yè)，正如沒(méi)有運(yùn)籌學(xué)本科專業(yè)），必須依附于其它學(xué)科才能生存。目前最一流的博弈論學(xué)家多數(shù)都是而且承認(rèn)自己是經(jīng)濟(jì)學(xué)家，但是或承認(rèn)自己是數(shù)學(xué)家或運(yùn)籌學(xué)家的一流博弈論學(xué)家相對(duì)較少，這其中包含沙普利。沙普利認(rèn)為自己是數(shù)學(xué)家，但我覺(jué)得他更合適或更確切的身份是運(yùn)籌學(xué)家。
運(yùn)籌學(xué)（Operations Research）在臺(tái)灣又被翻譯成“作業(yè)研究”，是在二戰(zhàn)中跟控制論、博弈論和計(jì)算機(jī)等共同發(fā)展起來(lái)的一門應(yīng)用型基礎(chǔ)學(xué)科。臺(tái)灣的這個(gè)直譯，跟很多其它學(xué)術(shù)名詞的翻譯一樣，盡管遠(yuǎn)沒(méi)有“運(yùn)籌學(xué)”那么高大上，卻道出了這門學(xué)科的核心：跟數(shù)學(xué)和理論經(jīng)濟(jì)學(xué)相比，運(yùn)籌學(xué)都是比較形而下的。
總體而言，運(yùn)籌學(xué)不像數(shù)學(xué)那么抽象，不致力于研究抽象結(jié)構(gòu)而是解決相對(duì)具體的問(wèn)題；其思想性也不像經(jīng)濟(jì)學(xué)那么強(qiáng)，運(yùn)籌學(xué)研究中很少見(jiàn)經(jīng)濟(jì)學(xué)中那種天馬行空的模型。
按照我的理解，運(yùn)籌學(xué)中的優(yōu)化理論位于經(jīng)濟(jì)學(xué)的上游，而它們都是數(shù)學(xué)的下游學(xué)科。運(yùn)籌學(xué)中偏重于建模的部分位于經(jīng)濟(jì)學(xué)的下游，這部分運(yùn)籌學(xué)家就是經(jīng)濟(jì)學(xué)家中的工程師。比如經(jīng)濟(jì)學(xué)家更多地對(duì)工業(yè)組織感興趣，運(yùn)籌學(xué)家則更多地對(duì)工業(yè)工程感興趣，當(dāng)然這種區(qū)分并不絕對(duì)，而博弈論則游走于運(yùn)籌學(xué)和經(jīng)濟(jì)學(xué)等多門學(xué)科。
從歷史上看，運(yùn)籌學(xué)和博弈論是共同成長(zhǎng)起來(lái)的兩門學(xué)科，他們最早期的研究者高度重合；從學(xué)科關(guān)系上來(lái)講，博弈論是決策科學(xué)的一個(gè)分支，而決策科學(xué)同時(shí)是運(yùn)籌學(xué)和經(jīng)濟(jì)學(xué)的重要內(nèi)容。
歷史上博弈論與數(shù)學(xué)關(guān)系也曾非常密切?？纯碙uce & Raiffa或者Owen等比較早期的博弈論教科書，引用的參考文獻(xiàn)大量來(lái)自Annals等一流的純數(shù)學(xué)期刊。但是再看看上世紀(jì)90年代初期Myerson等那幾本目前認(rèn)為最重要的教科書，發(fā)表于純數(shù)學(xué)期刊的那些結(jié)果能活下來(lái)的已經(jīng)寥寥可數(shù)。科學(xué)研究的殘酷性令人不勝唏噓，甚至連馮諾依曼這種量級(jí)的人物也只有極大極小定理等極少數(shù)成果能活下來(lái)。這說(shuō)明按照純數(shù)學(xué)的品味去研究博弈論，至少目前來(lái)看，是沒(méi)有前途的。雖然沙普利自稱數(shù)學(xué)家，我下面將稍微展開說(shuō)明，他的研究風(fēng)格恰恰不是純數(shù)學(xué)品味而是運(yùn)籌學(xué)品味。主流博弈論學(xué)家目前最認(rèn)可的刊物，多數(shù)來(lái)自經(jīng)濟(jì)學(xué)，少數(shù)來(lái)自運(yùn)籌學(xué)、生物學(xué)等。博弈論與純數(shù)學(xué)早已漸行漸遠(yuǎn)。
我對(duì)沙普利幾個(gè)著名的工作進(jìn)行了簡(jiǎn)單分析，說(shuō)明這些成果的確有鮮明的運(yùn)籌學(xué)特色，跟運(yùn)籌學(xué)精神以及運(yùn)籌學(xué)其他分支密不可分。運(yùn)籌學(xué)家可以理直氣壯地說(shuō)，曾獲得過(guò)運(yùn)籌學(xué)界最高獎(jiǎng)項(xiàng)馮諾依曼獎(jiǎng)的沙普利是我們的人。
（1）獲得諾獎(jiǎng)的穩(wěn)定匹配（Stable Matching）模型。
對(duì)這項(xiàng)工作的歷史通常的演繹如下：1962年蓋爾首先想到了這個(gè)模型，苦苦思索沒(méi)有答案，于是給他的好朋友沙普利寫信求助。沙普利利用一個(gè)下午的時(shí)間解決了這個(gè)問(wèn)題，隨后投稿。該結(jié)果經(jīng)過(guò)兩輪拒稿，最終發(fā)表于《美國(guó)數(shù)學(xué)月報(bào)》。半個(gè)世紀(jì)以后這篇“靈機(jī)一動(dòng)”的小文章幫助沙普利獲得了諾獎(jiǎng)。
我想特別說(shuō)明的是，沙普利能夠一個(gè)下午就解決這個(gè)問(wèn)題，并不是簡(jiǎn)單的靈機(jī)一動(dòng)，而是與他長(zhǎng)期思考相關(guān)的問(wèn)題密不可分。沙普利早在1955年就系統(tǒng)性地思考過(guò)這種雙邊結(jié)構(gòu)的博弈。我們現(xiàn)在熟知的手套博弈和指派博弈（1971年正式發(fā)表于IJGT的創(chuàng)刊號(hào)上），核心思想在1955年蘭德公司的工作論文中就有了。而指派博弈是穩(wěn)定匹配問(wèn)題的一個(gè)姊妹模型，很多性質(zhì)都是平行的。指派博弈來(lái)源于指派問(wèn)題，后者是運(yùn)籌學(xué)和組合優(yōu)化中的一個(gè)經(jīng)典模型。
當(dāng)然，沙普利研究穩(wěn)定匹配問(wèn)題的時(shí)候不見(jiàn)得能意識(shí)到這篇論文將來(lái)會(huì)有如此大的影響。這與羅斯等將這套理論發(fā)揚(yáng)光大并開發(fā)出很多軟件系統(tǒng)的實(shí)際工作密不可分。可以說(shuō)沙普利和羅斯成全了彼此。2008年金融危機(jī)后公眾對(duì)經(jīng)濟(jì)學(xué)普遍質(zhì)疑。在這樣的背景下，諾獎(jiǎng)委員會(huì)把2012年的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)?lì)C給了沙普利和羅斯這樣一項(xiàng)工程性的成果是比較容易理解的——經(jīng)濟(jì)學(xué)家也可以從事毫無(wú)爭(zhēng)議實(shí)實(shí)在在改變世界的工作。
我認(rèn)為跟博弈論領(lǐng)域其它的一流工作相比，沙普利和羅斯的工作在思想上或技術(shù)上的確沒(méi)有特別高深的東西。但就是有用——這就是頂級(jí)的運(yùn)籌學(xué)成果。值得指出的是，穩(wěn)定匹配的后續(xù)工作，除了經(jīng)濟(jì)學(xué)家在大批跟進(jìn)以外，也始終是計(jì)算機(jī)學(xué)家和運(yùn)籌學(xué)家的研究熱點(diǎn)。目前依然如此。
（2）凸博弈。
這是合作博弈論中的一類重要博弈，有非常漂亮的性質(zhì)，并且在各種背景的問(wèn)題中廣泛存在。盡管這個(gè)想法現(xiàn)在來(lái)看非常自然，沙普利能夠設(shè)計(jì)出這樣一類博弈，與他精深的凸分析造詣應(yīng)該是分不開的。事實(shí)上，他在凸分析方面有重要貢獻(xiàn)。從論文中可以看出，沙普利對(duì)當(dāng)時(shí)很前沿的組合優(yōu)化專家Edmonds的工作非常熟悉。
事實(shí)上，合作博弈論，尤其是凸博弈及后續(xù)研究，是由博弈論專家和組合優(yōu)化專家共同發(fā)展起來(lái)的。遺憾的是，盡管沙普利對(duì)雙方早期的工作都非常熟悉，后續(xù)的研究者很快分道揚(yáng)鑣了，長(zhǎng)期相互不引用。沙普利也很早就注意到了Choquet積分與凸博弈的密切關(guān)系，后續(xù)的多數(shù)研究者卻只認(rèn)可Lovasz extension。
令人贊嘆的是，在Topkis、Milgrom、Roberts和Vives等人的努力下，非合作博弈論里也發(fā)展出來(lái)一套類似的優(yōu)美理論——超模博弈。超模博弈和位勢(shì)博弈是目前最廣泛的可以保證純策略納什均衡存在的兩類博弈。沙普利對(duì)這兩類博弈都有開創(chuàng)性貢獻(xiàn)。這也是一個(gè)經(jīng)濟(jì)學(xué)家和運(yùn)籌學(xué)家共同作出的重要成果（沙普利既是經(jīng)濟(jì)學(xué)家又是運(yùn)籌學(xué)家，Topkis是運(yùn)籌學(xué)家，Milgrom、Roberts和Vives都是經(jīng)濟(jì)學(xué)家）。
更令人贊嘆的是，組合優(yōu)化領(lǐng)域里，在Edmonds、Lovasz、Fujishige和Murota等眾多一流科學(xué)家的帶領(lǐng)下，已經(jīng)建立起了從擬陣到次模分析到離散凸分析的一整套優(yōu)美理論。這套理論不僅可以把合作博弈論里的凸博弈與非合作博弈論里的超模博弈統(tǒng)一起來(lái)，同時(shí)處理很多連續(xù)問(wèn)題和離散問(wèn)題，還有望類似于凸分析跟連續(xù)優(yōu)化的關(guān)系，為組合優(yōu)化建立一個(gè)統(tǒng)一框架。
（3）沙普利值和Shapley-Shubik指數(shù)。
沙普利值大概是沙普利最著名的工作，但并沒(méi)有因此獲諾獎(jiǎng)。我個(gè)人認(rèn)為這個(gè)概念的重要性不僅無(wú)法跟納什均衡（Nash Equilibrium）相提并論，大概也比不上Core）。沙普利和Shubik將沙普利值應(yīng)用于政治科學(xué)中票數(shù)的權(quán)力度量問(wèn)題，創(chuàng)立了著名的Shapley-Shubik指數(shù)，成為該領(lǐng)域最重要的幾個(gè)指標(biāo)之一。當(dāng)然，這個(gè)指標(biāo)，跟任何其它指標(biāo)一樣，遠(yuǎn)不是完美的，這里不展開介紹。做評(píng)估和度量，是運(yùn)籌學(xué)和決策科學(xué)里的重要課題，也是經(jīng)濟(jì)學(xué)中相對(duì)比較工程性的問(wèn)題。
（4）位勢(shì)博弈。
這是沙普利和Monderer合作的重要成果。前面已經(jīng)介紹，位勢(shì)函數(shù)法是博弈論里證明純策略納什均衡存在性最常用的兩種方法之一。這在博弈論里也屬于比較技術(shù)性而非思想性問(wèn)題。值得一提的是，位勢(shì)函數(shù)的思想主要來(lái)自物理學(xué)。即便在博弈論領(lǐng)域，Rosenthal和Slade也分別早于Monderer和沙普利提出了這種思想（后者對(duì)前兩者有引用）。但是很多研究者都“方便起見(jiàn)”將此簡(jiǎn)單歸功于后者。這是學(xué)術(shù)領(lǐng)域里典型的（有失公平但不見(jiàn)得不合理的）馬太效應(yīng)。
（5）隨機(jī)博弈。
數(shù)學(xué)上來(lái)說(shuō)，這是馬氏決策的推廣。后者是運(yùn)籌學(xué)中的重要內(nèi)容。所知有限，不去詳述。
（6）算法博弈論。
學(xué)術(shù)界最近十多年才開始對(duì)博弈論里的算法問(wèn)題真正感興趣并發(fā)展出算法博弈論這個(gè)分支。這是計(jì)算機(jī)科學(xué)對(duì)經(jīng)濟(jì)學(xué)的一次入侵。盡管該方向正勢(shì)不可擋地被經(jīng)濟(jì)學(xué)主流接納，目前依然有一些經(jīng)濟(jì)學(xué)家對(duì)它的研究范式有“偏見(jiàn)”。沙普利不僅在1962年就研究穩(wěn)定匹配中的算法問(wèn)題，還很早就對(duì)納什均衡求解的Lemke-Howson算法感興趣。前面介紹的凸博弈研究中，沙普利也很注意算法問(wèn)題；而位勢(shì)函數(shù)不僅可以用來(lái)證明納什均衡的存在，還可以用很簡(jiǎn)單的算法來(lái)找到一個(gè)（特殊）均衡。沙普利毫無(wú)疑問(wèn)是算法博弈論的先驅(qū)。
從前面的討論可以看出，沙普利始終對(duì)運(yùn)籌學(xué)的前沿非常熟悉，他的博弈論研究帶有濃厚的運(yùn)籌學(xué)色彩。他自己也研究過(guò)運(yùn)籌學(xué)里的一些非博弈論課題，比如網(wǎng)絡(luò)流問(wèn)題。始終關(guān)注算法問(wèn)題，是沙普利跟很多博弈論學(xué)家和經(jīng)濟(jì)學(xué)家所不同的，也是我們稱其為運(yùn)籌學(xué)家的強(qiáng)有力證據(jù)。這與運(yùn)籌學(xué)和博弈論共同發(fā)源于以馮諾依曼為首的普林斯頓學(xué)派是密不可分的。比如馮諾依曼就是線性規(guī)劃對(duì)偶理論的發(fā)明者之一，Kuhn就是指派問(wèn)題中著名匈牙利算法的命名者，沙普利對(duì)這些怎么能不熟悉呢！
沙普利對(duì)博弈論的貢獻(xiàn)是全面的。跟同樣量級(jí)的博弈論學(xué)家和經(jīng)濟(jì)學(xué)家相比，沙普利的學(xué)術(shù)風(fēng)格具有濃厚的運(yùn)籌學(xué)家的務(wù)實(shí)色彩。對(duì)比于Aumann等對(duì)知識(shí)和理性的充滿哲學(xué)性的探討，對(duì)比于目前仍然在研究的前向歸納與后向歸納的關(guān)系，沙普利的工作或許顯得沒(méi)有那么深刻那么迷人。但是事實(shí)證明，將工程師的精神發(fā)揮到極致依然可以做出超一流的工作。
有人告訴我說(shuō)，天堂里沒(méi)有饑餓沒(méi)有寒冷沒(méi)有痛苦，所有的人每天都傻傻地快樂(lè)著。我完全無(wú)法想象那種生活狀態(tài)。天堂里的人還需要做選擇和決策嗎？天堂里的男女還需要做匹配嗎？天堂里還投票嗎？天堂里需要博弈論和運(yùn)籌學(xué)專家嗎？Aumann眼中博弈論里的上帝去了天堂，我不知道沙普利到了那里是否真的能成為上帝，只愿他能找到永恒的安寧和快樂(lè)。
（責(zé)任編輯 徐可）
