半夜终于刷完了Game theory最后一个长达86个ppt的lecture。

看完后恍然大悟，原来整节课其实就是在讲一群数学家追妹纸的心得总结啊！！然后我脑补了一下各种情节，在一个“实在是刷不动了啊”的复习期末考的苦逼夜晚有此文。特别声明：此文为Paul Harrenstein（唉，最后节课在宿舍睡过去了，都没见过他）于2012年7月10日关于“Two-Sided Matching: The Stable Marriage Problem”的绝对通俗译版。（版权为他所有，但是估计他也不会想要这个二逼版的版权。。）

以上为题记。

话说，很久很久以前（其实也不是很久，大概50多年前吧）,有两个没有妹纸的数学家Gale 和 Shapley（你问我为什么知道他们没有妹纸？开什么玩笑，他们是数学家哎！好吧，虽然我不是数学家，但是学数学的还是主动躺中一个好了。。）。言归正传，有一天，Gale 和Shapley第N+1次讨论起了妹纸的问题：我们到底为什么没有妹纸呢？当然这个问题是不会有结果的，于是他们深入了一层：

怎样让每个男人都有满意的妹纸呢？

作为数学家，他们要做的第一件事情当然是要定义一些东西。首先被定义的是“满意”这个词(原文是“stable matching")，原文如下：（不想看英文的直接跳过去看通俗译版）

DEFINITION: A man-woman pair (m;w) blocks if they prefer
each other to their spouses under , i.e., if
w prefers m (m), and
m prefers w (w).
A matching is stable if there is no man-woman pair blocking .

通俗地讲，假设如下情况：小明和小红是夫妻，小强和小芳是夫妻，但是相对于小红来讲，小明比较喜欢小芳；恰好对小芳来说，小芳也更喜欢小明（相对于小强来说），这样假如这两对碰到了小明和小芳岂不是就要私奔了？

所以这样的配对就叫做不稳定的配对，是”不满意“的。

接下来Gale 和 Shapley就开始着手研究消除不满意的配对从而”让每一个男人都有满意的妹纸“的方法了。

他们想到的第一个方法：

The Deferred Acceptance Algorithm (DAA):
1 Each man proposes to his favorite woman.
2 Each woman “engages” her favorite man among her suitors
and rejects the others.
3 Each rejected man proposes to his next favorite woman.
4 Repeat 2 and 3 until all women have been proposed to.

通俗地翻译下就是，首先每个男人向自己最喜欢的妹纸表白；被表白后，妹纸们分别在追求自己的男人中挑一个最喜欢的；接下来刚刚悲剧了的男人在向自己第二喜欢的妹纸表白,不在乎她有没有男朋友了（突然觉得这很贱呐），然后妹纸们（不管上一轮有没有接受其他男人）再挑一次，选择自己喜欢的。。。原则是男人被拒后不能再向同一个妹纸表白。（两个有”骨气“的数学家么。。。）

如此循环往复直到每个妹纸和每个男人都配对。（好吧，作为学数学的，我想说这里的条件是，两种人数目相当且都是有限的。。。当然对于某些腐女来说，这个条件可以更加宽松一点。。）

方法介绍完毕，通过一系列的推断证明，Gale 和 Shapley发现这个方法简直就是圣经啊，因为它总可以找到一个”“满意”的配对方案（也就是说绝对不会出现私奔的情况）。（如果有人真心想知道怎么证明的，我不介意把notes发给你的，真的。。）

接下来，他们有了更重大的发现，让广大男同胞泪流满面，这个结论就是：

按照这个方法，每个男人都能找到自己条件允许下最喜欢的妹纸。（THEOREM (Gale and Shapley, 1962):
DAA yields the unique M-optimal matching M.)

在Gale和Shapley的鼓动下，又有两个没有妹纸的数学家加入了进来，他们证明了让广大女同胞晴天霹雳的一个结论：

按照这个算法，每个妹纸最后跟的男人都是自己条件允许下最差的。。。。。。

THEOREM (McVitie and Wilson, 1971):
In the unique M-optimal matching, every woman is matched with
the worst partner she can have in any stable matching.

证明这个结论的两位分别叫做McVitie和 Wilson。。。

Notes在这里还没有结束，但是剩下的已经不重要了不是么？

最后来一句话总结下中心思想：

无论是妹纸还是汉子，喜欢人就要勇敢地表白啊！（四位闷骚的数学家已经给你们证明过了！！）

PS 本文纯属娱乐，不完全具备数学严谨性，调侃下前辈数学家（其实我是很尊重他们的，拜托final让我pass吧！）然后我想说，

我无聊的时候真是。。。唉。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

围脖：http://t.sina.com.cn/zhedawangshi

浙大往事：http://blog.sina.com.cn/zjus

人人网：http://www.renren.com/zjustory

搜狐：http://zhedawangshi.blog.sohu.com

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

【DNA】新浙大往事地点：浙大玉泉南门青芝坞56号（老地方川菜馆对面小巷20米一栋三层别墅）

联系电话：0571-86681146 店长张剑湖 13958819201

白色三层小别墅，独立主题小房间；棋牌，娱乐，喝茶，品咖啡，三五小众聚会圣地