中国高考招生录取机制—— 一个巨大的协调博弈.doc
中国高考招生录取机制 一个巨大的协调博弈聂海峰内容摘要：本文分析了当前高考招生的考后报考录取机制，刻画了这个机制的性质和缺点，并介绍了一种改进的机制。当前中国高考招生制度使得招生过程成了一个百万考生参加的巨大的显示偏好博弈，这个博弈只有唯一的一个纳什均衡结果，但是真实的偏好并不一定是每个考生的均衡策略。达到均衡结果需要参与人之间几乎不可能的协调。使用GaleShapley学生最优机制，可以达到同样的配置，并且真实偏好是学生的占优策略，结果也是帕累托有效，公平的。如果高考招生制度进行改革，将会有巨大的效率改进。关键词： 匹配 Gale-Shapley学生最优机制 占优策略 A Titanic Coordinating GameCollege Admission in China Nie Haifeng (Guanghua School of Management, Peking University)Abstract: The College Admission mechanism in China is a giant revealing preference game played by millions of students every year. Unfortunately, the true preferences of students are not their optimal equilibrium strategies. We prove that the equilibrium outcome is unique and Pareto efficient, but it is hardly a possible mission to coordinate to equilibrium. Fortunately, the admirable Gale-Shapley deferred mechanism in college admission model can be adapted to achieve the same outcome with more advantages. A great of efficiency would be achieved if the existing college admission mechanism had been replaced. Key words: Gale-Shapley mechanism Match StrategyproofJEL Classification： C78 ,D61,D78一、 引言现在的高考招生制度是从1978年恢复高等学校入学考试以来一直沿用至今，成为大学入学的基本方式。想进入大学学习的人员，参加由教育部统一组织的入学招生考试，然后各个招生学校根据考生的志愿和考试分数的高低决定是否录取。在当前的高考招生制度下，大学没有了自主的权利，大学的招生名额成了通过高考分数分配的公共品。高考期间，考生和家长不但要了解各种大学的情况得到对学校的偏好，而且如何填报志愿也是家长们焦头烂额的事情。在目前统一入学考试的制度下，各高校都强调分数的公平性，实际录取的规则也是分数优先。清华大学的招生简章所有引用的2004年招生简章，可从下面网址下载：中写道：“第十二条 清华大学按照考生的实际考分和报考志愿安排专业，各专业志愿之间存在一定的分数级差。分数级差的确定以调档线上该考区报考清华大学的所有考生的志愿满足率最大为标准，一般在310分之间，同等条件下参考相关科目成绩。”有些学校使用的是按所有报考该校的考生成绩排名录取，如同济大学招生专业录取规则是在从高分到低分排序的前提下，再按专业志愿先后进行录取，一般情况下，第一专业志愿优先 2 分录取专业，其他二、三等专业志愿之间考分高者先录取，同等分数情况下，专业志愿在前者先录取。” 但是，一个考生是否能进入大学学习，不仅需要一个好的分数，所填报的志愿也有重大影响。考生填报的志愿作为对大学专业的偏好，并不一定就是它对大学专业的真实偏好，这一点，任何考试咨询人员都会提到，每个考生家长也都深刻领会的。在当前的招生制度中，如果考生的志愿不当，就会面临丧失这个优势的风险。在高考招生中，各个学校先录取第一志愿的学生，只有当录取不满的时候才招收第二志愿的学生。如北京大学的录取规则：“第十三条 在第一志愿生源不足的情况下，北京大学接收非第一志愿考生。但其分数应不低于已投档的第一志愿考生的平均分。” 即使招收第二志愿的学校，也对考生的考分有规定。比如北京师范大学的招生简章写道：“第十五条 北京师范大学在部分省（自治区、直辖市）接收北京大学、清华大学的第二志愿考生（我校参加提前批录取的省份除外），招生数控制在所在省（自治区、直辖市）同类计划的 10%以内，分数级差在40分以上，在考生保证服从专业调剂的情况下，按照实考分数由高到低择优录取。”这样，如果志愿填写不当，考生就会有丧失分数的优先性的风险，甚至出现没有被任何大学录取的可能。因而，考生填写的志愿，不一定是他对大学真实的偏好，而是他的分数有优势的学校。如何首选第一志愿是每个考生和他家庭都极为关注的事情，整个志愿填报过程成了所有考生寻求最优策略的一个博弈。由于学生的考分和志愿事实上是决定是否被学校录取的主要标准，这就使得在学生和高校组成的高校招生博弈中，填写志愿的学生就是唯一的行动者，给定了学生的考分和志愿，根据高考招生制度，就可以的到高考的招生结果。现在全国的各高等院校是按照省为单位进行招生，每年各省参加高考招生人数近百万，整个高考志愿填报就成了一个百万人参加的巨大的博弈。每个家长如何寻找自己的最优策略，并不是一件轻而易举的事情。我们在下文中将证明,在完全信息下，这个巨大的协调博弈中，只存在唯一的一个纳什均衡结果。这个结果是帕累托最优的，公平的。但是在这个巨大博弈中，考生的真实偏好常常不是他的均衡策略。如何协调到均衡策略，对每个学生来说成了一个不可能的任务。自然，高考实际录取的情况就不会是帕累托最优的情况了，存在着可观的无效率。在实际的招生中，出现的高分落榜和学生不去学校报到的现象就是证据。大学招生模型的文献研究开始于Gale和Shapley 1的文章，他们研究了类似的大学招生问题，提出了GaleShapley学生最优机制。其后文献的发展在Roth和Sotomayer2中有全面的总结和综述。但是，中国的高考招生制度和Gale和Shapley研究的大学招生制度有一个显著的不同。在Gale和Shapley的大学招生模型中，学生和学校都是积极的参与人，学生对要申请的大学有一个偏好，大学也对所有学生有偏好。但在当前中国的高考招生制度中，学生的偏好和学生的成绩决定了学生是否能被学校录取，学校是所有学生共同拥有的公共品，考生的成绩和志愿决定了这些公共品如何在学生中间分配。 土耳其也是通过标准化考试来进行大学录取的。但和中国不同，土耳其通过一个类似中央招生办的机构对全体学生按照志愿和报考专业需要的单科成绩排名来统一录取的。Michel Balinski和Tayfun Sönmez3研究了土耳其的大学招生制度，提出了用GaleShapley学生最优机制来替代。Atila Abdulkadiroglu和Tayfun Sonmez4首次从机制设计的角度研究了美国公立学校的择校制度。其中的“波士顿机制”和高考的录取机制类似，也是根据学生的志愿来进行录取。在择校问题中，学校所在地的法律使得所有学生在每个学校中都有一个优先顺序，在不同的学校中学生的排序不同，根据学生的志愿顺序和优先顺序决定是否被中学录取。GaleShapley学生最优机制也被作者提出作为当前机制的一种替代，并且论证了被代替机制的弊端。Sonmez Tayfun 等人56利用试验经济学的方法分析了“波士顿机制”，发现这个机制下会出现帕累托无效的配置，学生都和高考一样操纵自己申报的偏好。在真实的世界中，GaleShapley学生最优机制现在被应用在美国进行全美实习医生的实习分配 789。 如果把学生的考分排序解释成学校对学生的偏好，高考的问题就成了一类特殊的Gale-Shapley大学招生问题。在这个大学招生问题中，所有学校对学生偏好是一样的。在GaleShapley大学招生问题中，GaleShapley学生最优机制可以达到学生最优的学校配置，最优配置对学生是帕累托最优的。当前的高考制度下博弈的均衡结果，和执行GaleShapley学生最优机制得到一样的均衡结果。但是，在执行GaleShapley学生最优机制时，真实显示偏好是每个学生的占优策略，不需要同时和其他人的偏好进行协调。同时，在GaleShapley学生最优机制下，如果考生的高考成绩提高，录取他的大学在他的偏好次序上不会下降。并且，使用GaleShapley学生最优机制, 不论填报志愿是在考试前，考试后还是估计分数填报，真实偏好都是学生的占优策略。这样，GaleShapley学生最优机制使得考生无需费心进行策略操纵，也减少了高分低就的损失。本文其他部分的组织如下：第二部分是对高考招生问题和对应的Gale-Shapley大学招生问题的描述，第三部分证明了高考博弈均衡结果的唯一性。第四部分是作为替代的Gale-Shapley学生最优机制和这个机制的性质。最后部分是总结。二、高考招生问题目前实际招生中是以省为单位进行的，每一个招生学校确定在不同省的招生名额和专业。本文的分析也是局限在各省的招生制度。下面的讨论中，学校的招生名额是已经划分到省的招生名额。全国不同的地区使用不同的试卷进行标准化考试，也使得招生是按照各省的学校名额进行的。在实际录取中，也是各个省内的考生录取。高考招生的基本要素是学生的考分、学生的志愿和学校的招生计划。志愿是每个学生对大学的偏好。在不同的省份，志愿递交的时间和全国统一招生考试的时间并不一致。统一招生考试由法定统一时间进行，志愿递交时间各省自己安排。根据学生填报志愿时对自己分数的了解程度，共有三种制度安排：考前填报，这时考生没有参加招生考试；估分填报，在招生考试结束的1-2日内填报，考生对自己的考分有一个预计；第三种是知分填报，所有考生的分数都确定下来，每个考生知道自己的分数和所有考生的分数分布。在2004年，北京、上海、重庆、吉林、广东等5个省（市）为考前填报志愿，浙江、四川等十个省市是在得知考试分数后填报志愿，其他的地区是在考试结束后的1-2天内填报志愿。目前，知分填报的模式是主要的安排，我们的在本文的分析也是知分填报的模式下的招生制度。 给定全国所有学校在当地的招生计划，各省招生办公室根据考生的高考成绩和填报的志愿，负责组织高等学校的招生工作。高考招生工作的一般流程如下。高考录取机制：1 每一个想进入大学学习的人员都报名参加统一招生考试，分数出来后填报自己的志愿。2 根据全部考生的分数和各类型学校的总的招生计划，各省招办划定各类型学校的高考分数线。在目前，学校类型分为本科、专科和职业学校，在本科学校中，被分为重点学校，一类本科和二类本科。学校的类型决定了学校在学生偏好中的顺序，也决定了录取学生的顺序。 只有考试分数高过招生录取分数线的学生，才有资格被相应类型的学校录取。同时各省规定不同加分政策，由加分和考试总分数得到确定每个学生在录取时的排序分数。根据学校的类型，招生办公室通过控制批次根据考生偏好投递考生的档案，学校根据学生的考分排名录取。3 录取过程是由省招生办公室和学校共同完成的，这个过程可以描述如下：第一轮 考虑所有学生的第一志愿。根据学生的志愿，学生分配到相应的学校。各个学校根据考生的分数排序，根据招生计划按照分数从高到低录取。如果学生数超过招生计划，则只录取成绩最高的招生计划数学生，其他学生被拒绝。如果学生数小于招生计划数，所有学生都被录取。第二轮 接下来考虑所有没有被录取的学生的第二志愿。这一轮只考虑所有学生的第二志愿，根据第二志愿送到仍然招生的学校。如果该志愿的学校已经招满人数，该学生被拒绝。仍有空余名额的学校，根据第二志愿考生的成绩排序后，一次一个从高到底录取，直到用完所有名额或者所有学生都被招收。依此类推，一般来说第k 轮。考虑所有还没有被录取的学生。在第k轮，只考虑所有未被录取的学生的第k志愿。如果学校还有名额没有招满，根据第k志愿是该学校的学生的录取成绩排序，从高到低一次一个依次录取，直到学校用完所有的招生名额或者所有的学生都被招收。在这样的招生方式下，如果一个考生想要被一所学校录取，他不但要分数足够高，也要在填报志愿的时候把这所学校作为他的第一志愿来填写。如果志愿填写不恰当，有可能被所有的学校拒绝，虽然分数较高但是没有学校可读。这时，每个学生有强的动机来操纵自己的偏好，使得他的分数可以发挥作用。这时的志愿偏好，就不是学生的真实偏好。在填报志愿的时候，学生的偏好是学校排序和学校内的专业排序，并且有是否服从学校内专业调剂选项。这种志愿的填报方式，使得学生对学校和专业的志愿成为字典序形式的偏好。各省的实际的录取过程是上面描述的过程的变形。由招生办公室执行学校偏好招收，而由学校来执行专业偏好的招收。当学校执行专业志愿满足率最大和全校大排行招收的时候，学校志愿和（学校，专业）志愿的执行一致。此外，各学校在招生的时候也是按照专业计划招生人数来执行招生，并且学校在招生后不分专业培养，因此，学校排序志愿和（学校，专业）志愿是一致的。我们在下文中不区分学校和（学校，专业），统一称为学校。下面我们用符号来表示，一个高考招生问题由以下几部分构成： 1 所有考生的集合 ； 2 所有学校的集合 ；3 一个招生计划人数向量 ，其中是学校的计划招生人数；4 每个学生高考录取分数的向量，其中是学生的高考分数和规定的加分后的录取分数。我们假设考生的考分没有相同的。在实际中考生的总分有大量的相同，但是可以使用一定的规则在总分相同的情况下额外排序，如是否有加分，单科成绩优先等方式。这样，任意的，都有，所有的考生的录取分数就得到一个完全的排序。5 学生的严格排序集合。每一个学生都在集合上有一个严格的偏好，这里表示不上大学的选择，我们规定，表示不上大学的选择可以容纳所有的学生。我们用集合表示上所有严格偏好序的集合。是对任何由排序得到至少一样好排序，即对于,我们有，当且仅当或者。如果，我们就说对于学生学校是可接受的。对所有的，我们用表示除去学生外其它所有学生的偏好。在下面的文章中，和都是固定的，这样，给定一个招生计划，高考录取成绩和学生偏好的三元组就得到了大学招生的基本要素，我们称其为一个高考招生问题。高考招生的目的就是给定三元组通过标准化统一考试成绩和招生程序，使学生和学校配合，由于不能使的每个学生都被自己最偏好的大学录取，因此高考招生制度根据学生的偏好和考试成绩对学生的偏好进行满足和选择能够进入大学学习的学生。我们把招生的结果称为匹配。一个匹配（match）就把学校分配到所有考生的一个方案，方案中一个考生最多能够得到一个大学的入学名额，每个大学招收的人数不超过它的招生计划。形式上，一个匹配就是一个函数使得对所有的，有，这表示大学招生不超过它的计划。如果，就表示学生没有被任何大学录取。所有匹配的集合记为。学生的偏好是定义在，我们可以把它扩展到匹配的集合上：学生偏好匹配超过匹配，当且仅当，在下文中，我们仍用表示这个扩展了的偏好。一个匹配是个人理性的，如果对于所有的学生，不会被分配给比宁愿不上学还差的大学。对于所有的学生，他得到的学校都是可接受的。用符号来表示，就是对于所有的，我们都有。一个匹配被称为是没有浪费的，如果有一个学生偏好另一所学校而不是录取他的学校，那么另一所学校必定已经招满了学生。用符号表示，就是对任意的和，如果，那么必然有。一个匹配帕累托占优另一个匹配，如果所有的学生都不偏好超过，而有些学生偏好超过。用符号来表示，匹配帕累托占优匹配，如果对所有的，我们都有,存在，有。一个匹配是帕累托有效，如果不存在匹配帕累托占优匹配。我们可以注意到，一个匹配是帕累托有效的，必然是个人理性并且没有浪费的。在高考录取中，分数高低决定了学生在学校录取时的排序。Balinski等（1999）分析土耳其的招生制度时，引入了分数公平的概念。一个匹配被称为是公平的（Fair），如果有一个学生偏好另一所学校超过录取他的学校，那么另一所学校已经招满了学生而且所有的学生的分数都高于这个学生。用符号表示，就是对任意的和，如果，那么必然有，而且对任意的，必然有。公平匹配有如下的结构：定理1（Michel Balinski；Tayfun Sönmez,3) 一个匹配是公平的，当且仅当对每个学校存在一个最低分数线，对所有的学生和学校，如下的条件成立： 1） 如果，必然有； 2） 如果，必然有在公平的匹配中，一个学生不能被他喜欢的学校录取，是由于这个学校已经录取的学生的成绩都高于这个学生，这个性质反映了学生在分数面前的公平性，这个分数的公平性，也体现在实际录取中学校和政府负责部门的要求中。一个机制（mechanism）就是一个系统的程序，对于每个给定的三元组，得到一个学生和学校的匹配。一个机制称为直接机制，如果它需要每个学生报告他的偏好。一个机制是帕累托有效的，如果它对每个招生问题给出的匹配都是帕累托有效的匹配。一个机制是公平的，如果对每一个高考问题的匹配结果都是公平的。三、高考招生博弈高考招生的结果就是一个学生和学校的匹配，这个匹配是通过我们上面描述的高考招生机制达到的。从机制设计的角度，对于每个学生，我们用表示学生的信号集合，用表示所有学生的信号空间，其中的每一个元素都是形如,这里对应学生的信号，是所有学生信号的组合的集合。从信号空间到匹配的函数称为结果函数。任何信号空间和结果函数的二元组称为称为一个机制。如果每个学生的信号空间是上的所有严格偏好集合，这个机制就称为直接机制。这样，给定一个招生计划，高考录取成绩和学生偏好的三元组，给定一个机制，就得到了一个考生的博弈。在实际的高考中，考生向招生负责办公室填报志愿，就是在一个直接机制里显示自己的偏好。由于考生知道考分和填报志愿的时间不同，共有三种不同的信息结构。在考前报考的模式下，考生的信息只是自己的偏好。在估分报考的模式下，考生的信息是自己的偏好和对自己分数估计，而在考后成绩出来报考的模式下，考生的信息是自己的偏好和所有考生的成绩。我们在这里考虑知道分数时的报考博弈，这时所有学生的考分是公共信息，高考的志愿填报成了一个显示偏好的博弈。下文我们将证明，在Gale-Shapley学生最优机制下，三种填报模式中真实显示自己的偏好都是学生的占优策略。在知分报考的模式下，给定三元组和一个直接机制 ,就得到了考生间的一个博弈。每个考生的纯策略集合是信号集合，也是上的所有严格偏好集合。我们允许混合策略存在，每个考生的混合策略是表示上的所有严格偏好集合上的概率分布。这样，高考志愿填报博弈就是，（，）。这里我们分析完全信息情况，所有考生的真实偏好是共同知识，在知分报考时每个考生也知道所有考生的考分。这个博弈的顺序如下：首先，考试分数确定，进入填报志愿阶段，所有考生同时行动。我们每个考生向招生办公室报告一个偏好，不一定是他的真实偏好，所有人的信号组合就是信号空间的一个元素。接着，根据考生填报的志愿顺序，招生办公室和学校根据按照前面描述的机制进行录取，得到最后的匹配。我们定义这个博弈的一个纯策略纳什均衡为，如果对所有的, 都有 ，对任意的，表示学生均衡时的匹配，是给定其他人的均衡策略时学生填报按照高考招生机制得到的匹配。在纳什均衡的时候，每个参与人填报志愿都是对其他人填报的志愿的最优反应，每个人都不能单方面改善他的匹配。我们假设每个考生都是预期效用最大化，类似通常的做法，我们可以定义这个博弈的混合策略纳什均衡。 在这个有百万人参与的直接博弈中，每个人都寻求最优的策略，努力使他的高考分数发挥最大的作用。我们在高考的实际招生中，看到许多高分落榜和学校没有招满的现象，是否在这个博弈中没有均衡结果导致了这些现象。我们有如下的结果：定理2 在高考博弈，（，）的纳什均衡是存在的。 证明：由于每个考生的纯策略是对学校的严格偏好，由于学校的数目是有限的，因而严格偏好也是有限的。同时，考生的数目是有限的。因此，这是一个有限博弈。根据纳什定理，任何有限博弈都是存在均衡的（可能是混合策略均衡）。 虽然这个博弈存在均衡，但是我们更加关心是否存在纯策略的均衡。显然，混合策略的均衡不是一个很好的结果。在后边我们将知道，确实存在纯策略的均衡。这里，我们证明所有纯策略均衡的均衡结果是相同的。定理3 在高考博弈，（，）中，纯策略纳什均衡结果是唯一的：令，是纳什均衡，则证明：（1）如果一个匹配是均衡的匹配结果，它必然是个人理性的。否则，存在，有。这里，是在均衡时学生的策略，他的真实的偏好是，是除学生外其他所有人的策略。给定其他人的策略不变，学生的策略变为偏好，偏好把选择作为学生的第一志愿。在偏好组下，高考机制的结果必然有，这样我们就得到 。这和匹配是均衡匹配结果相矛盾。（2）如果一个匹配是均衡的匹配结果，它必然是公平的。如果匹配不是公平的，那么存在和，有，或者或者存在，有。这里，是在均衡时学生的策略，他的真实的偏好是，是除学生外其他所有人的策略。给定其他人的策略不变，学生的策略变为偏好，偏好把学校作为学生的第一志愿。在偏好组下，高考机制的结果必然有这样我们就得到 。这和是纳什均衡结果矛盾。因此均衡结果必然是公平的。（3）如果，则存在两个均衡，并且。必然存在，我们有，不妨设，这是根据偏好的严格性得来的。令，由于是公平的，我们必然有对于任意的，并且。由于是公平的，我们必然对于任意的，有，不然就违反公平性。由于在中可以有个人被学校录取，我们必然有，而且。由于偏好是严格的，我们必然有；这样我们得到，且。对于任意的，和上面同样的推理我们可以得到，并且。这个推理可以一直进行下去，这和学生人数有限相矛盾，因此前提不成立，只有一个纳什均衡结果。 上面的定理表明，在知分报考的高考博弈中，博弈的纯策略均衡结果是唯一的，这个结果是公平的。但是这个博弈的均衡策略不一定唯一，并且真实策略并不一定均衡策略。我们用下面的例子说明高考招生的过程和高考博弈。例： 这里有三个学生和两所学校，表示不上学。每个学校的招生名额，学生的成绩和偏好如下 如果考生都真实的申报自己的志愿，在高考机制的录取结果是：第一轮，考虑所有学生的第一志愿，学生投档到学校，学生被投档到学校。学校按照考分从低到高录取。学校录取学生，学生被拒绝；学生被学校录取。两所学校都用完了招生名额。第二轮 考虑没有被录取的学生的第二志愿。但是所有的学校都已经录取满额，录取结束，高考落榜。这样，学生真实申报志愿的录取结果是。但是真实申报志愿不是的最优策略。给定其他人的真实志愿，可以填报，这样录取的结果是。可以验证，志愿组合是一个纳什均衡。在这个简单的高考博弈中，所有的纯策略纳什均衡为志愿组合，其中的志愿是任意一个排列。所有这些纳什均衡的结果都是。 上面的例子表明，在知分报考的高考博弈中，博弈的纯策略均衡结果是唯一的，这个结果是公平的。但是这个博弈的均衡策略不唯一，并且真实策略并不是均衡策略，这样，协调到均衡就是一个艰巨的任务。在实际报考中也存在协调的努力，各学校，各市都举办考前志愿预报来协调本地区考生之间的志愿，避免报考志愿的过度集中。这些协调的规模与实际招生的规模相比很小，每个考生也仍然很难调整到均衡的策略。是否存在一种招生机制，使得每个学生的真实偏好是他的均衡策略呢？仍然以上面的例子，我们介绍下面的GaleShapley学生最优机制，在所有考生真实申报自己的偏好的情况时，可以达到当前的高考同样的均衡结果。Gale-Shapley学生最优机制：第一轮，所有学生向可接受的学校中的第一志愿申请，学生投档到学校，学生投档到学校。学校按照考分从高到低录取。学生被学校预录取，学生被拒绝；学生被学校预录取。两所学校都用完了招生名额。第二轮 考虑上一轮被拒绝的学生，向没有拒绝过他的可接受的学校中最偏好的学校申请。学生向学校申请。学校考虑新的学生和上一轮预录取的学生，学生被拒绝，被学校预录取。学校没有申请的学生。第三轮 考虑上一轮被拒绝的学生。但是学生没有可接受的学校，停止申请。没有学校拒绝申请，学校录取程序结束。在学校预录取名单上的学生被正式录取，没有被任何学校录取的学生落榜。最后的录取结果是：。 我们看到上面的招生机制在所有考生真是显示偏好的情况下，达到了和高考同样的招生结果。并且，我们在下面证明，在这种机制下每个考生真实显示自己的偏好是他的占优策略。四、GaleShapley学生最优机制大学招生模型（Gale&Shapley,1962）由组成，包括一组学生和一组学校的集合 ，每个学校有固定的招生人数向量 。每一个学生对所有学校和不上学的选择有一个严格的偏好，同时，每个学校有一个对学生集合的严格偏好 关于学校的偏好讨论，参见Roth(1985)7。，这里，学校对所有学生组合包括空集的偏好，是定义在学生集合的子集上。对于任何，我们令表示其他学校的偏好。我们用和表示分别和相应的非严格偏好。在下文中，我们固定学生和学校的集合和。高考和大学招生模型有着一个重要的不同之处：在大学招生模型中，学生和学校都是参与人，他们同时可以策略的表示自己的偏好。而在高考制度中，大学按照学生的考分高低录取学生，几乎没有自己的选择，大学是所有学生共同拥有的公共资源，按照考分高低和学生的志愿分配到学生，这里只有学生是积极行动的参与人。但是，我们可以通过考生的分数构造每个大学的偏好，就把高考问题转化相应的大学招生模型。因为考生在学校的录取是由他的考分排序决定的，给定一个高考我们通过考生的分数可以构造大学的偏好。对于所有的大学，它的偏好满足：对所有的，当且仅当，并且对所有的，。这里，表示一个学生也不录取的选择。这样，在高考相应的大学招生模型中所有的学校对考生有相同的偏好。 同样，前面定义的匹配和个人理性的概念仍适用于大学招生模型。在高考博弈中，高考招生程序对于给定的得到一个学生和学校的匹配方案。这里，一个机制就是一组程序，对于给定的大学招生问题得到一个学生和学校的匹配方案。在大学招生模型中，一个非常重要的概念是稳定性（Stable）。一个学生和学校的组合破坏（block）了一个匹配，如果：，并且；或者，并且存在，。如果一个匹配是个人理性的，并且不会被任何学生和学校的组合破坏，那么这个匹配是稳定的。由定义我们看到稳定性和公平有很大的关联，一个匹配是稳定的当且仅当它是个人理性的，没有浪费和公平的。从我们前面的证明可知，高考博弈的纳什均衡结果是一个稳定的匹配。 Gale和Shapley（1962）证明了稳定的匹配总是存在的，并且在所有的稳定匹配中，存在一个匹配对于学生来说是帕累托最优的，他们并提出了如下达到学生最优匹配的机制，这个机制可以通过延迟接受学生申请机制达到。GaleShapley学生最优机制：第1轮 所有的学生向他接受的大学中的第一志愿学校申请。每一所大学从所有申请的学生中留下最好的个学生，其他的学生都被拒绝，进入下一轮申请。被留下的个学生计入预录名单。如果申请学生不足个，就预录所有的学生。第2轮 所有被拒绝的学生向他可接受并且没有拒绝过他的大学中的最好的志愿学校申请。每一所大学考虑所有本轮申请的学生和上一轮留在预录名单上的学生，从中留下最好的个学生，拒绝其他学生。被拒绝的学生进入下一轮申请，留下的个学生计入预录名单。一般来说，第k轮 所有在上一轮被拒绝的学生向他可接受并且没有拒绝过他的大学中的最好的志愿学校申请。如果没有可接受的学校，这各学生就停止申请。每一所大学考虑本轮所有申请的学生和上一轮留在预录名单上的学生，从中留下最好的个学生，拒绝其他学生。被拒绝的学生进入下一轮申请，留下的个学生计入预录名单。当没有学生的申请被拒绝的时候，这个录取程序就停止。由于学生和学校的数目有限这个过程一定会在有限步后停止，所有留在预录名单上的学生就被学校正式录取。如果一个学生被所有的学校拒绝，那么这个学生就落榜了。通过GaleShapley学生最优机制可以达到学生最优的稳定匹配，我们在前文的例子中已经见到这一点。在高考招生对应的特殊的大学招生模型中，所有的学校的偏好都相同。这时，只存在唯一的稳定匹配。为了说明这一点，我们在前面已经得到高考机制的纳什博弈均衡结果是一个稳定匹配。反过来，每一个稳定的匹配都是一个纳什均衡结果。定理4： 每一个稳定的匹配都可以作为一个高考机制的均衡结果。证明: 设是一个稳定的匹配，我们考虑如下的策略组合，其中学生的策略把他的匹配作为第一志愿，其他的学校都不可接受。这时，通过高考机制我们必然有。对于学生如果存在一个策略使得，这里是学生的真实偏好，必然有或者存在，但这和匹配稳定矛盾。结合我们证明的高考博弈结果的唯一性，我们得到在高考问题对应的大学招生模型中稳定的匹配是唯一的。通过高考博弈的均衡和GaleShapley学生最优机制，我们都可以达到这个稳定匹配。在GaleShapley大学招生模型中，与学生最优机制相应的还有大学最优机制，这个机制和学生最优机制的不同在于每一轮中是大学申请，由考生决定学校是否可以接受。Gale和Shapley（1962）证明学生最优机制和学校最优机制都可以达到稳定的匹配。由于这里稳定匹配集合的唯一性，我们知道GaleShapley学校最优机制也可以达到相同的稳定匹配。这个机制也可以如下进行，现把所有考生按分数从高到低排序，然后从高分到低分一次一个依次录取。第一个考生从所有招生学校中，选择他最偏好的学校。如果一个学校已经招满，就停止招生。一般来说，第k个考生从所有仍招生的学校中选择他最偏好的学校，如果没有愿意的学校，他选择不上学。这样下去，直到所有的考生都轮完或者所有的学校的招生名额用完，招生停止，剩下的考生落榜。这个招生机制也是北京市中考录取的机制。但是和高考博弈相比，GaleShapley学生最优机制还有一些吸引人的特征：定理 5（Dubins 和Freedman12,;Roth11）GaleShapley学生最优机制是Strategyproof.在高考博弈中，每个人很难知道在这个博弈中自己的最优策略是什么；在GaleShapley学生最优机制下，每个人的真实偏好就是他的占优策略，填报自己真实的偏好得到的结果不比任何其他的志愿来得差。在GaleShapley学生最优机制下，考生不需要担心他由于填报志愿不当而丧失了他的考分的优先性。这样，就没有考前，考后和估计分数报考的区别，考生的志愿和考试分数分开，使得考分真正的发挥分配的作用。在高考招生中，分数的面前的公平性是实际操作中基本要求，考分高的学生有更大的优先性录取到偏好的学校。高考招生博弈的均衡是公平的，但我们也有：定理 6（Gale&Shapley1，Michel Balinski;Tayfun,Sönmez3）GaleShapley学生最优机制帕累托占优任何公平机制。 这个定理得含义是给定一个招生问题，任何产生最后录取结果是公平匹配的机制得到结果都不会帕累托占优按照GaleShapley学生最优机制录取得到的结果。我们前文中的例子已经看到，高考招生博弈的纳什均衡结果和GaleShapley学生最优机制录取得到的结果一致就是这个定理得一个说明，并且这个性质对于任何的公平机制都是成立的。因此，Gale-Shapley 学生最优机制帕累托占优当前的高考录取机制。定理 7 (Alcalde&Barbera13)在大学招生问题中，Gale-Shapley学生最优机制是唯一的个人理性，没有浪费和公平，Strategyproof的学生录取机制。 这个定理刻画了在大学招生问题中GaleShapley学生最优机制的唯一性。任何要做到使得录取结果满足个人理性，没有浪费和分数公平，并且考生真实申报自己的学校偏好是占优策略的机制只能是GaleShapley学生最优机制。分数的公平性，一方面是在在高考录取过程中，一个学生的考分是他能否被学校录取的重要指标。公平性的另一方面，是学生录取机制应当尊重学生的考分，当一个学生的考分提高时，他所能达到的学校不会比他分数低时所能达到的学校还差。这样的机制就是尊重考分的机制。同样，Gale-Shapley学生最优机制具有这样的优点：定理 8：（Balinski, Michel; Sönmez, Tayfun3）唯一的尊重学生考分进步，并且满足个人理性，没有浪费和公平的学生录取机制是Gale-Shapley 学生最优机制。 以上这些定理表明，如果高考制度仍然是用统一考试和分数公平来决定录取，Gale-Shapley 学生最优机制具有许多有些性质优于当前的高考录取机制。五、总结 在高考的分数公平原则下，由于录取机制的第一志愿优先，使得高考的录取成了一个几百完考生参加的协调博弈。虽然存在唯一的均衡结果，但考生的真实偏好并不总是他的均衡策略，多重均衡和巨大的参与人数使得如何协调到一个均衡对所有考生都几乎不可能的事情。使用GaleShapley学生最优机制可以达到同样的录取结果。与当前的高考录取制度相比，GaleShapley学生最优机制具有一系列的优良性质，而且这个机制也已经在实践中被使用（Roth）。在GaleShapley学生最优机制的录取机制下，考生的真实偏好是他的占优策略，这个机制是唯一的满足个人理性，没有浪费和分数公平，并且尊重考生分数进步的学生录取机制。满足学生的真实志愿，是进一步最求知识的动力。如果改革录取方式，必然带来巨大的效率改进，省却无数家庭的烦恼和焦虑。参考文献：1 Gale, David; Shapley,Lloyd, College admissions and the stability of marriage J. American Mathematical Monthly, 1962, 69(1): 9-152 Roth, A. E.,Sotomayor, M., Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis M, Cambridge Univ. Press, London/New York, 19903 Balinski, Michel; Sonmez Tayfun, “A Tale of Two Mechanisms: Student Placement J. Journal of Economic Theory, 1999, 84(1): 73-944 Abdulkadiroglu, Atila; Sonmez, Tayfun, School Choice: A Mechanism Design Approach J, American Economic Review, 2003, 93(3):
