寻找相亲配对的“最佳算法”——“稳定婚姻问题”
假设你组织了一次相亲会，男女人数相同。参会者在相亲会上互相认识后，每个人心目中都对全体异性相亲对象有了一个偏好顺序。每个男性对每个女性都有了一个喜好的排序，所有女性也对男性有了这样一个排名。作为组织者，搜集到所有人的排名信息后，你会如何考虑将男女配对，让他们后续发展？有没有一种最佳的配对方法？
https://p3-sign.toutiaoimg.com/tos-cn-i-qvj2lq49k0/52ec10d566f2432cb78c660268550aed~tplv-tt-large.image?x-expires=1969860254&x-signature=siSBBvm9FNEv2qTocz9liPuaQGI%3D
当然，这里必须对“最佳”定个标准。在本问题中，“最佳”的首要标准是产生“稳定婚姻。“稳定婚姻”是这样定义的：
首先我们要定义的是“不稳定婚姻”。“不稳定婚姻”的定义是：如果有这样两对夫妇，其中一对的丈夫认为另一对夫妇中的妻子比自己的妻子好；同时另一对夫妇中的妻子认为当前的老公也不如另一个老公好。这里的“好”和“坏”就是按之前个人的喜好排名决定。如果存在这种情况，那就意味着有两对婚姻里有一男一女，同时存在离开现任配偶，与对方重组婚姻的意愿，那么这两对婚姻就是“不稳定婚姻”。
<hr>稳定婚姻和不稳定婚姻的例子，假设以下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好。
<hr>“稳定婚姻”的定义就是一组婚姻中，不存在不稳定婚姻。那么对任何一组偏好列表，是否总可以进行合理的匹配，使得最终配对的结构都是“稳定婚姻”？这就是“稳定婚姻问题”（Stable Marriage Problem）。
答案：确实有这样的一个算法，可以确定地找到一种稳定婚姻方案。算法也挺有意思，其实跟生活中的行为是很有相似度的。这个算法有两个镜像版本：“男性主动”或是“女性主动”的版本。就以“男性主动”版本为例：
男性循环向女性求婚（其实男性求婚顺序无关紧要，最终结果是一样的）。任何时刻，没有婚约的男性都向自己偏好列表中的排名最高的（且从未求婚过的女性）求婚。而女性第一次接到求婚请求时，暂时接受婚约。第二次接受求婚时，她显然会比较一下这个男性与现有现订婚的男性的排名，如果更高则接受，并且放弃之前的婚约；否则直接拒绝当前的求婚。
每次求婚之后，总有部分男性被拒了，则继续按照自己的偏好列表继续求婚，但只向自己未求婚过的女性求婚了。而所有女性策略还是相同，如果新的求婚排名高则接受，并且拒掉之前婚约，否则直接拒绝。
每次求婚之后，总有一些原先有婚约的男性不幸被拒，重新加入相亲军团。
那么如此循环，直到所有人都结婚，则算法结束，问题解决。
<hr>仍按之前三男三女为例，执行以上求婚算法，偏好列表是：
男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。
<hr>对此算法，你肯定会有若干疑问：
第一个问题是，怎么证明算法可以在有限时间内结束？
因为每名男性只可能向特定的女性求婚一次。所以，总的求婚次数最多是n²，n就是男性或女性人数。这个数字是有限的，所以算法必然在有限时间内结束。
第二个问题是，怎么确定算法结束时，每个人都结婚了？
可以用反证法，如果有这种情况，那么存在一个女人，她从来未被求过婚，并且有从未向这个女人求过婚的男人。但这是不可能的，因为如果只剩下这个男人和这个女人没有结婚，那么根据算法，不管这个女人在这个男人的喜好列表里的排名有多低，他还是得向这个女人求婚。所以，算法结束时，所有人都结婚了。
最后一个问题：怎么证明所有婚姻是稳定的？还是用反证法，如果存在这样两对不稳定夫妻，且不稳定因素是Bob和Alice。那么因为Alice在Bob心目中的排名比其现任妻子高，则Bob必然在现任妻子之前向Alice求婚过。而Alice心目中，Bob的排名比现任丈夫高，则不管其现任丈夫在Bob之前或之后求婚，留下的必然是Bob。所以不可能出现不稳定婚姻。
这个算法是1960年代，由科学家戴维·盖尔（Gale）和劳艾徳·沙普利（Shapley）提出来的，现在该算法用他们的姓氏首字母命名，称为“GS算法”。有意思的是“GS算法”在被正式提出之前，就已经在一些场合下被使用了。但不是用在相亲，而是用在一些地方的医学院接受实习医生的配对选择流程。
https://p3-sign.toutiaoimg.com/tos-cn-i-qvj2lq49k0/f6c89e3f4e9a45699adbc0544cf32cfe~tplv-tt-large.image?x-expires=1969860254&x-signature=P50eaOWktAPyrB3F4h3yVZ9iK1w%3D
(上图：一定人数下，可能产生的稳定婚姻组合数量。横轴为男性或女性人数，纵轴为稳定婚姻组合数。虚线为计算机采样结果，实线为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算法，其给出配对结果，男方与女方的稳定成本比较，哪一方的稳定成本比较低，哪一方对婚姻更满意呢？答案有点出人意料：男方满意度较高，女方较低。
实际上可以证明，在男方主动求婚的情况下，最后配对的结果，在所有可能的稳定配对结果中，男性总是可以与可能的最高顺位的女性配对，而女性则是所有可能结果中，与顺位最低的男性结婚。
https://p3-sign.toutiaoimg.com/tos-cn-i-qvj2lq49k0/98ef6b43cb754193a0181bd0d04d4d8a~tplv-tt-large.image?x-expires=1969860254&x-signature=i2LTJ9VumMqbHk3Sk9%2BkghSNoAE%3D
（上图：男性主动情况下的GS算法中，男女稳定成本的图例。横轴为人数，带○线为男性稳定成本，带黑点的实线为女性稳定成本。可以看出，在男性主动情况下，男性比女性对配偶更满意。图片来源同前。）
那么当然，如果算法改成女性主动求婚的话，那么结果总是女性的满意度最高，而男性的满意度最低。总之，可以学到的一点是，在找配偶的问题上，主动出击有时是很重要的。
<hr>仍按之前三男三女为例，以女性主动方式，执行以上求婚算法，偏好列表是：
男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。这种女性主动下的配对结果，女性会比较满意。
<hr>那么，会出现另一个问题，如果要求男女满意度差不多，该怎么办？这个想法又会引出很多问题。
先考虑这样一个问题：如果我们要求配对的结果是总体上稳定成本最小，即所有人的稳定成本之和最小，这种条件下，是否总是产生稳定婚姻？
很可惜，答案是否定的。也就是总体上最稳定的婚姻组合，局部很可能产生不稳定婚姻。比如之前的例子，全局最小稳定成本配对结果是：
男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-困难问题，虽然这种男女平等是大家很希望的一个结果。
https://p3-sign.toutiaoimg.com/tos-cn-i-qvj2lq49k0/56e4f8b6d1c84c389ee6d3e2263461f0~tplv-tt-large.image?x-expires=1969860254&x-signature=faSN%2F8l7AVPh7bNqCNnfHSp9Bx4%3D
（上图：稳定婚姻情况下，男女稳定成本对比，横轴为女性，纵轴为男性。图片是在200人的情况下，产生若干随机偏好列表列表，寻找其中所有稳定婚姻组合，分别计算男性和女性稳定成本。图片来源：Physics Reports 917 (2021) 1–79）
以上就是科学家提出过的三种“男女平等思想下”的度量。但我自己又考虑了下，其实还可以有其他的男女平等度量。比如基于“方差”的度量，因为人喜欢与其他人比较稳定成本，虽然这种心理不太好。
但是这样，就可以另外定义三种类似的度量：
“平等主义下的最小稳定方差：就是看所有人的稳定成本的方差，越小越好。
“性别平等下的最小成本方差”，顾名思义，就是那女分开来看，分别计算全体男性的稳定成本方差和全体女性的稳定成本方差，越小越好。
第三种，可能是“三观”最不正的，可以叫“最小夫妻嫌弃指数”：就是夫妻间，互相看对方的稳定成本，也就是排名的差值，希望越小越好。比如夫妻互看，都是第一名，那当然是最好；如果丈夫嫌弃妻子，妻子看丈夫也是哪都不行，虽然可能家庭不太和谐，但也算平等了吧。但如果一方看另一方排名很高，而另一方反过来排名很低，落差很大，那么男女就不太平等了。GS算法产生的结果往往就是这种情况，有时我们需要避免那种情况。那么就可以定义夫妻间“嫌弃指数”：双方看彼此的排名的差值的绝对值。那我们如果寻找所有夫妻的“嫌弃指数”的最小值，那么也是一种可以研究的问题。
以上三种度量可能是因为“三观不正”，目前我没有看到有人研究过算法，有兴趣的听众可以自己研究下。
那好了，以上对稳定婚姻问题的基本形态和目前的一些结果介绍完了，讲讲它的若干种扩展。扩展有两大类，一种是扩展配对的数量。
比如有这样一种家庭组合问题：有若干男女和待收养的小孩，所有男女和小孩都对其他集合的对象有一个偏好列表，问如何将一男一女和一个小孩组合在一起，成立家庭最为合理。问题内容挺奇葩的，但确实是一个很好的算法问题。
还有一种扩展，就更常见了，就是配对对象本身不分类型，希望被划分到若干组。比如一群人去吃饭，人数很多，需要分桌。每个人都有一些希望一起吃饭和希望不一起吃饭的人，那么怎样分桌可以使大家最满意，这就是一个“分桌问题”（Seating Problem）。有时它也被称为“稳定室友问题”(Stable Roommate Problem）。
https://p3-sign.toutiaoimg.com/tos-cn-i-qvj2lq49k0/8ffbe68b3246493db0debb975dcde2f2~tplv-tt-large.image?x-expires=1969860254&x-signature=6zwWyFyhaS9ygMr%2FBaSVdefwgQI%3D
(上图：室友关系好坏对学生是一个很重要的问题)
听上去“稳定婚姻”问题都是处理一些不太正经的问题，但其实它有很多非常正经的应用场合。除了之前的分配学生去医院实习的问题，其实大学录取过程，就有点像“稳定婚姻问题”。对美国的大学录取，就更为典型。比如，美国大学的基本录取流程就是，学生可以向若干大学同时发出申请，如果其中有若干大学同意录取，那么学生就可以选择自己最想去的大学。如果全部被拒了，那么学社还有几会继续发申请给其他大学。这个流程有点像前面“GS算法”，因为学生主动申请，结果会对学生比较理想，学生总是可以进入其可能进入的最好大学。当然，学校也会意识到这个问题，所以有时大学会主动邀请他们特别想录取的学生入学。
还有一种应用场合则更加性命攸关了，就是器官捐献和匹配。如果现在有三个可供移植的相同器官和三个等待移植的病人。把哪个器官分配给谁，如何做到公平合理，移植效果又最大化，这就是需要诸多权衡和考虑的问题。
最后，稳定婚姻问题在物理学中也有它的意义。我们可以把稳定成本想象成一个物体的能量或者能级。一般来说，一个系统中的物体总是倾向于从能级高到能级最低的状态演变。很多学术论文里，会直接把“稳定婚姻”问题里的“稳定成本”称为“能量”，那么寻找最小总成本的问题，就相当于寻找这个系统最稳定状态的问题，这就是“稳定婚姻问题”在物理学中的意义。
参考链接：
https://www.sciencedirect.com/science/article/pii/S0370157321000843
https://hal.archives-ouvertes.fr/jpa-00247483/document
DOI: 10.1051/jphyslet:019850046017077100
页:
[1]