一个算法解决高考填报志愿难题｜BetterRead

文｜王烁

博弈论、机制设计和实验经济学大家，2012年诺奖得主Alvin E. Roth刚出新书《谁得到啥？为什么？》（Who Gets What and Why，简称WWW），介绍市场设计（market design）。市场设计正是Roth的看家成就，此前都是论文，对普通人有如天书，WWW是他面向大众的惟一一本通俗读物，

自由市场概念，与物理学中无外力作用则匀速运动中的物体永远保持匀速运动的概念类似，而现实中多是匹配市场（matching market），即双向选择、并非完全由价格决定而有时完全不由价格决定的市场。这种市场比比皆是：大学招生，宿舍分配，器官分配。Roth的研究，揭示如何激发参与者如实披露其偏好信息，增加市场厚度（thick），减少拥塞（congestion），使市场安全、简便。这些不是象牙塔学问，确能济世。

不过，这书结构很怪。前半部分好比VCR快进，先把要涉及的主题匆匆扫射一遍，在后半部分才进入具体状况；又好比货贩把货藏在深处，在外放乏味的长篇广告。这种结构既罕见又没有好处，Roth精通市场设计，可完全不懂营销或者用户体验。

好在还是有货。

搞明白著名的延迟接受算法（deferred acceptance algorithm）是怎么回事了。

用高考填报志愿来解释。

每年高考，考生要填写第一志愿、第二志愿、第三志愿。考生会按自己心目中的顺序填志愿吗？最顶尖的考生也许会，但大多数有望考上大学但没把握上更好大学的学生不会。他们最想上的可能是北大，但如果填北大而未被录取，基本上就丧失了上重点大学的机会。所有重点大学都只录取那些填他们为第一志愿的考生。所以，考生不得不策略性地（strategically）填报志愿，将最有把握考上的重点大学填入第一志愿，同理类推。

博弈志愿填报的坏处，考生及家长心知肚明：如果考生最终发挥出色，成绩能上北大，但为了保险没有填报北大，则成人生遗憾。对北大也有坏处，因为北大没能把成绩最好又有意报考的考生都招进来，在这个假设的案例中，至少存在一位录取的考生成绩会差于那位策略性填报志愿的考生。

双输。

现在高考填报志愿的程序改了，大多数地方是公布考分后再填报志愿，考生比过往多了些把握，但需要博弈志愿填报的逻辑还在，不信，请问刚刚获知今年高考成绩的那些考生及其家长；造成双输的困境也还在。

解决这个问题，避免策略性填报志愿给考生和大学带来的双输风险，Lloyd S. Shapley和Alvin E. Roth有好办法。这个办法为他们带来了诺贝尔经济学奖。

第一步，考生填报志愿时，将心仪的大学按顺序列表，类似于过往的第一志愿、第二志愿、第三志愿，不同之处是现在这个列表越长越好，至少要有十几家大学，理论上，如果有这个精力，把所有大学都排出序来也行，虽然没必要做得这么绝。

考生需要做的就这一件事，接下来的事交给延迟接受算法。

第二步，每家大学按其招生人数计划向看中的考生发出对应数量的录取通知。优秀考生获得很多通知怎么办？算法为考生自动接受在他的优先列表上排在最前面的大学，并拒掉其他大学。注意，这里是关键，接受是暂时的（tentative），并未最终生效，这也是算法之所以得名“延迟接受”的原因。

第三步，必然有一些大学发出的部分录取通知被考生拒掉，于是，这些大学向不在其第一轮通知名单上的其他考生，发出新一轮录取通知，数量等同于被拒的录取通知数。如果这些考生收到了不止一个通知，已“暂时接受”其他大学的录取通知，则系统再度自动“暂时接受”在其列表上靠前的大学录取通知，拒掉其他。

这些步骤都是算法代劳，自动实现。

如此这般往复。。。

如此这般往复。。。

如此这般往复。。。

直到最后一步，当再也没有录取通知被考生拒掉时，市场出清，所有“暂时接受”的录取通知于此时一同生效，算法达成一个美妙的结果：考生要么上了其首选的大学，要么虽然没上成首选大学但他进入次选次次选次次次选大学的机会没有因此受到任何影响。

也就是说，考生可以而且应该按其心目中的真实顺序列出心仪大学的列表，不再需要担心为此付出代价：能力说话，考分说话，进入与自己的能力与考分相称的那家大学。人生已有太多遗憾，不应该在填报志愿这一环节为年轻人继续留下遗憾。

延迟接受算法已用于纽约、波士顿等地的幼升小、小升初招生，用于医院招募住院医生，用于求职，它或多或少适用于几乎任何不能由价格完决定的双向选择场景，对中国的大学招生录取，看起来更是绝配。

那么问题来了。

为什么中国的大学招生录取还不采用延迟接受算法？

BetterRead精选