算法告诉你，为什么女生应主动 | 甜欣屋

大二在圣路易斯上了一门类似博弈论的课，非常有启发性，对我的人生观和爱情观产生了很大影响。比如上课讲的稳定婚姻问题（Stable Marriage Problem），中文社区很少被提及，也不太找得到证明过程和结论梳理。所以欣欣我根据上课笔记，纯手写了这篇文章，分享给大家。

问题描述：有n个男性和n个女性，每个人对异性都有一个长度为n的意向排名（preference list）。要将他们配成n对，使得他们的“婚姻”是稳定（stable）的。

“稳定”的定义是，不存在任何一组男性A和女性B ，他们在一起比他们现在的分配要更好。这样的一对叫阻碍对（blocking pair）。

举个栗子。现在有三男三女：

m1: w2 > w1 > w3

m2: w1 > w3 > w2

m3: w1 > w2 > w3

w1: m1 > m3 > m2

w2: m3 > m1 > m2

w3: m1 > m3 > m2

那么这题的一个解是：

w1 – m3

w2 – m1

w3 – m2

为了解决这个问题，两个美国人提出了以他们名字命名的算法（Gale-Shapley Algorithm）。如下。

1）初始化所有人为单身。

2）对于每个单身男性m，让他向他意向表中未被他求婚过的排名最高的女性求婚，就叫w好了。这时候有两种情况：

i）w仍单身，那么m和w就在一起了。

ii）w已经和m’在一起了，那么比较w的意向表里m和m’谁的排名高，w就和谁在一起，另一个人就是单身。

3）重复第二步直至没有男性是单身。在一起的每一对就结婚了。

非常简单粗暴的算法。在循环的过程中，每个人的配对不断可能被更新，女性的配对不断变好，而男性的不断变差。当算法执行至停止时，每个人都会被配对。

首先，可证这个算法是正确的，我们最后得到的解是稳定的。假设解不稳定，那么根据定义，存在一组男性m和女性w，他们在一起比他们现在的分配（m，w’）和（m’，w）要更好。这样的话，m肯定在w’之前已经向w求婚过了，他们应该在一起了才对。与已知条件矛盾，假设不成立。

虽然这个解是稳定的，但这并不一定是最佳解，取决于你从谁的角度来看。这个算法对于主动方是最佳的。我们刚才描述的算法，是男性主动（man-proposed）的版本，每个男性能与他所能配对的最好的女性配对，或称男性最优（man-optimal）。同样地，如果把算法里的性别反一下，女性主动版本（woman-proposed）对女性最优。

证明有点绕。要证的是，一个男性不会被一个“可以配对到的（achievable）”女性拒绝。假设男性m被女性w拒绝了，那一定是w本身不可被配对到——如果w单身，那她肯定会接受才对；如果w选择和m’在一起，那么相比其他未拒绝m’的女性，m’更倾向于w，那么m’和w就会变成阻碍对，解不稳定。但这个算法得出的解一定是稳定的，所以原假设不成立。

稳定婚姻问题还有两个变种。一个是两个选项并列的情况，即一个人喜欢A和B同样多。一个是多了留空选项，比如A的意向列表里只有B，不在一起宁可单身一辈子。对于这两种变化，以上结论仍然成立。证明略，有兴趣的朋友可以自己试一下。

接下来扯点别的。当我听说“谁主动谁最优”的结论的时候，作为女生我有点震惊。值得注意的是，这个问题不只有“男性主动”和“女性主动”两种解法。我的理解是，还可以有很多介于两者之间或者其它的奇奇怪怪的算法。而我们所处的现实社会，可能是一种比较接近“男性主动”的算法的复杂版。

大家都说女生要矜持，不能太主动。而这样的结果可能就是，错过明明可以在一起的喜欢的人。没有阴谋论，但是那些说教者到底为的是什么效果，女生为什么又一定要坐等幸福来临，而不是去勇敢地追求自己想要的呢。

（此篇在微博得到了三十万阅读量，同步更新至甜欣屋）

评论区

shopee运营国际站 2022年7月18日回复

希望能学有所成。

雷达探币 2021年9月18日回复

人生能相遇,已是不易,心灵若相知,更要珍惜

高往北 2021年8月25日回复

我认为这个算法，可以改进成为一个产品的基础，让大家都公开分享自己的preference list，然后算法循环哈哈哈，等到算法停止的时候，大家各回各家，各找各夫（妻）
我承认我是在知乎被作者签名骗进来的，我还特地点开头像大图，看看像不像欧阳娜娜，结论是，还真像。

甜菜欣欣 2021年8月25日回复
唔，莫非我是照骗
- 高往北 2021年8月25日
  不算不算，低配版的欧阳娜娜！

大黑 2019年11月13日回复

已阅

白白 2019年11月6日回复

稳定婚姻算法！太惊人了

哆啦a梦大富翁 2019年3月23日回复

看不懂但感觉很厉害哈哈哈哈

TinaC 2019年2月3日回复

虽然算法我没看太懂（估计还要看第二遍），但对结论印象深刻，无论是机会还是婚姻，如果遇到了真心喜爱的，宁愿努力去争取，你也会收获属于你的独特的结果。

杰新博客 2019年1月7日回复

真心佩服，这么厉害头发还这么多

你的昵称* 2019年1月6日回复

类似的算法见过好几个了，也写过一些程序来模拟，最后得出的结论就是，自己单身是有原因的，这些算法有趣归有趣，该单身还是单身?

高往北 2021年8月25日回复
这个算法模拟的是人数和成员不变的情况下，在现实世界里，这是很不可能实现的一个情况。

精斑检测 2018年11月3日回复

用算法果然很可怕

女装品牌 2018年10月29日回复

文章不错支持一下

chencool.com 2018年10月11日回复

这个有意思，哈哈~

十三姨爱我 2018年10月11日回复

欣欣成大牛咯！

高歌人未老 2018年9月13日回复

例子的正确的解应该是：
w1 -m3
w2 – m1
w3 -m2

你之所以给出了你现有的那个答案是因为你对算法的步骤理解有偏差（严格点说，你写的算法步骤不正确）。单身男性的propose是一轮一轮来的，女性（不一定要单身）在某一轮的当中，从“所有”向她propose的男性中选她最喜欢的在一起。目前你所写的算法步骤在女性选择的时候并没有强调“同步”的意思，所以导致你的结果出现了偏差。