Gale Shapley 学生最优机制摘抄

Gale—Shapley学生最优机制（本文简称GS机制）就具有公平和抗策略的特性，并且相对于其他公平的机制而言，它是帕累托最优的。GS机制最早是在大学招生模型中提出来的（GaleandShapley,1962⑼），在大学招生模型中，学生和学校都是积极参与人。Gale和Shapley证明，在大学招生模型中稳定匹配总是存在的，并且在所有的稳定匹配中，存在一个匹配对于学生来说是帕累托最优的，一个匹配对于所有学校帕累托最优。他们提出了达到学生（学校）最优稳定匹配的机制，这个机制通过延迟接受学生（学校）申请来达到。由于我们关注的是学生利益，因此考虑学生最优机制，该算法过程如下：第1轮：每个学生申报其第一志愿，每个学校根据其偏好将第一志愿报考本校的前qc（qc为招生名额）个学生纳入考查名单，拒绝其他学生。第2轮：上轮被拒绝的学生申报第二志愿，每个学校将第二志愿报考本校的学生和列入考查名单的学生一起比较，将前qc个学生纳入第二轮考查名单。第k轮：上轮被拒绝的学生申报第k志愿，每个学校将第k志愿报考本校的学生和列入考查名单的学生一起比较，将前qc个学生纳入第k轮考查名单。当没有学生被拒绝，所有学生都分配到最终位置时，该算法结束。定理1（H.ErginandT.Sonmez，2006〔10〕）:给定考生的真实偏好以及考生在“波士顿机制”下的显示偏好博弈。这个博弈的纳什均衡结果与学生最优机制下真实申报偏好所得到的匹配结果是相同的。定理2（GaleandShapley，1962〔9〕;BalinskiandSon-mez，1999〔11〕）:GS机制帕累托优于其他任何公平机制。定理3（DubinsandFreedman，1981〔12〕;Roth，1982〔13〕）:GS机制是抗策略的。定理4（AlcaldeandBarbeia，1994〔14〕）在高考招生问题中，GS机制是唯一满足个人理性、公平、没有浪费和抗操纵的学生录取机制。由此看来，GS机制具有三大优点：（1）它能够促使考生真实申报其偏好，避免了考生之间的志愿博弈，完全解决了填志愿难的问题，节约了大量不必要的社会成本，志愿填报时间问题也迎刃而解。（2）在考生真实填报其志愿的前提下，最终的录取结果对所有学生而言都是最优的，并且不会出现不公平或资源浪费的现象。（3）它能够化解统一高考与自主招生之间的矛盾（关于坚持统一高考必要性的讨论参见刘海峰，1997〔15〕，2006〔16〕;张亚群，2005〔17〕等）。即便是高校有自己不同的评价标准，这种机制依然能够得到一个公平的匹配。这就意味着，这种机制能够在保证考生利益的同时，赋予高校更充分的自主招生权力，促进“多元化评价”的实施与推行。不过，该机制的运作效率较低，它最多要用步才能完成整个算法，这无疑是对招生工作的一种挑战，也是高考改革中常常面临的效率与公平之间的矛盾。在实践过程中，为了减少算法步骤，每所高校可以列出其招生的最低标准，比如限定某门学科的最低分数，以减少录取工作量。总体而言，高考改革的发展趋势是从效率优先走向公平优先，继而走向公平与效率的兼顾与平衡（刘海峰，2002〔18〕）。因此，要想获得让考生满意，高校满意、社会满意的良好效果,再大的挑战都应该迎难而上。事实上,这种机制也并非难以实施。2005年7月，波士顿和纽约就进行了公立学校择校机制改革，为减少父母们的志愿策略博弈，波士顿学校委员会投票决定将当前的波士顿学校录取机制改为GS学生最优机制。。但和中国不同，它通过一个类似中央招生办公室的机构，对全体学生按照志愿和报考专业需要的单科成绩排名来统一录取。在择校问题中，学校所在地的法律使得所有学生在每个学校中都有一个优先顺序，不同的学校中学生的排序不同,学生的志愿顺序和在学校的优先顺序决定他是否被录取。他们研究的“波士顿机制”和咼考的录取机制类似，也有因第一志愿不当而丧失排序优势的风险。他们提出Gale2Shapley机制是一个改进的替代机制。SnmezandErgin(2006)研究了“波士顿机制”下的各种博弈。SnmezandChen(2006)利用试验经济学的方法分析了“波士顿机制”，发现这个机制下学生会操纵自己申报的偏好，与Gale2Shapley学生最优机制相比有较大的效率损失。在Roth等博弈论专家的咨询协助下，波士顿和纽约的公立学校择校机制改革为Gale2Shapley学生最优机制。“波士顿机制”与高考录取机制类似也是“第一志愿优先”，AtilaAbdulkadroglu,ParagA.Pathak,AlvinE.Roth和TayfunSnmez(2006)分析了这个机制下学生填报的志愿数据。他们发现并不是所有的考生和家长都意识到或者有能力在这个机制下操纵自己的偏好，一些家长没有避免明显的错误。和经济理论中的均衡分析不同,在实际中可能并不是所有家长都有同样的能力和资源计算出均衡策略。因而录取机制无操纵也是一种公平的要求，使所有考生在同一平台上竞争。各地区的志愿填报方式(或机制)都是“志愿优先”，这一机制存在着“高分低就”的可能，在文献中也被称为公平性(fairness)或稳定性(stability)问题。学生可能不会将其最喜欢但是竞争激烈的学校放在第一志愿，而是把不太喜欢但风险较小的学校放在第一志愿，即不会按照自己真实的偏好序进行填报，这被称为抗操纵性(strategy-proof)问题。“平行志愿”的引入则是试图将“志愿优先”改为“分数优先”以克服上述两种弊端。填报志愿的时序，包括考前和考后填报志愿，后者又包括考后估分和考后知分填报志愿两种方式。两个不同维度上的组合可以产生不同的机制，与国外择校机制文献中研究的典型机制存在某种对应关系。概括来说，考后知分填报在没有平行志愿时对应于文献中的波士顿机制(BostonMechanism，BOS机制)，在具有“完全"平行志愿时对应于首位交易环机制(TopTradingCyclesMechanism，TTC机制；或称分数优先的系列独裁机制,SerialDictatorshipMechanism，SD机制)以及Gale—Shapley机制(GS机制，又称延迟录取机制，DeferredAcceptance，或DA机制)。已经证明，考后有平行志愿的填报机制是公平的、有效率的和抗操纵的。传统的择校机制文献认为BOS机制在抗操纵性、效率和公平等方面均无法与TTC机制或GS机制抗衡。正是在这些理论的指导下，BOS机制的命名地 美国波士顿地区公共学校 的政府管理部门从2005年开始将其择校机制改为了GS机制。不过具有讽刺意味的是，在这之后文献开始反思这些理论结果，一个核心的想法是：当存在学生偏好序或者学校优先序的不确定性时，BOS机制从事前效率和公平的角度讲，并不劣于甚至在一定条件下优于其他机制。国外的实证研究大都基于实验数据，ChenandSonmez（2007）比较了BOS、GS、TTC三种择校机制特征，发现BOS机制下确实有更多的偏好操纵，这使得BOS机制下的效率更低。不过，FeatherstoneandNiederle（2008）从事前角度、用实验方法考察了GS（或DA）机制和BOS机制，发现在学生偏好是私人信息以及学校对学生的优先序存在不确定性时，BOS机制可能比DA机制更有效率。在已有的少数利用实际数据的研究中，Abdulkadiroglu，Pathak,RothandSonmez（2006）利用美国波士顿地区择校结果的实际数据分析发现，在BOS机制下，进行偏好操纵的参与者比没有进行偏好操纵甚至错误填报偏好的参与者获得更大利益。Abdulkadiroglu，PathakandRoth（2009）依据纽约市2006-2007年8年级（即升高中）学生提交的偏好，用实验模拟比较了不同择校机制的匹配结果。这可能是目前唯一一篇基于实际数据比较不同机制的研究，但由于无法观察到实际偏好，他们只能将学生提交偏好假定为真实偏好。本文的另一个贡献在于选取了一个独特的角度来衡量匹配质量。匹配质量的衡量是择校机制经验研究的一个难点。首先，任何评价方法都要求了解每个考生的偏好，而这通常是观察不到的。其次，虽然从理论上定义匹配质量——效率与公平——并不困难，但从经验数据中衡量匹配结果的质量仍然是仁者见仁的事。最后，评价完整的匹配质量对数据可得性要求很高，需要掌握所有考生的偏好、分数排序以及最终录取结果的完整信息。本文通过只考察国内某一顶级大学学院所招收的学生群体的变化大大简化了问题。作为一个顶级大学