稳定匹配问题

这是 Algorithm Design 一书开篇介绍的一个很有意思的问题

问题描述

有n个男人和n个女人(n>=2)，每个男人对所有女人有一个好感度排名，每个女人对所有男人也有一个好感度排名。将男女两两配对，得到n对男女，称之为一个完美匹配。如果有一组男女A和B，他们在匹配中没有被配对，且对对方的好感度均大于对现有配偶的好感度（男人A觉得女人B好过现在的妻子C，女人B觉得A好过现在的丈夫D），则称之为一个不稳定配对。如果一个完美匹配中没有不稳定配对，则称改匹配为一个稳定匹配。

那么问题来了，稳定匹配是否一定存在呢？

看一个例子

Man	1st choice	2nd choice	3rd choice
Xavier	Alice	Bessie	Chelsea
Yale	Bessie	Alice	Chelsea
Zeus	Bessie	Alice	Chelsea

Woman	1st choice	2nd choice	3rd choice
Alice	Yale	Xavier	Zeus
Bessie	Xavier	Yale	Zeus
Chelsea	Xavier	Yale	Zeus

在这个例子中，Xavier-Alice，Yale-Bessie，Zeus-Chelsea就是一个稳定匹配；同样的，Yale-Alice，Xavier-Bessie，Zeus-Chelsea也是一个稳定匹配。

Gale-Shapley算法

事实上，一个很直觉的算法就可以得到稳定排序。换言之，上文描述的稳定匹配是一定存在的。

gale-shapley.jpg

算法大意是：只要还有男人没有配偶，就任取一个男人m，他会按照喜好度由高到低向他从未求婚过的女人们依次求婚。如果被求婚的女人现在没有配偶，就接受；如果女人有配偶，且对m的好感度高于现在的配偶m'，就将配偶替换成m，同时m'恢复单身；如果女人觉得现在的配偶优于m，则拒绝m的求婚。最终所有男人都有配偶时，算法结束。

这一算法的提出者之一 Lloyd S. Shapley 获得了2012年的诺贝尔经济学奖，同时获奖的还有 Alvin E. Roth。他们所被表彰的贡献正是该算法所研究的稳定配置理论。

下面简单阐述一下该算法的正确性：
一定会终止：男人不会向同一个女人求婚两次，那么最多有n^2次求婚。而且当一个男人求婚n次后，一定有配偶（假如有一个男人没有配偶，那么一定有一位单身女性，而且该女人没被他求婚过）。所以，算法一定终止，而且一定返回一个完美匹配。
所得匹配一定稳定：假如有一个不稳定配对，男人m1和女人w1是一对，男人m2和女人w2是一对，m1觉得w2好于w1，w2觉得m1好于m2。这两个匹配形成一定有先后顺序，假设m1和w1先配对，那么m1此时一定已经向w2求过婚，求婚结果有两种：w2当时接受了，注意到，算法中女人一旦接受了求婚，就一定会一直有配偶，且在她的视角而言，配偶只会越来越好，这与结果中w2与m2配对是矛盾的；如果w2当时没有接受m1的求婚，那么w2当时一定有比m1更好的配偶，最后也不会选择m2。所以算法返回结果中不存在不稳定配对，一定是稳定的。

在例子中我们已经看到了，稳定匹配不是唯一的。那么Gale-Shapley算法的输出唯一吗？

答案是肯定的。我们称一个女人w是某男人m的稳定伴侣，如果存在一个稳定匹配，其中m和w被配对。GS算法返回的结果中，每个男人得到的都是最佳的稳定伴侣。也就是说，男人主动地去追求配偶是一个男性占便宜的规则。而且，每个女人得到的都是最差的稳定伴侣。

一些有意思的拓展

已知GS算法后，撒谎是否有好处？
答：男人一定没有，女人可能会有。将上文例子中女人的偏好修改如下：

Woman	1st choice	2nd choice	3rd choice
Alice	Yale	Zeus	Xavier
Bessie	Xavier	Yale	Zeus
Chelsea	Xavier	Yale	Zeus

Alice将自己的第二选择和第三选择对调，大家可以自行模拟一下，最后Alice会配对到自己最心爱的Yale，而非说实话情况下的Xavier（贴吧阴险

如果取消男女限制，每个人对剩下所有人都有好感度排名会怎样
重新假设一个场景，2*n个男生进行宿舍匹配，每个人对其他人都有一个好感度排名。在这样的设定下，稳定匹配就不一定存在了，反例如下：

Name	1st choice	2nd choice	3rd choice
Adam	B	C	D
Bob	C	A	D
Chris	A	B	D
David	A	B	C

附

本文图片来自 Lecture Slides for Alogorithm Design by Jon Kleinberg and Éva Tardos.