久久99国产精品尤物-国产高清色播视频免费看-男生肌肌往女人桶爽视频-精品国产-91PORNY九色|www.jqdstudio.net

          【編者按】：這是作者為本周辭世的現(xiàn)代合作博弈論奠基人勞埃德·沙普利撰寫的紀(jì)念文章。因提出“蓋爾-沙普利”算法和穩(wěn)定匹配理論，沙普利獲得了2012年經(jīng)濟(jì)學(xué)獎。他和去年相繼離世的哈羅德·庫恩與約翰·納什同為普林斯頓大學(xué)1950屆博士畢業(yè)生，被稱為“普林斯頓博弈論學(xué)派三巨星”。他自稱是從來沒有修過一門經(jīng)濟(jì)學(xué)課程的數(shù)學(xué)家。作者認(rèn)為，與其不如說他是一位運籌學(xué)家，或者說經(jīng)濟(jì)學(xué)中的工程師。沙普利主要借助其運籌學(xué)或工程師的思維方式獲得了舉世矚目的成就。作者從運籌學(xué)與數(shù)學(xué)、博弈論和經(jīng)濟(jì)學(xué)關(guān)系的角度，梳理沙普利的主要學(xué)術(shù)貢獻(xiàn)。

勞埃德·沙普利（Lloyd Shapley，1980年）

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

加州大學(xué)洛杉磯分校教授沙普利由于在“匹配理論”(Matching Theory)方面的貢獻(xiàn)獲得2012年的諾貝爾經(jīng)濟(jì)學(xué)獎。沙普利的主要貢獻(xiàn)是1962年和數(shù)學(xué)家蓋爾在共同提出了“蓋爾-沙普利算法” （the Gale–Shapley algorithm），提出并發(fā)展了穩(wěn)定匹配理論，其研究重點是如何使雙方不愿打破當(dāng)前的匹配狀態(tài)，以保持匹配的穩(wěn)定性。

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

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

盡管獲得諾貝爾經(jīng)濟(jì)學(xué)獎是眾望所歸，沙普利從不把自己看成是經(jīng)濟(jì)學(xué)家——他一直宣稱自己是數(shù)學(xué)家。當(dāng)然，沒有經(jīng)濟(jì)學(xué)家因此而鄙視他。這在一流的博弈論和經(jīng)濟(jì)學(xué)家中比較少見。數(shù)學(xué)對于經(jīng)濟(jì)學(xué)的重要性無須贅述。但他們畢竟是兩門不同的學(xué)科，有著差別巨大的研究范式和評判標(biāo)準(zhǔn)。盡管沙普利開創(chuàng)的隨機博弈近些年受到越來越多的數(shù)學(xué)家關(guān)注，Shapley-KKM引理和 Shapley-Folkman引理等也都是很重要的數(shù)學(xué)貢獻(xiàn)，毫無疑問他在數(shù)學(xué)領(lǐng)域的影響遠(yuǎn)沒有在經(jīng)濟(jì)學(xué)領(lǐng)域大。

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

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

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

運籌學(xué)（Operations Research）在臺灣又被翻譯成“作業(yè)研究”，是在二戰(zhàn)中跟控制論、博弈論和計算機等共同發(fā)展起來的一門應(yīng)用型基礎(chǔ)學(xué)科。臺灣的這個直譯，跟很多其它學(xué)術(shù)名詞的翻譯一樣，盡管遠(yuǎn)沒有“運籌學(xué)”那么高大上，卻道出了這門學(xué)科的核心：跟數(shù)學(xué)和理論經(jīng)濟(jì)學(xué)相比，運籌學(xué)都是比較形而下的。

總體而言，運籌學(xué)不像數(shù)學(xué)那么抽象，不致力于研究抽象結(jié)構(gòu)而是解決相對具體的問題；其思想性也不像經(jīng)濟(jì)學(xué)那么強，運籌學(xué)研究中很少見經(jīng)濟(jì)學(xué)中那種天馬行空的模型。

按照我的理解，運籌學(xué)中的優(yōu)化理論位于經(jīng)濟(jì)學(xué)的上游，而它們都是數(shù)學(xué)的下游學(xué)科。運籌學(xué)中偏重于建模的部分位于經(jīng)濟(jì)學(xué)的下游，這部分運籌學(xué)家就是經(jīng)濟(jì)學(xué)家中的工程師。比如經(jīng)濟(jì)學(xué)家更多地對工業(yè)組織感興趣，運籌學(xué)家則更多地對工業(yè)工程感興趣，當(dāng)然這種區(qū)分并不絕對，而博弈論則游走于運籌學(xué)和經(jīng)濟(jì)學(xué)等多門學(xué)科。

從歷史上看，運籌學(xué)和博弈論是共同成長起來的兩門學(xué)科，他們最早期的研究者高度重合；從學(xué)科關(guān)系上來講，博弈論是決策科學(xué)的一個分支，而決策科學(xué)同時是運籌學(xué)和經(jīng)濟(jì)學(xué)的重要內(nèi)容。

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

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

（1）獲得諾獎的穩(wěn)定匹配（Stable Matching）模型。

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

我想特別說明的是，沙普利能夠一個下午就解決這個問題，并不是簡單的靈機一動，而是與他長期思考相關(guān)的問題密不可分。沙普利早在1955年就系統(tǒng)性地思考過這種雙邊結(jié)構(gòu)的博弈。我們現(xiàn)在熟知的手套博弈和指派博弈（1971年正式發(fā)表于IJGT的創(chuàng)刊號上），核心思想在1955年蘭德公司的工作論文中就有了。而指派博弈是穩(wěn)定匹配問題的一個姊妹模型，很多性質(zhì)都是平行的。指派博弈來源于指派問題，后者是運籌學(xué)和組合優(yōu)化中的一個經(jīng)典模型。

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

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

（2）凸博弈。

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

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

令人贊嘆的是，在Topkis、Milgrom、Roberts和Vives等人的努力下，非合作博弈論里也發(fā)展出來一套類似的優(yōu)美理論——超模博弈。超模博弈和位勢博弈是目前最廣泛的可以保證純策略納什均衡存在的兩類博弈。沙普利對這兩類博弈都有開創(chuàng)性貢獻(xiàn)。這也是一個經(jīng)濟(jì)學(xué)家和運籌學(xué)家共同作出的重要成果（沙普利既是經(jīng)濟(jì)學(xué)家又是運籌學(xué)家，Topkis是運籌學(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)一起來，同時處理很多連續(xù)問題和離散問題，還有望類似于凸分析跟連續(xù)優(yōu)化的關(guān)系，為組合優(yōu)化建立一個統(tǒng)一框架。

（3）沙普利值和Shapley-Shubik指數(shù)。

沙普利值大概是沙普利最著名的工作，但并沒有因此獲諾獎。我個人認(rèn)為這個概念的重要性不僅無法跟納什均衡（Nash Equilibrium）相提并論，大概也比不上Core）。沙普利和Shubik將沙普利值應(yīng)用于政治科學(xué)中票數(shù)的權(quán)力度量問題，創(chuàng)立了著名的Shapley-Shubik指數(shù)，成為該領(lǐng)域最重要的幾個指標(biāo)之一。當(dāng)然，這個指標(biāo)，跟任何其它指標(biāo)一樣，遠(yuǎn)不是完美的，這里不展開介紹。做評估和度量，是運籌學(xué)和決策科學(xué)里的重要課題，也是經(jīng)濟(jì)學(xué)中相對比較工程性的問題。

（4）位勢博弈。

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

（5）隨機博弈。

數(shù)學(xué)上來說，這是馬氏決策的推廣。后者是運籌學(xué)中的重要內(nèi)容。所知有限，不去詳述。

（6）算法博弈論。

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

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

沙普利對博弈論的貢獻(xiàn)是全面的。跟同樣量級的博弈論學(xué)家和經(jīng)濟(jì)學(xué)家相比，沙普利的學(xué)術(shù)風(fēng)格具有濃厚的運籌學(xué)家的務(wù)實色彩。對比于Aumann等對知識和理性的充滿哲學(xué)性的探討，對比于目前仍然在研究的前向歸納與后向歸納的關(guān)系，沙普利的工作或許顯得沒有那么深刻那么迷人。但是事實證明，將工程師的精神發(fā)揮到極致依然可以做出超一流的工作。

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