升学是现实生活中大家比较关心的一个问题。升学问题涉及到学生与学校之间的匹配，是一个典型的一对多匹配(one-to-many matching)问题。自Galeand Shapley(1962)提出匹配机制以来，在这一领域已经有了丰富的理论研究成果;而Abdulkadiro(g)lu and S(o)nmez(2003)又提出将双边匹配的理论应用于现实生活中的学生与学校之间的匹配。现在，很多地区（如美国波士顿、纽约市等）的中学生升学方案都以Gale and Shapley(1962)的延迟接受机制替换了从前的择校机制。在我国，也有部分省份（如湖南、江苏等省）借鉴了Gale and Shapley(1962)的延迟接受算法，将高考招生的投档机制由从前的志愿优先改为现在的平行志愿。　　学生与学校的匹配问题可以分为两类:一类是择校问题(school choiceproblem)。在此类问题中，由一个集中的机构给出分配学校席位的机制，并依据学生填报的志愿进行匹配。择校问题中学校的席位一般被视为待分配的公共物品，在考虑分配效率的时候只考察学生的偏好诉求。另一类是学校录取问题(college admission problem)。在录取问题中，学校是主动的一方，他们依据学生申请的情况以及自己对学生的偏好决定录取的学生。录取问题中的匹配双方的偏好诉求都需要被考虑。本文由两篇独立的论文构成，第一篇研究在择校问题中学生的匹配效率改进问题;另一篇研究在离散的录取问题中，学校的录取决策问题。　　在第一章，我们研究了择校问题中的效率改进。在一个择校问题中，每位学生需要向招生机构提交他对学校的偏好序，而每所学校对学生也有各自的录取优先顺序，一个匹配机制需要依据学生偏好序和学校的优先序将学生和学校匹配在一起。通常在择校问题中，学校的录取资格被视为待分配的公共品，因此在考虑分配效率的时候只考察学生的偏好满足的情况，而此时学校的录取优先序便成了学生在对应学校的优先权。对于这样一个匹配问题，Gale and Shapley(1962)提出了学生主动申请延迟接受算法(Student-proposingdeferred acceptance algorithm，也简称DA算法)，该算法总能找到学生最优的稳定的匹配。众所周知，DA算法给出的稳定匹配结果并非总是帕累托有效，例如Abdulkadiro(g)lu et al.(2009)依据纽约市高中录取情况，指出DA算法匹配结果中仍然有近7％的学生有帕累托改进的空间。Kesten(2010)发现，如果部分学生同意放弃他们对部分学校的优先权，这并不会损害他们自己的匹配结果，与此同时帮助其他的同学获得更好的匹配结果;因此他提出了包含同意的择校问题，通过获得同学们的同意，改进匹配的效率。我们从一个新的视角研究这一包含同意的择校问题。　　据我们所知，DA算法的效率损失来自于算法过程中特殊环(Ergin(2002)，Kesten(2010))。具体来说，在DA算法过程中:如果某位学生i申请了学校s并且暂时获得了该学校的录取资格;而学校s因为暂时录取了学生i而拒绝了某位排在其后的学生，这位被拒绝的学生申请了另一所学校继而引起又一位学生被拒绝，如此以往形成了一条拒绝链;若此拒绝链最终导致了学校s拒绝了学生i，我们就说学校的优先序中存在该特殊环。从上面的简单的例子中我们看到，通过申请学校s的行为，学生i本人什么也没有得到，但是引发了一条拒绝链使得在链上的其他学生失去了更好的学校。Kesten(2010)将像学生i这样的参与者命名为学校s的“捣乱者”(interrupter)，并指出“捣乱者”i如果同意放弃在学校s的优先权，允许一位排在其后的学生获得学校s的录取资格，那么他自己匹配的结果并不会变差，而其他的学生将从他的同意中获得更好的学校。　　在一个包含同意的择校问题中，学生们在提交他们的偏好序的同时会被询问这样一个问题:是否同意在不影响他们自己匹配结果的前提下放弃他们在更喜欢的学校中的优先权。在获得部分或全部学生的同意之后，Kesten(2010)设计了效率调整的延迟接受算法机制(efficient-adjusted DA mechanism，简称EADAM)对学生的匹配效率进行改进:在运行完标准的DA算法之后，找到最后一位被拒绝且选择了同意的“捣乱者”以及他所扰乱的学校，将该学校从该学生的偏好中删去，并重新运行DA算法。在反复的运行DA算法和删除被扰乱的学校之后，将得到一个被效率改进的匹配结果。Kesten(2010)在其论文中证明了(1)学生没有动机选择不同意，并且(2)当所有学生都选择同意时，EADAM将得到帕累托有效的结果。　　我们从一个新的视角考察了该包含同意的择校问题:学生选择同意放弃在他们更加喜欢的学校的优先权的动机。我们发现，为保证学生没有动机选择不同意，他们选择同意(1)不会伤害他们的匹配结果，同时(2)也不会伤害他们被改进的机会。所以我们在使用学生的同意的时候，他们应当是不能被帕累托改进的(Pareto unimprovable)学生。为了找到这些不能被改进的学生，我们定义了不被需求的学校(underdemanded school):在一个给定的匹配中的，相比于某所特定的学校，若所有的学生都更喜欢自己匹配到的学校，该所特定的学校就是不被需求的学校。我们证明了在给定的匹配结果中，如果学生匹配上了不被需求的学校，他们将无法被帕累托改进。具体到DA算法给出的匹配结果中，那些在运算过程中从未拒绝过任何学生的学校就是不被需求的学校，而匹配上这类学校的学生是无法被改进的学生。　　通过无法被改进的学生，我们提出了一个新的改进效率的算法:简化的EADAM。在一个包含同意的择校问题中，如果所有的学生都选择了同意，简化的EADAM算法进行如下操作:先运行DA算法，识别无法被改进的学生，将他们连同他们匹配上的学校移出该问题，并重新运行DA算法。通过反复的运行DA算法和移除操作，简化的EADAM将得到一个帕累托有效的结果。假如不是所有学生都选择同意，简化的EADAM仍旧按照上面步骤操作，只是在移除不同意的学生时，将每所他们喜欢的学校中排名在他们后面的学生列为不可接受;如此，在他们被移除后，选择不同意的学生的优先权不会被损害。我们证明了在简化的EADAM算法中，每轮至少有一所学校被认定为不被需求而被移除，因而算法将在至多m+2轮内结束，其中m是学校的数量。此外，我们证明了当所有学生选择同意时，简化的EADAM将得到一个帕累托有效的结果（不被其他匹配帕累托占优）;在部分学生选择同意时，简化的EADAM将得到一个约束下的帕累托有效的结果（可能被其他匹配帕累托占优，但任何帕累托占优于该结果的匹配都损害了至少一位选择不同意的学生的优先权）。　　简化的EADAM在每一轮都有很多的学生和学校被剥离出问题，待解决的问题也更加简单。因此简化的EADAM在计算效率上比Kesten的EADAM算法更加具有优势。我们通过计算机模拟的方式对这二者的计算效率进行了深入比较。　　尽管简化的EADAM与原Kesten(2010)的EADAM在许多方面不同，但是他们的递归结构是一致的。更重要的是，我们证明了Kesten(2010)的EADAM算法中最后一位被拒绝且选择了同意的“捣乱者”也是无法被改进的学生，因此这两种效率改进算法能被统一在“利用不能被改进的学生的同意改进其他学生”这一基本原理下。此外，我们还证明了这两个效率改进算法在结果上是一致的。更一般地说，所有基于“利用不能被改进的学生的同意改进其他学生”这一思路改进DA算法效率的算法，其结果都应该是一致的。　　我们将简化的EADAM算法应用到学校对学生的录取优先序是弱序的择校问题中(Erdil and Ergin(2008))。在弱序问题中，学校可以将多名学生列为相同的录取优先顺序（严格的优先序），并利用一个固定的方式对并列的学生打破僵局(fixed tie-breaking)。但是不合适的的打破僵局规则会造成效率的损失。我们假设所有的学生都不同意放弃严格的优先权，但无法拒绝与他们原本排在同一优先序上但为打破僵局而排在他们后面的同学获得他们更加偏好的学校。我们调整简化的EADAM:每轮运行完DA算法之后，识别所有无法被改进的学生并将他们移除;对每一位将被移除的学生，在他们更加偏好的学校中将严格排在他们后面的学生从学校的优先序中剔除出去，而与他们排在同一严格偏好序的学生将保留在问题中。这种调整过后的简化EADAM，可以被看做是一个特殊版本的Erdil and Ergin(2008)的稳定匹配下的效率改进环机制(stableimprovement cycles mechanism)，在这里改进环的选择是内生的。调整过后的简化EADAM能恢复所有因不合适的打破僵局规则而造成的效率损失，因此得到的匹配结果是约束下帕累托有效的。　　本章内容的主要贡献在于，从一个全新的角度出发研究改进DA算法效率的问题，并提出了一个更加直观且计算效率更高的简化的EADAM。　　在第二章，我们从理论角度研究离散的高校录取问题。集中的匹配市场中存在一个组织者收集参与者的偏好信息并指定匹配结果。例如，在中国的小学升初中、初中升高中的匹配中，由市教育局担任该组织者;在中国高等教育招生考试中（高考），由各省高招办担任组织者。但在现实生活中，更多的匹配市场是由参与者们自行组织匹配过程和决定匹配结果的，并没有一个统一的组织者。例如，毕业生招聘、企业招工市场等。与集中的市场相比，离散市场有诸多特征:首先，由于没有组织者收集和公布参与者的信息，所有的参与者必须在充满不确定性的情况下进行决策。其次，离散市场中信息传递效率低，参与者通常无法调整他们的决策达到市场出清状态。第三，与个人相比，机构在离散市场中有先天的优势，所以在离散市场的匹配过程中，通常是机构方占据主动一方，但同时也是承担风险的一方。由前两条特征可看出离散市场的匹配结果存在很大的效率损失(Roth and Xing(1997));而第三条特征表明，该效率的损失主要由主动的一方承担。我们以美国高校招生为背景，研究离散市场中主动一方（高校）的决策问题。　　让我们先简单看看美国高校在招生市场上面临的难题。在美国，每年有近三百万学生需要匹配上美国的2，675所高校;与之对比的是，高校只有一到两次机会发放他们的录取通知书。学校需要在不确定学生是否入学的情况下做出他们的录取决定。对高校负责招生的人员来说，录取决策是个巨大的挑战，而不合适的录取决定通常会导致招入过多或过少的学生，这都会给学校造成额外的成本。因此，学校作为招生市场上的主动一方，有很强的动机改变他们的决策方法、改善他们匹配的效率。在本文中，我们将站在学校的立场上，从理论角度解决他们在招生决策过程的问题。　　每学年的高校招生通常从每学年9月份学生报名开始，到第二年9月学生入学结束。我们主要关心的问题是学校的招生决策的问题，所以我们将整个招生过程分为录取前的申请阶段以及录取阶段，并将重点放在录取阶段。在申请阶段(application phase)，每名学生需要从众多的高校中选择几所至几十所，并向他们提供申请表、推荐信、以及其他需要的申请材料，这一过程从每学年开始的9月持续至12月。由于学生的申请是有成本的（他们需要缴纳申请费，还要准备申请材料），所以学生必须权衡学校的录取可能性和申请成本，再做申请的决策。我们认为学生的策略行为主要发生在申请决策中，在之后的录取阶段学生只能被动的接受学校的录取决策。在之后一年的1月至3月，学校通过对他的申请者进行材料审核，组织他们进行网络面试、参观校园，或者对他们进行家访等，对申请者进行评估。在申请阶段结束之后，我们认为学生对他们申请的学校已经有了一定的偏好，同时学校对他的申请者们也进行了排序。我们定义了一个包含学生、学校、学生申请情况、学生的偏好、学校的偏好以及计划招生数等信息的高校招生市场(college admission market)来描述申请阶段结束时的状态。该高校招生市场同时也是接下来的录取阶段一个待解决的问题。　　在录取阶段(notification phase),学校需要在规定的时间内给部分申请者发放录取通知书（美国高校统一的发放录取通知书的时间规定为每年的4月1日至5月1日），而学生需要在录取阶段结束前通过接受或拒绝来答复学校的录取通知书。由于每位学生只能进入一所学校，若他过早接受了某所学校，他将错失进入其他更好学校的机会。因此，学生在选择接受的时候会比较谨慎，通常要等到最后时刻才做决定。相比于接受，学生对拒绝不重视，通常他们也会等到最后的时刻才拒绝学校。学校将大部分时间浪费在等待学生答复上，而学生拖延答复的时间造成学校在录取阶段实际上只能发一轮录取通知书。学校需要在不了解其他学校录取决策和学生偏好等信息的条件下进行录取决策。我们用一个同步行动博弈来描述现实中学校面临的录取决策问题。　　我们发现，当学生决定拒绝某学校的时候，他们实际上对及时拒绝与不及时拒绝是无差异的。更具体地说，当某学生收到了部分学校的录取通知书之后，他已经知道他是不会接受那些比已经收到的最好的学校更差的学校（不论该学校是否选择录取他）。对于这些不会被接受的学校，他并没有动机及时拒绝他们。为了鼓励学生尽快的拒绝这些不被接受的学校，我们提出返还申请费规则:学校承诺返还拒绝他的学生部分申请费，并且拒绝的越早返还的越多。由于数额小，返还的申请费不会影响学生对学校的选择;但当最终录取的学校不受影响时，即拒绝那些不被接受的学校时，返还的申请费给学生的拖延增加了额外的成本，因此学生会尽快的拒绝这些不被接受的学校。在收到学生的拒绝之后，学校能够通过发新的录取通知书调整他们的录取决策。对一所采用了返还报名费规则的学校来说，没有拒绝他的学生手上都没有拿到比他更好的学校的录取通知书，即没有拒绝的学生都会接受他。因此我们提出让学校按照他们对学生的排序和招生计划数进行录取的录取规则。　　我们的返还申请费策略由返还申请费规则和录取规则组成。从学校间的录取决策博弈角度看，我们证明了一下结论:对一所学校来说，由返还申请费策略得到的录取学生的集合是在学校的录取决策博弈中的最优决策;而对所有采用返还申请费策略规则的学校来说，他们选择录取的学生集合构成了他们在录取决策博弈中的纳什均衡。从学校的得到的结果看，我们有以下结论:当市场上所有其他学校都采用静态策略时，采用返还申请费策略的结果都不差于任何静态策略的结果，因此返还申请费策略是占优策略;当市场上有部分其他学校采用返还申请费策略时，每一静态策略的结果都不如对应约束下的返还申请费策略的结果，因此可以用该约束下的返还申请费策略代替它。本章中提出的返还报名费的策略能解决高校在离散市场中的录取决策问题。