稳定配置理论

《稳定配置理论》由会员分享，可在线阅读，更多相关《稳定配置理论（7页珍藏版）》请在金锄头文库上搜索。

1、稳定配置理论：理论、证明和市场设计实践今年的诺贝尔经济学奖得主是劳耶德沙普雷和阿尔文罗斯。他们进行了长时间的研究， 从 19 世纪 60 年代形成的抽象理论到 19 世纪 80 年代的实证研究，再到现在正在进行的为 解决现存问题而作的努力。他们解决的实际问题包括刚毕业的医生和工作医院的匹配，学生 与学校的匹配以及等待器官移植的患者与器官捐献者的匹配等。在研究中劳耶德贡献了早期 的理论，在后来阿尔文的调查中，他发现劳耶德的理论在20年后无意中被运用在了美国医 生的就业市场中。他的发现激发了后来理论分析的发展和对市场机构的市场设计实践。在传统经济分析研究的市场中，都是依靠价格变动来实现供求平衡的。

2、理论和实践都表 明这种市场在大部分情况下运转良好。但在某些特殊情况下，这种标准市场机制也遇到了问 题，那就是价格在分配资源时完全派不上用场。比如说许多学校不允许收学费以及在器官移 植中，在道德层面上不考虑金钱的支付都是这些情形的实例。尽管如此，在以上事例及许多 其它情况中，分配又是必不可少的。那么这些过程到底是如何运作的？什么情况下这些操作 又是高效的呢？配对理论GS 算法(The Gale-Shapley algorithm)对分配机制的分析依赖于一个更抽象的理念。如果理性人(做出使自己利益最大化的行 为的人)仅仅参与无条件限制的相互贸易，那么这种分配的结果就是有效的。如果不是这样， 一些个

3、体就会进行新的贸易来使他们更加富有。一种没有任何个体从其他贸易中寻求财富的 分配就是稳定的。稳定这个概念是合作博弈论中的核心概念，合作博弈论是经济数学中的一 个抽象领域，这个领域研究是什么决定了一系列理性人选择了能使他们共赢的分配方式。这 个博弈论的分支最早的创始人就是劳耶德沙普雷，他在19世纪50年代到60年代就形成 了这个理论的主要概念。无条件限制的贸易是隐含在稳定这个概念中的重要假设。尽管他经得起严格的分析，但 它在现实生活中的情形还是很难想象的。在1962年，沙普雷把稳定这个理念运用在了一个 特殊案例中。在一篇与大卫盖尔合作的短篇论文中，他分析了两人配对这个案例：个体怎 样才能在他们对

4、谁应该成为最合适的配对持不同看法的情况下完成配对。夫妻配对盖尔和沙普雷在抽象、宏观的层面上分析了配对。他们用婚姻作为阐述观点的一个实例： 在尊重他们个人喜好的前提下，怎样始十个男人和十个女人配对。最大的挑战是要设计一个 简单的能够实现稳定配对的机制，稳定指的是没有一对夫妻离婚也没有人寻找新的伴侣来使 自己更加幸福。盖尔-沙普雷的“延迟接受算法”是以一系列能够直接实现稳定配对的简单 法则，它解决了上述问题。GS 算法在男选女和女选男这两种情形下都是适用的。就拿女选男这种情况来说，首先 每个女性选择自己觉得最好的男性，然后每个男性对不同的追求者进行挑选（如果有的话）， 男性留下他认为最有吸引力的追

5、求者（暂时不用接受）并拒绝其他追求者。在第一轮中被拒 绝的女性接着选择她们觉得第二好的男性，男性继续在第一次保留下来的和第二次新的追求 者中挑选出自己觉得最好的并拒绝其他人。这种情形一直进行到没有女性想继续挑选新的男 性。当每个男性都接受了他留下来的最求者后，配对过程就结束了。盖尔和沙普雷用数学方 法证明了这个算法总能实现稳定的配对。算法中特定的步骤对分配结果又重要的影响，比如说本例中选择的权利是属于男性还是 女性。如果选择权在女性，那么配对结果就更有利于女性，因为一些女性最终与她们喜欢的 男性配对成功，而且而且没有女性会得到比男性拥有选择权的情况下更糟糕的配对。事实上， 这种配对结果比任何其

6、它稳定配置都要有利于女性。相反的，在男性拥有选择权的算法中， 配对结果对女性是最不利的。简洁而清晰的语言使盖尔和沙普雷的论文成为了全世界经济学学生的学术读物，但它与 现实生活的联系是很久以后才被发现的。在19世纪80年代初，阿尔文罗斯开始研究一个 非常实际的分配问题：应届毕业医生的就业市场。实例应届毕业医生的就业市场在美国，从医学院毕业的学生大部分都会到医院当实习医师，他们是劳动力的重要组成 部分，在19世纪初，这个市场是相当分散的。在19世纪40年代，对稀缺的医学院学生的 竞争迫使医院在毕业前好几年就要向学生提供实习机会。在学生能证明他们的就业资格之前 甚至在学生还没决定他们想在医学的哪个领

7、域工作时配对就已经完成了。如果医院提供的实 习机会没有被学生接受，那么再向别的候选人提供机会就太晚了。一个充斥着这些问题的市 场就没有实现稳定配置。因为不能及时提供足够的能使双方共赢的交易。为了更快地提供更 多的实习机会，医院对学生考虑是否接受实习的时间作了严格的限制。相应的，这又迫使学 生在不知道后面还会有什么机会的情况下早早地做出决定。为解决这些问题，19世纪50年代国家推出了一个名为国家住院医师匹配项目（NRMP） 的集中交易场所。从1984年开始，阿尔文罗斯在论文中研究了这个交易所使用的算法并 发现了它与GS算法关系密切。他随之假设出NRMP项目成功的根本原因就是它创造了稳定配 置方法

8、。在 19世纪90年代初，罗斯继续研究了英国相似的医生就业市场。他发现英国不同 地区采用了不同的算法，有的是用了稳定配置而有的没有使用。那些使用了稳定配置的地方 都成功的将医生与医院配对了，而是用其它算法的都因各种各样的原因以失败告终。市场设计实践医生与医院的配对尽管NRMP项目是成功的，但它还是存在一些问题。因为女性医生的增加，情侣在同一 地区寻求实习机会的现象越来越普遍，因此许多申请者不想使用这种机制。这是这个机制不 稳定的一种表现。 NRMP 项目也被职责为从体制上讲更有利于医院而不是学生，因为医院具 有选择的主动权。事实上，在盖尔和沙普雷设计出这个理论时，双方中有利的一方就已经确 定了

9、（在本例中为医院）。在 1995年，罗斯受邀改进原算法来消除以上问题。罗斯与埃利奥 特一起设计了一个新算法，这个新算法对医生一方有利且对情侣也适用。这个新算法在1997 年被NRMP所采纳并良好运作，此后每年超过2万个医生找到了合适的工作岗位。强调了改进后设计的调查引发了新理论的发展。理论上说，申请人可以操纵原始算法- 拒绝他们实际的首选，保留那些他们不喜欢的-以达到更好的结果。在一些理论分析的论文 中，罗斯分析了，在一些算法中，接受方（原来NRMP系统中的医生）为保证自身利益会如 何歪曲他们的真实喜好。知道了这一点，改进后的NRMP算法是用来避免学生的选择与他们的喜好相背离的，而 且电脑模拟

10、也证实了在实际应用中医院的策略上的操纵对比算法没有影响。 学生与高中的配对GS算法在其他配对过程中也是适用的，比如说高中录取学生。直到2003年，申请上纽 约市公立高中的学生都被要求按顺序列出五所他们最想上的学校，这些志愿排序表都会被送 到高中去。然后高中决定哪些学生被录取，哪些被淘汰以及哪些是待定的。这个过程还会重 复进行两轮，三轮选择后还没有被任何学校录取的学生就通过一套管理流程来分配。但是这 样就不能给申请者充分的机会来列出他们的志愿了，而且学校也没有足够的机会来向学生伸 出橄榄枝。结果，每年约有3 万名学生最后进入了不在他们志愿之内的高中。更糟的是，这医院与医生的配对。当医生有选择权的

11、时候，他们的首选都是医院a,但医院a的首选是医生1所以医院a选择了 医生1。在第二轮中，医生2选择了医院b,医生3选择了医院c,这形成了一种稳定分配。但如果选择权在医院的话, 结果就是医生2与医院c和医生3与医院b。个流程歪曲了学生的真实喜好。因为学校录取把他们排在第一志愿的学生的可能性比较大， 不太可能被自己最喜欢的学校录取的学生发现选择一个更容易被录取的学校作为第一志愿 对他们比较有利，此时隐瞒了自己真实喜好的申请者只能无奈地接受不尽人意的结果。基于 使申请者拥有选择权的GS算法，在2003年，罗斯与他的同事重新设计了这个录取系统。新 的算法成功运行，被不在自己所填志愿中的学校所录取的学生

12、数量下降了90%。目前，越来 越多的城市采用了与GS算法相似的录取方法。等待器官移植的患者与器官捐献者的匹配到目前为止我们介绍的配对方法都是涉及主动选择的双方的，但是一些现实生活中的情 况只是单方面主动的。一个实例就是等待移植的肾脏或其它器官，这个配对怎样才能被有效 的完成呢？沙普雷和他的同事研究了这个问题，同样是用了稳定的概念。这次采用的算法其实非常 简单，也就是所谓的“首位交易循环”。这是以先前的分配为基础，然后再进行后续交换的。 在器官移植这个例子中存在很大的挑战，那就是一些捐献者和待移植的病人的器官是不匹配 的，而复杂的多人交换又很耗时间。再一次的，沙普雷等人用理论和实证研究相结合的方

13、法 比较了不同方式的首位交易。得益于他们的研究，现在美国的多个州都采用了这个越来越完 善的肾脏捐献流程。在新领域的运用上述例子中共有的显著的特点就是在分配过程中没有用到金钱。这种基于GS算法的不 考虑金钱的机制是否会限制它的应用呢？答案是并非如此。沙普雷等人在把金钱考虑进来的 情况下(考虑了医生的工资)又检查了最初的医生与医院配对的模型。考虑金钱之后的算法 依然运转良好且实现了与原先相似的稳定分配。事实上，把金钱考虑进来之后的分配与拍卖 非常相似，在买家与拍卖物的分配中价格起着决定性的作用。把分配方法和拍卖联系在一起 的研究创造了一个新的有趣的理论，这在实际运用中很有价值。一个比较适当的例子是

14、网络 拍卖，某些搜索引擎用拍卖的方法来出售它们的广告席位。这么做的公司都从GS算法中获 利了且他们都雇佣了顶尖的经济学家来为他们设计新的拍卖方式。今年的诺贝尔经济学奖奖励给了一个繁荣发展的研究领域，在其中理论、实证和实际应 用被结合起来使用。虽然劳耶德沙普雷和阿尔文罗斯是相互独立地进行研究的，但却是沙 普雷的理论成果和罗斯发现的其在实际应用中的价值结合起来才有了今天的成就的。我们相 信这是一个潜力无穷的领域并会继续繁荣地发展。连接和延生阅读 想获得更多关于今年诺贝尔经济学奖的科学背景的英文文献，可以登录瑞典皇家科学学 院的官方网站，http:/kva.se和http:/nobelprize.o

15、rg。他们还提供了公布奖项的新闻 发布会的网络视频。有关诺贝尔经济学奖的展览和活动在可以登录网站 www.nobelmuseet.se 力廿以了解。博客Market Design www.marketdesigner.blogspot.se讲座Roth, A. E. (2007) What Have We Learned from Market Design, Rosenthal Memorial Lecture. Boston U A. E. (2007) Market Failure and Market Design, Google Tech Talks. 回顾文章Roth A. E.

16、 (2008) What have we learned from market design?, Economic Journal1,18: 285 - 310.参考文献Moulin H. (1995) Cooperative Microeconomics. Princeton University Press.Roth A. E. and Sotomayor M. (1990) Two-sided Matching: a Study in Game-theoretic Modeling and Analysis, EconometricSociety Monograph Series, Cambridge University P