离散数学课(CSCI 2110)上,讲到一个有趣的问题。
假设有五个男生,五个女生,每个人都在自己心中对五个异性有一定的preference排序,比如:
以上的排序表解读为:男生1最中意女生C,次中意女生B,次次中意女生E。。。。
以此类推。。。。
在五男五女全部成功脱光之后(假设都在圈子内部解决),定义一个unstable matching为:如果存在一对不是情侣的男女符合以下情况:
对于该男,该女在他的preference列表中处于现任女友的前面,对于该女,该男在他的preference列表中亦处于现任男友的前面,那么这对男女必然有私奔的倾向。。。。
这样的情景即为unstable matching。反之,若不存在这样一对有私奔倾向的男女,即为stable matching。
问题是:是否在任何情况下,即不论各位的preference列表如何变化,只要男女数量相同,总是存在一个stable matching。? (当然,搅基之类的,是不可以的。。。)
在上面五男五女的例子里,一种stable matching如下:
因为每个女生最中意的男生都不同,所以只要让女生们都选择跟自己最中意的男生在一起,她们就都不会有和其他男生私奔的想法。虽然男生们会表示略苦逼啊!仍然不失为一个stable matching。。。。。
那么如果有n男n女,每个人心中都已经有了一个preference 列表,stable matching是不是一定存在呢?
1962年,Gale 和 Shapley 证明了stable matching是一定存在的。
首先他们给出了一个算法:
第一天早上: 男生都向自己最中意的女生表白。
第一天中午:每个女生都被表白了n次(可能是0次)之后,拒绝了相对不太中意的那n-1位,hold住其中最中意的那位。。。即暂时不答应也不拒绝
第一天晚上,被拒绝的男生们在自己的preference列表中划掉了那个拒绝他的人。。。
第二天早上: 没有被hold住的男生都向自己最中意的女生(无视已经被划掉的)表白。
第二天中午:女生们在那些向她表白的男生和已经hold住的那男生中选择最中意的一位,拒绝掉其他的。
第二天晚上:被拒绝的男生们在自己的preference列表中划掉拒绝了自己的人。。。。
第三天,重复同样的过程。。。
第四天。。。。
。。。。。。。
这样的过程是有限的,不会一直循环下去。(Claim 1)
在这样的过程结束之后,每个女生都会hold住一个男生。(Claim 2)即在那一天之后没有男生可以继续表白了,这时女生们终于都向那个男生说了yes!
按照这样的过程,最后不会存在一对男女有私奔倾向(Claim3)
即完成了stable matching。
关于Claim1, Claim2, Claim3的证明,有兴趣的同学可以参考这里
离散数学课(CSCI 2110)上,讲到一个有趣的问题。
假设有五个男生,五个女生,每个人都在自己心中对五个异性有一定的preference排序,比如:
以上的排序表解读为:男生1最中意女生C,次中意女生B,次次中意女生E。。。。
以此类推。。。。
在五男五女全部成功脱光之后(假设都在圈子内部解决),定义一个unstable matching为:如果存在一对不是情侣的男女符合以下情况:
对于该男,该女在他的preference列表中处于现任女友的前面,对于该女,该男在他的preference列表中亦处于现任男友的前面,那么这对男女必然有私奔的倾向。。。。
这样的情景即为unstable matching。反之,若不存在这样一对有私奔倾向的男女,即为stable matching。
问题是:是否在任何情况下,即不论各位的preference列表如何变化,只要男女数量相同,总是存在一个stable matching。? (当然,搅基之类的,是不可以的。。。)
在上面五男五女的例子里,一种stable matching如下:
因为每个女生最中意的男生都不同,所以只要让女生们都选择跟自己最中意的男生在一起,她们就都不会有和其他男生私奔的想法。虽然男生们会表示略苦逼啊!仍然不失为一个stable matching。。。。。
那么如果有n男n女,每个人心中都已经有了一个preference 列表,stable matching是不是一定存在呢?
1962年,Gale 和 Shapley 证明了stable matching是一定存在的。
首先他们给出了一个算法:
第一天早上: 男生都向自己最中意的女生表白。
第一天中午:每个女生都被表白了n次(可能是0次)之后,拒绝了相对不太中意的那n-1位,hold住其中最中意的那位。。。即暂时不答应也不拒绝
第一天晚上,被拒绝的男生们在自己的preference列表中划掉了那个拒绝他的人。。。
第二天早上: 没有被hold住的男生都向自己最中意的女生(无视已经被划掉的)表白。
第二天中午:女生们在那些向她表白的男生和已经hold住的那男生中选择最中意的一位,拒绝掉其他的。
第二天晚上:被拒绝的男生们在自己的preference列表中划掉拒绝了自己的人。。。。
第三天,重复同样的过程。。。
第四天。。。。
。。。。。。。
这样的过程是有限的,不会一直循环下去。(Claim 1)
在这样的过程结束之后,每个女生都会hold住一个男生。(Claim 2)即在那一天之后没有男生可以继续表白了,这时女生们终于都向那个男生说了yes!
按照这样的过程,最后不会存在一对男女有私奔倾向(Claim3)
即完成了stable matching。
关于Claim1, Claim2, Claim3的证明,有兴趣的同学可以参考这里