新加坡官方交友App背后：Gale-Shapley稳定婚姻算法揭秘

新加坡政府推出的交友应用采用了经典的 Gale-Shapley 稳定婚姻算法（Stable Marriage Algorithm）进行用户匹配，这一消息在技术社区引发了热烈讨论。一个由政府主导的交友平台，选择用一套诞生于理论数学领域的算法来撮合姻缘，既体现了新加坡在应对低生育率问题上的务实态度，也让这个曾经停留在教科书里的算法走进了公众视野。

什么是 Gale-Shapley 稳定婚姻算法

Gale-Shapley 算法由数学家 David Gale 和 Lloyd Shapley 提出，用于解决所谓的「稳定婚姻问题」（Stable Marriage Problem）。其核心目标是：给定两组同等数量的对象（通常比喻为男性和女性），每个人对另一组所有成员都有一个偏好排序，算法要找到一种一一配对方式，使得整体匹配达到「稳定」状态。

所谓「稳定」，指的是不存在这样一对男女：他们彼此都更偏好对方，却没有被配对在一起。换句话说，没有任何两个人有动机抛弃现有的配对、私下结合。这个性质保证了匹配结果的鲁棒性——一旦配对完成，系统不会出现「集体叛变」的局面。

Shapley 也正是凭借在博弈论与匹配理论上的贡献，与 Alvin Roth 共同获得了诺贝尔经济学奖。这套算法的影响力远超交友场景，它早已被广泛应用于医学院毕业生与医院的住院实习分配、学生择校等现实问题中。

Gale-Shapley 算法发表于 1962 年，原始论文题为《College Admissions and the Stability of Marriage》，除了婚姻配对场景，论文同时讨论了大学录取问题——这也预示了它在教育和医疗资源分配领域的广泛应用。Lloyd Shapley 于 2012 年获得诺贝尔经济学奖时，David Gale 已于 2008 年辞世，因此未能共享这一荣誉。值得注意的是，算法本身的核心证明非常简洁：假设存在不稳定配对，则可以推导出矛盾，这种反证法的优雅让它成为算法课程中介绍「构造性证明」的经典范例。

算法如何运作

算法采用「求婚—接受」的迭代机制。以男性主动求婚为例：每一轮中，尚未配对的男性向自己偏好列表中排名最高、且尚未拒绝过他的女性求婚。女性收到求婚后，会在当前所有追求者（包括临时配对的对象）中保留自己最中意的一位，拒绝其余的人。被拒绝的男性进入下一轮，向偏好列表中的下一位求婚。

这一过程持续到所有人都完成配对为止。算法可以在多项式时间内收敛，并且数学上已证明必然产生一个稳定匹配。

一个有趣且常被讨论的性质是：算法对「主动求婚的一方」存在偏向性。由谁来主动发起求婚，谁就能获得在所有稳定匹配中对自己最有利的结果，而被动接受的一方则得到对自己最不利的稳定匹配。这种非对称性在政府交友应用的语境下尤其值得玩味——究竟由哪一方主导匹配，会直接影响用户的匹配满意度。

从时间复杂度来看，Gale-Shapley 算法的运行时间为 O(n²)，其中 n 为每组的参与人数。最坏情况下，每位男性需要向所有 n 位女性依次求婚，整个过程最多发生 n² 次求婚操作。这一复杂度在现实规模下完全可以接受——即便平台有数万名用户，计算本身也不是瓶颈。算法还有一个重要的确定性特征：无论求婚顺序如何调整，最终的「男性最优稳定匹配」结果唯一，不会因为实现细节不同而产生差异。这种结果的唯一确定性，对政府平台而言意味着相同的偏好输入永远得到相同的匹配输出，有助于消除质疑算法公正性的争议。

为什么新加坡选择它

新加坡长期面临生育率低迷的挑战，政府很早便通过官方机构介入婚恋领域。选用 Gale-Shapley 算法而非简单的相似度打分或机器学习推荐，背后有其考量。

相比黑箱式的推荐系统，稳定婚姻算法逻辑透明、结果可解释，且具备坚实的理论保证。对于一个政府项目而言，可解释性和公平性往往比单纯追求点击率、匹配量更重要。稳定性意味着用户不太容易产生「系统本可以给我更好的匹配」的不满情绪，这对维护平台公信力有实际价值。

不过，Hacker News 社区的讨论也指出了现实中的难题：经典算法假设双方人数相等、偏好完整且稳定，而真实的交友场景充满不确定性——用户偏好会随时间变化、信息不完整、两性用户数量往往失衡。如何将理论模型改造成可用的产品，是工程实现上的真正挑战。

Gale-Shapley 算法在现实中最著名的应用案例是美国的「全国住院医师匹配项目」（NRMP，National Resident Matching Program），该系统自 1952 年就开始运作，后来在 Alvin Roth 的参与下于 1998 年正式引入改良版 Gale-Shapley 算法，每年为数万名医学毕业生与医院完成匹配。这一先例对新加坡政府颇具说服力：在医疗分配这种高风险、高关注度的场景下，该算法已经经受了数十年的公众检验，其稳定性保证有效降低了参与者事后的抱怨与诉讼风险。相比之下，推荐算法在交友类商业应用中虽然普遍，但其优化目标（停留时长、付费转化）与政府平台的公共使命之间存在根本性冲突。

理论算法落地的启示

这则新闻真正引人深思的地方，在于一套纯理论的数学工具如何被赋予公共服务的使命。从教科书到约会软件，Gale-Shapley 算法的旅程说明了基础研究的长尾价值——一个最初为抽象问题设计的算法，数十年后可能在意想不到的领域发挥作用。

同时，它也提醒我们：算法的选择本身就是一种价值取向。采用稳定婚姻算法，意味着设计者优先考虑了结果的稳定与公平，而非商业平台惯用的互动最大化目标。当政府成为技术的部署者时，这种取舍往往会更倾向于社会效益而非商业指标。

对技术从业者而言，这个案例是一次很好的提醒：在选型时，经典算法的严谨性与可解释性，有时比追逐最新的机器学习模型更契合具体场景的需求。