>>>  創業先鋒 眾人拾柴火焰高  >>>

簡體     傳統

（本文來自知乎網友尼克余）

我來講戀愛中的博弈，不，我來講戀愛中的算法，不，我來講算法！！

有個著名的問題，叫做 stable matching。早年是一個可愛的俄羅斯老頭在圖論課上教我的，印象非常深刻，拿出來娛樂下大家。因為這個算法應用太廣泛了，這個算法的兩位發明人 David Gale 和 Lloyd Shapley，在 2012 年因為這個算法獲得諾貝爾經濟學獎。

先說結論：女生遇到心動的男人一定要追！我馬上就要來證明。

前方高能預警！！！含大量數學圖論及計算機編程算法知識，萌妹子請直接退散。

假設，有一個平行世界，我們姑且叫這個世界，平行世界 999 號，這個世界有 n 個男人，還有 n 個女人，然后每一個男人，都有一個對喜歡的女人的排序，比如男 A，有一個排序（女 A，女 B，一直到女 N），每一個女人都有一個喜歡的男人的排序，比如女 A，有一個排序（男 A，男 B，一直到男 N）。每個男的都會試圖去追求自己的排序里頭排的最高的女性，每個女的都會接受自己排序里頭最高的男性的追求。

再假設這個平行世界 999 號，有以下追求方法（算法）：

1. 這個世界上只有男人能夠追求女人，女人收到一個男人的追求，可以選擇說“你做我男友吧”，或者“你滾犢子”。當女人說“你做我男友吧”的時候，這個男人和女人進入了男女朋友模式，當女人說，“你滾犢子”的時候，這個男人回復單身。

2. 每個男人只能在單身的時候追求女人，而每個女人最多只能有一個男朋友

3. 每個男人都會追求自己名單上排位最高的女人，當被拒之后，會追求排位次高的女人，被拒之后再追第三高的女人，以此類推。每個女人，如果沒有男朋友，收到追求，會立刻說，“你做我男友吧”，如果有男朋友，會將現有男朋友與追求者比較，選擇其中排位更高的，甩掉排位更低的。

4. 每個男人都會鍥而不舍的一直把整個排序追求完，直到脫離單身狀態為止。

5. 當每個男的和女的都有一個女、男朋友的時候，會所有人一起結婚。

怎樣，是不是和現實很像？讓我喝口水繼續寫！

我的結論是，這個世界里頭，一定會有這么一個組合，使得，這 n 個男的，和 n 個女的，會形成一個穩定的一一對應的婚姻關系。也就是說，這 N 個男人和女人，都合理的選擇了自己名單上最高的排位的那個對象。

我說的有點亂，因為我學的是用英語學的，而我的翻譯實在是不咋地，我先來簡化問題：

一、假設這個世界上只有 1 個男人，1 個女人

那不用想了，排什么排，去滾床單，裸奔，過沒羞沒躁的生活去吧。

二、假設這個世界上有 2 個男人（男 A，男 B），2 個女人（女 A，女 B）

這就開始復雜了，

如果，男 A 和男 B 的排序都是（女 A，女 B),女 A 和女 B 的排序都是（男 A，男 B）。

那么很簡單，男 A 和男 B 一起去追女 A，男 B 迅速杯具，男 A 和女 A 在一起，男 B 和女 B 在一起，故事完結。

如果,男 A 和男 B 的排序都是（女 A，女 B)，女 A 和女 B 的排序都是（男 B，男 A）。

那么也很簡單，男 A 和男 B 一起去追女 A，男 A 迅速杯具，男 B 和女 A 在一起，男 A 和女 B 在一起，股市完結。

如果，男 A 的排序是 （女 A，女 B），男 B 的排序是（女 B，女 A），女 A 的排序是（男 B，男 A），女 B 的排序是（男 A，男 B）呢，那怎么辦？

那么現在，男 A 會去追求女 A，女 A 會說，“你做我男友吧”，男 B 會去追求女 B，女 B 會說“你做我男友吧”。

于是大家結婚了。

所以現在的組合是，男 A 和女 A，男 B 和女 B。

但是！！！但是！！！

你們發現了問題沒有？？？

每個男的都追求到了自己最喜歡的女士，每個女士卻只贏得了自己最不喜歡的男士！！！！

這就是這個算法的一個弊端，就是追求者，有占優的可能性。

如果反過來，平行世界 999 里，只允許女人追求男人，會出現下面情況：

女 A 去追求男 B，男 B 會說，“你做我女友吧”，女 B 去追求男 A，男 A 會說“你做我女友吧”。

于是大家都結婚了。

現在的組合是男 A 和女 B，男 B 和女 A。這同樣是一個穩定的匹配。

但是！！！但是！！！現在每個女士都追求到了自己最喜歡的男士，每個男士卻只贏得了自己最不喜歡的女士！！！

三、推廣到 N 男 N 女，也是一樣的推論。

簡單的說，就是因為這是一個單向篩選，每個男的都會確保會向自己的排序中最高的女性表白。然而男性被“滾犢子”的唯二可能性，是因為這個女性有一個她心目中排序更高的男朋友，或者當了一段時間男朋友，但一個排序更高的男人向她表白。（當然現實中大家也懂，你就是沒戲的了，而且是你本來就沒戲）

因此，確保了男性一定能追求到自己喜歡的名單里頭，排位最高的女性。

也就是說，在這個追求關系里頭，主動的那一方更能夠找到自己更喜歡的異性，而被動那一方，卻沒有這樣的優勢。

所以結論就是，妹子們，遇到喜歡的男人，一定要主動！

CocoaChina 2015-08-23 08:44:31