Stable Marriage Problem

研究生学习开始啦

本文是 Design and Analysis of Algorithms 的一部分

这节课介绍了一些著名的问题解决方案及其典型算法，并且还有它们的实践内容

Problem Description

• 有 n 个男人和 n 个女人
• 每个人都有一个 preference list，即对另一性别的人的偏好排序
• 问题：如何匹配男女，使得每个人都能得到满意的匹配？(稳定)

稳定：不存在一对男女，他们之间相互更喜欢。换言之，不存在一对男人和女人，他们都更喜欢对方而不是他们当前的配偶。

如果存在一对男女，他们不是当前匹配中的伴侣，但相互之间都优先于他们各自的伴侣
则称其为 rogue / vogue couple / 阻碍对 (为什么要叫这个名)

存在 rogue couple 的匹配是不稳定的，因为这对男女都有动机离开他们当前的伴侣而彼此匹配

如果我们允许同性恋，那么这个问题就是 Stable Roommates Problem，在这种情况下 没有 稳定匹配

Unisex Case

让我们来看一个不可能进行稳定匹配的例子，它需要与第四个人创造一个三角恋

A -> B / D / C
B -> D / A / C
C -> N/A
D -> A / B / C

C 的喜好无关紧要，因为 C 是每个人的最后选择

Proof

让我们假设存在稳定匹配：

1. 有 [A, D]
2. 那么另一对必然是 [B, C]
3. 但是 A 相比 D 更喜欢 B，B 相比 C 更喜欢 A
4. 所以 [A, B] 应该是一对
5. 那么 [C, D] 就是另一对
6. 但是 B 相比 A 更喜欢 D，D 相比 C 更喜欢 B
7. …… 无限循环

所以不存在稳定匹配

但是在 bipartite graph (二分图) 中，我们一定可以找到稳定匹配

这类问题无法使用 greedy 或者 induction (or recursion) 算法解决，所以我们需要

Gale-Shapley Algorithm

也叫 Deferred Acceptance 算法

Steps

1. 每个男人都向他的首选求婚
2. 每个女人都暂时选择她当前最喜欢的求婚者，拒绝其他人
3. 每个被拒绝的男人向他的下一个选择求婚
4. 重复步骤 2 和 3，直到每个女人都接受了一个求婚者

我们将每一轮定义为一天
女人在每一轮接受的求婚都是临时的，这就是为什么此算法又叫 Deferred Acceptance 延迟接受 的原因。

Theorem 1: 在 $n^2 + 1$ 天内结束

反证

让我们来看看算法还未终止时必须发生的一件事情：
某个男孩从他的名单上划掉一个女孩

为什么？因为算法如果没有终止，那么某个女孩至少有两位追求者
那至少有一个人会被拒绝，则他会把她划掉

因此，如果算法没有在 $n^2 + 1$ 次内终止，那么总共会有 $n^2 + 1$ 次划掉
但是，每个人最多只能划掉 n 次，所以最多可以有 $n^2$ 次划掉
我们有了矛盾。最后一天只有接受，没有拒绝

$n^2 + 1$ 并不是算法的最坏情况，所以让我们来计算

最坏 $(n - 1)^2 + 1$

让我们来举一个最坏的情况：每个男孩都会被拒绝 n - 1 次
总不能被拒绝 n 次吧，那不是就没人要了

总求婚数 = 总拒绝数 + 总接受数
则
$$ 总求婚数_{直到第 n - 1 天} = 男孩的数量 \times 每个男孩的求婚数 = n \times (n - 1) $$
得到
$$ 总求婚数 = n \times (n - 1) + 1 = n^2 - n + 1 $$

在第一天，每个男人都会求婚，则进行了 n 次求婚
随后的每一天，都只会有 一个 男人求婚（这也是为什么总求婚数可以计算总天数的原因）

所以我们可以据此求出总天数：
$$ 总天数 = 总求婚数 - 第一天求婚的次数 + 第一天 = [n^2 - n + 1] - n + 1 = n^2 - 2n + 2 $$

所以，在最坏的情况下，$\Omega (n^2)$ 天内中止
（算法所需的时间至少与参与者数量的平方成正比）

大 $O$ 记号提供了一个上界，表示运行时间的增长速率不会快于某个特定的函数
大 $\Omega$ 记号提供了一个下界，表示运行时间的增长速率至少是某个特定函数

Lemmas

1. 当男孩结婚时，他已经遍历了所有更喜欢的女孩

2. 如果一个男孩到头来也没结婚，那么他一定遍历过了所有女孩

3. 每个女孩都会嫁给 追求过 她的男孩中最喜欢的那个

4. 如果一个女孩被追求过，那么她一定会结婚

Theorem 2: 在算法中，每个人都会结婚

在有以上 Lemmas 后，我们可以反证这个定理

• 假设一个男孩 B 没有结婚
• 但是在 L2 中说明了他遍历了所有女孩
• 但是根据 L4，每个女孩都会结婚
• 由于男孩的数量等于女孩的数量
• 因此每个人都会结婚

Theorem 3: 算法总是产生稳定匹配

为了自相矛盾，假设有一对 rogue [B, G]
运行算法，有 [B, G1] 和 [B1, G]

如果 [B, G1]，但是 B 更喜欢 G
则根据 L1，B 一定追求过 G，G 拒绝了

但根据 L3，G 一定接受了比 B 更好的男孩
所以 G 比 B 更喜欢 B1
意味着 [B, G] 不是 rogue couple

（我怎么看不懂呢，这个 不是 到底是怎么推出来的）

Theorem 4 / 5: 算法会产生 求婚 / 被求婚 方的 最佳 / 悲观 匹配

定义：

• 最佳伴侣是他 / 她从可能的伴侣中最喜欢的
• 悲观伴侣是他 / 她从可能的伴侣中最不喜欢的

Boy optimal / Girl optimal

男性主动求婚，女性被动选择，持续优化直至男性满足，导致女性最坏结果

Uniqueness：如果两种情况下算法得到相同的匹配结果，那么这个结果就是唯一的稳定匹配

Max Magnitude $\theta (2^n)$

习题

证明题

Suppose there are $n$ boys and $n$ girls. $m$ boys are tall and the same number of girls are blonde.
Boys prefer blonde girls to non-blonde girls.
Girls prefer tall boys to non-tall boys.

金发配高个

Show that in every stable match, blonde girls are paired with tall boys.

这题是在说有一些高个男生和一些金发女生，男生更喜欢金发女生，女生更喜欢高个男生
要证明在每一个稳定匹配中，金发女生都会和高个男生配对

要证明，我们假设矛盾：存在一个稳定组合 $(b, g)$ 有

1. $b$ 是高个男生, $g$ 不是金发女生

或者

2. $b$ 不是高个男生, $g$ 是金发女生

1 和 2 是对称的，所以我们分析 1，同理可得 2

令高个的反义为矮个，金发的反义为黑发

既然有 高个配黑发，由于男女人数相同，那么一定有一个 $(b’, g’)$ 是矮个配金发

我们发现 $g’$ 更喜欢 $b$，因为 $g’$ 更喜欢高个
所以 $(b, g’)$ 是 rogue couple，这就与题目中的稳定匹配矛盾了

---

证明思路：假设初始匹配稳定，随后找出 rogue couple，导致违反稳定匹配的条件

相同偏好

If all the girls have the same preference list, then there is only one stable pairing.

要证明只存在一种稳定匹配，我们就假设有 A / B 两种稳定匹配

A 有 $(g, b)$，而在 B 中有 $(g, b’)$
同一个女生出现在不同的匹配中

由于所有女生偏好相同，则在任何稳定匹配中，将完全由男生的优先级决定，
无论 g 与谁匹配，其他女生的相对偏好不变

由于同一个女生出现在了不同的匹配中，这意味着至少在某个匹配中，
她得到了相对于另一个匹配更 高 / 低 优先级的男生

因为如果 $g$ 在 B 中能与 $b’$ 匹配，那么在 A 中与 $b$ 匹配的的其他女生将偏好 $b’$
这就导致了 rogue couple，违反了稳定匹配的条件

最优解

There is no pairing, stable or unstable, in which all the boys are better off than when the Gale-Shapley algorithm is used.

这题意思就是证明 GS 算法是最优解（而且是 boy optimal）

假设存在一个配对，在这个配对中所有的男孩比使用 GS 算法时更满意
这意味着每个男孩都与他的偏好列表中更高位的女孩配对了

然而，根据 GS 算法的性质，算法结束时每个男性都无法与他偏好列表中更高位的女性配对
因为这样的女性要么与他们自己的偏好列表中更高位的男性配对，要么在追求过程中拒绝了这些男性

因此，如果所有男性在某个配对中都比 GS 算法的结果更满意
那么这意味着至少有一个男性与他的偏好列表中的一个女性配对
而该女性在 GS 算法中拒绝了他

如果所有男孩在某个配对中都比 GS 算法的结果更满意
那么至少会有一对男女是不稳定的，因为至少有一个女孩可以与她更偏好的男孩配对
所以不存在这样的匹配，因为它会违反 GS 算法的稳定匹配性质

匹配题

Boy
b1	g1	g4	g3	g2	g5
b2	g3	g1	g4	g2	g5
b3	g4	g3	g5	g1	g2
b4	g1	g5	g2	g4	g3
b5	g4	g1	g5	g3	g2

Girl
g1	b4	b2	b1	b5	b3
g2	b4	b1	b3	b2	b5
g3	b4	b3	b1	b2	b5
g4	b1	b3	b4	b2	b5
g5	b2	b3	b5	b1	b4

---

Day	g1	g2	g3	g4	g5
1	b1, b4	-	b2	b3, b5	-
2	b4, b5	-	b2	b3, b1	-
3	b4	-	b2, b3	b1	b5
4	b4, b2	-	b3	b1	b5
5	b4	-	b3	b1, b2	b5
6	b4	b2	b3	b1	b5

---

(g1, b4), (g2, b2), (g3, b3), (g4, b1), (g5, b5)