丘比特之箭与数学匹配的魔法：婚姻配对问题

jhDfiPdP · 2025-2-22 10:54:06

男女稳定婚姻问题

现实篇：相亲修罗场里的蝴蝶效应
霓虹闪烁的都市里，婚介所的王阿姨正对着满墙的会员资料发愁。985硕士张先生执着于温柔贤惠的文科女生，创业女强人李小姐却将幽默感列为择偶第一要素。看似简单的牵线搭桥，实则暗藏玄机——若强行配对"条件相当"但偏好错位的两人，很可能上演现实版《前任攻略》：小王和小芳虽在婚介所登记结婚，私下却与彼此的真爱暗度陈仓。
这正是数学家Gale和Shapley在1962年精准捕捉的婚姻配对问题：当 \(n\) 位男士与 \(n\) 位女士各自手握一份心动排序表，如何设计一个"拆不散"的终极配对方案？这里的"拆不散"不是月老的红线，而是一种精妙的数学稳态——稳定匹配。
定义：稳定婚姻问题
设男士集合 \(M = \{m_1, m_2, ..., m_n\}\)，女士集合 \(F = \{f_1, f_2, ..., f_n\}\)，每个人心中都有一杆秤：

每位男士 \(m_i\) 对女士的偏好可表示为全序关系 \(>_{m_i}\)
每位女士 \(f_j\) 对男士的偏好同理为 \(>_{f_j}\)

一个匹配 μ 是将男士与女士一一对应的双射。匹配的方案有很多种，但这个匹配要成为稳定匹配，必须消灭所有"私奔因子"——即不存在 \((m, f)\) 使得：

\(m\) 比起其现任 \(μ(m)\) ，更爱 \(f\)（即\(f >_{m} μ(m)\)）
同时 \(f\) 比起其现任 \(μ(f)\) ，更爱 \(m\)（即\(m >_{f} μ(f)\)）

这样的危险组合 \((m, f)\) 被称为阻塞对(blocking pair)，就像婚恋市场里的不定时炸弹。他们更喜欢彼此，却都委屈的和不太喜欢的现任在一起。而我们的任务，就是构建一个让所有炸弹自动失效的匹配方案。
Gale-Shapley算法：相亲会

此刻，数学家们已经挥舞着算法之杖悄然降临。用递玫瑰的智慧破解爱情密码。想象所有男女来到相亲会配对。Gale和Shapley设计的算法，作为主持人，指挥着这场求偶仪式：

初始化：每位男士和女士都处于自由状态，手中空空如也。
求婚阶段：每位自由男士 \(m\) 按照自己的偏好列表，向尚未拒绝过他的最高位女士 \(f\) 献上玫瑰。
抉择时刻：每位女士 \(f\) 收到若干玫瑰后，暂时保留最心仪的那一支（即偏好列表中排名最高的男士），其余男士惨遭拒绝。已经拥有配偶的女士会将当前配偶也加入和新的请求比较，选择最心爱的那一个。这意味着已配对的男性可能重新单身，他需要向偏好位下一位的女性继续求婚。
循环往复：被拒绝的男士们重获自由身，继续向下一位心仪女士发起攻势，直到所有女士都手握一支玫瑰。

用伪代码描述这场玫瑰盛宴：
初始化所有男士和女士为自由状态while 存在自由男士 do 选择一位自由男士m f = m的偏好列表中尚未被自己求婚的最高位女士 if f处于自由状态 then m和f暂时配对 else if f更偏爱m而非当前配对对象m' then 解除f与m'的配对 m和f暂时配对将m'设为自由状态 else m继续保持自由状态 end if end ifend while

正确性与复杂度

Gale-Shapley算法最令人惊叹之处，在于它总能找到一个稳定匹配。：

终止性：算法必然在有限步内结束。因为每位男士最多向 \(n\) 位女士求婚，且每次求婚至少有一位男士被拒绝或配对，总步数不超过 \(n^2\)，时间复杂度为\(O(n^2)\)
完美匹配：算法总是所有男士和女士都配对成功时才结束。若有男士 \(m\) 未配对，必有女士 \(f\) 也未配对，而 \(m\) 会继续向 \(f\) 求婚。
稳定性：假设存在阻塞对 \((m, f)\)，即非夫妻但 \(m\) 更爱 \(f\)，\(f\) 更爱 \(m\)。根据算法，\(m\) 必然曾向 \(f\) 求过婚，而 \(f\) 要么拒绝了\(m\)（与 \(f\) 更爱 \(m\) 矛盾），要么接受了 \(m\)（与 \(m\) 未配对矛盾）。因此，阻塞对不存在。

谁才是真正的赢家？

Gale-Shapley算法有一个有趣的性质：男士最优或女士最优。即算法找到的稳定匹配，对主动求婚的一方（通常是男士）最有利，对被动接受的一方（通常是女士）最不利。

男士最优：在所有可能的稳定匹配中，算法结果使每位男士获得尽可能高的偏好对象。
女士最劣：在所有可能的稳定匹配中，算法结果使每位女士获得尽可能低的偏好对象。

这一性质揭示了算法的不对称性：主动出击者往往能获得更优的结果。