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

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

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

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

(此篇在微博得到了三十万阅读量,同步更新至甜欣屋)

评论区

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

    希望能学有所成。

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

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

  3. 高往北 2021年8月25日 回复

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

    • 甜菜欣欣 2021年8月25日 回复

      唔,莫非我是照骗

      • 高往北 2021年8月25日

        不算不算,低配版的欧阳娜娜!

  4. 大黑 2019年11月13日 回复

    已阅

  5. 白白 2019年11月6日 回复

    稳定婚姻算法!太惊人了

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

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

  7. TinaC 2019年2月3日 回复

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

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

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

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

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

    • 高往北 2021年8月25日 回复

      这个算法模拟的是人数和成员不变的情况下,在现实世界里,这是很不可能实现的一个情况。

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

    用算法果然很可怕

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

    文章不错支持一下

  12. chencool.com 2018年10月11日 回复

    这个有意思,哈哈~

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

    欣欣成大牛咯!

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

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

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

    • liqingya 2019年2月1日 回复

      同意你的看法,感觉这个例子博主po出的解是有些问题的

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

    你给的例子的解
    w1 – m2
    w2 – m1
    w3 – m3

    好像并不stable吧,比如考虑 m3和w1,按照你的ordering,w1 prefer m3 to m2,而同时 m3也prefer w1 to w3。所以你给的解并不stable。

  16. 通古思 2018年9月3日 回复

    我觉得,我们之间,我还是主动点的好。

  17. 探索之家 2018年9月1日 回复

    不错. 顶一下女程序猿

  18. zh 2018年8月28日 回复

    不过主动追求可能有不知道未来会不会遇到更好的问题

  19. 大学生暑假兼职 2018年8月22日 回复

    看来,算法可以解决大部分事情了

  20. 博客之家 2018年8月12日 回复

    幸福和機會也是要爭取的。

  21. foobar 2018年8月9日 回复

    不接入更灵活的评论 https://disqus.com/ ?

  22. 清风夜独醉 2018年7月30日 回复

    太,太深奥了,看不懂。

  23. 叶檀 2018年7月30日 回复

    大量的运算,脑容量算不出来

  24. 辛锐 2018年7月29日 回复

    为什么感觉页面滑动的时候比较卡

  25. 鸟叔 2018年7月26日 回复

    三十万阅读量,好厉害

  26. 杨小杰博客 2018年7月23日 回复

    虽然是第二次看了,但是我依然懵圈

  27. 吃馒头的猫 2018年7月23日 回复

    哇,涨姿势了

  28. will 2018年7月23日 回复

    羡慕理科生 可以多一个维度去了解世界 真好

    • Khalil 2018年8月30日 回复

      同感

  29. Elgar 2018年7月23日 回复

    没抢到第一???

  30. 张格拉斯 2018年7月23日 回复

    ????哈哈哈哈,第一耶

发表回复

您的电子邮箱地址不会被公开。