如何用「延迟接受算法」解决择校问题？ 知乎用户，经济学教师 我争取结合跟国内招生来谈谈。 1. 择校问题和招生问题是同一个问题，主要包括中小学招生和大学招生。招生问题的基本模型是一个双边匹配模型：把学校的座位和学生一对一地匹配起来。学生对学校可以有不同的喜好（术语为偏好），学校对学生也一样。不同国家不同招生问题可能还包括基本模型之外的考虑（例如少数民族照顾政策，平权法案等等），但基本框架都一样。 2. 我们谈算法的时候谈的是招生中的集中录取机制。 国内大学招生是集中录取而中小学招生很大意义上不是（美国是反过来的），男女婚姻匹配在任何地方都不是。集中录取（分配）指的是把学校和学生都集中到一起，双方都只需要向录取机构汇报自己的偏好，然后录取机构跑一下算法决定学生和学校怎么匹配。非集中录取的的典型例子有解放前后的大学录取和申请美国研究生院：学生申请多所学校，学校根据自己偏好录取一部分拒绝一部分学生，学生有多个 offer 可以拒绝掉不会去的学校，这样那些学校可以继续给替补的学生发 offer。但通常学生不会轻易拒绝不要的 offer （可能会拖上一个月）同时想等更好的，导致事实上每所学校能发的 offer 轮次往往不过两三轮。很多学生等不到心仪的学校而被迫接受差的，匹配效率很低。 3. 平行志愿和志愿优先机制。现在大部分省份高考招生用的是平行机制，该机制是 Gale-Shapley 的延迟接受算法（Deferred acceptance algorithm; DA）的一个简单修改版。而直到十多年前，高考招生都用的是志愿优先机制（文献中称作 Boston Mechanism; Boston）。这两个机制的最显著区别在于前者不根据志愿顺序歧视考生，但后者绝对地歧视。 例子： 假定有两所学校和，每所只招一个学生；假定有三个学生；用代表社会大学。学生和学校的偏好以及平行志愿和志愿优先机制运算的过程如下： （每个步骤描述的是学生申请学校和学校的接受 / 拒绝。看懂这两个运算过程并且理解算法的定义不需要额外的文字说明。如果把双方理解为男人 / 女人，容易看出这是个多角恋关系。） DA: Boston: 二者的差异从第二步开始，当被拒绝转而以第二志愿投档到的时候。尽管比第一志愿申请的在优先权更高，在志愿优先机制下由于是第二志愿申请而被歧视。 4. 录取机制的优劣。不同的录取机制有不同的性质，例如平行志愿的结果是稳定的 (stable)，意思是不会有学生更想去某个大学而该大学却录取了比他分数低的人。而志愿优先机制下，高分落榜的例子比比皆是（上例中的）。同时，平行志愿下学生没有“谎报”志愿的激励，而在志愿优先的情形下，学生报志愿需要非常小心地估计自己能考分够上什么学校，按照真实喜好顺序填志愿是很危险的。换言之，志愿优先机制的最大缺点是带给人的不安全感太高，填志愿的时候学生很可能过度谨慎。平行志愿机制本身的一个问题是其匹配结果对于学生可能不是帕累托最优的（上例中和交换学校两个人都会变好），但这不会在高考招生中发生，因为国内大学对学生的偏好排序都是一样的——高考分数越高就越好。 5. 国内高考招生和中小学招生改革。个人认为，高考录取机制有两个需要注意的地方：一，分批录取会带来一定的效率损失，应该整合（似乎正在朝这个方向做）；二，平行志愿填报时候平行的个数可以适当放宽（当然，这是个实证问题）。更重要的是中小学招生改革，对此的实际操作我了解得很少，只能想当然地谈一下。目前国内正在推行的是就近入学，这本身不是不合适，但简单推行的结果是学生和家长的偏好基本没有被考虑，相信有一部分效率损失可以通过设计得到改进。民办学校的集中录取和公办民办之间的协调也是值得考虑的问题。另一相关的问题是教师轮岗的机制设计。 最后，列一篇关于国内高考机制研究的参考文献，作者之一是密歇根大学的 Chen Yan 教授。该文在附录里详细回顾了中国高考改革的历史。其他相关研究可参见该文的参考文献。 References: Chen Yan and Onur Kesten (2014), "Chinese College Admissions and School Choice Reforms: Theory and Experiments", working paper, University of Michigan. 查看知乎原文
