稳定匹配与恋爱策略

　　稳定匹配与恋爱策略

　　一个社会由n男n女组成(不考虑性别失衡的问题)，怎样让他们都组成家庭?当然因为和谐社会的原因，我们这里不考虑同性家庭和一夫多妻制，因此一个家庭是由1男1女组成的。如果在有限时间内组成了n个家庭，则我们认为这是一个完美匹配。如果所有家庭中没有一个出现离婚的情况(即所有家庭成员中没有2婚的情况)，我们将其称为稳定匹配。我想大家都希望达到稳定匹配吧，如果你在这个社会中，你会如何处理呢?如果你是上帝，你会怎样安排他们约会，并尝试达到一个稳定匹配?

　　你可能会想：当一个美女被多位男士同时追求的时候,美女会怎么处理这种情况呢?杰哥告诉你，如果可能，她们会选择和每个男士约会并打分(请自行脑补女版留几手:))，并最终得到一个列表，让我们假设得分高的男士排在前面，我们把这个列表叫做优先列表。当然每个男士也有自己的优先列表，这个优先列表中包括他所有约会过的女生。女生会尽量让自己和列表上优先级最高的男士结婚，同理男士会尽量让自己和优先列表中最高的女生结婚。

　　是不是脑袋有点大?休息一下。先搁下这个问题，让我们来看看反例：假设2对家庭：(A男,A女)和(C男,C女)，如果背悲剧的出现了A男更偏爱C女且A女更偏爱C男,那么毫无疑问没什么能阻止2对家庭的破裂并从新组合成(A男,C女)和(A女,C男)。我们把这样的情况称之为不稳定因素。如果由我们来构建和谐社会，这种情况自然是要尽量排除的。

　　让我们再看两个正面的例子：

　　例1：假设有两个男士:A男和C男，两个女生：A女与C女。 优先列表如下：

　　A男更偏爱A女而不爱C女;

　　C男更偏爱A女而不爱C女;

　　A女更偏爱A男而不爱C男;

　　C女更偏爱A男而不爱C男;

　　在上面这个例子中男人在女人的顺序是一致的且女人在男人的顺序上也是一致的。存在一个由(A男，A女)和(C男，C女)组成的唯一稳定匹配(就是说他们不会离婚);相反，由(A男，C女)和(C男,A女)组成的完美匹配是不稳定的，因为在这种情况下(A男，A女)构成了相对于这种匹配的不稳定因素(双方都想离开他们各自的伴侣而重新组建家庭)。

　　好吧我直说A男是高富帅，C男是那啥，你懂的。

　　例2：这个例子更复杂一些，假设优先列表如下：

　　A男更偏爱A女且不爱C女;

　　C男更偏爱C女且不爱A女;

　　A女更偏爱C男且不爱A男;

　　C女更偏爱A男且不爱C男;

　　在这个例子中，男人们的优先列表是完全相互协调(他们把不同的女人排为第一)，女人们的优先列表也完全协调，但男人和女人的优先列表完全冲突。这里存在两个稳定匹配：由(A男，A女)和(C男，C女)组成的匹配是稳定的，因为两个男人已经都满意了，因此没有人会离开他的伴侣;由(A男，C女)和(C男，A女)组成的也是稳定的匹配，因为两个女士已经都满意了，因此没有人会离开她的伴侣。

　　由此可以看出，稳定匹配不是唯一的。

　　存在两对(A男，A女)和(C男，C女)。其中A男更偏爱C女且A女更偏爱C男，因此会转而组成(A男，C女)和(C男，A女)。

　　还有读者反馈A男A女之类看着头疼。因此本篇中杰哥用m表示男，w表示女。

　　先假设一个人最终只有两种状态：单身，以婚。

　　再假设由男士主动追求，而女生只要同意就可以结婚。什么，为什么是女生决定?现实中不是这样吗?或者你听过男人像蓝牙，女生像wifi的说法吗?

　　算法开始时，每个人都是未婚的。假设一个未婚的男人m选择了他的优先列表上排名最高的女人w,并且向她求婚。如果你是w，你会怎么做?杰哥要是这个女人，既不会立刻拒绝m，也不会立刻同意求婚。原因很简单：w可能还没有收到她自己优先列表上排名比m排名高的某人的求婚，但是说不定在将来的某个时候，在w优先列表上排名更高的男人m'会像她求婚。那么很自然，w和m会进入一个中间状态-约会。

　　我们现在思考GS算法的某种中间状态，某些男人和女人是自由的(还没有进入约会状态)，而有某些是处于约会中的。那么看起来像这样，任意一个自由的男人m选择他还没有求过婚的在他的优先列表中排名最高的女人w求婚。此时会进入以下两种情况之一:(1)w是自由的，则(w,m)进入约会状态。(2)(w,m')处于约会状态中，此时w会判断m与m'在其优先列表中的排名，与排名更高的男人进入约会状态，排名较低的男人变成自由状态。

　　现在来看看GS算法的最终状态：当没有一个人是自由的，GS算法结束，命运之轮停止转动;此时所有处于约会状态的(w,m)，w都会接受求婚。很显然，这是一个完美匹配。

　　觉得这个思路如何?估计很多人都会吐槽：说不定最终状态根本就不会存在;即使侥幸让杰哥撞上了，得到的完美匹配也不一定就是稳定匹配。

　　OK，怀疑的很有道理。那么就让杰哥继续往下分析。先考虑从女士w在算法执行中的状态，我们可以发现一个事实：w从接受对她第一次求婚开始保持约会状态，且正在约会的一系列男士会依照她的优先列表变得越来越好。

　　再考虑男士m在算法执行过程中的状态，可以看到他是相当的悲剧：m求过婚的一系列女人依照他的优先列表变得越来越差。

　　你可能会想：虽然这是事实，但GS算法可未必有终止的一天。没错，现在就来看看GS算法终止的条件是什么?

　　终止条件就是不存在自由的男人!对这有想不通的同学请输入2c仔细看。

　　哥要证明这一点：如果男士m在GS算法执行的某点是自由的，那么必然存在一个他还没有求过婚的女人w。

　　杰哥选择用反证法。假设GS算法执行的一个点，此刻m是自由的但是向所有女人都求过婚了。那么由于事实1的存在，n个女人都已经是约会状态，因此在这个时间点上一定也有n个男人处于约会状态。但总共只有n个男人，且m不在约会，因此矛盾。所以m在这个状态下可以向w求婚。接着杰哥再假设在算法终止时存在自由的男人。那么在终止时一定是这种情况，m向所有n个女人求过婚，否则算法不会终止。但这和刚才的结论相反。因此GS算法必然会终止，且此时没有自由的男人。

　　存在(m,w)和(m',w'),m更偏爱w'且w更偏爱m'。

　　GS算法结束后可能产生这样的结果吗?杰哥来倒推一下：m的最后一次求婚是想w求婚。那么在更早的时间点，m想w'求过婚吗?如果他没有，那么在m的优先表上w一定比w'高，这样条件向矛盾。如果他向w'求过婚被拒绝了，那么他被拒绝的理由一定是w'更偏爱其他人m''，m'是w'的最终伴侣，因此要么m''=m'或者w'更偏爱m',这与条件矛盾。因此GS算法的结果是稳定匹配。

　　看到这里，你是不是暗自咬牙：胡扯了两篇，好不容易说明白了稳定匹配，但是恋爱策略连影子都没看到。或者说是不是如果我是女生，只要采取向GS算法中的w一样的策略就可以了?

　　不要急，精彩的总是放在最后的。杰哥这里再买个关子：欲知策略是什么，请关注下一篇文章，也是本文的最后一篇。结束之前杰哥建议准备采取GS算法中w的恋爱策略的女生，把GS算法中的男士主动追求，女士决定的情况反过来，思考一下。

　　大家看了上篇文章，是否觉得做女生挺好，只需要选择就好了。而且选择的结果总是朝着自己优先列表高的方向发展。真的是这样吗?让我们再从另一个角度看看，还记得《稳定匹配与恋爱策略-上》中举的那个说明稳定匹配并不唯一的例子吗?我们再来回顾一下：

　　优先列表如下：

　　m更偏爱w而不爱w',

　　m'更偏爱w'而不爱w,

　　w更偏爱m'而不爱m,

　　w'更偏爱m而不爱m'.

　　注意这个例子中稳定匹配理论上有两种:(1)(m,w)和(m',w);(2)(m,w')和(m',w)。第一种情况是所有男人最终都和他们的第一选择匹配，而在第二种情况是所有女人都和她们的第一选择匹配。

　　现在，我们按上篇文章中描述的GS算法执行一下(忘记GS算法的同学请输入"2c"查看伪代码)。我们看到得到的是第一种情况。我们再执行一次，还是第一种情况。无论执行多少次GS算法，第二种情况永远不会出现!

　　这意味着什么?在这个例子中，女士的的选择被忽略了!为什么女士的选择被忽略了?因为女士是被动选择方。

　　让我们将这个例子中的男士主动追求变成男士被动接受。现在发现了什么?结果稳定在第二种情况。

　　等等，这个结果和上篇说的不太一样啊。这就是关键所在!

　　对这个结果的解释，杰哥放在这篇文章的后面。先记下这个结论：如果把这种情况称为不幸，那么男人主动求婚，女人就是不幸的;女人主动求婚，那么男人就是不幸的。

　　这就是杰哥要告诉大家的恋爱策略!就两个字：“爱情是要主动追求的!”

　　#### 如果只想知道恋爱策略，读者可以跳过以下部分直接看后记了 #######

　　现在我们就来仔细分析一下这个血淋淋的事实。

　　我们引入一个概念：最佳伴侣。如果存在一个稳定匹配包含了(m,w)对，我们就说女人w是男人n的有效伴侣。如果w是m的有效伴侣，且没有别的有效伴侣w'(w'>w)在m的优先列表中,那么w就是m的最佳伴侣。我们用best(m)表示m的最佳伴侣。

　　我们用S*表示集合{m, best(m):m∈M},很显然，这个集合是唯一的。

　　我们现在来看一个很神奇的事情。GS的每次执行都会得到S*。杰哥第一次看到的时候也是完全不相信的。为什么两个男人有相同最佳伴侣的情况最终不会发生?为什么不同男士求婚的顺序完全不影响最终的结果(我相信你也疑惑这一点吧)?

　　好吧，真相总是血淋淋的。让我们来证明这一事实：

　　杰哥还是用反证法。假设GS算法的某次执行a得到了匹配S，其中某个男人与一个不是他最佳伴侣的女人配对。因为男人m求婚的次序按优先列表递减，如果m被第一个有效伴侣w拒绝，那么w一定是m的最佳伴侣best(m)。

　　m被w拒绝的事情已经发生，或者是w对已有约会对象m'更有好感，或者是有更好的男人m'向w求婚。无论如何都构成当m被w拒绝时m'与w处于约会状态。

　　因为w是m的有效伴侣，所以存在一个稳定匹配S'，S'包含了一对(m,w),现在考虑在S'中m'与谁配对?让我们假设与m'匹配的w'(w'≠w)。因为m被w拒绝是a执行中一个男人被有效伴侣第一次拒绝，所以在m'开始与w约会这个时间点上，m'一定还没有被有效伴侣拒绝过(否则m'就是悲剧的m，即m'=m)，由于m'的求婚也是按优先列表递减的，所以一定是m'更偏爱w而不爱w'。但是我们已经看到w更偏爱m'而不爱m，因为她拒绝了m而倾心与m'。即m'与w相互倾心。因此必定会组成(m',w)，但S'中已经包含了(m,w)。因此(m',w)不属于S',也就是说(m',w)是S'中的不稳定因素。这与我们声称的S'是稳定匹配矛盾，因此与我们的初始假设矛盾。证明结束。

　　同理我们可以看到：在GS每次执行都得到S*,S*表示集合{w, worst(w):w∈W}，即每个女人只能与她的最差伴侣配对。

　　这个证明杰哥就不做了，留给你思考吧。

　　因此我们可以看到GS算法对主动的一方是有偏爱的，主动一方能够获得最佳伴侣，被动一方只能获得最差伴侣。

　　在现实生活中也一样，凡事都要主动争取，千万不要等着天上掉馅饼。这就是杰哥从GS算法中体会到的，现在，你有什么感受?如果你觉得有道理，就请转发杰哥这篇文章哦。

　　#### 后记 #####

　　稳定匹配算法写完了，不管你看的是否过瘾，杰哥还是写的挺辛苦的。杰哥现在要澄清一下：GS算法并不是杰哥杜撰的归宿的含义，而是Gale和Shapley的首字母简写。

　　在1962年，Gale和Shapley提出了一个问题：给定一组在雇主和申请人之间的优先权，我们能否把申请人分配给雇主，以使得对每个雇主E,以及没分配为E工作的每个申请人A，至少下面两种情况之一成立：

　　(1)E对他所接受的每个申请人比A更满意;或者

　　(2)A对他目前的情况比其为雇主E工作更满意。

　　他们给出了这个问题的一个解答(就是《稳定匹配与恋爱策略-中》的GS算法)。凭借对稳定匹配问题的研究，Shapley于2012年获得了诺贝尔经济学奖。