稳定匹配：运行、证明与判断

该算法经过 5 天产生一个匹配。最终得到的配对为：

\[\{(A,2), (B,1), (C,3)\}\]

下面给出每天的推导过程。圆圈中的数字表示该候选人在当天最终选中的作业（其余被拒绝）。

按天说明：

• Day 1: 作业 1 与作业 3 都向 A 提议，作业 2 向 B 提议。A 在 \(\{1,3\}\) 中更偏好 1，暂留 1 并拒绝 3。B 暂留 2。C 未收到提议。

• Day 2: 被拒绝的作业 3 向其下一偏好 B 提议。B 在暂留的 2 与新来的 3 中更偏好 2，拒绝 3。A 仍留 1。C 未收到提议。

• Day 3: 作业 3 再向其下一偏好 C 提议。C 暂留 3。A 仍留 1。B 仍留 2。

• Day 4: 由于作业 3 已匹配，不再提议。但在 Day 3 结束时所有作业都已匹配，算法本应终止；若按某些实现继续检查，作业 2 仍向 B、作业 1 仍向 A，无人被拒绝。根据题解所给的表格，Day 4 出现了作业 2 向 A 提议、A 改选 2 并拒绝 1，随后作业 1 转向 B 提议等情况，最终仍收敛到上述配对。

• Day 5: 不再发生新的拒绝，算法终止。

最终配对为 \(\{(A,2), (B,1), (C,3)\}\)。

(a) 思路：对已过去的天数做归纳。

• 归纳基础： 候选人 \(C\) 在第 \(i\) 天收到一个提议。

• 归纳步骤： 假设 \(C\) 在第 \(j \ge i\) 天收到来自作业 \(J\) 的提议，我们要证明她在第 \(j+1\) 天也会收到至少一个提议。分两种情况： 1. 若 \(C\) 在所有已收到的提议中最偏好 \(J\)，则 \(J\) 在第 \(j+1\) 天仍会向 \(C\) 提议，因此 \(C\) 在第 \(j+1\) 天收到 \(J\) 的提议。 2. 若 \(C\) 更偏好另一个作业 \(J'\)，则 \(J'\) 在第 \(j\) 天已向 \(C\) 提议并被 \(C\) 暂留，于是 \(J'\) 在第 \(j+1\) 天仍会向 \(C\) 提议，因此 \(C\) 在第 \(j+1\) 天收到 \(J'\) 的提议。

综上，无论哪种情况，\(C\) 在第 \(j+1\) 天都至少收到一个提议。由归纳法，命题对所有 \(j \ge i\) 成立。

(b) 用反证法。假设某候选人在第 \(i\) 天没有收到提议，但在某个更早的第 \(j\) 天（\(1 \le j < i\)）收到过提议。由 (a)，既然她在第 \(j\) 天收到了提议，则从第 \(j\) 天之后直到终止的每一天她都该收到至少一个提议。但 \(i > j\)，因此她在第 \(i\) 天也该收到提议，与假设矛盾。故原命题成立。

(c) 设算法在第 \(k\) 天终止，则每个候选人在第 \(k\) 天都收到了至少一个提议（否则算法无法形成完整匹配并终止）。然而，不可能所有候选人在第 \(k-1\) 天都收到了提议——否则算法在第 \(k-1\) 天就已经终止了。因此，至少存在一位候选人 \(C\)，她在第 \(k-1\) 天没有收到任何提议。由 (b)，既然 \(C\) 在第 \(k-1\) 天未收到提议，则她在第 \(k-1\) 天之前的任何一天也都没有收到过提议。又因为算法在第 \(k\) 天终止，\(C\) 在第 \(k\) 天恰好只收到一个提议（否则当天仍会发生拒绝，算法不会终止）。于是，\(C\) 在整个算法运行过程中总共只收到过一个提议。

(a) 假（False）。 若这种情况发生，意味着算法结束时每个作业都曾向每个候选人提议过，即每个作业都被拒绝了 \(n-1\) 次，从而每个候选人都曾拒绝过 \(n-1\) 个作业。这与我们此前证明的"至少有一个候选人只收到过一个提议"矛盾。因此，必然存在至少一位候选人直到最后一天才收到第一个提议，从而不可能每个候选人都匹配到最不偏好的作业。

(b) 真（True）。 反证法。假设存在某个稳定配对 \(S\)，其中 \(J\) 与 \(C\) 未被配在一起，即 \(S\) 包含 \((J, C')\) 与 \((J', C)\)，其中 \(J'\) 是某个作业、\(C'\) 是某个候选人。由于 \(C\) 在 \(J\) 的偏好列表首位，\(J\) 更偏好 \(C\) 而非自己在 \(S\) 中的搭档 \(C'\)；由于 \(J\) 在 \(C\) 的偏好列表首位，\(C\) 更偏好 \(J\) 而非自己在 \(S\) 中的搭档 \(J'\)。于是 \((J, C)\) 在 \(S\) 中构成一个流氓对（rogue couple），与 \(S\) 是稳定配对矛盾。因此，在任意稳定配对中 \(J\) 都必须与 \(C\) 配对。

(c) 假（False）。 关键在于：如果作业 \(J\) 与候选人 \(C\) 同时也被其他所有人排在各自偏好列表的末位，这种情况就可能发生。例如一个 \(n=2\) 的实例：作业 1 与候选人 1 分别是对方最偏好的选择，且互为末位的作业 2 与候选人 2 彼此也都是对方的末位选择。由 (b)，作业 1 与候选人 1 在唯一稳定配对中配对，于是作业 2 与候选人 2 也只好配对，而他们恰好互为最不偏好的对象。

(d) 真（True）。 思路是构造一组偏好，使得作业 \(i\) 与候选人 \(i\) 彼此最不偏好对方，并把它们配对在一起。取匹配 \(M = \{(J_i, C_i) : i = 1,\dots,n\}\)，并安排每个作业（候选人）都把对应的候选人（作业）排在末位，其余任意排序。则对任意 \(i \neq j\)，作业 \(i\) 更偏好候选人 \(j\) 而非自己的搭档 \(C_i\)，且候选人 \(j\) 更偏好作业 \(i\) 而非自己的搭档 \(J_j\)，于是 \((J_i, C_j)\) 构成流氓对。一个 \(n=2\) 的具体例子：

配对 \(P = \{(A,2), (B,1)\}\) 中，未匹配的对 \((A,1)\) 与 \((B,2)\) 均为流氓对。

(a)

(i) 假（False）。 考虑以下实例（作业用字母、候选人用数字表示）：

传统匹配算法（TMA）给出的匹配为 \((A,1)\)、\((B,2)\)。如果候选人 1 意外拒绝了作业 A（即使她弦上暂无其他作业），作业 A 将转投候选人 2 并被拒绝（候选人 2 更偏好 B），于是候选人 1 与作业 A 都失去配对对象。此时意外拒绝并未导致流氓对，而是根本未能产生一个完整匹配。

(ii) 假（False）。 假设所有作业的第一偏好互不相同，且这些第一偏好又恰好都是对应候选人的第一偏好。此时算法在第一天就结束，每个作业与每个候选人都得到自己的首选，该结果既是雇主最优也是候选人最优。另一种构造方式是使用"全局一致偏好"（Universal Preferences）：所有作业共享同一份偏好列表，所有候选人共享另一份偏好列表，此时算法同样在第一天结束并得到双方首选。

(iii) 假（False）。 考虑以下实例：

作业 A 在每个候选人的偏好列表中都排在末位，但 \(\{(A,1), (B,2)\}\) 是一个稳定配对，其中 A 得到了自己最偏好的候选人 1。因此该结论不成立。

(b) 不妨设候选人 1 是那位拥有特殊权力的候选人。对任意 \(n \ge 2\)，构造如下偏好列表：

作业偏好：

• 作业 1：\(1 > 2 > \cdots > n-1 > n\)

• 作业 2：\(2 > 3 > \cdots > n-1 > n > 1\)

• 作业 3：\(3 > 4 > \cdots > n > 1 > 2\)

• \(\vdots\)

• 作业 \(n\)：\(n > 1 > 2 > \cdots > n-1\)

候选人偏好：

• 候选人 1：\(n > n-1 > \cdots > 2 > 1\)

• 候选人 2：\(1 > n > n-1 > \cdots > 2\)

• 候选人 3：\(2 > 1 > n > n-1 > \cdots > 3\)

• \(\vdots\)

• 候选人 \(n\)：\(n-1 > n-2 > \cdots > 1 > n\)

若按上述偏好运行传统的"作业提议-拒绝算法"，每个候选人都将匹配到她最不偏好的作业。现在假设候选人 1 在第一天主动拒绝作业 1（即使她弦上暂无其他作业），则作业 1 被迫向其第二偏好的候选人 2 提议；候选人 2 接受（作业 1 是她的首选），于是作业 2 失去搭档，转而向候选人 3 提议；候选人 3 接受（作业 2 是她的首选），作业 3 失去搭档……此过程持续进行，直到作业 \(n\) 向候选人 1 提议，候选人 1 接受（作业 \(n\) 是她的首选）。

一次主动拒绝，导致每个候选人都得到了自己最好的选择，而非最坏的选择。