这篇太强了，虽然今天大众情人节向来是躲着走的，不想贴什么了，早起看到这篇强文，真是令人愉快如沐春风啊，不由得击节三叹，还是忍不住转载了——数学和博弈是件多么浪漫奇妙的东西！文章里讲到数学的地方不要躲着走，里面的意思其实很浅显的。

　　原文见此，《我要我们在一起（科普文，慎入）》。

————————————————————————————————————

　　张生在普救寺第一眼见到崔莺莺就陷入了不可自拔的境地。“呀！正撞着五百年前风流业冤。”于是为了搭讪，张生插科打诨无所不用其极。“月色溶溶夜，花阴寂寂春；如何临皓魄，不见月中人？”诗是好诗，可惜是隔墙念的。

　　崔莺莺见了只沉吟不语。然而回到家里，“神魂荡漾，情思不快，茶饭少进。”红娘瞧了暗笑：“姐姐往常不曾如此无情无绪；自见了那张生，便觉心事不宁，却是如何？”

　　这开头如此典型，以至于可以套在古今中外无数或真或假的八卦前面。19岁的海涅第一眼见到15岁的表妹阿玛丽，就像维特见到了夏绿蒂，“一位天使！ ——没说的！谁谈起自己的意中人都这么说，不是吗？可是我却无法告诉你，她是多么完美，她为什么会那么完美；够了，她已经把我整个心都俘获了。”我不知道 别人有没有产生过和我一样的疑惑，他们真的这么写情书么？收信人不觉得难受么……

　　还是中国人含蓄，“这个妹妹我曾见过的。”妥帖多了，但也多少有点无趣。严格说起来，贾宝玉也真的从来不曾像张生或者维特那样追过女孩子。在元宵夜 宴上贾母声色俱厉地指出过张生模式的不靠谱。贾宝玉听了作何想法，我们不知道。但是我们知道的是他多少算是个被动的人，连宝钗都算比他要勇敢些。

　　于是宝钗成功地和宝玉在一起了。这当然只是个和西厢记一样不靠谱的个案，但是也不是没有道理可言的。

　　花开两朵，各表一枝。话说在1962年，两个数学家David Gale 和Lloyd Shapley提出了下面的问题：

　　给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序。是否存在一种男女配对组合构成一种稳定的组合关系？这里稳定组合的 意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。）进一步的问 题是，在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式（如果它存在的话）？你可以理解为这是数学家们替月老问的问题：给定一群孤男寡 女，寻找一种牵红线的方式，以确保把红杏扼杀在摇篮里。

　　这一问题被称为稳定婚姻问题。它有很多种可能的解法。为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特 定的数学价值。当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？于是 它就这样流传下来了。

　　话说回来，有很多组合数学问题都可以如此这般的翻译为生活中的问题。比如著名的Hall定理：给定n个有限集合（其间可以有交集），如果其中任意m 个集合的并集的元素个数都不小于m，那么一定存在n个不同的元素，使得它们正好依次存在于这n个集合之中。我相信没有人明白以上这是在说什么。可是它有一 个很好的解释：把那n个集合想象成n个男生各自心仪的女孩子们（一般来说都不止一个），中间的那个条件是说，如果对于其中任意一部分男生，他们喜欢的女孩 子的总数都不少于这组男生的人数（这个条件是必要的，否则就打起来了），那么总的说来一定存在一种办法给每个男生都分配一个女生恰好是他喜欢的。

　　听起来真是令人心情愉快啊……

　　（这个定理事实上还有很多别的解释方式，比如说，把52张扑克牌任意分成13堆，每堆4张牌，那么上面的定理告诉我们，一定存在一种方式从每堆牌中 抽出一张来一共13张恰好凑成一条不一定同花的顺子。这件事情乍一听也是挺奇妙的，不过在这个特殊的日子里，我们还是专注于我们的主题吧。）

　　回到一开始提到的稳定婚姻问题，给定每个人关于异性的偏好排序，要寻找一种男女配对组合构成稳定的组合。Gale 和Shapley不但提出了这个问题本身，而且给出了一种著名的解法。这个解法可以描述为如下的求偶过程：

　　首先，让这些男生去向他们最心仪的女生求婚——这是数学家们的原本的用词。如果你觉得太快了的话，让我们暂时改成表白吧……

　　然后，等所有男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了，不要着急，表白会有的。

　　以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。首先由还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白 （无论人家是否已经有了男朋友），然后，等所有单身男生表白完毕后，所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有 男朋友而表白者中有自己更喜欢的，不要犹豫，换之。等到尘埃落定之后，再开始如上所述的新的一轮表白。

　　依此类推。可以证明的是，这个过程一定是会终止的，也就是说，不会陷入任何死循环。并且一旦终止，每个人都会找到一个伴侣。更关键的是，这个过程最 终得到的一定是如前所述的“稳定组合”：不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。——这几个事实都不难证明，有兴趣的话可以自己试 试看。

　　所以这就得到了稳定婚姻问题的一个解（顺便也证明了解的存在性）。但是真正有趣的部分还在后面。一般来说，给定若干个男生女生和他们之间的偏好关 系，稳定组合存在不止一种。上述“算法”只是给出了所有可能的稳定组合其中之一而已。但是这个特定的解具有某些特别的性质：可以证明（这一次证明不很容易 了），上述方式得到的稳定组合和所有其他的可能的稳定组合相比，是对男生最优而对女生最劣的。

　　确切地说是这样：

　　它是对男生最优的。也就是说，对每个男生来说，按照这种方式最后找到的伴侣，是在所有的稳定组合中自己可能具有的伴侣中自己评价最高的。——注意这 并不等于说每个男生都能追到自己最喜欢的女生，而只是说，他一定能追到“有可能和他在稳定组合中在一起的女生”中自己最喜欢的。有些女生虽然很好，但是和 她在一起是不可能形成稳定组合的。这就是人生啊……

　　另一方面，它是对女生最劣的。也就是说，对每个女生来说，按照这种方式最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的。同 样的，这也不等于说每个女生都只有和自己最不喜欢的男生在一起，而只是说她最后的男朋友会是所有“有可能”的男生中自己觉得最勉强的。不过这样听起来也已 经很悲惨了。

　　这两个结论并不直观，因为看起来在上面所描述的过程中，女生是相对占有优势的。作为男生，需要很辛苦地去不断表白，然后被拒，再表白，再被拒……而女生只要随心所欲挑选就好，而且还有随时更换男友的权利（在上面的规则里男生是不能主动提出分手的）。为什么结局会是如此？

　　但是如果仔细思考上面所描述的规则，会看到男生至少有一样优势——也许是至关重要的优势：他们是主动方。主动的好处是，即使一次又一次的被拒，他也 仍然可以和剩下的女生中自己最喜欢的在一起。而对于女生来说，纵然有再多挑选的自由，可是一个女生也许永远也等不到自己最喜欢的男生来追自己——或者在她 等到之前，游戏就已经结束了。

　　毫无疑问，你已经看出在上面的设定里“男生”和“女生”都只是代号而已，它符合古典文学的一贯叙事，但是在当代语境里也许并不政治正确。另一方面， 这个定理也不是真的用来描述爱情的——数学家们还没有这么疯狂，认为可以用逻辑来推理情感。它只是一个过于简化的模型而已，比张生和维特的故事还要不靠谱 的多。

　　但是我也相信你一定已经看出了我这篇文章的主题。在一切古典文学的叙事里，我们都满怀着希望注视着那些勇敢的孩子们，看着他们的努力和坚持，也许最后会失败，可是他们至少尝试过。

　　现在连数学也在帮着说明这个道理了，所以呢？