经济学家的找对象研究

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

那么有什么办法让这群男女快速配对呢？

Gale和Shapley给出了著名的延迟接受算法：就是男方按自己的好感程度又高到低给每个女方表白，女方决定是否同意；当然这还会有很多人剩下来，没关系继续这样的模式搞一遍，只要还有男人没有对象，就任取一个剩男，他会按照好感度由高到低向他从未表白过的女人们依次表白。如果被表白的女人现在没有对象，就接受；如果女人有配偶，且对这位剩男的好感度高于现在的对象，就换成剩男，而原来的对象成为剩男一员（经济学家还真是现实呢）；如果女人觉得现在的配偶优于这位剩男，则拒绝。最终所有男人都有对象时，算法结束。

最后的结果有几个有意思的性质：

1、这个方法一定会终止，且最终结果是稳定的。嗯嗯 不再有一堆痴男怨女，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
2、在所有的稳定组合中，男的一定能追到自己可能具有的对象中自己评价最高的。
3、对每个女生来说，按照这种方式匹配的所有稳定组合中，最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的。

所以引申的含义就是：谁主动谁占优[笑而不语]

单身狗的博主祝各位情人节快乐。