稳定匹配：幸福不靠等，脱单要主动

看到这个，你的第一反应可能是，搞对象这种我喜欢你你喜欢他他又喜欢我的东西，也能和算法扯上关系？



还真能。当然，我们得把处对象的问题定义和量化，就用这样一个男女配对的场景：

• 现在有单身的 N 个男生和 N 个女生，他们都想和对方处对象。

• 每个男生呢，对 N 个女生的喜好，都有一个明确的高低排序。

• 每个女生呢，同样，对 N 个男生也有明确的喜好高低排序。

• 当然，处了对象后，每个人都不想自己的对象出轨，给自己戴绿帽。

什么情形下会出现出轨的情况？很简单。

• 假设有两对情侣，情侣 A 中的男生比起自己现在的对象，更喜欢情侣 B 中的女生。

• 一个巴掌拍不响，情侣 B 中的女生也一样，比起现在的对象，更喜欢情侣 A 中的男生。

那么，这两人就很可能就勾搭上，给自己对象戴绿帽。



你觉得，大家应该基于什么样的策略来行动，使得他们能够全部成功配对脱单，同时所有配对都是稳定的，不会有出轨的情况？

不用想得太复杂，我们不妨就试下“男生追，女生挑”的策略。现实中也是大致如此。具体步骤是：

1. 每个男生按照自己对各个女生的喜好高低排序，挨个找女生表白；

2. 每个被追求的女生，如果自己单身或比起现任更喜欢新的追求者，就和新的追求者在一起；被甩掉的现任，要重新加入脱单大军；

实际上，这个就是所谓的 Gale-Shapley 算法，也叫求婚-拒绝算法，或延迟接受算法。



对于这种N男N女配对脱单的问题，GS 算法能保证输出唯一的稳定匹配结果，即所有人都成功配对，同时没有不稳定的组合。

通过反证法很容易证明这一点，这里就不啰嗦了。



Gale-Shapley算法在 1962 年提出，2012年获得诺贝尔经济学奖，目标是解决价格作用受限制的市场的资源配置问题。

资源最优配置是经济学研究一大主题。真实世界里配置资源的方式多种多样，价格机制是最常见最有效的一种。

但是在一些市场里，价格的作用受到法律、习俗或伦理道德等限制。最明显的例子就是婚恋市场，找对象不是价高者得，而是情投意合才能在一起。

毕竟，爱情不是买卖，不是你想买就能卖。

顺便一提，GS 算法在现实生活中的应用也是相当的广泛。例如，我们国家的高考志愿制度，也是 GS 算法的一种形式：学生按照自己的喜好填报志愿，学校根据学生的成绩进行录取和退档。

艺术源于生活，科学也能从生活升华。大家无意识形成的策略，背后的算法原来那么科学。

然而，找对象有 GS 算法找出稳定匹配，是不是就意味着皆大欢喜，人人幸福了呢？

很遗憾，不是。GS 这个算法实际上是不公平的，它对其中一方更有利。

那是不是对女生更有利？因为她们总是可以拒绝和反悔，选择更好的对象。

很遗憾，也不是。相反，GS 算法对主动的一方更有利，而且是现有条件的最优解。

也就是说，别看男生被甩得多，被发卡多，但最后他找到的妹子，会是他这条件能到到的最好的对象。​



我们来考虑一个极端的情况：

有 3个男生、3个女生，他们对对方的喜好排序是这样子的：



按照 GS 算法，得到的配对是这样的：





• 显然，3 个男生个个都是人生赢家，都和自己最喜欢的女生在一起。

• 然而，3 个女生就悲剧了，她们的伴侣恰好都是她们最讨厌的一个。

• 但是，只要不想单身，所有女生对这种局面都无能为力。

• 因为，这是一个稳定配对，没有男生会背叛自己的现任。



这展现一个什么道理？那就是，幸福往往不是等到的，被动等待带来的往往不是最好的结果，只有主动出击，才能保证让自己得到配得上你的幸福。

特别是很多小姐姐，仍习惯于别人追你来选，现在是不是突然有点后背发凉？

确实，现实生活中，具体问题比我们这种假设的场景更复杂。例如，首先不是所有人都是异性恋，也不会凑巧真有数目一样的男女一起等着脱单，不是一定男生追女生挑，不是每个男生都会按照自己喜好找女生挨个表白，不是每个女生都会因为遇到更好的人就甩掉现任。

不过，无论现实情况再复杂，只要场景吻合，GS 算法的导向必然是主动占优被动吃亏。

平时我们也能观察得到，别看主动的人被发好人卡多，往往他得到的是他能得到的最好结果。感情际遇不好，常抱怨自己运气不佳的，也往往是在感情中消极被动的一方。

所以记住啊，幸福是要靠自己用手抓住的，啥也不说，相信科学，主动出击！