假設有五個男生，五個女生，每個人都在自己心中對五個異性有一定的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的證明，有興趣的同學可以參考這裡：http://en.wikipedia.org/wiki/Stable_marriage_problem#Solution
下面是我們的關鍵問題：
在這樣男生主動的算法中，占了優勢的是男生還是女生呢？
表面上，男生略苦逼：要麼被拒絕，要麼被hold住還不知道是不是第二天就會被拒絕；女生則有著充分的選擇權，享受著眾星捧月的優越感，而且最差情況下到頭來還是會有個伴兒也不至於孤家寡人。。。。。。
但是實際上，占了優勢的卻是男生！
對於男生，設最後他的女友是在他當初的preference列表的第i位，那麼在i位之前的那些女生，他是怎麼追也追不到的：因為即使追到（即該女生一時糊塗答應了），那麼那個女生（記為Y）也必然會有比他心儀的對象另一男X（因為既然是一時糊塗，表明在當時的情況下有更心儀的男生已經向她表白），而男X既然在當時向該女生表白，表明在Y之前的女生都拒絕了他，而如果Y也拒絕了他，他最後在一起的女生必定排在Y之後。
所以，X和Y是註定要私奔的！
所以嘛，男生沒有追到的那些女生，都是命中不該有不可強求的。。。即他最後追到的女生是他最好的選擇了。。。
對於女生：
設最後她的男友在她當初的preference列表的第i位，那麼在i位之前的那些男生，都是還沒機會向她表白就被其他女生hold住的，也就是說，她永遠也等不到的最好的，多苦啊。。。
實際上，還可以證明，這個男友是在所有的stable matching中她能得到的最差的選擇。
即：若她選擇了（在她眼中的）更差的男生，最後的配對就是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青年的存在），他最終能不能交到更加心儀的女友呢？答案是不能。撒謊只會讓男生交到在男生心目中排得更靠後的女生。原因不難分析，同學們可以自行嘗試。結論是：對於主動的一方，真誠和坦白是保證得到最優選所必需的。。。