七夕话题——婚姻稳定问题

今儿是七夕，中国的情人节。老衲晚上没有节目，只能上 blog 来扯淡。说点跟这日子多少沾边的话题吧——“婚姻稳定问题”。

婚姻是个复杂的东西，稳定性问题哪有那么容易解决。这里要说的是一个关于“婚姻稳定”的数学模型：

比如，现有 5 个男生和 5 个女生。他们每个人的心目中都对 5 个异性有按喜爱程度的排序（自然是萝卜青菜，各有所爱）。问：怎样为他们牵线，才能使最终得到的 5 对恋人最稳定？

所谓稳定，是指男女双方都无法再找到另外的自己更青睐的异性，同时人家相对于现有恋人也更钟情于自己。这个解释有点绕。比方说，男 1 号与女 1 号交往，男 2 号与女 2 号交往。但是男 1 号更爱女 2 号，女 2 号同时也更爱男 1 号。在这种情形下，他们就会抛弃现在的恋人，重新结合。于是，我们就可以说，男 1 号与女 1 号的关系是“不稳定”的。

毫无疑问，如果每个人都能得到自己的至爱，皆大欢喜，那自然是最稳定的。但这种好事连在小说里都不会发生，更何况是人生。那么，到底有没有这样的配对方案，使这些男男女女们毫无遗憾地安心过日子呢？还是说命中注定了，人就是非要这么无休止地折腾下去？

幸好，两个数学家 David Gale 和 Lloyd Shapley 在 1962 年找出了解决方案。他们证明了，不管存在多少对男女，只要使用他们提出的策略，就总能够找到一种稳定的婚姻搭配方案。有意思的是，他们提出的策略，几乎就是现实生活的翻版。这个策略是由男生一轮一轮地向女生表白，而女生可以选择“接受”或者“拒绝”。具体操作如下：

• 第一轮，每个男生向自己最心仪的女生表白。女生这时可能面临三种状况：
  • 多个男生向自己表白。这时，选择自己最喜欢的一个“接受”，并“拒绝”其他人。
  • 只有一个男生向自己表白。这时，无条件选择“接受”。（聊胜于无，或者更准确地说，劣胜于无）
  • 没有男生向自己表白。没办法，只能暂时单身。
• 第二轮，所有仍然单身的男生向自己心目中排名第二的女生表白（排第一的人家已经给发了“好人卡”了）。女生如果认为追求者比现任男友更优秀，就可以选择“接受”新的追求者，而“拒绝”现任，使之变为“前任”。不用说，被甩的男生又“重获自由”了。
• 单身的男生按照心目中的排序，依次向女生表白。而女生则根据自己的喜好，来选择更优秀的男生作为男友。如此不断循环下去。
• 最终，所有的男生和女生都配对成功。此时，就是最稳定的状态。

是不是跟现实很像呢？

稍微观察一下，就会发现，女生的对象越来越好，而男生的对象则越选越糟……（我绝对绝对不是在抱怨——这句话绝对绝对不是欲盖弥彰——这两句话绝对绝对没有越描越黑……）

为了证明我确实不是在抱怨，来看下面的例子。假设有 3 男 `ABC` 和 3 女 `XYZ`，他们的代号以及各自对异性的喜好顺序也已用字母标出：

A: YXZ
B: ZYX
C: XZY
X: BAC
Y: CBA
Z: ACB

对于这 3 对男女来说，有三种方案都是稳定的：

• AY, BZ, CX ——对追求者（男生）最有利，每个男生都得到了最爱，而每个女生都困于最差。由于此时没有男人想出轨，因此婚姻稳定。
• AX, BY, CZ ——大家都得到中庸的结果。由于每个人的最爱都不爱自己，所以中庸的选择倒也安稳。
• AZ, BX, CY ——对审查者（女生）最有利，每个女生都得到了最爱，而每个男生都困于最差。由于此时男人想出轨也没人搭理他，因此婚姻稳定……

尽管有着三种稳定方案，但是如果按照前文提到的策略来进行，最终结果就是第一种——对男生最有利的。因为这个例子中，每个女生都不会同时有多个追求者，因此游戏在第一轮就结束了，女生还没有来得及发挥她们的“后期优势”。

所以，各位灰太狼哥们，大家如果彼此协调配合一下，是完全可以在第一回合就让游戏结束的。省时又省力，何乐不为？

不过，各位美羊羊姐们，你们如果能够稍微矜持一点，不着急对抢到沙发的人说 Yes 的话，才能真正货比三家，择优录取……

写得乱七八糟。忽然发现，最后的例子貌似也不能证明我不是在抱怨嘛……whatever…