稳定婚姻(Stable Marriage Problem)

不知道有没有人在这个BBS上讲过这个问题. 这个理论比较奇特,
但是和排骨那些BT理论不同的是, 这个是数学界切切实实研究过
的问题. 对于以前没有接触过这个问题的人, 这个理论最出人意
外的结论是: 传统的求爱, 结婚过程是male-optimal的, 也就是
说, 男性能够得到尽可能好的心上人, 女性却不然. 

这个问题和图论有关, 最早是由两个美国数学家1962年在American 
Mathematical Monthly上提出的, 相关的参考文献其实很多, 下
面这个网页大概是讲得最通俗易懂的:

	http://www.cs.columbia.edu/~evs/intro/stable/writeup.html

俺可以在这里大概讲一下. 假设有一百个男人和一百个女人, 每
个男人都凭自己好恶给每个女人打分, 我最爱a, 其次爱b, 再次
爱c...每个男人打的分不同, 你最爱的可能是我最讨厌的, 我最
爱的可能是他不甚喜欢的. 每个女人也同样给每个男人打分.

然后就是求婚过程.

第一天上午, 所有的男人都向自己最爱的女人求婚. 

下午, 每个女人看看自己有没有收到, 收到了多少人的求婚. 如
果只收到一个男人的求婚, 那么就和他订婚. 如果收到多于一个
男人的求婚, 那么就和其中她最爱的那个男人订婚, 同时把其他
男人都锯掉. 如果一个求婚都没有, 不要着急, 最后总会有的.

晚上, 检查一遍, 如果所有女人都订婚了, OK, 万事大吉, 明天
举行集体婚礼.

但如果还有女人没有订婚, 那么事情还没有完, 第二天还得重复.

第二天上午, 所有还没订婚的男人向自己次爱的女人求婚(因为
昨天已经被他们的最爱锯了). 

下午, 每个女人再看一遍自己收到订婚的情况. 如果她已经订婚
了, 但是又有一个她更爱的男人来向她求婚, 那就把原来那个锯
掉, 再和这个更爱的男人订婚; 如果还没订婚, 那就和第一天的
下午的处理一样.

晚上再检查一遍, 如果还是有人没有订婚, 那第三天再重复.

第三天上午, 所有没有订婚的男人, 包括第一天订了第二天又被
踹出来的, 再向还没有锯过他的女人中他最爱的那个求婚

...

如此周而复始, 直到最后大家都订了婚, 便一起结婚.

这么个过程, 数学上可以证明:

第一, 这个过程会中止, 也就是说, 总有大家都订了婚的一天, 
不可能无限循环.

第二, 中止后所有的婚姻是稳定婚姻. 所谓不稳婚姻是说, 比
如说有两对夫妇M1, F1和M2, F2, M1的老婆是F1, 但他更爱F2;
而F2的老公虽说是M2. 但她更爱M1, 这样的婚姻就是不稳婚姻, 
M1和F2理应结合, 他们现在各自的婚姻都是错误. 我们能证明
的是, 通过上面那个求婚过程, 所有的婚姻都是稳定的, 没有
人犯错误.

第三, 比较引人注目的是, 这个过程是male-optimal的, 男性
能够获得尽可能好的伴侣, 比如说最后有二十个女人拒绝了他,
他仍然能够得到剩下的八十个女人中他最爱的那一个.

第四, 更有甚者, 这个过程是female-pessimal的, 女人总是
在可能的情况下被最不喜欢的人追上. 这一点没有那么直观的
理解, 勉强要解释的话, 可以这么看: 虽说女人每换一次订婚
对象, 都往上升一层, 但起点可能很低, 虽说在一步步接近她
最爱的目标, 但最后往往达不到. 比如说还差三十名就达到她
最爱的人了, 但这时Game Over, 所有的人都已订了婚, 这样
她也只能死了心了. 还有三十个她更爱的人还没向她求过婚, 
可是她也无可奈何了...

俺们上算法课的时候有一整节课专讲这个问题, 上完课男生一个
个眉花眼笑, 不过女生们的嘴撅得可以挂酱油瓶了...

课后哥们几个聊起来, 这个理论给mm们的最大教训是, 想要好gg,
自己就得主动.