这是 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算法
事实上，一个很直觉的算法就可以得到稳定排序。换言之，上文描述的稳定匹配是一定存在的。
算法大意是：只要还有男人没有配偶，就任取一个男人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.
