稳定婚姻问题
假设有一百个男人和一百个女人, 每个男人都凭自己好恶给每个女人打分, 我最爱a,
其次爱b, 再次爱c...每个男人打的分不同, 你最爱的可能是我最讨厌的, 我最爱的可
能是他不甚喜欢的. 每个女人也同样给每个男人打分. 让你寻找所有的男女组成稳定的搭配。
要求：不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。比如a-b是情侣。c-d是情侣。不能存在b感觉c比a好的同时，c感觉b比d好。
做法：
第一天上午, 所有的男人都向自己最爱的女人求婚. 下午, 每个女人看看自己有没有收到, 收到了多少人的求婚. 如果只收到一个男人的求婚, 那么就和他订婚. 如果收到多于一个男人的求婚, 那么就和其中她最爱的那个男人订婚, 同时把其他男人都锯掉. 如果一个求婚都没有, 不要着急, 最后总会有的. 晚上, 检查一遍, 如果所有女人都订婚了, OK, 万事大吉, 明天举行集体婚礼. 但如果还有女人没有订婚, 那么事情还没有完, 第二天还得重复.
第二天上午, 所有还没订婚的男人向自己次爱的女人求婚(因为昨天已经被他们的最爱锯了). 下午, 每个女人再看一遍自己收到订婚的情况. 如果她已经订婚了, 但是又有一个她更爱的男人来向她求婚, 那就把原来那个锯掉, 再和这个更爱的男人订婚; 如果还没订婚, 那就和第一天的下午的处理一样. 晚上再检查一遍, 如果还是有人没有订婚, 那第三天再重复.
第三天上午, 所有没有订婚的男人, 包括第一天订了第二天又被踹出来的, 再向还没有锯过他的女人中他最爱的那个求婚 ... 如此周而复始, 直到最后大家都订了婚, 便一起结婚.
结论：
比较引人注目的是, 这个过程是male-optimal的, 男性能够获得尽可能好的伴侣, 比如说最后有二十个女人拒绝了他, 他仍然能够得到剩下的八十个女人中他最爱的那一个. 更有甚者, 这个过程是female-pessimal的, 女人总是在可能的情况下被最不喜欢的人追上. 这一点没有那么直观的理解, 勉强要解释的话, 可以这么看: 虽说女人每换一次订婚对象, 都往上升一层, 但起点可能很低, 虽说在一步步接近她最爱的目标, 但最后往往达不到. 比如说还差三十名就达到她最爱的人了, 但这时Game Over, 所有的人都已订了婚, 这样她也只能死了心了. 还有三十个她更爱的人还没向她求过婚, 可是她也无可奈何了...
这个理论给女生们的最大教训是, 想要好男生, 自己就得主动.
