一个简单的例子说明stable marriage稳定婚姻匹配问题

时间:2020-12-21 09:48:35

问题描述非常简单:
有n位男士n位女士,每位男士对所有女士按照他喜欢的程度进行排名,同时,每位女士也对所有男士有一个喜爱程度排名,无并列。
比如我们现在有4位男士:m1,m2,m3,m4,和四位女士w1,w2,w3,w4(m的意思就是man男士,w的意思就是woman女士)。第一位男士对所有女士的喜爱排名为:’w3’,’w2’,’w1’,’w4’,即他最喜欢的是第三位女士w3,接着是第二位,第一位,最后是第四位女士w4。
我们列出每位男士对所有女士的喜爱程度排名如下:
m1:’w3’,’w2’,’w1’,’w4’
m2:’w2’,’w4’,’w1’,’w3’
m3:’w3’,’w1’,’w4’,’w2’
m4:’w1’,’w2’,’w3’,’w4’
可以看出来m1和m3都最喜欢第三位女士w3,其中m3最喜欢w3而最不喜欢w2,而m2恰恰相反,他最喜欢w2最不喜欢w3,果然是萝卜青菜各有所爱啊。
接下来列出每位女士对所有男士的喜爱程度排名如下:
w1:’m1’,’m3’,’m2’,’m4’
w2:’m3’,’m4’,’m2’,’m1’
w3:’m2’,’m3’,’m4’,’m1’
w4:’m4’,’m2’,’m1’,’m3’
可以看出来虽然m1和m3都最喜欢w3,但w3最喜欢的却是对她最不感兴趣的m2,唉,造化弄人啊!
接着我们用具体的步骤说明如何找到一个稳定婚姻匹配:
step1:
每位男士都向自己喜欢列表中最靠前的那位女士求婚,女士们接收到求婚后,在那些向自己求婚的男士中(当然可能只有一个)选择一个自己最喜欢的,与之订婚。
m1向w3求婚,m2向w2求婚,m3向w3求婚,m4向w1求婚。w3接收到了两位男士的求婚,m1和m3,经过比较,她选择了她更喜欢的m3,拒绝了m1。于是第一步的匹配结果如下:
m2—-w2(横线表示这两个人已经订婚)
m3—-w3
m4—-w1
m1 w4(表示这两个人还是free状态)
step2:
接着,所有还没有订婚(free)的男士,向自己所喜欢的女士列表中的下一位求婚。
则m1会向w2求婚,此时w2已经与m2订婚,w2会将m1和m2进行比较,发现自己更喜欢现在的未婚夫m2,于是她会拒绝m1的求婚,可怜的m1依旧单身。第二步匹配结果没有发生改变,和第一步相同。
step3:
依旧单身的m1向他喜欢列表中的下一位女士求婚,也就是w1,此时w1已经和m4订婚,她将m1与m4进行比较,发现自己更喜欢现在的追求者m1而不是她的未婚夫,于是她会抛弃m4,与m1订婚。第三步之后,匹配结果变成:
m1—-w1
m2—-w2
m3—-w3
m4 w4
step4:
被抛弃的m4向他喜欢列表中的下一位女士求婚,也就是w2,而此时w2已经与m2订婚,她经过比较发现,她更喜欢现在的追求者m4,于是w2会抛弃m2,重新与与m4订婚,第四步之后匹配结果如下:
m1—-w1
m3—-w3
m4—-w2
m2 w4
step5:
刚刚被抛弃的m2,向他喜欢列表中的下一位女士求婚,也就是w4,而w4此时还是单身(free),那么顺利成章他们两个订婚了,所有的人都有了自己的归宿。最终的结果为:
m1—-w1
m2—-w4
m3—-w3
m4—-w2
关于稳定婚姻匹配的一些证明之类的内容我这里都没有讲到,只是通过一个实际的例子说明算法的具体步骤是怎么样的,具体的代码我用Python实现贴在这里:

manprefers = {'m1':['w3','w2','w1','w4'],
'm2':['w2','w4','w1','w3'],
'm3':['w3','w1','w4','w2'],
'm4':['w1','w2','w3','w4']}

womanprefers = {'w1':['m1','m3','m2','m4'],
'w2':['m3','m4','m2','m1'],
'w3':['m2','m3','m4','m1'],
'w4':['m4','m2','m1','m3']}

men = sorted(manprefers.keys())
women = sorted(womanprefers.keys())

def match():
manfree = men[:] # man who is free (not engaged)
engaged = {} # map
while manfree: # still some man is free
man = manfree.pop(0)
manlist = manprefers[man]
woman = manlist.pop(0)
fiance = engaged.get(woman)
if not fiance:
# the woman is free
engaged[woman] = man
print("%s and %s" % (man,woman))
else:
womanlist = womanprefers[woman]
if womanlist.index(fiance) > womanlist.index(man):
# the woman is not free but she prefers this man rather than her old fiance
engaged[woman] = man
print("%s dumped %s for %s" % (woman,fiance,man))
if manprefers[fiance]:
manfree.append(fiance)
else:
# she is faithful to her old fiance
if manlist:
manfree.append(man)
return engaged

engaged = match()
print engaged

最后,再贴上一段互动百科中给出的这个过程描述:

第一天上午,所有的男人都向自己最爱的女人求婚,下午,每个女人看看自己有没有收到,收到了多少人的求婚,如果只收到一个男人的求婚,那么就和他订婚。 如果收到多于一个男人的求婚,那么就和其中她最爱的那个男人订婚,同时把其他男人都拒掉。如果一个求婚都没有,不要着急,最后总会有的。晚上,检查一遍,如果所有女人都订婚了,万事大吉,明天举行集体婚礼,但如果还有女人没有订婚,那么事情还没有完,第二天还得重复,第二天上午,所有还没订婚的男人向自己次爱的女人求婚(因为昨天已经被他们的最爱拒了)。下午,每个女人再看一遍自己收到订婚的情况,如果她已经订婚了,但是又有一个她更爱的男人来向她求婚,那就把原来那个拒掉,再和这个更爱的男人订婚;如果还没订婚,那就和第一天的下午的处理一样。晚上再检查一遍,如果还是有人没有订婚,那第三天再重复,第三天上午,所有没有订婚的男人,包括第一天订了第二天又被踹出来的,再向还没有拒过他的女人中他最爱的那个求婚,如此周而复始,直到最后大家都订了婚,便一起结婚。

这个过程数学上可以证明:
第一,这个过程会中止,也就是说,总有大家都订了婚的一天,不可能无限循环。
第二,中止后所有的婚姻是稳定婚姻。 所谓不稳婚姻是说,比如说有两对夫妇M1, F1和M2, F2, M1的老婆是F1, 但他更爱F2;而F2的老公虽说是M2. 但她更爱M1, 这样的婚姻就是不稳婚姻,M1和F2理应结合, 他们现在各自的婚姻都是错误. 我们能证明的是, 通过上面那个求婚过程, 所有的婚姻都是稳定的, 没有人犯错误。
第三, 比较引人注目的是, 这个过程是male-optimal(对男性有利)的,男性能够获得尽可能好的伴侣,比如说最后有二十个女人拒绝了他,他仍然能够得到剩下的八十个女人中他最爱的那一个。
第四, 更有甚者,这个过程是female-pessimal(对女性不利)的, 女人总是在可能的情况下被最不喜欢的人追上。这一点没有那么直观的理解,勉强要解释的话, 可以这么看: 虽说女人每换一次订婚对象,都往上升一层,但起点可能很低,虽说在一步步接近她最爱的目标,但最后往往达不到。比如说还差三十名就达到她最爱的人了,但这时Game Over, 所有的人都已订了婚,这样她也只能死了心了。 还有三十个她更爱的人还没向她求过婚,可是她也无可奈何了。

P.S. 互动百科中有算法的C++实现代码。