CS70Disc01B

稳定匹配问题

问题描述: 稳定匹配问题是指，在给定两个相等大小的群体（如工作和候选人），每个成员有自己对另一群体成员的偏好顺序的情况下，寻找一个匹配，使得不存在所谓的“阻挡对”，即没有任何一对成员更愿意选择彼此而不是当前的配对对象。

该问题的经典解决方法是 Gale-Shapley 稳定婚姻算法，又叫“提议和拒绝”算法。算法的目标是找到一个稳定匹配，在这个匹配中，所有匹配的成员都是“互相满意”的，不会有偏爱的其他选择。

1.例子分析:

在这个例子中：

工作集 $ J = {1, 2, 3} $
候选人集 $ C = {A, B, C} $

我们有以下偏好表：

工作偏好:
- 工作1: A > B > C
- 工作2: B > A > C
- 工作3: A > B > C
候选人偏好:
- 候选人A: 2 > 1 > 3
- 候选人B: 1 > 3 > 2
- 候选人C: 1 > 2 > 3

算法步骤:

该算法的核心思路是，工作主动提出提议，候选人根据自己的偏好进行选择。每个工作可以向其优先级最高的候选人提议，候选人会根据自己的偏好接受当前最好的提议，并拒绝其他提议。

算法分为几轮进行，每轮的步骤如下：

提议：未匹配的工作向其偏好列表中尚未拒绝的候选人提出配对。
拒绝：候选人暂时接受自己最喜欢的提议，拒绝其他提议（但保留较高优先级的提议）。

算法运行详解：

第 1 天：

工作1 向 $ A $ 提议，$ A $ 暂时接受提议。
工作2 向 $ B $ 提议，$ B $ 暂时接受提议。
工作3 向 $ A $ 提议，但 $ A $ 已接受 $ 1 $ 的提议，因此 $ 3 $ 被拒绝。

候选人	配对情况
A	1, 3
B	2
C

第 2 天：

工作3 向 $ B $ 提议，但 $ B $ 已接受 $ 2 $ 的提议，因此 $ 3 $ 再次被拒绝。

候选人	配对情况
A	1
B	2, 3
C

第 3 天：

工作3 向 $ C $ 提议，$ C $ 暂时接受提议。
此时所有工作都有候选人接受提议，但还未达到稳定配对。

候选人	配对情况
A	1, 2
B	3
C	3

第 4 天：

工作1 向 $ A $ 提议，但 $ A $ 已更偏爱 $ 2 $，因此拒绝 $ 1 $ 的提议。
工作1 向 $ B $ 提议，$ B $ 根据偏好接受 $ 1 $ 的提议，拒绝了 $ 3 $。

候选人	配对情况
A	2
B	1, 3
C

第 5 天：

工作3 最终向 $ C $ 提议， $ C $ 接受提议，最终达成稳定匹配。

候选人	配对情况
A	2
B	1
C	3

最终结果:

经过 5 天的提议和拒绝，最终的配对结果为： $ { (A,2), (B,1), (C,3) } $

这个配对是稳定的，因为没有任何一个工作和候选人会更偏爱彼此而不是当前的配对。

2. 提议与拒绝算法的证明

(a) 证明: 在算法的任意执行中，如果一个候选人在第 $ i $ 天收到提议，那么她之后的每一天都会收到提议，直到算法终止。

证明：
- 基础情况： 候选人 C 在第 $ i $ 天收到提议。
- 归纳步骤： 假设 C 在第 $ j i $ 天从工作 J 收到提议，证明她在第 $ j+1 $ 天也会收到提议。有两种情况：1) C 更喜欢 J；2) C 更喜欢某个工作 $ J' $。
- 在第一种情况中，J 会在第 $ j+1 $ 天再次向 C 提议；在第二种情况中，$ J' $ 会在第 $ j+1 $ 天向 C 提议。因此 C 在第 $ j+1 $ 天至少会收到一个提议。

(b) 证明: 如果候选人在第 $ i $ 天没有收到提议，那么她在之前的任何一天 $ j $（$ 1 j < i $）也没有收到提议。

证明：
- 使用反证法，假设候选人在第 $ i $ 天没有收到提议，但在之前的某一天 $ j $ 收到了提议。根据 (a) 部分，既然她在第 $ j $ 天收到提议，她之后的每一天都会收到提议，这与她在第 $ i $ 天没有收到提议的假设矛盾。

(c) 证明: 在算法的任意执行中，至少有一个候选人只收到过一个提议。

证明：
- 假设算法在第 $ k $ 天结束。此时每个候选人在第 $ k $ 天都必须收到提议，但至少有一个候选人在第 $ k-1 $ 天没有收到提议。根据 (b) 部分，既然该候选人在第 $ k-1 $ 天没有收到提议，她在之前的任何一天都没有收到提议。因此，该候选人在整个算法运行过程中只收到过一次提议，即在第 $ k $ 天。

3. 判断题

(a) 在 $ n $ 个工作和 $ n $ 个候选人的稳定匹配实例中，当工作提议时，所有工作最终都与它们最不喜欢的候选人匹配。(假)

解释： 这意味着所有工作都向每个候选人提议过，并且被拒绝 $ n-1 $ 次，但根据之前的证明，至少有一个候选人只收到一个提议，因此这种情况不可能发生。

(b) 在稳定匹配实例中，如果工作 J 和候选人 C 都将对方排在偏好列表的首位，那么 J 必须与 C 匹配在每一个稳定配对中。(真)

解释： 假设 J 和 C 没有匹配，则它们会组成一个“叛逃对”，这会导致当前配对不稳定，因此 J 和 C 必须在每个稳定配对中配对。

(c) 在至少有两个工作和两个候选人的稳定匹配实例中，如果工作 J 和候选人 C 将对方排在各自偏好列表的末位，那么 J 不可能与 C 配对。(假)

解释： 如果所有其他人也将 J 和 C 排在偏好列表的末位，则 J 和 C 可以配对。例如，两个工作和两个候选人的实例中，只有一个稳定的配对，且工作 J 和候选人 C 是彼此的最差选择。

(d) 对于每个 $ n > 1 $，存在一个稳定匹配实例，在该实例中，每对未匹配的工作和候选人都是“叛逃对”。(真)

解释： 可以构建一个实例，使得每对未匹配的工作和候选人都更喜欢对方，从而形成“叛逃对”。

4. 稳定匹配问题 III

(a) 判断题

如果候选人意外拒绝了她更喜欢的工作，算法仍然总是以匹配结束。 (假)
- 解释： 如果候选人 A 拒绝了工作 1，工作 1 向其他候选人提议并被拒绝，最终可能导致没有匹配。
提议与拒绝算法永远不会生成候选人最优的匹配。 (假)
- 解释： 如果所有工作的第一选择不同，那么算法会在第一天结束，候选人也会得到最优选择。
如果所有候选人都将同一个工作放在偏好列表的末尾，该工作最终会与它最不喜欢的候选人匹配。 (假)
- 解释： 即使工作 1 在所有候选人的列表中排名最后，也有可能得到它的最优选择。

(b) 举例说明：假设某个候选人可以任意拒绝一个提议，说明这种能力如何让每个候选人都获得比原来更好的工作。

解释： 假设候选人 1 拒绝了工作 1，导致工作 1 向候选人 2 提议，最终所有候选人都得到了比原本更好的工作。这种拒绝行为导致了一连串的提议，优化了每个候选人的结果。