Asymptotic Equivalence of Immediate and Deferred Acceptance

想象一下，你是一位繁忙城市的市长。在这个城市里，每个孩子都需要一个学位，而学校提供的座位数正好等于学生的总数。问题不仅仅是找到一个座位，而是找到一个“合适的”座位。每个家庭都有一份心仪的学校名单，从“我的梦想学校”一直到“实在没办法只能去的学校”。城市也有自己的规则：比如，某些学校会优先考虑住在附近的或者家里已有兄弟姐妹在该校就读的孩子。对于管理者来说，大问题在于：我们如何匹配学生与学校，才能让每个人尽可能地开心？

几十年来，专家们一直在争论两种主要的匹配方式。第一种被称为延迟接受（Deferred Acceptance, DA）。你可以把它想象成一场缓慢而谨慎的舞蹈。学生提交申请，申请他们最喜欢的学校。学校会保留他们最看好的申请人，但不会立即说“是”，而只是说“也许”。如果稍后出现了一位更优秀的申请人，学校可以进行替换。这个过程不断重复，直到所有人最终尘埃落定。这种方法以公平且无法作弊而闻名，但它可能有点繁琐且效率不高。

第二种方法是即时接受（Immediate Acceptance, IA），通常也被称为“波士顿机制”。这更像是一场疯狂的赛跑。学生排队并申请他们的首选学校。学校观察队伍，根据优先级挑选出最心仪的人选，然后立即宣布：“你被录取了！”如果你被拒绝了，你会立即转向你的第二选择。其代价是，如果你申请首选学校的时间太晚，即使你非常渴望那所学校，你也可能会输给那些申请得更早、优先级更高的人。因此，IA 常被批评为不公平或容易被操纵。然而，它有一个巨大的超能力：如果每个人都如实陈述自己的意愿，IA 能保证产生一个“没有人能在不让别人变得不满意的情况下，让自己变得更满意”的结果。这被称为“帕累托效率（Pareto efficiency）”。

所以，这里有一个价值百万美元的问题：IA 的超能力在现实生活中真的能带来巨大差异吗？ 它是否能让孩子们进入比 DA 方法好得多的学校？还是说，这种差异仅仅是一个微小到几乎看不见的斑点？这就是 Josué Ortega 在他的论文中所探讨的谜题。

---

伟大的学校赛跑：两种机制的故事

研究员 Josué Ortega 来自贝尔法斯特女王大学，他决定通过进行一场大规模的思想实验来解决这场争论。他没有去观察那些有着复杂历史和政治背景的真实城市，而是构想了一个“随机市场”——在这个世界里，每个学生的喜好名单都是完全随机抽取的，就像从帽子里抓名字一样。在这个世界里，有 $n$ 个学生和 $n$ 所学校。

Ortega 想衡量的是“平均排名”。想象一下，如果每个学生根据分配到的学校在他们名单上的位置获得一个分数。如果你得到了第 1 志愿，你的排名就是 1；如果你得到了第 100 志愿，你的排名就是 100。目标是让这个数字尽可能低。

长期以来，我们已经知道了关于这种“缓慢而谨慎的舞蹈”（DA）的答案。早在 20 世纪 70 年代，数学家们就发现，在一个随机市场中，学生的平均排名大约是 $\log n$（$n$ 的对数）。如果你有 1,000 名学生，平均排名大约是 7；如果你有 100,000 名学生，平均排名大约是 11。它在增长，但增长得非常缓慢。

但是对于“疯狂的赛跑”（IA）呢？因为 IA 的运作方式不同——申请顺序至关重要，且学生可能仅仅因为“申请晚了”就被拒绝——数学家们认为它可能要复杂得多。一些计算机科学家曾尝试解决这个问题，但他们只能算出获得特定排名的概率，却无法算出所有人的“平均排名”。他们猜测结果也可能是对数级的，但没有人能证明这一点。

“收集者问题”的秘密

Ortega 的突破在于意识到，尽管这两种机制看起来完全不同，但它们实际上在玩同一个游戏。他使用了经典的**收集者问题（Coupon Collector Problem）**来解释它。

想象一下，你正试图收集一套完整的 $n$ 种不同的交易卡片。每当你买一盒麦片，你就会得到一张随机的卡片。你需要买多少盒麦片才能集齐所有的卡片？
答案大约是 $n \times \log n$。为了找到最后几张稀有的卡片，你需要花费大量的时间购买盒子。

Ortega 展示了 延迟接受（DA） 正好就像这种情况。学生不断申请学校，直到每一所学校都至少收到了一份申请。所有人发出的总申请量大约等同于你为了集齐所有卡片而需要购买的麦片盒数量。由于平均每个学生进行约 $\log n$ 次申请，所以他们的最终学校排名也是大约 $\log n$。

随后，Ortega 将目光转向了 即时接受（IA）。起初，由于学生不能立即持续申请，必须等待一个“轮次”结束后才能再次尝试，这看起来似乎有所不同。但 Ortega 意识到，如果从特定的角度来看，它也是一个收集者问题。

他构思了一个略带“失忆症”的版本。假设一个学生不断随机挑选学校，即使他已经尝试过这些学校。如果他选到了已经尝试过的学校，他就直接忽略（这属于“浪费”的抽取）。Ortega 证明，即使存在这些浪费的抽取，填满所有学校所需的“实际”申请量仍然大致等于收集者问题的规模。

大揭秘

结论就在这里：这两种方法之间的差异出人意料地小。

Ortega 从数学上证明了，随着市场规模变得巨大（即当 $n$ 趋于无穷大时），即时接受（IA）系统下学生的平均排名也同样大约是 $\log n$。

这意味着，尽管 IA 具有“帕累托效率”（意味着如果每个人都说实话，它在理论上是完美的），但它并没有在让学生获得心仪学校方面，比缓慢的 DA 方法带来巨大的优势。那种“一阶改进”——即显著的、可见的提升——根本不存在。

Ortega 的论文明确排除了这样一种观点，即 IA 是一个能够大幅改善大型随机市场中学生结果的“灵丹妙药”。虽然 IA 在特定的、微小的场景或特定的优先级规则下可能表现更好，但论文表明，在一般情况下，这两种机制是渐近等价的（asymptotically equivalent）。它们都会让学生落在与其市场规模呈对数关系（$\log n$）的排名水平。

这为什么重要

对于“即时接受”系统的支持者来说，这个发现可能有点令人沮丧，但对于数学研究来说，这是一种慰藉。它告诉我们，当涉及到平均幸福感时，IA 的“帕累托效率”其实是一个幻象。那个经常被批评为不公平、易被操纵的机制，在实际结果上并没有比那个公平且难以作弊的机制带来显著更好的平均表现。

Ortega 的研究也将这一发现扩展到了其他变体。无论是学校拥有多个座位（多对一匹配），还是学生被允许跳过已满学校（一种被称为“带有跳过的 IA”的变体），结果依然成立：平均排名始终保持在 $\log n$ 左右。

因此，下次当你听到有人争辩说我们必须使用“波士顿机制”，因为它更有效率时，你可以微笑并说：“嗯，也许它确实很高效，但它在平均水平上并不能比另一种方法让孩子们进入更好的学校。”在学校选择的这场伟大赛跑中，两名选手几乎是在同一时间冲过了终点线。