用“合作博弈”理论设计有效匹配方案

　　在人类历史上，很早就出现了蕴涵博弈思想的故事，但真正将博弈思想规范为一般理论的是冯·诺伊曼和摩根斯坦。在此基础之上，纳什和沙普利分别将博弈论研究推向两个不同方向：非合作博弈和合作博弈。

　　非合作博弈在研究不对称信息情况下市场机制的效率问题中发挥了重 要作用。但非合作博弈的解——“纳什均衡”仅仅意味着“双不亏”，并不能实现共赢。

　　与非合作博弈着重个人理性不同，合作博弈强调的是集体主义、团体理性。故而合作博弈也称为联盟博弈。这个联盟形成后能够使博弈双方的利益都有所增加，所以这是一种正和博弈。

　　长期以来，经济学家对求解这种多重理性手足无措，只能避而远之。合作博弈在理论上的重要突破及其以后的发展在很大程度起源于沙普利的研究及其公理化刻画。

　　博弈论是个工具，它告诉我们激励将被引向何方。从这个意义上说，博弈论方法具有实证的特征。而罗思正是利用实验经济学方法推动博弈论成为实证经济学的关键人物。

　　⊙史晨昱

　　旷日持久的全球金融危机，使多数精致的经济学理论黯然失色。这也难怪今年的诺贝尔经济学奖回归传统和保守。而向博弈论靠拢无疑是最稳妥的方式。算上这一届，已有六次授予该领域的专家。而博弈论正以主流经济学的面貌出现，这不是偶然。

　　不过，略别以往的是，今年的两位得主，成就了理论+实践的典范：劳埃德·沙普利（Lloyd S. Shapley）的理论出色，采用“合作博弈”理论去研究和比较不同的匹配方法；阿尔文·罗思（Alvin E. Roth）将实证、实验和实用的设计相结合，既证实了匹配理论，还重新设计了若干稳定机制，提高了很多市场的效率和表现。

　　而诺贝尔经济学奖第一次将目光投向了具体理论的可操作性上，这也是一次尝试。照此说来，二人共同获奖，也算是一桩绝配。

　　以公正为原则稳定分配合作收益

　　博弈论领域的学者大多认为，对博弈论理论贡献最大的当属冯·诺伊曼、约翰·纳什和沙普利。在人类历史上，很早就出现了蕴涵博弈思想的故事，但真正将博弈思想规范为一般理论的是冯·诺伊曼和摩根斯坦（1944）。在此基础之上，当时普林斯顿大学数学系的两个博士生纳什和沙普利分别将博弈论研究推向两个不同的方向：即非合作博弈和合作博弈。

　　纳什开创并奠定了非合作博弈的理论基础，正是基于这些贡献，1994年他获得该年度诺贝尔经济学奖。由于20世纪后期信息经济学的发展，非合作博弈在研究不对称信息情况下市场机制的效率问题中发挥了重要作用，非合作博弈似乎在博弈论中有独占鳌头之趋势。但非合作博弈的解——“纳什均衡”仅仅意味着“双不亏”，并不能实现共赢。

　　在人类社会实践中，正因为人们的理性，为了极大化自身的利益，会去寻求长期、互利合作的可能性。因此，非合作博弈的研究不能取代合作博弈的研究。与非合作博弈着重个人理性不同，合作博弈强调的是集体主义、团体理性。故而合作博弈也称为联盟博弈。

　　理性主体往往为了利益与其他理性主体订立协议，形成联盟。这个联盟形成后能够使博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害，因而整个社会的利益有所增加，所以这是一种正和博弈。若不带来更大的利益，联盟是不可能形成的。但联盟形成后如何分配获得的收益呢？这是合作博弈所关心的问题。

　　收益分配，取决于博弈各方的力量对比和技巧运用。因此，妥协必须经过博弈各方的讨价还价，达成共识，进行合作。在这里，合作剩余的分配既是妥协的结果，又是达成妥协的条件。长期以来，经济学家对求解这种多重理性手足无措，只能避而远之。合作博弈在理论上的重要突破及其以后的发展在很大程度起源于沙普利的研究及其公理化刻画。

　　沙普利（1952）将“核”发展为合作博弈的一般利益分配集合，即它是一种所有成员均无法提升自身效用的稳定联盟状态。由于“核”这个概念不能给出联盟内成员效用分配的唯一预测，沙普利（1953）进一步在合作博弈框架中加入了一些着眼于“公平”分配合作利益的公理。沙普利首先对“公平”、“合理”等概念给予了严格的公理化描述，然后寻求是否有满足人们想要的那些公理的解。当然，如果对一个解的性质或公理要求太多，则这样的解可能不存在；另一方面，如果这些性质或公理要求得少，则又可能有许多解，即解存在但不唯一。

　　他证明在这些公理的约束下，存在唯一的效用分配方案，这就是沙普利值。沙普利值是根据各人给联盟带来的增值来分配，在直观上是所有边际贡献的平均值。沙普利值计算方法简单，而且能得到合作博弈的唯一解，使用较为广泛。到目前为止这个解仍然是合作博弈领域内最重要的结果之一。不仅如此，沙普利的工作具有方法论上的重要意义，他的公理化方法使我们可以研究讨论合作博弈中其他各种各样的解。

　　沙普利本人正是该技术最好的应用者。他与舒比克发表了一篇著名的论文《委员会制度下的权利分配评价方法》，后来称之为沙普利—舒比克权力指数。当时他们将沙普利值引入投票机制，评价了委员会制度的权力分配体系。目前，这一指数已广泛的应用于公司金融领域，反映了股权对公司决策的影响力，能够客观地度量某股东或某些股东对股份制公司的控制力。

　　由于在解决世界上各类资源共享问题和避免冲突方面有独到的方法，合作博弈近年来在经济学中的地位与日俱增。沙普利使用合作博弈的方法来研究现实中的匹配难题。

　　传统经济学中，通过价格调整可以实现供需平衡。然而，在一些特殊市场中，价格不能用作配置资源的手段，资源只能以分配或配给方式加以配置。配置的关键问题在于保证一个配对是稳定的。所谓稳定解，指的是在匹配市场上没有剩下彼此愿意与对方组对，但却没有被市场允许的一对人，同时，已组对的人对自己的队友应该是满意的。

　　1962年，沙普利与盖尔合写一篇短文，以10名男子和10名女子“婚配”为范例，设想先让所有男人向自己最满意的女人求婚，然后让所有女人挑选最中意的，并剔除所有其他人选；再让没有被选中的男人再次向自己第二满意的女人求婚，然后让所有女人挑选最中意的，并剔除所有其他人选；这一过程不断重复，直到所有人找到了配偶为止。

　　上述方法被称为GS运算法则。这种方法能确保匹配是稳定的，因为任何一个男子，如果他发现某个女子比老婆更可爱，则那个女子一定拒绝过他。这些方法同时也限制了市场主体操纵匹配过程的动机。沙普利设计的方法能够系统性地对两个市场主体其中一方有利。

　　沙普利的贡献还有提出了随机博弈的概念。随机博弈是一种包含一个或多个参与者进行的具有状态概率转移的动态博弈过程。随机博弈由多个博弈阶段组成。此外，他在长期竞争理论上与2005年诺奖得主罗伯特·奥曼的工作均对经济学理论产生了巨大影响。而在80多岁高龄之际，沙普利在学术上仍有产出，如多人效用和权力分配理论。真是老骥伏枥，志在依然。

　　以博弈为工具成功实验市场设计

　　从方法论角度看，博弈论研究的是在一定信息结构下，什么是可能的均等结果。博弈论中的最佳策略是经济学意义上的最优化，没有政治、道德的含义，它不作道德上的劝告，在伦理上是中性的，它只回答是什么导致博弈均衡，均衡的结果是什么。博弈论是个工具，它告诉我们激励将被引向何方。从这个意义上说，博弈论方法具有实证的特征。罗思正是利用实验经济学方法推动博弈论成为实证经济学的关键人物。

　　1995年之前，罗思的所有工作还仅限于学术范围。罗思首先也是一位博弈论大师。在传统的博弈论中，行为人是理性的。这里的理性是一种行为方式，特点是人们在博弈开始的时候就知道了博弈的最终结果。但人们的行为显然并未如此。人们是在博弈中学习的。

　　为了建立人们的学习和认知行为模型，罗思（1995）利用公共物品提供博弈、市场博弈和“最后通牒”讨价还价模型三个博弈实验来观察人们的行为。共物品提供博弈和市场博弈在许多条件下，都能达到预期的均衡点。但在最后通牒博弈中，在一系列的条件下，行为却远离预期的均衡点。

　　1995年，罗思与卡格尔合作编著了《实验经济学手册》一书。这本著作的重点是阐明实验研究作为一个渐进的研究工具，在可能的情况下应建立起一系列彼此作用的实验研究。此外此书还传达一个特定的方法论：学习如何设计和进行实验既是考虑一个好的实验室如何在需要调查的事件和假设基础上有组织的建立起来的。

　　1995年以后，罗思开始将实验理论付诸实践，并将上述理论+实践的二位一体冠之以市场设计，自此一项微观经济工程诞生了，涉及经济学、计算机科学和其他学科的理论和实证研究。市场设计，顾名思义，即是在接近真实的、复杂的市场状况中，研究资源如何合理分配，以及如何实际合理的市场机制达到这样的分配效果。

　　市场设计最根本的核心问题是：市场如何运作。罗思自然不会忘记“实验”这个工具。他意识到沙普利的理论计算结果可以让实践中重要市场的运作方式变得更清晰。罗思成功地通过系统性的实验，帮助许多特殊的市场建立了更合理的均衡匹配。

　　罗思首先解决的是美国医学院的实习分配问题。他分析了这个问题的演化情况。美国的医生实习制度引入于上世纪初。起初，实习的机会多于学生的数量，所以医院争相竞争。这导致医院向学生发邀请的时间一再提前，以至影响了学校的教学。为此，经过努力，50年代美国医学院联合会采纳了在一个固定日期前，不允许学校提供学生信息的建议。这使市场暂时稳定了，但又产生现新的问题。

　　由于越来越多的女生选择就读医学院，在校期间结婚的学生数量也出现激增。旧的分配系统很难满足学生夫妻希望在同一地点接受住院培训的要求。于是，毕业生们只好直接与医院联系。1997年5月，该联合会通过了实行新的市场规则的建议。这个新方案由罗思设计，并于1998年投入使用，利用他设计的系统可以顺利地将医学院毕业生分配到全美的2.5万个实习岗位。

　　另外，美国等待肾脏捐赠的患者名单上有多达8.5万人，每年有4,000名患者因器官短缺而死亡。其中的重要原因之一，便是捐赠匹配系统的效率太低。2003年，罗思开始负责设计新系统。对于想捐肾给亲人，但由于血型不匹配无法实现的案例，该系统可以帮助他们与其他不匹配的捐赠组交换器官。目前，虽然利用这一系统进行肾脏移植的患者还不多，2009年只有不到1,000例，但是它的前景仍为许多人看好。罗思在肾脏匹配方面的工作为现代器官移植领域的发展发挥了巨大的推动作用。

　　迄今为止，罗思解决过的最棘手的现实难题，是纽约市高中的匹配系统。一般来说，许多美国孩子都是就近入学，但在纽约之类的大城市中，八年级学生却有着数量惊人的选择。该市共有8万名八年级学生，700所高中，从理论上讲，每位学生都可任选其中的一所学校就读。不过，对于生活在贫民区、邻近学校很差的孩子们来说，选择合适的学校就显得异常重要。

　　在罗思介入之前，纽约的高中入学匹配系统糟糕透顶，以至于该市有1/3的八年级学生不愿意参与系统匹配。在一位哈佛研究生和哥伦比亚大学经济学家的帮助下，罗思利用某种GS算法重新设计了该系统。罗思及其团队将这一团乱麻简化成清晰可靠的系统，使学生能按自己的喜欢程度最多填报12个志愿。罗思设计的新系统投入使用后，学生的参与率从66%跃升至93%。利用该算法的其他版本，他还参与设计了波士顿公立学校的匹配系统以及医学院毕业生的住院培训分配系统。

　　罗思把复杂的市场设计变成了一件看起来非常简单的事情。他精力旺盛，喜欢穿牛仔裤、开领衬衫和梅里尔登山鞋，他的办公室里到处散落着各种期刊。他不像传统经济学家那样，把重心单纯放在理论或经验研究上，而是不断以创新的方式将现有的市场设计应用到新的领域。看起来，他是个充满活力的人。

　　（本文作者系北京大学经济学博士，现供职于中国工商银行，也系本报每年诺贝尔经济学奖得主学术思想述评主要撰稿人）

　　阿尔文·罗思

　　（Alvin E. Roth）

　　生于1951年12月19日，美国经济学家，目前在哈佛商学院担任经济及工商管理乔治-冈德(George Gund)教授。罗斯在博弈论、市场设计和实验经济学领域都曾作出重要贡献。

　　罗思的父母都是高中教师。罗思1971年本科毕业于哥伦比亚大学，获得运筹学学士学位，随后赴斯坦福大学攻读研究生，1973年获运筹学硕士学位，一年后获运筹学博士学位。

　　离开斯坦福之后，罗思直到1982年一直在伊利诺斯大学厄本那—香槟分校任教。此后他在匹兹堡大学担任安德鲁-梅隆经济学教授直到1998年，之后他加入哈佛大学并在此工作至今。

　　罗思是美国杰出年轻教授奖：斯隆奖的获得者，古根海姆基金会会士，美国艺术和科学院院士。他还是美国国家经济研究局(NBER)和美国计量经济学学会成员。

　　主要学术著作：

　　1979年《交易的不言自明模式》 经济和数学系统讲稿 美国Springer Verlag出版社；

　　1985年《交易的博弈理论模式》剑桥大学出版社；

　　1987年《经济学的实验室实验：6个观点》 剑桥大学出版社 该书已于2008年翻译了中文版；

　　1987年《沙普利价值：致劳埃德-沙普利的评论》 剑桥大学出版社；

　　1990年《匹配的两面：博弈理论模拟和分析的研究》 与索托马约尔(M. Sotomayor)合著 剑桥大学出版社；

　　1995年《实验经济学手册》 与卡格尔(J.H. Kagel)合编 普林斯顿大学出版社；

　　2001年《鲍伯-威尔逊传统的博弈论》 与霍姆斯特罗姆(Bengt Holmstrom)和米尔格罗姆(Paul Milgrom)合编。

　　劳埃德·沙普利

　　（Lloyd S. Shapley）

　　美国数学家和经济学家，美国加州大学洛杉矶分校数学和经济系教授。在数理经济学与博弈论领域有卓越贡献。

　　沙普利1923年6月2日生于美国麻省剑桥，他的父亲是杰出天文学家哈罗·沙普利。沙普利1943年入学哈佛，同年作为一名中士加入美国陆军航空队，前往成都支援中国抗战。他因破解前苏联气象密码获得铜质勋章。

　　战后他重返哈佛大学并于1948年获得数学学士学位。在美国兰德公司(RAND corporation)工作一年后，他赴普林斯顿大学学习，于1953年获得博士学位。毕业后，他在普林斯顿短暂停留后重返兰德公司(1954年至1981年)。

　　1955年他与玛丽安·鲁道夫结婚，有两个孩子。自1981年起，他就任加州大学洛杉矶分校教授一职。

　　主要学术著作：

　　1953年《随机对策理论》，《美国国家科学院学报》，39期，1095至1100页；

　　1954年《委员会体系下权力分配评估理论》，(与Martin Shubik合著)《美国政治学评论》，48期，787至792页；

　　1962年《大学录取和婚姻稳定》，《美国数学月刊》，69期，9至15页；

　　1962年《简单博弈论：描述理论概述》，《行为科学》，7期，59至66页；

　　1969年《市场博弈论》，《经济学理论》，1期，9至25页；

　　1969年《功用比较及博弈论》，《决策》，251至263页；

　　1994年《长期竞争：博弈论分析》《博弈论论文：纪念Michael Maschler Nimrod Megiddo》；

　　1996年《潜在博弈论》，《博弈论和经济行为》，14期，124至143页；

　　2003年《机构权力分配》(与X.Hu合作)，《博弈论和经济行为》，45期，132至152页；153至170页。 (来源：上海证券报)