直播预约，《环球科学》编辑陪你用科学总结2024年！
12月20日晚20:00，直播间将现场公布《环球科学》2024年度十大科学新闻，一场直播带你了解2024一整年的科学发展大事件，千万不能错过！
直播全程抽奖不断，杂志、桌垫送不停，更有24年最后一波超惠订阅福利！
不想错失这么多的超级好礼，就快点击【预约】按钮预约直播吧！
撰文｜麦克斯·施普林格（Max Springer）
翻译｜张岱铭
审校｜王昱
设想我们在制作一档与众不同的相亲真人秀。我们将在一座热带岛屿上租一栋别墅，然后邀请五男五女住在那里，他们每个人都有自己心仪的异性。不过，我们的目标和《爱情岛》系列节目完全相反：我们不想要任何戏剧化的冲突。我们能否确保所有人都能找到一个伴侣，并一直维持伴侣关系，而不会心生嫉妒？
数学家把这种难题称为“稳定匹配问题”或“稳定婚姻问题”。虽然感情本身可能难以捉摸，但研究人员已经证明，通过一个简单的算法，他们总能在两个人数相等的群体之间找到一组稳定的匹配。已故数学家劳埃德·沙普利（Lloyd Shapley）因发现这一算法而获得了2012年的诺贝尔经济学奖（纪念奖）——这个奖项他当之无愧：这一算法至今仍被用于住院医的医院分配以及入学儿童的学校分配中，它甚至启发了约会应用的算法设计。
在数学家的定义中，一段关系是稳定的意味着两个人都没有更好的选择——即便有，这个更好的选择对他们也不感兴趣。而不稳定的情况可能是这样的：想象一下，爱丽丝和鲍勃在一起，而查理则和达琳在一起。但是，鲍勃暗恋达琳，而达琳也无法忍受与查理在一起的生活。由于鲍勃和达琳可能会抛下他们的伴侣私奔，数学家称这种情况为不稳定。
这一难题不只出现于浪漫关系中。沙普利和数学家大卫·盖尔（David Gale）对这一问题最初的描述与大学录取相关：什么样的申请流程可以确保大学和申请人双方都对他们的选择感到满意呢？1962年，盖尔和沙普利证明，对于任何一组学生和大学（或者在相亲节目中的男女）构成的集合，总能找到一个使每一组配对都稳定的组合方式。而且，他们还提供了一个简单的配对流程，也就是算法。通过这个算法，他们可以根据每个人的优先排序来构建出相对满意的配对。
算法是这样运作的。为了给相亲节目的10位嘉宾找到一组稳定的、没有戏剧冲突的配对方式，我们首先让每位嘉宾按照他们的偏好顺序对异性成员进行排名。
然后，在节目的第一天，每位女性向她最中意的男性提出追求。一些男性可能会收到来自许多人的追求，而有些可能一个都没收到。接着，每位男性拒绝除他最喜欢的追求者之外的所有其他人的追求，这样一来，一些嘉宾会暂时形成配对，而另一些则仍未找到对象。
第二天，每位被拒绝的女性向她的第二顺位提出追求（无论对方是否已经配对）。如果男性更喜欢新的追求者，他们可以放弃当前的配对。于是，那些刚刚失恋的女性将继续追求下一个可能的伴侣。
这个过程会在第三天、第四天，以及随后的日子里不断重复，直到所有人都找到配对为止。通过这个流程，虽然未必每个人都对自己的配对感到满意，但数学上可以保证不会同时存在两个希望私奔——也就是说相比于各自当前的伴侣，他们更愿意和彼此在一起——的人（假设在相处的过程中他们的偏好没有发生改变）。虽然这并不能保证我们的《爱情岛》“姊妹集”没有任何戏剧冲突，但这可能已经是最好的结果了。
有趣的是，首先提出配对请求的一方是有优势的——当女性先提出追求时，她们最终的匹配结果往往比男性的匹配结果更符合各自的理想型。加州大学尔湾分校（University of California, Irvine）的计算机科学家维杰·瓦兹拉尼（Vijay Vazirani）解释道：“盖尔-沙普利算法的其中一个问题在于，它会让一方的匹配结果变得极端。”
虽然结果可能会有些偏颇，但盖尔和沙普利的策略是无懈可击的。而且事实上，从20世纪50年代起，一个匹配医学生和全国各地住院医项目的组织就已经在使用这种算法的某种变体了。1984年，斯坦福大学（Stanford University）的经济学家阿尔文·罗斯（Alvin Roth）利用盖尔和沙普利的数学语言证明了这个组织所使用的算法不仅能够保证匹配的稳定性，而且还是“策略防范”的——这意味着没有人可以利用这个系统投机取巧。这个重要的特征一般被称为激励相容性，因为它意味着只要每个人如实报告他们的偏好，他们最终都会得到最好的选择。
罗斯和经济学家埃利奥特·佩兰森（Elliott Peranson）还对算法做了一些改进。调整后的算法考虑到了那些已婚医学生的需求，即希望与彼此在同一个地方完成住院医实习。他们还注意到，由于医院先提出配对申请，医学生往往处于不利地位。罗斯主张让医学生先提出申请，以确保他们能得到最好的结果。直到现在，医院和新入职的住院医生仍然会互相进行排名，从而在数学上确保二者的匹配最终会达成稳定状态。罗斯和沙普利因此获得了2012年诺贝尔经济学奖。
罗斯和他的同事们还运用了这种数学语言来解决另一个棘手的匹配问题：为美国大城市的孩子分配公立学校。2003年，他们修改了盖尔-沙普利算法，以用于将纽约市的适龄学生分配到竞争激烈的公立高中。在实施的第一年，被分配到他们首选学校的学生人数从大约5万增加到了超过7万。该算法的另一版本也被用于将学生分配到波士顿的公立学校。
回到浪漫关系上，盖尔-沙普利算法甚至启发了包括Hinge在内的约会软件的底层算法逻辑。尽管用户并没有明确地对潜在匹配对象进行排名，但这些应用会观察用户的点赞和点踩的历史记录，以及他们所表明的约会偏好，来计算得到“最佳匹配”，并优先展示给用户。用户对潜在匹配对象发出的“点赞”或“消息”类似于原算法中的“追求”。
“像盖尔-沙普利这样的模型，其力量在于它能够跨越不同的场景而归纳出一个抽象的想法，”康奈尔大学（Cornell University）计算机科学教授乔恩·克莱因伯格（Jon Kleinberg）强调道。他说，不同领域的问题“在概念上都可能有某些共同之处”，而盖尔-沙普利算法“为我们提供了一种数学语言来讨论这些问题”。
虽然这个算法简单可靠，但如果排名中存在偏见，它也可能放大已有的不平等。据《城市新闻》（The City，一家位于纽约市的非营利新闻机构）获得的录取数据显示，黑人和拉丁裔学生在纽约市高中，尤其是在很多顶尖学校中的录取率通常低于白人和亚裔学生。对应的住院医匹配算法也被证明在种族和性别平等方面存在类似的问题。
“真正的问题不在于算法本身，而在于它们所使用的排名数据和所部署的社会环境，”波士顿学院（Boston College）经济学教授乌特库·温弗（Utku Ünver）解释道。这种效应在当前的人工智能热潮中显而易见：随着复杂的算法学会了再现数据中的模式，它们也往往复刻了我们的偏见。
“如果人类有偏见，那么我们的偏见就会体现在数据中，”康奈尔大学（Cornell University）计算机科学教授艾娃·塔尔多斯（Éva Tardos）说。研究人员已经提出了一些方法来消除数据中的偏见。例如，医院或学校等机构可以使用更大且更加多样化的评委小组来对候选人进行排名，也可以使用额外的算法在匹配之前对排名进行重新加权，以弥补已知的偏见。
当然，没有任何算法可以保证婚姻或教育中的完美匹配。但最佳选择仍然是一个简单、透明并能激励诚实的算法——正因如此，即使60年过去了，似乎仍然没有其他方法能够超越盖尔-沙普利算法。
原文链接：
https://www.scientificamerican.com/article/the-stable-marriage-problem-solution-underpins-dating-apps-and-school/
本文来自微信公众号“环球科学”。如需转载，请在“环球科学”后台回复“转载”，还可通过公众号菜单、发送邮件到newmedia@huanqiukexue.com与我们取得联系。相关内容禁止用于营销宣传。
-电商广告-
《环球科学》2024年12月新刊正在热卖
点击图片或阅读原文立即购买！
《环球科学》2025年度征订现已开启
点击图片或阅读原文即可订阅！
