📈 economics

A Note on the Strategic Vulnerability of the Boston Mechanism in Random Markets

该论文首次对随机市场中的波士顿机制在均衡策略下的表现进行了渐近分析，揭示了尽管在诚实申报下该机制能高效匹配多数学生，但在纳什均衡中随着市场规模扩大，其匹配效率将急剧恶化，导致平均分配排名从对数级退化为近线性级。

原作者： Josue Ortega

发布于 2026-03-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Josue Ortega

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章探讨了一个关于学校招生机制的有趣发现，特别是关于著名的“波士顿机制”（Boston Mechanism）。为了让你轻松理解，我们可以把学校招生想象成一场**“抢座位”的游戏**。

1. 背景：什么是“波士顿机制”？

想象一下，有 1000 个学生（玩家）和 1000 个学校（座位）。

规则很简单：
1. 第一轮：每个学生都直接去填报自己最喜欢的学校。
2. 录取：如果某个学校收到了申请，它立刻、永久地录取那个优先级最高（比如离得近、成绩好）的学生。
3. 后续轮次：没被录取的学生，第二轮去填报第二喜欢的学校，以此类推，直到所有人都被录取。

这个机制在现实中很流行，因为政策制定者喜欢一个指标：“第一志愿录取率”（即有多少孩子直接去了他们最想去的地方）。

2. 之前的发现：诚实的“大赢家”

以前的研究（Pritchard & Wilson, 2023）发现，如果所有学生都老实巴交、诚实地填报（不耍心眼），这个机制表现得超级好：

大约 63% 的学生能直接去他们最喜欢的学校。
这比其他任何著名的招生机制（比如“随机分配”或“延迟接受”）都要好得多。
比喻：就像大家都不排队，直接冲向自己最喜欢的冰淇淋店，结果因为大家随机乱跑，反而有六成以上的人抢到了第一名的口味。

3. 本文的核心发现：一旦大家开始“耍心眼”，局面崩塌了

作者 Josué Ortega 指出，上面的好结果有一个巨大的漏洞：它假设学生都是“傻瓜”，不会动脑筋。

但在现实中，学生和家长都是精明的。他们会想：“哎呀，那个热门学校大家都想去，我优先级又低，第一志愿填它肯定没戏，不如填个稍微冷门点的，先保住一个位置。”

一旦大家开始策略性博弈（耍心眼），结果就完全变了：

发现一：第一志愿录取率直接归零

现象：当学生都变得精明，开始互相算计时，能去第一志愿的学生比例会从 63% 暴跌，随着人数增加，最终趋近于 0%。
比喻：这就好比原本大家是乱跑抢冰淇淋，现在大家开始互相观察：“哎呀，那个店人太多了，我不去了。”结果所有人都挤到了第二、第三名的店，原本那个“第一志愿”的店反而没人敢去，或者去了也抢不到。原本 63% 的幸运儿，一个都没了。

发现二：平均排名从“第 7 名”跌到“第 145 名”

现象：
- 诚实情况下：平均每个学生能去到自己列表上的第 7 个喜欢的学校。
- 策略博弈下：在某些糟糕的均衡状态下，平均每个学生只能去到自己列表上的第 145 个喜欢的学校。
比喻：
- 诚实时：大家像一群无头苍蝇乱撞，反而撞到了好位置。
- 耍心眼时：大家开始玩“胆小鬼游戏”。每个人都想避开热门，结果导致所有人都挤到了中下游的学校。原本大家能排到第 7 名，现在大家为了“安全”，互相推挤，最后每个人都掉到了第 145 名。

4. 为什么会这样？（核心逻辑）

这就涉及到了**“连锁反应”**：

诚实时：大家第一轮都冲上去，虽然很多人被刷下来，但第一轮确实“填满”了很多学校，留下了很多好位置。
耍心眼时：
- 学生 A 想：“热门学校我肯定进不去，我不填了，填个第二志愿。”
- 学生 B 本来能进第二志愿，结果 A 来了，把 B 挤掉了。
- 学生 B 被迫去填第三志愿，又把 C 挤掉……
- 结果：这种“避险”的连锁反应像多米诺骨牌一样，把原本能去好学校的人，一路推到了很差的学校。

5. 总结与启示

这篇文章告诉我们一个深刻的道理：

机制的“好”是脆弱的：波士顿机制之所以看起来数据漂亮（63% 第一志愿），完全是建立在**“大家都老实”**这个假设上的。
策略会毁了一切：一旦参与者开始根据规则进行“算计”，这个机制不仅失去了优势，甚至可能变得比那些原本被认为“平庸”的机制还要糟糕。
政策建议：政策制定者不能只看“第一志愿录取率”这个光鲜的指标。如果机制鼓励大家耍心眼，最终导致大家平均只能去很差的学校（从第 7 名掉到第 145 名），那这个机制就是失败的。

一句话总结：
波士顿机制就像一场**“诚实者的游戏”，只要大家都不耍心眼，结果就很好；但一旦大家开始“互相猜忌、互相算计”**，原本的好运气就会变成一场灾难，让所有人都去更差的学校。

这是一份关于 Josué Ortega 论文《A Note on the Strategic Vulnerability of the Boston Mechanism in Random Markets》（随机市场中波士顿机制的战略脆弱性注记）的详细技术总结。

1. 研究问题 (Problem)

学校选择机制（School Choice Mechanisms）在教育政策中至关重要，其中波士顿机制（Boston Mechanism, BM，又称即时接受机制 Immediate Acceptance）尽管存在激励相容性方面的争议，仍被广泛采用。

评估该机制的两个核心指标是：

第一志愿录取率 (First Preference Rate)：学生被分配到其首选学校的比例。
平均排名 (Average Rank)：学生被分配到的学校在其偏好列表中的平均位置（数值越小越好）。

核心问题：
现有的文献（如 Pritchard & Wilson, 2023，简称 PW）表明，在诚实申报偏好（Truthful Reporting）的假设下，波士顿机制在随机市场中表现优异：第一志愿录取率收敛于 $1-e^{-1} \approx 63\%$ ，且平均排名为 $O(\log n)$ 。然而，波士顿机制众所周知具有策略性操纵（Strategic Manipulation）的脆弱性。
本文旨在填补这一空白：当学生采取纳什均衡策略（即进行策略性博弈）时，波士顿机制在大规模随机市场中的渐近性能会发生怎样的变化？ 特别是，诚实申报下的优异表现是否会在均衡中消失？

2. 方法论 (Methodology)

模型设定：
- 采用随机市场 (Random Markets) 框架：包含 $n$ 名学生和 $n$ 所学校，每所学校容量为 1。
- 学生的偏好 ( $\succ$ ) 和学校的优先级 ( $\triangleright$ ) 是独立且均匀随机抽取的。
- 这是一个完全信息环境：学生在提交偏好列表前，知晓所有真实的偏好和优先级。
机制定义：
- 波士顿机制 (BM)：多轮匹配。第 1 轮学生申请首选，学校立即永久录取优先级最高的申请者；第 $k$ 轮剩余学生申请第 $k$ 志愿，学校录取最高优先级者。
- 延迟接受机制 (DA)：作为对比基准，学校的录取是临时的，允许后续被更高优先级者取代。
博弈分析：
- 构建由波士顿机制诱导的偏好申报博弈 (Preference Revelation Game)。
- 利用 Ergin 和 Sönmez (2006) 的结论：在完全信息下，波士顿机制的纳什均衡结果集合精确等同于真实偏好下的稳定匹配 (Stable Matchings) 集合。
- 引入均衡选择规则 (Equilibrium Selection Rule, $\sigma$ )：由于可能存在多个纳什均衡（即多个稳定匹配），研究考察所有可能的均衡选择规则下的期望性能。
分析工具：
- 渐近分析 (Asymptotic Analysis)：考察当市场规模 $n \to \infty$ 时，指标的变化趋势。
- 利用随机图论和匹配理论中的经典结果（如 Knuth, 1976; Pittel, 1989），特别是关于 DA 机制中申请次数的分布。

3. 主要贡献 (Key Contributions)

首次渐近分析：提供了波士顿机制在随机市场中均衡策略行为下的首个渐近分析结果。
揭示策略脆弱性：证明了波士顿机制在诚实申报下的显著优势（高第一志愿率）在策略性博弈中完全消失。
量化效率损失：展示了策略行为如何导致平均分配质量从对数级 ( $\log n$ ) 恶化至接近线性级 ( $n/\log n$ )。
连接理论与现实：将已知的有限市场均衡性质（Ergin & Sönmez）扩展到大规模随机市场的渐近框架，为政策制定者理解机制在真实博弈环境下的表现提供了理论依据。

4. 核心结果 (Key Results)

4.1 第一志愿录取率 (First Preference Rate)

诚实申报 (Truthful)：收敛于 $1 - e^{-1} \approx 0.63$ 。这是因为在随机市场中，几乎所有学校都会收到至少一个申请，且申请是均匀分布的。
策略均衡 (Strategic Equilibrium)：
- 命题 2：对于任何均衡选择规则 $\sigma$ ，第一志愿录取率 $f(BM^\sigma_n)$ 收敛于 0。
- 收敛速度：以 $O(1/\log n)$ 的速度衰减。
- 直觉解释：在均衡中，学生预见到热门学校会被高优先级者占据，因此会策略性地避开首选（“赌博”），转而申请更有把握的学校。这种连锁反应导致原本由“幸运”的第一轮申请支撑的 63% 录取率崩塌。由于在随机市场中，每个学校平均收到 $\log n$ 个申请，只有约 $1/\log n$ 的学生拥有其首选学校的最高优先级，因此第一志愿率必然趋于零。

4.2 平均排名 (Average Rank)

诚实申报 (Truthful)：平均排名为 $O(\log n)$ ，优于串行独裁制 (Serial Dictatorship, SD)。
策略均衡 (Strategic Equilibrium)：结果取决于具体的均衡选择规则 $\sigma$ $σ$ 。
- 命题 3：
  - 下界 (Best-case Equilibrium)： $\inf_{\sigma} r(BM^\sigma_n) = \Theta(\log n)$ 。这对应于学生最优稳定匹配（Student-Optimal Stable Matching）。此时策略行为影响较小，平均排名仍保持对数级。
  - 上界 (Worst-case Equilibrium)： $\sup_{\sigma} r(BM^\sigma_n) = \Theta(n / \log n)$ 。这对应于学校最优稳定匹配（School-Optimal Stable Matching）。此时平均排名从对数级恶化为接近线性级。
- 具体案例：在 $n=1000$ 的市场中，诚实申报下平均学生被分配到第 7 志愿；而在某些纳什均衡下，平均分配可能恶化至第 145 志愿。

5. 意义与启示 (Significance)

政策警示：
- 波士顿机制在统计报告（如第一志愿率）中表现出的“优异”可能是一种幻觉，仅存在于学生天真（诚实）申报的假设下。
- 一旦考虑策略性行为，该机制不仅失去了第一志愿率的优势，还可能导致整体分配效率的剧烈下降（从对数级到线性级的恶化）。
- 这解释了为什么许多地区（如波士顿、纽约等）最终放弃了该机制，转而采用延迟接受机制 (DA) 或其他策略性稳健的机制。
理论贡献：
- 揭示了机制设计理论中“诚实申报”假设的脆弱性。对于非策略性稳健的机制，其渐近性能在均衡中可能完全不同于诚实申报下的性能。
- 阐明了随机市场中稳定匹配集合的极值性质（学生最优 vs 学校最优）如何直接映射到波士顿机制的纳什均衡结果中。
未来方向：
- 文章讨论了不完全信息（Incomplete Information）下的鲁棒性问题，指出在信息私有时，均衡与稳定匹配的等价关系可能不再成立，这为后续研究留下了空间。
- 探讨了在“厚市场”（学生数远大于学校数）中，战略脆弱性是否依然存在。

总结：
Ortega 的这篇论文通过严谨的渐近分析证明，波士顿机制在随机市场中对策略性操纵极度敏感。其著名的 63% 第一志愿录取率在均衡中不复存在，且平均分配质量可能因均衡选择的不同而遭受灾难性打击。这一发现强烈支持了在大规模学校选择系统中避免使用波士顿机制，转而采用策略性稳健机制（如 DA）的必要性。