[ALDE 0x02] GS 算法

01 稳定匹配问题

稳定匹配（Stable Matching）问题是博弈论和算法中的一个经典问题，它被提出于 1962 年的一篇论文 College Admissions and the Stability of Marriage。虽然它最初的描述是一个结婚对象的分配问题，但在实际中应用广泛，经常被用于资源分配问题的建模，最有名的例子就是医疗资源分配问题——按医学生的意向和医院的录用倾向，将医学生分配到不同医院。

稳定匹配问题的描述是：

现有 $N$ 个男士和 $N$ 个女士，每位男士和女士心里都有一个按偏好程度排列的异性偏好表 (preference list)。现要为这些男女配婚，并且每位男士和女士最终都会被分配到一个异性伴侣。当出现下列情形时，认为出现了一对不稳定匹配 (unstable pair)：假设最终的分配方案中存在两个匹配为 $(m_1,w_1)$ 和 $(m_2,w_2)$，但 $m_1$ 更偏好 $w_2$ 而不是他现在的伴侣，且 $w_2$ 也更偏好 $m_1$ 而不是她现在的伴侣，那么他们就有一起私奔 (elope) 的可能性，则我们称 $(m_1,w_2)$ 为一个不稳定匹配。求一种稳定的分配方案，使得分配方案中不存在不稳定匹配。

举例：下面是 3 位男士和 3 位女士的偏好列表：

💭假设我们按照 $(X,C), (Y,B), (Z,A)$ 的方案进行分配，得到的会是一个稳定匹配吗？

👉答案是 No! 因为这里面存在一个不稳定匹配，也就是 Xavier 和 Bertha，他们俩偏好彼此胜过自己现在的伴侣。

💭那么 $(X,A), (Y,B), (Z,C)$ 是一个稳定匹配吗？

👉这是一个稳定匹配，因为找不到任何不稳定匹配。

02 Gale–Shapley 算法

稳定匹配问题是由 D. Gale 和 L. S. Shapley 这两位数学家提出并解决的，它们提出的 Gale–Shapley 算法（简称 GS 算法）以一种极为简单的思想解决了这一问题。GS 算法的伪码描述如下：

初始时所有人都是单身
while (存在男士还没有匹配对象 并且 还存在女士没有被他求过婚) {
    从这种男士中选出一位并令其为 m
    令该男士列表上排名最靠前的没有被他求过婚的女士为 w
    if (w 为单身)
    	将 m 和 w 配对
    else if (w 偏好 m 超过它现在的未婚夫 m')
    	将 m 和 w 配对并把 m' 设置为单身
    else
    	w 拒绝 m 的求婚
}

GS 算法保证最后能找到一种稳定匹配方案。每轮循环，算法都选出一个男士，来跟他列表上的一位女士进行匹配，这样的配对一共存在 $n^2$ 种，即算法最多尝试 $n^2$ 种匹配，因此该算法的时间复杂度为 $O(n^2)$。

03 正确性证明

下面我们将讨论 GS 算法的正确性。但在证明之前，我们先从算法中得到两个洞察，这两个洞察将会帮助我们证明：

1. 洞察 1:男士永远按照自己的偏好程度降序地去向女士求婚。
2. 洞察 2:女士一旦被匹配，就无法变回单身，只会权衡利弊更换男士。

我们将从完全性和稳定性方面证明。首先是完全性（perfection）。GS 算法的完全性是指：所有的男士和女士都会被配对，不会存在遗漏。我们使用反证法证明这一点：

1. 假设算法结束后，男士 $Z$ 还未被匹配。
2. 由于男士和女士数量相等，并且一位男士只能匹配一位女士，因此还肯定存在一位女士 $C$ 也还未被匹配。
3. 由洞察 2 可知，$C$ 肯定一次都没有被求婚过。
4. 但 $Z$ 肯定是向每位女士都求过婚但是没有成功才会到最后都没有被匹配，因此 $C$ 不可能没有被求过婚，由此产生了矛盾。
5. 综上，假设不成立，因此 GS 算法是完全的。

下面证明稳定性（stability）。GS 算法的稳定性是指：肯定不存在不稳定匹配。同样的，我们使用反证法进行证明：

1. 假设存在 $(A,Z)$ 是一对不稳定匹配，他们都偏好彼此胜过他们当前的未婚夫（妻）。
2. 情况一：$Z$ 从来没有向 $A$ 求婚：
   1. 由洞察 1 可知男士会按偏好程度从高到底对女士进行求婚，如果 $Z$ 没有向 $A$ 求过婚，那说明他已经和排在 $A$ 前面的女士匹配好了。
   2. 如此一来，$(A,Z)$ 应该是稳定匹配，与假设矛盾。
3. 情况二：$Z$ 向 $A$ 求过婚。
   1. 如果 $Z$ 像 $A$ 求过婚但 $Z$ 没有和 $A$ 匹配上，那说明 $A$ 把 $Z$ 拒绝了，由洞察 2 可知，此时 $A$ 肯定更偏好她当前的匹配对象。
   2. 如此一来，$(A,Z)$ 应该是稳定匹配，与假设矛盾。
4. 综上，假设不成立，因此 GS 算法是稳定的。

04 算法优化

我们之前说 GS 算法的时间复杂度为 $O(n^2)$，这是最理想的情况，实际上如果不加任何优化，时间复杂度将会退化至 $O(n^3)$。为什么？比如，每次循环男士都要向当前还未被自己求过婚的，偏好列表上排名最前的女士进行求婚，女士也要根据自己的偏好列表决定要不要拒绝当前男士，如果直接遍历偏好列表，就会在循环内部多出 $O(n)$ 的查询时间，使得时间复杂度达到 $O(n^3)$。长此以往，还有其他地方也会使得时间复杂度上升，我们将一一解决。

首先是循环的最开始，我们要去挑出一位单身的男士。为了避免去遍历男士列表来寻找这位男士，我们可以维护一个“单身汉”队列，每轮循环开始，都从队首找出这样一位单身汉；每轮循环中如果有匹配被取消，就把被换掉的男士插回队尾；每轮循环结束，如果没有配对成功就插回队尾。这样能使得寻找单身汉的时间变为 $O(1)$。

关于男士向女士求婚：首先要为每位男士维护一个偏好列表，该列表按照男士偏好，将女士从高到底排序。此外，还要维护一个数组 count，其中，count[m] 表示第 $m$ 位男士求婚的次数，可以根据这个值来直接找出本轮循环要求婚的女士。

关于女士接受/拒绝男士：要为每位女士维护一个偏好列表的翻转列表 inverse，inverse[m] 表示第 $m$ 位男士在该女士的偏好列表中的排名，假设 $m^{\prime}$ 是该女士当前未婚夫的序号，那么只需比较 inverse[m'] 和 inverse[m] 就知道是否该拒绝男士 $m$ 了。

05 man-optimality

假设在一个稳定匹配问题中存在多组稳定匹配，那么 GS 算法将会输出哪一种呢？

事实上，GS 算法具有 man-optimality 的性质。意思是，GS 算法最终输出的匹配方案，对男士而言是最优的，每个男士将得到在保持稳定性的情况下对自己而言最好的对象，但反过来，女士并不一定得到最优解。对于女士而言，这里完全可能还存在着另外一种稳定匹配方案，使得自己能得到更好的对象，但不破坏稳定性。

下面我们将证明这一点，并且分析造成这种现象的原因。

我们仍然使用反证法证明 GS 算法是 man-optimal 的：

1. 假设某些男士最终的匹配对象不是最优解。由于男士都按降序进行求婚，因此这些男士肯定都被一位合法匹配对象拒绝了。
2. 令第一位被合法匹配对象拒绝的男士为 $Y$，第一位拒绝它的合法匹配对象为 $A$。（所谓“合法匹配对象”是指一位女士，并且存在一种稳定匹配方案，使得在这个方案中，该男士的匹配对象是该女士）
3. 令 $S$ 为一个稳定匹配方案，并且在 $S$ 中存在 $(Y,A)$。
4. 当 $Y$ 被 $A$ 拒绝的时候，$A$ 一定和另一位男士在一起，令这位男士为 $Z$，这说明 $A$ 偏好 $Z$ 胜过 $Y$。
5. 令 $B$ 为 $Z$ 在 $S$ 中的匹配对象。
6. 由于 $Y$ 是第一个被合法匹配对象拒绝的男士，因此在 $Y$ 被 $A$ 拒绝之前，任何男士（包括 $Z$）都未被其合法匹配对象拒绝。而男士在 GS 算法中按偏好顺序求婚，因此 $Z$ 尚未被拒绝意味着他尚未向其在 $S$ 中的匹配对象 $B$ 之前的女性求婚失败，从而 $Z$ 更偏好 $A$ 于 $B$。
7. 但是 $A$ 偏好 $Z$ 胜过 $Y$，因此在 $S$ 中 $(A,Z)$ 是不稳定匹配，这与 $S$ 是一个稳定匹配的假设矛盾，因此假设不成立。

那么为什么 GS 算法会对男士更加友好？这是因为在 GS 算法中，提出求婚的一方（这里是男士）始终按照自身偏好从高到低行动，而被求婚的一方只是在已有选择中做“保留更优、拒绝较差”的被动筛选。这个过程保证了：任何男士一旦被某位女士拒绝，就不可能在任何稳定匹配中与她配对。因此，算法结束时，每位男士得到的都是在所有稳定匹配中对自己而言最好的合法匹配对象。换言之，主动方通过系统性地“先尝试最好选项”，排除了所有在稳定解中不可能实现的更优匹配，从而实现了对主动方的整体最优性。

06 启示

GS 算法表明，在规则明确、偏好稳定的匹配环境中，谁掌握主动权，谁就会在可行结果集合中获得结构性优势。男士并不是等到“确定最优”才行动，而是按照偏好顺序不断尝试；被拒绝并不是失败，而是信息的获得：它直接告诉你“这条路在任何稳定结果中都走不通”。不仅是求偶，升学、找工作也是同样的道理，一定要去试错，等来的那个结果，肯定是对对方有益，而不是对你最好的结果。

同时，GS 算法的例子也告诉我们：算法和规则并非中立，它们会系统性地偏向某一方。因此，在设计或参与匹配机制时，一方面需要意识到主动权带来的不对称收益，另一方面也应根据公平性目标谨慎选择“谁提出申请、谁进行筛选”，以避免长期、隐性的制度性压迫。