稳定婚姻问题求解器

稳定婚姻问题求解器

稳定婚姻问题求解器 是 Gale-Shapley 延迟接受算法 的交互式实现。该算法由 David Gale 和 Lloyd Shapley 于 1962 年提出，证明了在给定每个成员对另一方的完整排名的情况下，两个规模相等的群体之间总能产生稳定的配对。此工具接收您的偏好列表，逐步运行算法，并将结果显示为稳定匹配、动画二分图、偏好热图，以及无阻碍对存在的验证证明。

什么是稳定婚姻问题？

给定两个规模相等的互斥集合 — 例如 n 个男人和 n 个女人，或 n 个申请人和 n 个职位 — 并且每个成员都有一个对另一方所有成员的完整偏好列表，匹配是指两个集合之间的一一对应配对。如果匹配之外不存在任何一对 (a, b) 相比目前的伙伴更愿意在一起，则该匹配被称为稳定的。

形式上，如果不存在阻碍对（即一对 (a, b)，其中 a 匹配到 b'，b 匹配到 a'，且满足以下条件），则匹配 M 是稳定的：

如果这两个条件都满足，a 和 b 都会抛弃他们目前的伙伴，从而使匹配变得不稳定。稳定匹配就是不存在此类配对的匹配。

Gale-Shapley 算法

Gale 和 Shapley 通过构造法证明了对于任何偏好集，稳定匹配总是存在的，并给出了一种寻找稳定匹配的高效算法。该算法分轮次运行：

1. 每个未参与婚约的提议者向其名单上排名最高且尚未拒绝过他们的接收者提议。
2. 每个收到一个或多个提议的接收者选择他们最喜欢的提议者（与当前的暂定未婚夫进行比较）并暂时接受；其他人则被拒绝。
3. 被拒绝的提议者重新恢复自由，并在下一轮中转向他们的下一个选择。
4. 当所有提议者都已订婚时，算法终止 — 保证这最多在 n² 次提议内发生。

关键理论性质

存在性与唯一性

稳定匹配总是存在的 (Gale & Shapley, 1962)，但并不一定是唯一的。对于给定的偏好集，可能存在多个稳定匹配，它们形成一个按共同偏好排序的格（Lattice）。

提议者最优性

当由一方发起提议时，Gale-Shapley 会产生提议者最优的稳定匹配：每个提议者都会得到他们在任何稳定匹配中可能配对的最好伙伴。根据对称论证，这对于接收方来说也是接收者最劣的匹配 — 接收方得到的是他们最差的稳定伙伴。在本计算器中切换提议方通常会改变结果。

提议者的策略抗性

在 Gale-Shapley 算法下，提议者没有动力虚报偏好：说实话是他们的占优策略。然而，接收者有时可以通过策略性虚报获益 — 这也是美国医院-住院医师市场被设计为以学生作为提议方的原因之一。

偏远医院定理

在所有稳定匹配中，未匹配的代理人集合是完全相同的。因此，如果您的实例规模不平衡（超出了本经典工具的范围），在每个稳定方案中，相同的人都将处于未匹配状态。

输入格式

此计算器要求每人一行，姓名后接冒号，然后是以逗号分隔的完整偏好排名表：

要求：

• 两组必须拥有完全相同数量的成员。
• 每个成员必须对另一组的每一个成员进行排名 — 不接受部分列表。
• 姓名可以使用字母、数字、下划线、连字符、空格和常见的 Unicode 字符。
• 每侧支持多达 15 名成员，以确保快速的交互式动画。

如何使用此计算器

1. 在左侧文本区域输入 A 组偏好 — 每位成员一行，提供完整的排名列表。
2. 在右侧文本区域输入 B 组偏好 — 每位成员一行，格式相同。
3. 选择提议方。 选择 A 组或 B 组。尝试两种方式以比较 A 组最优与 B 组最优的结果。
4. 点击“求解稳定匹配”。 计算器运行 Gale-Shapley 并生成稳定配对、统计数据、动画和稳定性证明。
5. 控制动画。 使用播放/单步/重置控件，按顺序查看每次提议、接受、更换和拒绝的过程。
6. 查看热图。 每个单元格显示排名；黄色边框的单元格构成了最终匹配 — 观察这些单元格的位置高低，即可了解每一方的“满意度”。

操作实例 — 经典 3×3

男方：Alex, Bryan, Chris。女方：Bea, Claire, Diana。偏好：

以男方发起提议运行 Gale-Shapley，第一轮即可得到 Alex–Bea、Bryan–Claire、Chris–Diana 的匹配（每个男人的第一选择刚好匹配到一个第一选择是其他人的女人 — 无冲突）。该匹配是稳定的：没有任何男女配对会因为交换伙伴而变得更好，因此不存在阻碍对。

现实应用

为什么劳埃德·沙普利获得了诺贝尔奖

2012 年，瑞典皇家科学院将 诺贝尔经济学奖 授予了 劳埃德·沙普利（Lloyd Shapley，因其理论贡献，与已故的 David Gale 共同获奖）和 艾尔文·罗斯（Alvin Roth，因其将理论应用于现实市场，包括重新设计美国医疗住院医师匹配和肾脏交换网络）。该奖项表彰了“稳定分配理论和市场设计实践”。

常见问题

什么是稳定婚姻问题？

稳定婚姻问题的问题是：给定两个规模相同的群体，其中每个成员都对另一个群体的所有成员按偏好从高到低进行排名，我们能否将所有人配对，使得不存在两个人都更愿意离开目前的伙伴而选择对方的情况？这种配对被称为稳定匹配。Gale-Shapley 算法以 O(n²) 时间复杂度解决此问题，并且总能找到稳定匹配。

Gale-Shapley 算法是如何工作的？

Gale-Shapley 延迟接受算法分轮次进行。在每一轮中，每个目前未参与婚约的提议者向其名单上排名最高且尚未拒绝过他们的接收者提议。每个接收者暂时接受目前收到的最好的提议并拒绝其余提议；任何被替换的提议者将再次恢复自由。当没有提议者处于自由状态时算法终止，这最多在 n² 次提议中发生。

稳定匹配是唯一的吗？

不是。一个稳定婚姻实例可以有多个稳定匹配。然而，当一方提议时，Gale-Shapley 总是产生提议者最优的稳定匹配：每个提议者都得到了他们在任何稳定匹配中可能得到的最好的伙伴。根据对称性，这对于另一方来说也是接收者最劣的匹配。切换提议方通常会产生不同的稳定匹配。

什么是阻碍对？

阻碍对是指当前未匹配的一对 (a, b)，其中 a 相比当前伙伴更喜欢 b，且 b 也相比当前伙伴更喜欢 a。如果存在任何阻碍对，则匹配是不稳定的，因为这两个人更愿意互相配对。稳定匹配没有阻碍对，此计算器在每次求解后都会自动验证这一点。

稳定匹配的实际应用有哪些？

Gale-Shapley 算法支持了美国分配医学生到住院医师实习期的全国住院医师匹配计划（NRMP）、波士顿和纽约的择校系统、几个国家的大学录取、器官捐献者肾脏交换链以及宿舍分配系统。劳埃德·沙普利和艾尔文·罗斯因这项工作部分获得了 2012 年诺贝尔经济学奖。

两组的大小必须相同吗？

在经典的稳定婚姻表述中，是的。双方必须拥有相同数量的成员，并且每人必须提供另一方的完整排名。虽然存在不平衡变体（如不完整名单的稳定匹配或医院-住院医师问题），但它们需要修改算法。此计算器强制执行等大规模和完整的偏好列表。

延伸阅读

• 稳定婚姻问题 — 维基百科
• Gale-Shapley 算法 — 维基百科
• 全国住院医师匹配计划 — 维基百科
• 2012 年诺贝尔经济学奖 — 沙普利与罗斯