離散數學之把妹要訣
離散數學課（CSCI 2110）上，講到一個有趣的問題。
假設有五個男生，五個女生，每個人都在自己心中對五個異性有一定的 preference 排序，比如：
以上的排序表解讀為：男生 1 最中意女生C，次中意女生B，次次中意女生E……
以此類推……
在五男五女全部成功脫光之后（假設都在圈子內部解決），定義一個 unstable matching 為：如果存在一對不是情侶的男女符合以下情況：
對于該男，該女在他的 preference 列表中處于現任女友的前面，對于該女，該男在他的 preference 列表中亦處于現任男友的前面，那么這對男女必然有私奔的傾向……
這樣的情景即為 unstable matching。反之，若不存在這樣一對有私奔傾向的男女，即為 stable matching。
問題是：是否在任何情況下，即不論各位的 preference 列表如何變化，只要男女數量相同，總是存在一個 stable matching。 （當然，攪基之類的，是不可以的……）
在上面五男五女的例子里，一種 stable matching 如下：
因為每個女生最中意的男生都不同，所以只要讓女生們都選擇跟自己最中意的男生在一起，她們就都不會有和其他男生私奔的想法。雖然男生們會表示略苦逼啊！仍然不失為一個 stable matching……。
那么如果有n男n女，每個人心中都已經有了一個 preference 列表，stable matching 是不是一定存在呢？
1962 年，Gale 和 Shapley 證明了 stable matching 是一定存在的。
首先他們給出了一個算法：
第一天早上：所有男生都向自己最中意的女生表白。
第一天中午：每個女生都被表白了n次（可能是 0 次）之后，拒絕了相對不太中意的那n-1 位，hold 住其中最中意的那位……即暫時不答應也不拒絕
第一天晚上，被拒絕的男生們在自己的 preference 列表中劃掉了那個拒絕他的人……
第二天早上：所有沒有被 hold 住的男生都向自己最中意的女生（無視已經被劃掉的）表白。
第二天中午：女生們在那些向她表白的男生和已經 hold 住的那男生中選擇最中意的一位，拒絕掉其他的。
第二天晚上：被拒絕的男生們在自己的 preference 列表中劃掉拒絕了自己的人……
第三天，重復同樣的過程……
第四天……
…………
這樣的過程是有限的，不會一直循環下去。（Claim 1）
在這樣的過程結束之后，每個女生都會 hold 住一個男生。（Claim 2）即在那一天之后沒有男生可以繼續表白了，這時女生們終于都向那個男生說了 yes！
按照這樣的過程，最后不會存在一對男女有私奔傾向（Claim3）
即完成了 stable matching。
關于 Claim1， Claim2， Claim3 的證明，有興趣的同學可以參考這里
下面是我們的關鍵問題：
在這樣男生主動的算法中，占了優勢的是男生還是女生呢？
表面上，男生略苦逼：要么被拒絕，要么被 hold 住還不知道是不是第二天就會被拒絕；女生則有著充分的選擇權，享受著眾星捧月的優越感，而且最差情況下到頭來還是會有個伴兒也不至于孤家寡人……。。
但是實際上，占了優勢的卻是男生！
對于男生，
設最后他的女友是在他當初的 preference 列表的第i位，那么在i位之前的那些女生，他是怎么追也追不到的：
因為即使追到（即該女生一時糊涂答應了），
那么那個女生（記為Y）也必然會有比他心儀的對象另一男X（因為既然是一時糊涂，表明在當時的情況下有更心儀的男生已經向她表白），
而男X既然在當時向該女生表白，表明在Y之前的女生都拒絕了他，而如果Y也拒絕了他，他最后在一起的女生必定排在Y之后。
所以，X和Y是注定要私奔的！
所以嘛，男生沒有追到的那些女生，都是命中不該有不可強求的……即他最后追到的女生是他最好的選擇了……
對于女生：
設最后她的男友在她當初的 preference 列表的第i位，那么在i位之前的那些男生，都是還沒機會向她表白就被其他女生 hold 住的，也就是說，她永遠也等不到的最好的，多苦啊……
實際上，還可以證明，這個男友是在所有的 stable matching 中她能得到的最差的選擇。
如果她選擇了i+1，也就是拒絕了i，那么i最后只能跟不如她的女生（在i眼中）在一起。
而i+1 也是不如i的，那么最后她還是要和i私奔。
即：若她選擇了（在她眼中的）更差的男生，最后的配對就是 unstable matching 了，所以，沒辦法更差了！這已經是最差了有木有啊！
綜上，我們驚奇地發現，男生追到的女生，是他最好的選擇。
女生接受的男生，是她最差的選擇。
如果情況相反，即女生主動追求男生，那么結論也會相反。
這個事實教導我們，主動表白是多么重要啊！
但是……
羞澀的女生如果不愿主動表白，還是有機會避免這種最差結果的。這時候，撒點小謊就顯得非常重要……。
假設一個簡單的情境，4 V 4 好了。
男1：BADC A女：1234
男2：ABCD B女：2143（紅色是在第一天表白的）
男3：BCAD C女：3241
男4：ADBD D女：4231
按照 Gale Shapley 算法，
第一天，男 1 和男 3 向B女表白，男 2 和男 4 向A女表白。
A 女喜歡 2 勝過喜歡4，但是她對 2 說謊了（“不，我不愛你……”）她拒絕了2
B 女喜歡 1 勝過喜歡3，但是她對 1 說謊了，她拒絕了1
于是第二天早上，被拒的男 1 向A女表白，同時男 2 向B女表白……。。
最后的結果是：
1-A
2-B
3-C
4-D
女生們最終都得到了最佳選擇。
以上的事實教導我們，當女生拒絕你的時候，可能她不是真的不喜歡你（至少在當時），所以……一切死纏爛打都是有理論依據滴，不可等同于耍流氓……
最后，如果是男生撒謊（即不按 preference 列表來表白，不能否認這樣的 2B 青年的存在），他最終能不能交到更加心儀的女友呢？答案是不能。撒謊只會讓男生交到在男生心目中排得更靠后的女生。原因不難分析，同學們可以自行嘗試。結 論是：對于主動的一方，真誠和坦白是保證得到最優選所必需的……
<span id="shareA4" class="fl">
</span>
</div>