💡 阿星精讲：匹配理论 的本质

想象一下，你是一个天才红娘，手上有 \( n \) 位男生和 \( n \) 位女生。每个人心里都有一个“理想对象排行榜”。你的任务不是简单地乱点鸳鸯谱，而是要设计一套无可挑剔的相亲算法，确保最终配成的 \( n \) 对情侣中，没有人会“出轨”——也就是不存在一对不是情侣的男女，彼此喜欢对方胜过喜欢自己现在的伴侣。这种状态就叫 “稳定匹配”。

1962年，盖尔（Gale）和沙普利（Shapley）证明，无论大家的偏好列表如何，稳定匹配总是存在的。他们设计的“延迟接受算法”（俗称“求婚算法”），就像一场精心设计的舞会：男生轮流向自己最心仪的女生求婚，女生则暂时接受她目前遇到的最好选择，并婉拒更差的。这个过程保证了最终没人想破坏现有关系去私奔。这个深刻而优美的理论在2012年为他们赢得了诺贝尔经济学奖。它不仅在婚恋市场成立，更广泛应用于大学招生、医院实习分配、器官移植等关键社会领域。

数学上，我们定义男生集合 \( M = \{m_1, m_2, ..., m_n\} \)，女生集合 \( W = \{w_1, w_2, ..., w_n\} \)，以及每个人的严格偏好排序。匹配 \( \mu \) 是一个一一对应的映射。稳定匹配的核心条件是：不存在一对 \( (m, w) \)，使得 \( m \) 相对于 \( \mu(m) \) 更偏好 \( w \)，同时 \( w \) 相对于 \( \mu(w) \) 更偏好 \( m \)。

🔥 经典例题精析

🚀 举一反三：变式挑战

答案与解析

经典例题答案： 稳定匹配为 \( \{(A, Y), (B, X), (C, Z)\} \)。（解析见上方阿星拆解部分）

变式一解析（思路）： 算法流程与男生主动版完全对称。医院 \( H_i \) 依次向自己最心仪且尚未被拒绝的学生发出offer。学生 \( S_j \) 在收到的所有offer和当前暂接受的offer中选择最好的一个，拒绝其他。重复直至所有医院席位满员或无法再发出offer。最终匹配对医院（主动方）是最优的，对学生（被动方）是最劣的（在所有稳定匹配中）。

变式二解析：
不可能。我们来检查稳定性条件。
- 对于 \( m_1 \)：他的现伴侣是 \( w_3 \)，但他更偏好 \( w_2 \)（因为 \( w_2 > w_3 \)）。
- 对于 \( w_2 \)：她的现伴侣是 \( m_3 \)。
- 我们需要检查 \( w_2 \) 是否也更偏好 \( m_1 \) 胜过 \( m_3 \)？题目未给出 \( w_2 \) 的偏好列表，所以无法判断。
- 但是，关键点在于：\( m_1 \) 单方面已经更偏好别人（\( w_2 \)），这本身不破坏稳定。破坏稳定需要双方都更偏好对方。然而，我们分析 \( m_1 \) 和 \( w_3 \) 这一对：\( m_1 \) 把 \( w_3 \) 排在最后，\( w_3 \) 把 \( m_1 \) 排在最后。他们都没有从这段匹配中获得任何可能更差的选择（因为彼此都是对方清单上的最后一名）。在他们的偏好视角下，找不到比对方更差的伴侣了。所以，他们在一起是可能的，并且这一对本身不构成对任何其他对的威胁。因此，仅凭给出的信息，不能断定这不是稳定匹配的一部分。此题陷阱在于引导我们仅凭一方不满意就判定不稳定，而忽略了稳定性的定义是“不存在相互更偏好”的破坏对。

变式三解析（思路）：
这是一个“一方多于另一方”的匹配问题，常用“医院-实习生”（HR）模型解决，它是G-S算法的扩展。我们可以引入一个“虚拟女生” \( \emptyset \) 来平衡人数，所有男生将其排在可接受列表末尾，且该虚拟女生接受所有人但偏好最低。然后运行男生主动的G-S算法。最终与 \( \emptyset \) 匹配的男生即为单身。匹配的“稳定性”定义为：不存在一个男生 \( m \) 和一个女生 \( w \)，使得 \( m \) 更偏好 \( w \) 而非他当前的伴侣（或单身），并且 \( w \) 也更偏好 \( m \) 而非她当前的伴侣。这样就能找到一个稳定匹配。