📈 economics

Note on the size of a stable matching

本文证明了在最大个体理性匹配规模为 $n$ 的一对一匹配市场中，每个稳定匹配必须包含至少 $\lceil n/2 \rceil$ 对配对，刻画了达到该下界的偏好剖面，并分析了最大化就业与维持稳定性之间的权衡。

原作者： Gregory Z. Gutin, Philip R. Neary, Anders Yeo

发布于 2026-06-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Gregory Z. Gutin, Philip R. Neary, Anders Yeo

原始论文根据 CC0 1.0（http://creativecommons.org/publicdomain/zero/1.0/）发布到公有领域。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，就业市场就像一个巨大的舞池。在舞池的一侧，是正在寻找舞伴的劳动者；在另一侧，是正在寻找劳动者的企业（或舞伴）。每个人都有一个“愿望清单”，列出了他们更想与谁共舞，而且如果遇到自己不喜欢的人，他们宁愿坐在一旁也不愿起舞。

Gutin、Neary 和 Yeo 的论文提出了一个简单但棘手的问题：如果我们坚持要寻找一种“稳定”的安排（stable arrangement），那么在找到所有可能的最佳配对方式（即“最大匹配”）的情况下，我们至少能保证有多少人正在跳舞？

以下是他们研究结果的拆解，使用了简单的比喻：

1. “50% 法则”（核心发现）

想象你有一个满是人的房间。你找到了能够让每个人都乐于配对的绝对最大配对数量。假设在“完美世界”的情景下，你可以组成 100 个人（50 对）的配对。

论文证明，如果你寻找的是一种稳定的安排（即不存在两个人会秘密地想要离开现有的舞伴而转去与彼此共舞的情况），你至少能保证有 50 个人（25 对）在跳舞。

比喻： 把“稳定性”想象成一条“禁止出轨”的规则。即使你试图强行实现最高效的舞池规模，这条“禁止出轨”的规则也可能会迫使一些舞伴分手。然而，作者证明你永远不会损失超过一半的舞者。你拥有的舞者数量，至少始终是你理论上可以实现的配对数量的一半。

2. 最坏的情况何时发生？

论文还探讨了：什么样的偏好会导致我们失去正好一半的舞者？

他们发现，当那些“不受欢迎”的人（在稳定版本中未能找到舞伴的人）彼此之间完全无法接受对方时，就会发生这种情况。

比喻： 想象那些在稳定版本中没有获得工作的劳动者。如果他们看向那些空缺的舞位，并表示：“我宁愿坐在沙发上，也不愿和任何那些空位跳舞”，那么系统就会锁定在一个较小的稳定群体中。
“顶层的共识”： 论文还描述了一种特定的模式，即所有获得工作的人都达成了一致：那些没获得工作的人被排在他们愿望清单的最底端。这种“共识”创造了一道墙，阻止了系统扩张以填满所有的空缺，从而使舞者人数保持在恰好 50% 的最低水平。

3. “充分就业”的代价

论文的最后一部分探讨了一种权衡。如果我们试图填满每一个职位空缺，哪怕这意味着要拆散稳定的舞伴，会发生什么？

作者展示了一个令人惊讶的关系：

如果稳定群体是尽可能小的（即 50% 的场景），那么该稳定群体中的任何一对舞伴都不会出现在“最大就业”群体中。
比喻： 想象你有一个由 25 对舞伴组成的稳定舞圈。如果你试图扩大舞池以容纳 50 对舞伴，你可能必须拆散原本那 25 对中的每一对，才能为新的、不同的配对腾出空间。
启示： 试图实现“最大化就业”并不只是增加就业人数那么简单；它可能意味着你必须牺牲掉那些已经存在的、稳定的配对关系。想要“填满所有空缺”是有隐藏成本的，这个成本不仅在于人数，还在于你会失去那些原本运作良好的特定配对。

总结

简而言之，这篇论文告诉我们：

稳定性是安全的： 即使在最坏的情况下，一个稳定的市场所雇佣的人数也至少是理论最大可能人数的一半。
“不可接受”的陷阱： 只有当失业的劳动者和空缺的职位互不接受时，市场才会缩减到这个最小规模。
权衡： 如果你试图强行让市场雇佣所有人，你可能不得不彻底拆解现有的稳定配对。你无法同时拥有“最大化就业”和“保留原始稳定舞伴”。

作者将他们的研究限制在这一特定的“一对一”舞池场景中，并未声称这些规则适用于更复杂的市场（例如夫妻共同申请或拥有多个名额的学校），尽管他们暗示这些可能都是有趣的未来课题。

技术摘要：关于稳定匹配规模的笔记

问题陈述
本文研究了一对一双边匹配市场（工人与单职位企业）中，稳定匹配的规模与最大个体理性（最大）匹配规模之间的关系。虽然 Gale-Shapley 框架保证了稳定匹配的存在性，但它并不保证这些匹配能使就业工人或填补职位的数量达到最大。作者探讨了以下问题：在一个最大个体理性匹配包含 $n$ 个对子的市场中，任何稳定匹配的对子数量的下界是多少？此外，他们试图刻画出迫使稳定匹配相对于最大匹配尽可能小的特定偏好结构，并分析稳定对与最大对之间的重叠情况。

研究方法
作者采用图论方法对匹配市场进行建模，利用了无向图和有向图两种表述形式。

无向图表述： 市场被建模为一个二部图 $G = (W, F; E)$ ，其中边代表可接受的配对。作者利用极大匹配（maximal matching）和最大匹配（maximum matching）的性质来建立界限。
有向图（Digraph）表述： 为了刻画偏好结构，作者采用了 Maffray (1992) 提出的匹配有向图表述。在该有向图 $D = (V, A)$ 中，顶点代表可接受的对 $(w, f)$ ，弧代表偏好排序（例如，从 $(w, f)$ 到 $(w, f')$ 的弧表示工人 $w$ 相比于 $f$ 更喜欢 $f'$ ）。
迭代删除无吸引力替代方案 (IDUA)： 作者利用 IDUA 程序（Balinski and Ratier, 1997; Gutin et al., 2023）将市场简化为“标准形式”。这一过程通过迭代移除那些不可能属于任何稳定匹配的配对（例如，当参与者与一个较差的伴侣匹配，而其最偏好的伴侣处于未匹配状态时，该配对会被移除）。
构造性刻画： 作者通过构建偏好剖面来定义特定的市场类别（ $G_n$ 和 $F_n$ ），这些剖面通过在基础市场（具有最大稳定匹配）的基础上增加新的参与者，并构造其偏好，使这些新参与者对现有稳定参与者而言是“无吸引力”的。

核心贡献与结果

定理 1（规模界限）： 主要结果表明，在任何最大个体理性匹配规模为 $n$ 的市场中，每个稳定匹配的规模至少为 $\lceil n/2 \rceil$ 。
- 证明逻辑： 证明依赖于两个事实：(i) 稳定匹配是一个极大匹配（不存在双方都未匹配的可接受对）；(ii) 图中的任何极大匹配至少是最大匹配规模的一半。
- 意义： 只要最大匹配是个体理性的，均衡就业率永远不会低于最大可实现就业率的 50%。
定理 2（极值偏好的刻画）： 本文刻画了达到此下界的偏好剖面类 ( $F_n$ )。
- 一个市场达到该界限（稳定规模 = $\lceil n/2 \rceil$ ，最大规模 = $n$ ）当且仅当它属于类别 $F_n$ 。
- 结构属性： 在这些市场中，不在任何稳定匹配中出现的参与者（即均衡中的“未匹配者”）必须发现彼此是不可接受的。如果他们彼此可接受，则会形成阻塞对（blocking pair），从而增加稳定匹配的规模。
- 顶端一致性： 这些市场的一个自然子类表现出“顶端一致性”（agreement at the top），即其中的参与者将所有新的、非稳定的参与者排在其最不喜欢的稳定伴侣之下。
定理 3（重叠与牺牲）： 作者分析了稳定匹配集合 ( $\mu^*$ ) 与最大匹配集合 ( $\mu$ ) 之间的交集。
- 令 $r$ 为共同对的数量。定理指出： $|\mu^*| \geq (|\mu| + r) / 2$ 。
- 意义： 当稳定匹配被最小化时（即 $|\mu^*| = \lceil |\mu|/2 \rceil$ ），重叠 $r$ 必须为零。这意味着，如果市场的结构使得稳定匹配尽可能小，那么稳定匹配中的任何对都不出现在最大匹配中。
- 稳定的代价： 最大化就业（填补所有空缺）可能需要“牺牲”所有原本会存在于较小稳定配置中的均衡配对。

重要性与范围
本文将其分析框架定位于对“稳定性的代价”的探索。它量化了稳定性与效率（以匹配规模衡量）之间的权衡。作者指出，虽然稳定性确保了没有阻塞对，但与理论最大值相比，它可能会导致就业人数的大幅减少，特别是在定理 2 所识别出的具有特定偏好结构的市场上。

作者明确将研究范围限制在一对一双边匹配市场。他们承认，尽管该框架应用广泛（如学生-学院、医生-医院），但此处推导出的特定界限和刻画并不能自动扩展到更复杂的环境，如多对一市场、包含伴侣的市场或单方面“室友”问题。本文并非提出新的算法或实验应用，而是提供了一个理论界限以及对就业率在稳定均衡中出现最坏情况的结构性刻画。

1. “50% 法则”（核心发现）

2. 最坏的情况何时发生？

3. “充分就业”的代价

总结

类似论文