“博弈论里的上帝”去了天堂

点击：  作者：曹志刚    来源： 知识分子  发布时间:2016-03-29 13:46:12

 

          【编者按】：这是作者为本周辞世的现代合作博弈论奠基人劳埃德·沙普利撰写的纪念文章。因提出“盖尔-沙普利”算法和稳定匹配理论，沙普利获得了2012年经济学奖。他和去年相继离世的哈罗德·库恩与约翰·纳什同为普林斯顿大学1950届博士毕业生，被称为“普林斯顿博弈论学派三巨星”。他自称是从来没有修过一门经济学课程的数学家。作者认为，与其不如说他是一位运筹学家，或者说经济学中的工程师。沙普利主要借助其运筹学或工程师的思维方式获得了举世瞩目的成就。作者从运筹学与数学、博弈论和经济学关系的角度，梳理沙普利的主要学术贡献。

 

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

继哈罗德·库恩（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眼中博弈论里的上帝去了天堂，我不知道沙普利到了那里是否真的能成为上帝，只愿他能找到永恒的安宁和快乐。