📈 economics

The Distribution of Envy in Matching Markets

本文利用应用概率工具，研究了随机匹配市场中延迟接受算法（DA）下嫉妒的分布，通过建立与赠券收集问题的联系，推导出了无人嫉妒的提议者数量的精确有限市场表达式及渐近界，并将其与随机序列独裁（RSD）机制进行了对比分析。

原作者： Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

发布于 2026-03-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

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

这篇论文探讨了一个非常有趣的问题：在“分配学校”或“匹配伴侣”的随机市场中，有多少人是真正“心满意足”的，又有多少人“没人嫉妒”？

为了让你轻松理解，我们可以把整个市场想象成一场**“超级大抽奖”，或者是一场“抢座位游戏”**。

1. 核心背景：我们在玩什么游戏？

想象有 $n$ 个学生（比如 1 万人）和 $n$ 所学校。每个学生都有自己喜欢的学校排名，每所学校也有自己喜欢的学生排名（或者随机分配）。

这里有两个主要的“游戏规则”（算法）：

DA（延迟接受算法）： 这是目前最主流、最公平的规则。学生按顺序向喜欢的学校申请，学校暂时“保留”最好的，把其他的拒掉。被拒的学生继续申请下一所，直到没人被拒为止。这就像是一个**“层层筛选、不断重试”**的过程。
RSD（随机序列独裁）： 这就像**“抽签排队”**。大家随机排个队，第一个人挑最好的，第二个人挑剩下的最好的，以此类推。

2. 两个关键概念：谁在“羡慕”谁？

论文研究了两种“完美状态”：

A 类人：没人嫉妒他（The Unenvied）
- 比喻： 想象你在排队领奖品。如果没有任何人觉得“要是我坐在他那个位置就好了”，那他就是“没人嫉妒”的。
- 现实含义： 这意味着他匹配到的学校，在其他人眼里并不是“更好的选择”。通常，这发生在那些**“冷门学校”**（或者叫“需求不足的学校”）里。因为大家都没抢着去，所以没人嫉妒坐在那里的人。
B 类人：他不嫉妒任何人（The Envy-Free）
- 比喻： 想象你在排队领奖品。如果你拿到了自己最想要的那个，你当然不会羡慕别人。
- 现实含义： 这意味着他匹配到了自己的第一志愿。

3. 论文发现了什么惊人的结果？

作者用数学工具（主要是“集邮问题”的变体）算出了在随机市场中，这两类人大概有多少。

发现一：没人嫉妒的人（A 类）非常少，而且两个规则结果一样！

DA 规则下： 没人嫉妒的学生数量大约是 $H_n$ （这是一个数学常数，叫调和级数，对于 1 万人来说，大概只有 9 到 10 个人）。
RSD 规则下： 居然也是 $H_n$ ！
通俗解释： 无论你用复杂的“层层筛选”（DA），还是简单的“抽签排队”（RSD），最终只有极少数人（大概 $\log n$ 个）是坐在“没人眼红”的位置上的。
- 这就好比在一个有 1 万人的大礼堂里，无论你怎么安排座位，最后只有不到 10 个人坐的是“没人想换”的角落。绝大多数人（99.9%）都会觉得：“哎呀，如果我能坐那个位置就好了。”

发现二：拿到第一志愿的人（B 类），DA 规则下少得可怜！

RSD 规则下： 因为大家是轮流挑，前面的人能挑到第一志愿，后面的人也能挑到剩下的第一志愿。平均下来，大约一半（50%） 的人能拿到自己的第一志愿。
DA 规则下： 只有大约 $n / \log n$ 的人能拿到第一志愿。
- 通俗解释： 在 DA 规则下，因为大家互相“卷”，导致很多人为了抢热门学校被拒之门外，最后只能去第二、第三志愿。对于 1 万人的市场，大概只有 1100 人能拿到第一志愿（11%），而在 RSD 下则有 5000 人（50%）。
- 结论： DA 规则虽然公平（稳定），但在让大家“如愿以偿”方面，表现比简单的抽签差很多。

4. 一个有趣的“反差萌”

论文最精彩的地方在于对比：

RSD（抽签）： 像是一个**“慷慨的圣诞老人”**，让很多人（50%）拿到了最想要的礼物，但也让很多人（剩下的一半）嫉妒别人拿到了更好的。
DA（筛选）： 像是一个**“严格的守门员”，它保证了没人能“无理取闹”地换座位（稳定），但代价是绝大多数人（99%）都觉得自己没拿到最好的，或者觉得别人的位置更好。**

最讽刺的巧合是： 尽管 DA 让很多人没拿到第一志愿，但它和 RSD 一样，都只留下了同样极少的一群人（约 10 人）是“没人嫉妒”的。这说明，“没人嫉妒”这个现象，是随机市场本身的固有属性，而不是某种算法的缺陷。

5. 总结：这对我们意味着什么？

这篇论文告诉我们一个有点“扎心”但很真实的道理：

在大规模的资源分配（如学校录取、医院分配）中，“完美”是极其罕见的。

没人眼红的位置（冷门）： 无论用什么规则，只有极少数人坐在那里。
拿到第一志愿的人： 在复杂的公平规则（DA）下，能拿到第一志愿的人比例会随着人数增加而急剧下降。

打个比方：
如果 1 万个学生抢 1 万个学校，在 DA 规则下，你可能觉得“大家都没拿到最好的，都在互相嫉妒”。论文告诉你：是的，99% 的人都在互相嫉妒，只有极少数人（不到 10 个）是真正“岁月静好、无人打扰”的。

给政策制定者的启示：
如果你追求的是“让尽可能多的人拿到第一志愿”，DA 可能不是最好的（RSD 更好）；但如果你追求的是“稳定”（没人能私下换座位），DA 是必须的。但你要接受一个代价：在这个系统中，绝大多数人都会觉得自己“不够幸运”或者“被嫉妒”。 这不是算法的错，而是大数定律下的必然结果。

论文技术总结：匹配市场中的嫉妒分布

1. 研究背景与问题定义

核心问题：在随机匹配市场（Random Matching Markets）中，研究**延迟接受算法（Deferred Acceptance, DA）**产生的嫉妒（Envy）分布情况。具体关注两类学生：
1. 无人嫉妒的学生（Students whom nobody envies）：即没有被任何其他学生嫉妒的学生。
2. 不嫉妒任何人的学生（Students who envy nobody）：即没有被分配到自己最偏好学校的学生（通常指分配到了第一志愿）。
研究动机：
- 帕累托效率：DA 算法通常不产生帕累托最优匹配，而关于高效机制的嫉妒分布结论（如总有人不嫉妒别人，总有人不被嫉妒）不一定适用于 DA。
- 福利衡量：不嫉妒任何人的学生数量直接对应获得“第一志愿”的比例，这是政策制定者常用的福利指标。
- 改进空间：这两类学生是“不可改进的”（unimprovable），即无法通过任何交换从 DA 结果中获益。量化这两类群体的规模有助于确定 DA 结果的可改进下限。
模型设定：
- 双边匹配市场， $n$ 个学生， $n$ 所学校（每所学校配额为 1）。
- 偏好和优先级是独立同分布（i.i.d.）且均匀随机生成的。
- 仅关注提议方（学生）的福利。

2. 方法论

本文结合了应用概率工具，特别是优惠券收集问题（Coupon Collector Problem）与延迟决策原则（Principle of Deferred Decisions）。

序列实现与优惠券收集：
- 利用 McVitie 和 Wilson (1971) 提出的 DA 算法序列实现版本：未匹配的学生依次向当前未申请过的最偏好学校申请。
- 将学生的偏好生成过程建模为从学校集合中无限次独立均匀抽取序列，直到遇到未尝试过的学校。
- 关键洞察：学校收到提案的时间点等同于优惠券收集问题中所有类型的优惠券都被收集到的时间点。
渐近分析：
- 利用 DA 算法中申请次数的渐近性质（约为 $n H_n$ ，其中 $H_n$ 为第 $n$ 个调和数），推导学生被拒绝和接受概率的几何分布近似。

3. 主要结果

3.1 无人嫉妒的学生数量 ($NEn$)

定义：被分配到“需求不足”（under-demanded）学校的学生，即在整个 DA 过程中只收到过一次提案的学校所匹配的学生。
精确结果（命题 1）：
- 在规模为 $n$ 的随机学校选择问题中，无人嫉妒的学生的期望数量精确等于第 $n$ 个调和数：
  $NEn = H_n = \sum_{k=1}^n \frac{1}{k}$
- 推导逻辑：在 DA 执行过程中，只有那些在原始抽取序列中恰好出现一次的学校才是“需求不足”的。这与经典优惠券收集问题中“单例优惠券（singleton coupons）”的数量分布一致。Myers 和 Wilf (2006) 已证明该期望值为 $H_n$ 。
渐近性质：
- $H_n \approx \ln n + \gamma$ 。
- 无人嫉妒的学生比例 $NEn/n \to 0$ （当 $n \to \infty$ ）。
- 直观含义：随着市场规模增大，几乎没有任何学生是“完全不被嫉妒”的。例如，当 $n=10,000$ 时，期望值小于 10 人。

3.2 不嫉妒任何人的学生数量 ($ENn$)

定义：被分配到第一志愿（最偏好学校）的学生。
渐近结果（命题 2 与推论 1）：
- 学生的排名分布近似于参数为 $1/H_n$ 的几何分布。
- 不嫉妒任何人的学生期望数量近似为：
  $ENn \approx \frac{n}{H_n}$
直观含义：虽然该数量也随 $n$ 增大而占比趋零，但其绝对数量远大于“无人嫉妒”的学生。例如，当 $n=10,000$ 时，期望约有 1,100 人获得第一志愿。

3.3 与随机序列独裁（RSD）的对比

作者将 DA 的结果与**随机序列独裁（Random Serial Dictatorship, RSD）**进行了对比：

不嫉妒任何人（第一志愿）：
- RSD：期望值为 $\frac{n+1}{2}$ （常数比例，约 50% 的学生获得第一志愿）。
- DA：期望值约为 $\frac{n}{H_n}$ （远小于 RSD）。
- 结论：DA 在满足第一志愿方面表现远差于 RSD。
无人嫉妒：
- RSD：期望值精确等于 $H_n$ 。
- DA：期望值精确等于 $H_n$ 。
- 结论：尽管两种机制结构截然不同，但它们在“无人嫉妒的学生数量”上表现出惊人的一致性。这表明 $H_n$ 是随机市场的一个基本属性，而非特定机制的缺陷。

4. 关键贡献

精确解析解：首次给出了 DA 算法下“无人嫉妒”学生数量的精确有限市场表达式（ $H_n$ ），而非传统的渐近近似。
理论连接：建立了 DA 算法执行过程与优惠券收集问题中单例优惠券分布之间的深刻联系。
机制对比：揭示了 DA 和 RSD 在嫉妒分布上的异同。虽然 DA 在效率（第一志愿匹配率）上不如 RSD，但在“无人嫉妒”这一特定指标上，两者遵循相同的数学规律。
市场洞察：证明了在随机市场中，无论是 DA 还是 RSD，真正“不可改进”（既不被嫉妒也不嫉妒别人）的学生群体都是消失的（vanishing），即占总人数的比例趋于零。

5. 意义与启示

公平性与效率的权衡：DA 虽然保证了稳定性（无正当嫉妒），但在减少总体嫉妒（即让尽可能多的人满意）方面，其表现与 RSD 存在显著差异（第一志愿匹配率低）。
市场基本属性： $H_n$ 这一结果在 DA 和 RSD（以及 TTC 机制）中的一致性，暗示了随机匹配市场中存在某种内在的、与机制无关的结构性限制，即无论机制如何设计，完全“无嫉妒”的学生数量都极其有限。
政策启示：在大规模学校选择市场中，依赖 DA 算法无法让大多数学生避免嫉妒，且获得第一志愿的学生比例随市场扩大而急剧下降。

6. 局限与未来方向

目前结果主要基于 i.i.d. 随机偏好假设。
未来研究可探讨偏好相关性、多对一市场（Many-to-one）以及更广泛的机制（如 TTC）是否也遵循 $H_n$ 规律。
论文指出，不可改进学生的比例在随机市场中收敛于零，这为理解匹配市场的帕累托改进空间提供了理论边界。

总结：该论文通过概率论工具，精确量化了 DA 算法在随机市场中的嫉妒分布，发现“无人嫉妒”的学生数量遵循调和数 $H_n$ ，这一发现不仅适用于 DA，也适用于 RSD，揭示了随机匹配市场中嫉妒分布的深层数学规律。