一、先替一个学生出主意
说明: 这是一篇案例,涉及真实的机构和数字。我核对到出处的事实会写明出处;只有二手转述或我没核对的,会明确标出;为演示逻辑而编的例子,会写"编的"。
请你想象这样一个场景。一座城市里,三个孩子要报三所学校,每所学校只有一个名额。三个孩子是你、小周和小林,你为自己报志愿。
学校按自己的优先顺序挑学生(比如离家近、有兄弟姐妹在读、成绩),三所学校的优先顺序是:
- 学校 X:小周 > 你 > 小林;
- 学校 Y:你 > 小林 > 小周;
- 学校 Z:你 > 小周 > 小林。
三个孩子的真实心愿是:
- 你:X > Y > Z;
- 小周:X > Z > Y;
- 小林:Y > X > Z。
现在规则是这样:每个孩子交一张志愿表。第一轮,所有孩子都去申请自己的第一志愿;每所学校按优先顺序录取,名额满了就不再收,被录取的孩子就定下来了。没被录取的孩子,第二轮申请自己的第二志愿,以此类推。(这是波士顿规则,下面会讲它的来历。)
先别往下读。请你想一想:你应该在志愿表的第一位填什么?是你真正最想去的 X,还是别的?
我们来算一算。
如果你如实填(X > Y > Z),小周也如实填,小林也如实填:
- 第一轮:你和小周都申请 X,小林申请 Y。X 按优先顺序录取小周(小周比你靠前);Y 录取小林。你被拒。
- 第二轮:你申请第二志愿 Y,可是 Y 的名额在第一轮已经被小林占了,你被拒。
- 第三轮:你去 Z,录取。
你最后去了 Z,是你最不想去的学校。 可是请你注意:你在学校 Y 的优先顺序,比小林更高。 如果你一开始就申请 Y,你本来可以得到它。
如果你把 Y 填在第一位(Y > X > Z):第一轮,你和小林都申请 Y,Y 按优先顺序录取你;小周拿到 X;小林被拒,后来去了 Z。你拿到了 Y,比 Z 好。
也就是说,在这个规则下,如实填志愿,反而吃亏。 这个现象,是这篇案例的主角。
二、第一个故事:医学生与医院
先讲一个更老的故事。美国的医学生毕业后,要去医院做住院医师。每年有大批学生要和医院的岗位互相选择。
据 Roth 1984 年的论文《医学实习生和住院医师劳动市场的演变:博弈论的案例研究》(《政治经济学杂志》92 卷第 6 期,991–1016 页),这个市场的组织方式,在 1951 年形成了现在的样子之前,经历了好几次变化;那些变化的记录,给研究这类市场的规律提供了难得的机会。论文用博弈论解释了今天这套办法为什么能有序运行、持续这么久,而早先的几次短命的尝试,则一片混乱。
这套 1951 年定下来的办法,就是全国住院医师匹配项目(NRMP)。据通行的说法,Roth 发现,它实际使用的算法,和后来 Gale 和 Shapley 在理论里提出的"医院提议的延迟接受"本质上是同一个。(这一点我没有读到全文,只能转述。)
“稳定"为什么重要
这套办法的核心性质是稳定:没有一对学生和医院,互相更喜欢对方,而不是各自被分到的。 如果存在这样一对,这一对完全可以在系统之外私下说好:医院绕开系统,直接发 offer,学生绕开系统直接接受。这样,系统就垮了。所以一个不稳定的匹配办法,会被大家绕开。
Roth 1991 年(《美国经济评论》81 卷第 3 期,415–440 页)研究了英国的七个地区性的新医生劳动市场。据摘要,这些市场和美国一样都曾经历失败,后来采用了各种集中办法。因为不同地区用了不同的办法,它们构成了一个"自然实验”,检验美国市场的成功是否来自它产生了稳定匹配。摘要的结论是:在参与者可以利用不稳定的环境里,产生不稳定匹配的集中办法,表现不比它们取代的分散市场更好;稳定性在英国这些更复杂的市场里同样重要。
后来,这套办法在 1990 年代末重新设计。Roth 和 Peranson 1999 年(《美国经济评论》89 卷第 4 期,748–780 页)的论文,据摘要,报告了全国住院医师匹配项目新设计的清算机制(据摘要,每年为约两万名新医生匹配岗位)。现实里有很多"互补性"(比如夫妻想去同一座城市),简单匹配理论不能直接用;可是计算实验表明,理论仍然是一个很好的近似;作者给出的一个解释是:每个申请人只面试全部岗位中的一小部分。
夫妻问题值得单独说一句。当两个学生是一对,想去同一座城市的两家医院,这对夫妻对两个岗位的偏好是"捆绑"的。据通行的结论,一旦有夫妻,稳定匹配可能不存在。(我没有核对例子。)这是理论和现实的一个典型落差,也是 Roth 和 Peranson 要用工程的办法去应对的地方。
三、第二个故事:孩子与学校
学校选择的故事,要从你刚才算的那个小例子说起。
在波士顿,家长要为孩子报志愿,学校按优先顺序录取(据一般的叙述,优先顺序包括是否住在学校附近、是否有兄弟姐妹在读等)。Abdulkadiroğlu 和 Sönmez 2003 年的《学校选择:一个机制设计的方法》(《美国经济评论》93 卷第 3 期;这次我没核对页码)分析了这类规则,指出了波士顿规则的问题。据 The Boston Public School Match 一文的叙述,那篇论文发表之后,一名《波士顿环球报》的记者找到作者,询问波士顿学校的分配办法,后来才有了波士顿的改革工作。2005 年 7 月,波士顿学校委员会投票决定,用延迟接受机制取代原来的办法(据 NBER 工作稿的摘要)。
纽约市的故事是:纽约要为每年九万多名初中毕业生分配公立高中。据 Abdulkadiroğlu、Pathak 和 Roth 2005 年的短文(《美国经济评论》95 卷第 2 期,364–367 页),原来的办法是三轮分散的"提 offer、接受、等候名单"。新办法在 2003–2004 学年第一次使用,是一个单一 offer的学生提议延迟接受。据该文,第一年大约 3000 名学生被分到了自己没有填过的学校,是上一年同类分配数的 10%。(由此推算,上一年大约有 3 万名学生是这样的,这是我的推算,原文没有直接给这个数。)
四、两个规则,算一遍
回到开头的小例子。我们再用延迟接受的规则做一遍。
延迟接受:每一轮,所有没被"暂时接受"的孩子,申请自己下一个还没申请过的志愿。每所学校暂时留下优先顺序最高的学生(不超过名额),其余的拒绝。被拒的孩子下一轮继续申请下一个志愿。直到没人被拒。“暂时"二字很关键:被留下的学生,如果后来有优先顺序更高的人来申请,会被换掉。
三个孩子都如实填志愿:
- 第一轮:你和小周申请 X,小林申请 Y。X 暂时留下小周,拒绝你;Y 暂时留下小林。
- 第二轮:你申请第二志愿 Y。Y 里有小林,你的优先顺序比小林高,Y 换成你,拒绝小林。
- 第三轮:小林申请第二志愿 X。X 里有小周,小周的优先顺序比小林高,拒绝小林。
- 第四轮:小林申请 Z,Z 空着,留下。
结果:你去 Y,小周去 X,小林去 Z。
| 真实志愿 | 波士顿规则:都如实填 | 波士顿规则:你把 Y 填在第一位 | 延迟接受:都如实填 | |
|---|---|---|---|---|
| 你 | X > Y > Z | Z(第 3 志愿) | Y(第 2 志愿) | Y(第 2 志愿) |
| 小周 | X > Z > Y | X(第 1 志愿) | X(第 1 志愿) | X(第 1 志愿) |
| 小林 | Y > X > Z | Y(第 1 志愿) | Z(第 3 志愿) | Z(第 3 志愿) |
看这张表,有几件事:
- 波士顿规则下,如实填的你吃亏了;你得 Z,而你在 Y 的优先顺序明明高于小林,这是不公平的:你有正当的怨言(学校 Y 的优先顺序里你在小林前面,你却没被分到 Y)。
- 波士顿规则里,会算计的人占便宜:你把 Y 填在第一位,得到了 Y;可是小林因此从 Y 掉到了 Z。如果小林是个老实人,小林就是被"会算计的人"挤掉的。
- 延迟接受下,如实填就够了:你不需要耍心眼。我把你的六种填法都试了一遍:在延迟接受下,只要把 Y 排在 Z 的前面,就能拿到 Y(如实填的 X > Y > Z 正是其中之一);没有任何填法能让你拿到 X,因为你在 X 的优先顺序低于小周。如实填的结果,就是你能得到的最好结果,没有任何谎报能让你更好。
⚠️ 这里第一次读,容易有一个误会:“延迟接受不就是让大家都满意吗?” 不是。小林拿到了 Z,是小林的第三志愿。 延迟接受没有让每个人满意,它保证的是:没有人有正当的怨言(在这个例子里,小林在 X 和 Y 的优先顺序都不够高,所以拿不到更好的),以及没有人需要为了得到更好的结果而说谎。
为什么波士顿规则会这样
波士顿规则里,第一轮被录取的人,当场就定下来了,后来优先顺序更高的人也挤不掉。这就是你吃亏的原因:你第一志愿是 X,被拒之后第二志愿 Y 已经"满"了,哪怕你在 Y 的优先顺序比占着的小林更高。
延迟接受里,“暂时"留下的人可以被换掉,所以你可以放心地先申请自己最想去的 X,被拒了再去 Y,Y 里有人也没关系,你的优先顺序更高就能把人换下来。
五、现实不是教科书
上面的小例子里,学校的优先顺序是严格的、清楚的。现实里往往不是。
并列和抽签
很多学校的优先顺序里,一大批学生是并列的(比如同一个片区的学生都是"同等优先”)。这时要用抽签来打破并列。这看起来很公平,可是会带来新问题。
用一个编的小例子(我用程序对所有抽签顺序都算过)说明。三个学生 a、b、c,三所学校 X、Y、Z,各一个名额。
- 学生的志愿:a:Y > X > Z;b:Y > Z > X;c:Z > Y > X。
- 学校的优先顺序:X 里 c 最高,a 和 b 并列;Y 里 c 最高,a 和 b 并列;Z 里 b 和 c 并列最高,a 最低。
用延迟接受,按抽签结果打破并列。抽签顺序是 a 先、b 次之、c 最后时,结果是:a 去 X,c 去 Y,b 去 Z,三个人都拿到第 2 志愿。
可是还有另一个分配:a 仍去 X,b 去 Y,c 去 Z。b 和 c 都拿到了第 1 志愿,a 没有变差。而且,这个分配没有违反任何学校的优先顺序,只是用到了并列之间的自由。
在这个例子里,6 种抽签顺序只有 1 种会得到前面这个"本可以更好"的结果;其余 5 种里,都没有办法在不伤害任何人的前提下让谁更好。可是这说明了一个深刻的道理:说真话(策略无关)和效率,在有并列的时候,可能冲突。 Abdulkadiroğlu、Pathak 和 Roth 在 2009 年的论文《有并列时的策略无关与效率之间:重新设计纽约市高中匹配》(《美国经济评论》99 卷第 5 期,页码我没核对)就是在讨论这个问题。(我只核对到题目和出处,没读到摘要的细节。)
复杂的现实
| 现实里的复杂 | 带来什么问题 |
|---|---|
| 夫妻要同城 | 稳定匹配可能不存在(据通行的结论) |
| 并列和抽签 | 说真话和效率可能冲突 |
| 志愿表的长度有上限 | 家长要在"稳妥"和"冒险"之间取舍 |
| 学校的名额、优先权规则复杂 | 算法要处理很多约束 |
| 家长不一定懂规则 | 老实人吃亏,会算计的人占便宜 |
中国的高考录取
中国的读者可以顺着这个思路想想高考录取。Chen 和 Kesten 2017 年的《中国高校录取与学校选择改革:一个理论分析》(《政治经济学杂志》125 卷第 1 期,99–139 页),据摘要,开头写道:中国约有 1000 万高三学生,竞争约 600 万个大学名额(以论文写作时的数字为准)。作者刻画了一个参数化的机制家族,里面包含顺序机制(类似波士顿规则)、延迟接受和平行机制这三类。据通行的说法,中国许多省份使用的"平行志愿”,对应的是其中的平行机制;这一点请以论文为准。
六、证据、局限和分歧
理论预测。
- 波士顿规则:如实填可能吃亏,会算计的人占便宜;
- 延迟接受:说真话是最优的,而且没有人有正当的怨言;
- 有并列时:说真话和效率可能冲突;
- 有夫妻时:稳定匹配可能不存在。
证据(我核对的是出处和摘要层,没有读全文):
- Roth 1984(JPE 92(6):991–1016,摘要):1951 年形成的现行市场,与之前短命的尝试对比;
- Roth 1991(AER 81(3):415–440,摘要):英国地区市场的"自然实验",不稳定的集中机制不比分散市场更好;
- Roth 和 Peranson 1999(AER 89(4):748–780,摘要):NRMP 的重新设计;
- Abdulkadiroğlu、Pathak 和 Roth 2005(AER P&P 95(2):364–367):纽约,约 3000 名学生被分到没填过的学校,为上一年的 10%;
- 波士顿 2005 年 7 月改用延迟接受(NBER 工作稿摘要);
- Chen 和 Kesten 2017(JPE 125(1):99–139,摘要);
- 2012 年诺贝尔经济学奖授予 Shapley 和 Roth,授奖词是"稳定分配理论和市场设计的实践"。
局限。
- 小例子是编的,三个学生三所学校,不代表真实规模;
- 现实里,家长的行为受信息、情绪、文化的影响,不一定是教科书里的"最优反应";
- “稳定"是一个很强的好性质,但不是唯一的好性质:它不保证每个人都满意,也不保证社会总体最好。
分歧(事实问题和价值问题要分开)。
- 事实问题:老办法下,有多少家长真的"耍心眼”?有多少老实人真的吃了亏?新办法改了之后,家长是不是真的更放心?这需要具体的数据。
- 价值问题:学校的优先权,该怎么定? “离家近"优先、“有兄弟姐妹在读"优先、“成绩"优先,各有各的道理,各有各的代价(比如"离家近"会让好学校周围的房价上涨,让穷人更难进)。说真话重要,还是总体效率重要? 有并列时两者可能冲突,选哪个,是价值判断。这些问题,匹配理论能告诉你"某个规则会导致什么”,不能替你决定"你想要什么”。
七、小结
- 波士顿规则:第一轮被录取的人当场定下来。如实填志愿的人可能吃亏;会算计的人占便宜,老实人被挤掉。
- 延迟接受:被录取的人只是"暂时"留下,可以被换掉。说真话是最优的;没有人有正当的怨言;不保证每个人都满意。
- 例子:三个孩子三所学校,波士顿规则下你如实填去了 Z,把 Y 填在第一位去了 Y(小林从 Y 掉到 Z);延迟接受下如实填就去 Y。
- 医学生匹配:1951 年定型(Roth 1984);英国的"自然实验”(Roth 1991)表明稳定性重要;1990 年代末重新设计(Roth 和 Peranson 1999)。
- 学校选择:波士顿 2005 年改用延迟接受;纽约 2003–2004 学年起,用单一 offer 的延迟接受,约 3000 人被分到没填过的学校,为上一年的 10%。
- 并列:说真话和效率可能冲突;例子里 6 种抽签顺序有 1 种不够好。
- 现实的复杂:夫妻、并列、志愿表上限、复杂的优先权。
- 分歧:有多少人"耍心眼"是事实问题;优先权怎么定、说真话与效率谁重要,是价值问题。
下次你听到"按志愿录取",请想一想:这个规则会不会让如实填志愿的人吃亏?学校的优先顺序里,有没有并列?谁来承担"打破并列"的结果?
思考题
- 开头的例子里,把学校 Y 的优先顺序改成小林 > 你 > 小周(其他不变)。用延迟接受,三个孩子如实填志愿,结果是什么?波士顿规则呢?
- 开头的例子(Y:你 > 小林 > 小周)。在波士顿规则下,你把志愿表的前几位换着填,一共有 6 种填法,分别能让你去哪所学校?只有哪几种能让你去 Y?
- 在同一个例子里,小林想通过改填志愿表得到比 Z 更好的学校。在延迟接受下可能吗?在波士顿规则下呢?(小林如实填是 Y > X > Z,你和小周如实填。)
- 并列的例子里,抽签顺序是 b 先、a 次之、c 最后时,延迟接受的结果是什么?它是不是"本可以更好"的分配?
- 纽约新办法的第一年,约 3000 名学生被分到没填过的学校,是上一年同类分配数的 10%。那么上一年大约是多少?这个数字能不能说明"新办法一定更好"?你还想看什么证据?
- 想一个你身边"按志愿分配"的场景(选课、宿舍、岗位、志愿填报)。它的规则更像波士顿规则,还是延迟接受?如实填志愿会不会吃亏?哪些是事实问题,哪些是价值问题?
思考题提示
- 延迟接受:第一轮,你和小周申请 X,小林申请 Y:X 留小周,Y 留小林;你被拒。第二轮,你申请 Y,Y 的优先顺序小林在你前面,拒绝你。第三轮,你申请 Z,留下。结果:小周去 X,小林去 Y,你去 Z。波士顿规则:第一轮小周得 X、小林得 Y;第二轮你申请的 Y 已满;第三轮去 Z。结果同样是你去 Z、小周去 X、小林去 Y(这时你在 Y 没有优先权,Y 给小林是对的,没有人有正当的怨言)。
- 六种填法在波士顿规则下的结果:X>Y>Z → Z;X>Z>Y → Z;Y>X>Z → Y;Y>Z>X → Y;Z>X>Y → Z;Z>Y>X → Z。只有把 Y 填在第一位才能去 Y。
- 延迟接受下,小林的六种填法都得到 Z,没有更好的结果,所以谎报没有用。波士顿规则下,小林把 Y 放在第一位(也就是如实填)得到 Y;把 X 或 Z 放在第一位得到 Z。所以在你如实填的前提下,小林在波士顿规则下的最佳填法,恰好就是如实填(Y 放第一位);可是一旦你把 Y 填到第一位,小林就会掉到 Z。
- 抽签顺序 b、a、c:延迟接受的结果是 a 去 X,b 去 Y,c 去 Z。a 第 2 志愿,b、c 第 1 志愿。不是“本可以更好"的分配(它就是例子里右边那个分配)。
- 3000 ÷ 10% = 30000(推算,原文没有直接给)。不能说明"一定更好”:没分到没填的学校,只说明少了"没填的",不说明大家的满意度、公平性、学校的整体表现;还想看:被分到第一志愿的比例、不同学生群体之间的差异、家长的感受。
- 开放题。例如选修课按"志愿 + 先到先得":看你的规则是不是"第一轮定死"。事实问题:如实填的人是不是真的吃亏;价值问题:是否该优先照顾某一类学生。