罗思与沙普利的稳定分配理论

2012年诺贝尔经济学奖：罗思与沙普利的稳定分配理论

瑞典皇家科学院

    瑞典皇家科学院决定，将纪念阿尔弗雷德·诺贝尔的2012年瑞典国家银行经济学奖授予美国哈佛大学哈佛商学院教授阿尔文·罗思（Alvin E. Roth）与美国加利福尼亚大学洛杉矶分校教授劳埃德·沙普利（Lloyd S. Shapley），以此嘉奖两位教授对稳定分配理论及市场设计实践上的成就。
价格体系不是总管用
    经济学家研究社会如何分配资源。一些分配问题可以在价格体系中获得解决，例如，某一职位用高工资吸引劳动者，高能源价格引导消费者去节约能源。但在许多情况下，使用价格体系会遭致法律和道德上的异议，如公立学校在学童中的分配，或人体器官在需要移植的病人中的分配。并且，许多市场中虽然存在价格体系运作，但传统上假设的完全竞争仍未接近于实现。尤其是许多商品是由不同的商品组成且是不可分割的，而每一分类商品的市场十分稀薄。这些稀薄的市场如何配置资源取决于管理这些交易的体系。
    今年获奖的成就包括一个用于分析资源配置的理论框架，以及对现实世界中的体系（如劳动力市场交流中心和学校招生程序）进行的实证研究和真实再设计。这一理论框架的基础是1962年戴维·盖尔（David Gale）和劳埃德·沙普利建立的对特定一类分配问题进行的数学探讨。二人考察的模型由两组必须相互匹配的对象组成，例如劳动者和公司。如果其中一位劳动者被A公司雇佣，但这位劳动者更青睐B公司，且B公司本来也想雇佣这位劳动者，那么，这次交易中就存在未被利用的收益，因为如果这位劳动者由B公司雇佣，那么对于双方来说会更好。盖尔和沙普利定义，如果交易中不存在这种未被利用的收益，那么这次匹配就是“稳定”（stable）的。在一个理想的市场下，劳动者和公司有无限制的时间和能力去达成交易，其结果总是稳定的。当然，现实中的市场可能在许多重要方面与理想中的不同，但盖尔和沙普利提出的“延迟接受”（deferred-acceptance）程序易于理解，且总能达到稳定的结果。该程序说明市场一方中的对象（如雇佣者）如何向另一方中的对象提出要约，而后者如何根据一定的规则接受或拒绝要约。
    该理论框架的实证意义由阿尔文·罗思证明。罗思在1984年发表的研究文章中发现，美国的新医生市场长久以来受到一系列市场失灵因素的影响，但一家集中的交流中心由于采用了本质上相当于盖尔和沙普利的延迟接受的程序而大大改善了当时的情况。罗思的这篇文章阐明了市场所执行的任务，并说明这个稳定概念如何提供了一个组织原则，帮助我们理解为何市场有时运转正常，有时不正常。
    之后，罗思和他的同事利用这个理论框架，结合实证研究、对照实验室实验和计算机模拟，对其它市场的运作进行了研究。研究结果不仅揭示了这些市场的运作方式，还证明了体系设计有助于帮助市场更好地运行，这些设计常常利用演绎后的盖尔-沙普利程序或拓展后的盖尔-沙普利程序。这已经促使一门被称作“市场设计”的新兴经济学分支出现。需要注意的是，这里所说的“市场”并不假定存在一个价格体系。事实上，货币转移在许多重要应用中都被排除在外。
没有足够盈余
则无法稳定分配
    今年获奖的成就使用了非合作博弈理论与合作博弈理论的工具。非合作博弈理论也是1994年诺贝尔经济学奖得主约翰·海萨尼（John C. Harsanyi）、约翰·纳什（John Nash）、莱因哈德·泽尔腾（Reinhard Selten）及2005年诺贝尔经济学奖得主罗伯特·奥曼（Robert Aumann）和托马斯·谢林（Thomas Schelling）的研究主题。非合作分析的出发点是对个体决策者面临的策略性问题进行详细的描述。相比之下，合作博弈理论则研究个人集合团体（“联盟”）如何通过合作扩大自己的利益，因此，合作分析的出发点是对每个联盟所能达成的结果进行分析。对合作博弈理论的发展做出主要贡献的是劳埃德·沙普利。
    合作与非合作分析方法在许多方面相辅相成。市场设计的两个关键属性是稳定性（stability）和激励相容（incentive compatibility），二者阻止对市场的策略性操纵。“稳定性”这个概念来自于合作博弈理论，“激励相容”则来自于机制设计理论——非合作博弈理论的一个分支，这也是2007年诺贝尔经济学奖得主莱昂尼德·赫维奇（Leonid Hurwicz）、埃里克·马斯金（Eric Maskin）及罗杰·迈尔森（Roger Myerson）的研究主题。
    对照实验室实验是市场设计领域经常使用的方法。弗农·史密斯（Vernon Smith）因其在实验经济学方面的成就分享了2002年诺贝尔经济学奖。今年获奖的阿尔文·罗思是另一位为这一领域做出重大贡献的人。
    合作博弈理论研究个体形成联盟的激励因素，其假定一个联盟内部的任何潜在利益冲突都可以通过约束性协议解决。这些协议引导联盟成员采取行动以使联盟“盈余”（一定数额的货币）最大化，而最大化的盈余就是联盟的价值。但是，如果盈余还取决于非联盟成员的行动，困难就会出现。这时候，可以通过假设非联盟成员努力最大化自己的回报，以一致的方式确定联盟的价值。
    在“可转移效用博弈”中（一旦联盟形成，其成员可以以他们希望的任意方式分割盈余，每个成员的“效用”等于他们各自分割的盈余份额，这就是“可转移效用”），隐含的假设是联盟中的个体之间可以自由地转移效用，实际上通过“单边支付”（side-payments）来完成转移。但在一些情况下，单边支付受到限制，效用无法（完美地）转移。例如人体器官捐赠，此时单边支付会被视为“令人反感的”（罗思，2007年）。合作博弈理论能够处理这种情况，因为它在一般的非转移效用博弈理论层面也得到了非常好的扩展。
    某个联盟的成员如果可以利用自己的资源让自身的境况更好，那么就可以说这个联盟能够“改进”回报向量。一般来说，一个分配如果不能被任何联盟“改进”，那么它就是稳定的分配。事实上，没有联盟能够通过利用自己的资源，带来令所有成员更青睐的结果，就是所谓的稳定分配。合作博弈理论中的稳定性与非合作博弈理论中的“纳什均衡”（Nash equilibrium）相对应，后者指没有个人可以单独背离并让自身的境况更好。
    稳定分配是否总是存在？一般来说，如果无法得到足够多的盈余，那么就不可能对其进行稳定的分割。邦达列娃（Bondareva，1963年）和沙普利（1967年）各自发展出一个精确的公式，用于计算要使可转移效用博弈中的“核心”（core，即“稳定分配的集合”）非空则需要多少盈余。两人的研究成果被斯卡夫（Scarf，1967年）和比莱拉（Billera，1970年）进一步拓展至不具有可转移效用的合作博弈中。沙普利（1971年）又证明，如果博弈是“凸博弈”（即参与者对联盟的边际贡献值如果在其他参与者加入联盟后提高），那么“核心”就总是非空的。
盖尔和沙普利的
双边匹配算法
    在许多市场中，商品是私人的，但是由不同的商品组成且是不可分割的，传统上假设的完全竞争是无法维持的。重要的例证包括熟练工就业市场。由于不可能存在两位特征完全一样的劳动者，因此面向每个特定劳务群的市场可能非常稀薄。在这样的市场中，参与者必须适当匹配才能相互交易。
    考虑到一个市场有两个不相交的对象集（如买家和卖家，劳动者和公司，学生和学校）必须互相匹配以进行交易。盖尔和沙普利（1962年）研究的就是这种双边匹配市场。他们排除了单边支付——工资（等匹配特征）不在谈判内容中。
    稳定匹配（stable matchings）。具体而言，假设市场的一方为医学院学生，另一方为医疗机构，每个机构需要一名实习生，每个医学院学生都想获得一个实习职位。很自然，学生和医疗机构对对方都有偏好的选择。为了方便起见，我们假设偏好是严格的（也就是没有关系的）。对于双方的任何一个对象来说，如果匹配之后不如未匹配之前，那么这个匹配就是“不可接受的”。
    一般来说，一个分配如果不能被任何联盟“改进”，那么它就是稳定的分配。在上述这个模型中，稳定的匹配必须满足以下两个条件：（1）没有一个对象认为匹配不可接受，（2）没有任何一对机构和学生希望是他们之间匹配，而不是各自目前的匹配。条件1即“个体理性”（individual rationality）条件，条件2则是“成对稳定性”（pairwise stability）。两个条件意味着没有一个联盟、没有一对机构和学生能对目前的配对进行改进。
    盖尔-沙普利算法（the Gale-Shapley algorithm）。盖尔和沙普利为了寻找一个稳定匹配设计出了“延迟接受算法”（deferred-acceptance algorithm）。市场一方中的对象（医疗机构）向另一方中的对象（医学院学生）提出要约，每个学生会对自己接到的要约进行考虑，然后抓住自己青睐的（认为它是可接受的），拒绝其它的。该算法一个关键之处在于，合意的要约不会立即被接受，而只是被“抓住”（hold on to），也就是“延迟接受”。要约被拒绝后，医疗机构才可以向另一名学生发出新的要约。整个程序一直持续到没有机构再希望发出新的要约为止，到那个时候，学生们才最终接受各自“抓住”的要约。
    在这个过程中，每个医疗机构首先向被自己列为第一位的求职者发出要约，也就是最想接收为实习生的那个医学院学生。如果这个要约被拒绝，这家机构才能向被自己列为第二位的学生发出要约，依次类推。因此，在该算法的操作中，医疗机构的预期随着要约对象所处偏好排序降低而下调（当然，医疗结构不会对不可接受的求职者发出要约）。反过来说，由于学生总是抓着所接收要约中最合意的那个，且要约不能被撤回，因此每个学生的满意度在该算法的操作中是单调递增的。当医疗机构下降的预期与学生提高的志向变得相一致时，该算法停止。
    盖尔和沙普利（1962年）证明，延迟接受算法是稳定的，也就是说，它总能产生一个稳定的匹配。该算法为这种类型的双边匹配问题提供了一个存在性证明：既然它总会终止于一个稳定匹配，那么稳定匹配是存在的。
    激励相容（incentive compatibility）。盖尔-沙普利算法能帮助真实世界市场中的参与者找到稳定匹配吗？回答这个问题需要非合作分析，也就是对控制匹配过程的规则和对策略性行为的激励因素进行详细的分析。
    在上文中，延迟接受算法被解释为一个由求职、发出要约、拒绝和接受组成的分散化的程序。但在实践中，该算法由人才交流中心以集中的方式应用。每个求职者和雇主向交流中心提出自己的偏好排序，基于提交的偏好，交流中心履行算法的各项步骤。用机制设计理论的术语来说，交流中心运行着一个“揭示机制”（revelation mechanism），这是一种虚拟市场，不存在一些真实市场遭遇的某些问题。揭示机制诱发同步行动博弈（simultaneous-move game），所有参与者都会提交自己的偏好排序，考虑到他们完全理解该算法如何将提交的偏好排序映射到分配中。可以用非合作博弈理论对这个同步行动博弈进行分析。
    如果讲实话是占优策略，那么揭示机制是激励相容的，这样，参与者总是发现提交自己真实的偏好排序是最佳的。由雇主发出要约的算法（被视作揭示机制）对于雇主来说是激励相容的：没有雇主甚至雇主联盟可以通过虚报偏好排序获益。但该机制对于求职者来说就不是激励相容的了，例如上述某个医学院学生可以通过操纵或策略性虚报自己的真实偏好排序让自己获得更中意的实习职位。这说明，讲实话对于求职者来说不是占优策略。罗思（1982年）证明，当讲出真实的偏好不是每个对象的占优策略时，稳定的匹配机制不存在。但需要指出的是，尽管有一名学生有操纵行为，但最终的匹配结果在真实的偏好下是稳定的。并且，这是不被占优的纳什均衡结果。这说明了盖尔-沙普利算法的一个一般事实，并被罗思证明（1984年）：偏好操纵博弈的一切不被占优的纳什均衡结果，对于真实的偏好都是稳定的。
    但罗思（1984年）这项研究结果的用处受到下面这个事实的限制：求职者识别自己的最佳反应可能是困难的，但这正是纳什均衡定义中所要求的。例如，上述虚报偏好排序的学生如果知道其他求职者都诚实，但不知道他们的偏好具体是什么，那么这个学生仍无法完全预见最终结果，因此他不能确认通过操纵一定会带来利益。这个论点暗示，在大而多样化的市场，参与者对于其他人的偏好信息了解有限，策略性操纵的范围可能因此非常局限。罗思和罗斯布鲁姆（Rothblum，1999年）证实，当一位求职者的信息足够有限，他就无法通过提交一份将真实意愿中两名雇主的排序对调的偏好排序来获益。但是，他可以通过假称一名可接受的雇主是不可接受的来获益。
（本报记者兰晓萌编译自诺贝尔奖官方网站）

查看更多华夏时报文章，参与华夏时报微信互动（微信搜索「华夏时报」或「chinatimes」）