算法告诉你，为什么女生应主动

大二在圣路易斯上了一门类似博弈论的课，非常有启发性，对我的人生观和爱情观产生了很大影响。比如上课讲的稳定婚姻问题（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，不在一起宁可单身一辈子。对于这两种变化，以上结论仍然成立。证明略，有兴趣的朋友可以自己试一下。

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

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

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