Loading...
墨滴

webcraft

2021/11/28  阅读:74  主题:默认主题

寻找相亲配对的“最佳算法” —— 稳定婚姻问题 (Stable Marriage Problem)

假设你组织了一次相亲会,男女人数相同。参会者在相亲会上互相认识后,每个人心目中都对全体异性相亲对象有了一个偏好顺序。每个男性对每个女性都有了一个喜好的排序,所有女性也对男性有了这样一个排名。

作为组织者,搜集到所有人的排名信息后,你会如何考虑将男女配对,让他们后续发展?有没有一种最佳的配对方法?

当然,这里必须对“最佳”定个标准。在本问题中,“最佳”的首要标准是产生“稳定婚姻。“稳定婚姻”是这样定义的:

首先我们要定义的是“不稳定婚姻”。“不稳定婚姻”的定义是:如果有这样两对夫妇,其中一对的丈夫认为另一对夫妇中的妻子比自己的妻子好;同时另一对夫妇中的妻子认为当前的老公也不如另一个老公好。这里的“好”和“坏”就是按之前个人的喜好排名决定。如果存在这种情况,那就意味着有两对婚姻里有一男一女,同时存在离开现任配偶,与对方重组婚姻的意愿,那么这两对婚姻就是“不稳定婚姻”。


稳定婚姻和不稳定婚姻的例子,假设以下3男3女,有如下偏好关系,左边的为最喜欢:

男1:女1,女2,女3;

男2:女1,女3,女2;

男3:女2,女3,女1;

女1:男3,男1,男2;

女2:男1,男2,男3;

女3:男3,男2,男1;

则: 男1女1;男2女3;男3女2;是一组稳定婚姻。

男1女2;男2女1;男3女3;是一组不稳定婚姻。因为男1觉得男2的妻子女1,比现任妻子女2好;女1觉得女2的丈夫男1,比现任丈夫男2好。


“稳定婚姻”的定义就是一组婚姻中,不存在不稳定婚姻。那么对任何一组偏好列表,是否总可以进行合理的匹配,使得最终配对的结构都是“稳定婚姻”?这就是“稳定婚姻问题”(Stable Marriage Problem)。

答案:确实有这样的一个算法,可以确定地找到一种稳定婚姻方案。算法也挺有意思,其实跟生活中的行为是很有相似度的。这个算法有两个镜像版本:“男性主动”或是“女性主动”的版本。就以“男性主动”版本为例:

男性循环向女性求婚(其实男性求婚顺序无关紧要,最终结果是一样的)。任何时刻,没有婚约的男性都向自己偏好列表中的排名最高的(且从未求婚过的女性)求婚。而女性第一次接到求婚请求时,暂时接受婚约。第二次接受求婚时,她显然会比较一下这个男性与现有现订婚的男性的排名,如果更高则接受,并且放弃之前的婚约;否则直接拒绝当前的求婚。

每次求婚之后,总有部分男性被拒了,则继续按照自己的偏好列表继续求婚,但只向自己未求婚过的女性求婚了。而所有女性策略还是相同,如果新的求婚排名高则接受,并且拒掉之前婚约,否则直接拒绝。

每次求婚之后,总有一些原先有婚约的男性不幸被拒,重新加入相亲军团。

那么如此循环,直到所有人都结婚,则算法结束,问题解决。


仍按之前三男三女为例,执行以上求婚算法,偏好列表是:

男1:女1,女2,女3;

男2:女1,女3,女2;

男3:女2,女3,女1;

女1:男3,男1,男2;

女2:男1,男2,男3;

女3:男3,男2,男1;

则一种可能的求婚过程是:

男1向女1求婚,女1接受;

男2向女1求婚,因女1对男1比男2更偏好,则女1拒绝;

男3向女2求婚,女2接受;

男2向女3求婚,女3接受。

此时,所有人都有婚约;结果如下:

男1女1;男2女3,男3女2。可以验证,结果为稳定婚姻。

可以看出,此结果中,男性较为满意,但女性不太满意,特别是女2。


对此算法,你肯定会有若干疑问:

第一个问题是,怎么证明算法可以在有限时间内结束?

因为每名男性只可能向特定的女性求婚一次。所以,总的求婚次数最多是n²,n就是男性或女性人数。这个数字是有限的,所以算法必然在有限时间内结束。

第二个问题是,怎么确定算法结束时,每个人都结婚了?

可以用反证法,如果有这种情况,那么存在一个女人,她从来未被求过婚,并且有从未向这个女人求过婚的男人。但这是不可能的,因为如果只剩下这个男人和这个女人没有结婚,那么根据算法,不管这个女人在这个男人的喜好列表里的排名有多低,他还是得向这个女人求婚。所以,算法结束时,所有人都结婚了。

最后一个问题:怎么证明所有婚姻是稳定的?还是用反证法,如果存在这样两对不稳定夫妻,且不稳定因素是Bob和Alice。那么因为Alice在Bob心目中的排名比其现任妻子高,则Bob必然在现任妻子之前向Alice求婚过。而Alice心目中,Bob的排名比现任丈夫高,则不管其现任丈夫在Bob之前或之后求婚,留下的必然是Bob。所以不可能出现不稳定婚姻。

这个算法是1960年代,由科学家戴维·盖尔(Gale)和劳艾徳·沙普利(Shapley)提出来的,现在该算法用他们的姓氏首字母命名,称为“GS算法”。有意思的是“GS算法”在被正式提出之前,就已经在一些场合下被使用了。但不是用在相亲,而是用在一些地方的医学院接受实习医生的配对选择流程。

(上图:一定人数下,可能产生的稳定婚姻组合数量。横轴为男性或女性人数,纵轴为稳定婚姻组合数。虚线为计算机采样结果,实线为Pittle的理论公式预测。一般认为,稳定婚姻组合数的增长与N*lnN同级。图片来源:Michael Dzierzawa, Marie-José Oméro, Statistics of stable marriages, Physica A 287 (1–2) (2000) 321–333.)

GS算法流程是清楚了,但你肯定还有不少的疑问和思考,那以下我就讲讲这个问题的若干变种和对它们的一些分析。

第一个变种是,虽然GS算法给出的结果都是稳定的婚姻,但是同样是稳定,稳定的程度是不同的。可以想到有这样一种现成的对婚姻稳定度的度量:每一对夫妇,其配偶在自己的喜好列表上的名次。名次越高,名次的数值越小,表示对配偶越满意,婚姻也越稳定。

这一度量取值范围是1到n,n为男性或女性人数。对这个度量,我称其为“稳定成本”,因为它表达了婚姻的稳定度,并且越低,越稳定,所以是“成本”。

有了“稳定成本”这样一种度量,我们一下子可以考虑很多有意思的问题。比如对之前男方主动求婚的GS算法,其给出配对结果,男方与女方的稳定成本比较,哪一方的稳定成本比较低,哪一方对婚姻更满意呢?答案有点出人意料:男方满意度较高,女方较低。

实际上可以证明,在男方主动求婚的情况下,最后配对的结果,在所有可能的稳定配对结果中,男性总是可以与可能的最高顺位的女性配对,而女性则是所有可能结果中,与顺位最低的男性结婚。

(上图:男性主动情况下的GS算法中,男女稳定成本的图例。横轴为人数,带○线为男性稳定成本,带黑点的实线为女性稳定成本。可以看出,在男性主动情况下,男性比女性对配偶更满意。图片来源同前。)

那么当然,如果算法改成女性主动求婚的话,那么结果总是女性的满意度最高,而男性的满意度最低。总之,可以学到的一点是,在找配偶的问题上,主动出击有时是很重要的。


仍按之前三男三女为例,以女性主动方式,执行以上求婚算法,偏好列表是:

男1:女1,女2,女3;

男2:女1,女3,女2;

男3:女2,女3,女1;

女1:男3,男1,男2;

女2:男1,男2,男3;

女3:男3,男2,男1;

则一种可能的求婚过程是:

女1向男3求婚,男3接受;

女2向男1求婚,男1接受;

女3向男3求婚,男3接受,女1被毁约;

女1向男1求婚,男1接受,女2被毁约;

女2向男2求婚,男2接受。

配对结果为:

女1男1,女2男2,女3男3。这种女性主动下的配对结果,女性会比较满意。


那么,会出现另一个问题,如果要求男女满意度差不多,该怎么办?这个想法又会引出很多问题。

先考虑这样一个问题:如果我们要求配对的结果是总体上稳定成本最小,即所有人的稳定成本之和最小,这种条件下,是否总是产生稳定婚姻?

很可惜,答案是否定的。也就是总体上最稳定的婚姻组合,局部很可能产生不稳定婚姻。比如之前的例子,全局最小稳定成本配对结果是:

男1女2,男2女1,男3女3。男性总稳定成本为:2+1+2=5,女性总稳定成本为:3+1+1=5,总成本为10。可以验证,这是一种达到最小总成本的配对方案,然而这个方案是不稳定的,不稳定因素来自男1和女1。这也是社会学领域经常遇到的情况,即因为个体的“自私”,导致社会总成本上升,这种情况非常常见。

另一个问题是,怎么寻找这种总体上的最优解?算法复杂度如何?之前的GS算法是比较好的算法那,它的复杂度是n²,n是男人或女人的人数。而寻找总体最优解,如果用蛮力搜索,枚举所有组合,那么需要n!次搜索,显然不太优越。你也可以想象,如果是需要找到精确最优解的话,那它是一个指数复杂度的问题和一个NP问题。甚至还是一个“NP-困难”的问题,因为给出一个组合,验证这个组合是否是全局最优,都没有一个多项式算法。

但这个情况下,有个有意思的计算,就是全局最优情况下,每个人匹配到配偶的排名期望值是多少?数学家给算出来了,这个值是1.617√N(黄金分割比?),N是男性或女性人数。也即是说,如果是100个男性和女性,如果按全局最配对,那么平均每个人能匹配到的配偶的排名是1.617√100,约等于16名。 这个结果还不错,就是每个人的配偶是自己心目中,在100个人里排名第16名左右。但这是不考虑婚姻是否稳定的,其中有可能存在不稳定婚姻的情况。

那么下一个问题是,要求稳定婚姻的情况下,最低总稳定成本的情况如何?这里有一个意外的情况是,这种条件下,有了多项式时间的匹配算法。而之前,在不要求稳定婚姻情况下,反而没有多项式时间的算法。增加了约束条件后,却有了更快的算法。这是非常有意思的,问题的要求更多,计算反而更快了。原因是可以猜到的:因为在要求稳定婚姻的情况下,有很多组合不用考虑了,反而能加速了。

这个具体算法略复杂,,现在的算法复杂度是N³,比GS算法的N²要复杂点,但仍然是多项式时间的算法。那么这时候平均每个人的稳定成本或配偶排名是多少呢?数学家也算出来了,答案是2√(N),也就是100对夫妻的话,平均每个人的配偶排名大概是第20名。比之前的16名要差一些,但总体上还是挺靠前的。

所以,如果你要搞相亲会的话,也许这种稳定婚姻情况下的全局最优算法,是一种比较好的匹配算法。

但目前为止,我们还没有讨论过男女平等的问题。那么我们来看看怎么能做到男女平等,但我们需要先定义一个男女平等的标准。高德纳(Donald Knuth)和波利亚(George Polya)等人曾提出过这么三种标准:

第一种:平等主义下的最低稳定成本(minimization of egalitarian cost)。它的意思是把全体男性看各自妻子的名次累加得到一个数值,然后把全体女性看各自丈夫的名次累加得到一个数值,两个数值相加得到一个总成本值,并寻找其最小值。其实这个标准与之前的全局最低是一摸一样的,之所以叫它“平等主义”就是不区分性别了,男女混在一起算,这可能也算一种男女平等,是现在比较流行的一种平等概念。

第二种:最小后悔成本(minimization of regret cost)。这种情况下,规定这样一种“后悔成本”:一对夫妻中,夫妇看对方的名次中,比较大的那个数值,就称为这对夫妻的“后悔成本”。比如说,丈夫看妻子是排名第1,妻子看丈夫则是排名第10, 则这对夫妻的后悔成本是10。现在我们要寻找这样一种使得全体夫妻的后悔成本总和最小的配对,这种配对方案被称为“最小后悔成本”。对这种问题,现在已经找到一种算法,复杂度与GS算法是一样的N²,说明这个问题现在已经很好得被解决。

第三种男女平等标准:“性别平等下的最小成本”(minimization of sex-equalness cost),它应该是大家心目中最常见的男女平等,即全体男性的稳定成本之和,与全体女性的稳定成本之和,两者比较差值的绝对值,希望越小越好。不像第一种,第一种是比较男女成本的和值,这个是比较差值,这大概是大家心目中典型的男女平等。这种条件下的稳定婚姻问题,也被称为“平衡稳定婚姻问题”(Equitable Stable Marriage Problem)。对这类问题,又有一个意外情况就是,它没有多项式算法了。如同寻找全局最优问题一样,它又变成一个NP-困难问题,虽然这种男女平等是大家很希望的一个结果。

(上图:稳定婚姻情况下,男女稳定成本对比,横轴为女性,纵轴为男性。图片是在200人的情况下,产生若干随机偏好列表列表,寻找其中所有稳定婚姻组合,分别计算男性和女性稳定成本。图片来源:Physics Reports 917 (2021) 1–79)

以上就是科学家提出过的三种“男女平等思想下”的度量。但我自己又考虑了下,其实还可以有其他的男女平等度量。比如基于“方差”的度量,因为人喜欢与其他人比较稳定成本,虽然这种心理不太好。

但是这样,就可以另外定义三种类似的度量:

“平等主义下的最小稳定方差:就是看所有人的稳定成本的方差,越小越好。

“性别平等下的最小成本方差”,顾名思义,就是那女分开来看,分别计算全体男性的稳定成本方差和全体女性的稳定成本方差,越小越好。

第三种,可能是“三观”最不正的,可以叫“最小夫妻嫌弃指数”:就是夫妻间,互相看对方的稳定成本,也就是排名的差值,希望越小越好。比如夫妻互看,都是第一名,那当然是最好;如果丈夫嫌弃妻子,妻子看丈夫也是哪都不行,虽然可能家庭不太和谐,但也算平等了吧。但如果一方看另一方排名很高,而另一方反过来排名很低,落差很大,那么男女就不太平等了。GS算法产生的结果往往就是这种情况,有时我们需要避免那种情况。那么就可以定义夫妻间“嫌弃指数”:双方看彼此的排名的差值的绝对值。那我们如果寻找所有夫妻的“嫌弃指数”的最小值,那么也是一种可以研究的问题。

以上三种度量可能是因为“三观不正”,目前我没有看到有人研究过算法,有兴趣的听众可以自己研究下。

那好了,以上对稳定婚姻问题的基本形态和目前的一些结果介绍完了,讲讲它的若干种扩展。扩展有两大类,一种是扩展配对的数量。

比如有这样一种家庭组合问题:有若干男女和待收养的小孩,所有男女和小孩都对其他集合的对象有一个偏好列表,问如何将一男一女和一个小孩组合在一起,成立家庭最为合理。问题内容挺奇葩的,但确实是一个很好的算法问题。

还有一种扩展,就更常见了,就是配对对象本身不分类型,希望被划分到若干组。比如一群人去吃饭,人数很多,需要分桌。每个人都有一些希望一起吃饭和希望不一起吃饭的人,那么怎样分桌可以使大家最满意,这就是一个“分桌问题”(Seating Problem)。有时它也被称为“稳定室友问题”(Stable Roommate Problem)。

(上图:室友关系好坏对学生是一个很重要的问题)

听上去“稳定婚姻”问题都是处理一些不太正经的问题,但其实它有很多非常正经的应用场合。除了之前的分配学生去医院实习的问题,其实大学录取过程,就有点像“稳定婚姻问题”。对美国的大学录取,就更为典型。比如,美国大学的基本录取流程就是,学生可以向若干大学同时发出申请,如果其中有若干大学同意录取,那么学生就可以选择自己最想去的大学。如果全部被拒了,那么学社还有几会继续发申请给其他大学。这个流程有点像前面“GS算法”,因为学生主动申请,结果会对学生比较理想,学生总是可以进入其可能进入的最好大学。当然,学校也会意识到这个问题,所以有时大学会主动邀请他们特别想录取的学生入学。

还有一种应用场合则更加性命攸关了,就是器官捐献和匹配。如果现在有三个可供移植的相同器官和三个等待移植的病人。把哪个器官分配给谁,如何做到公平合理,移植效果又最大化,这就是需要诸多权衡和考虑的问题。

最后,稳定婚姻问题在物理学中也有它的意义。我们可以把稳定成本想象成一个物体的能量或者能级。一般来说,一个系统中的物体总是倾向于从能级高到能级最低的状态演变。很多学术论文里,会直接把“稳定婚姻”问题里的“稳定成本”称为“能量”,那么寻找最小总成本的问题,就相当于寻找这个系统最稳定状态的问题,这就是“稳定婚姻问题”在物理学中的意义。

参考链接:

https://www.sciencedirect.com/science/article/pii/S0370157321000843

https://hal.archives-ouvertes.fr/jpa-00247483/document

DOI: 10.1051/jphyslet:019850046017077100

webcraft

2021/11/28  阅读:74  主题:默认主题

作者介绍

webcraft