离散数学课（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（因为既然是一时糊涂，表明在当时的情况下有更心仪的男生已经向她表白），