红娘与座次：稳定匹配的一种算法

为婚宴安排来宾的坐席，永远是一门艺术。亲友喜好和相互避嫌的清单，是必备：和谁聊得来、谁和谁最好别挨着、谁想坐靠窗、谁一定要离甜品台近。按这些信息给来宾排座的目的不是“最优”，而是别留下让来宾想起身换座的诱因。对数学家而言，这是算法世界里的一个重要概念——稳定匹配。

“匹配”，是指把对象一一配对；而“稳定”，则是指已经完成的匹配中不存在这样一组“不稳定”的对象，他们不是各自被分配到的对象，却彼此都更愿意和对方“在一起”。如果有这样的一组对象，就会像婚宴上有人“起身去找别桌的人聊天，一聊就不回来了”。很多破裂的家庭，也是源自出现了这样的存在。这种不稳定匹配可能出现在不同的场景中，可以是相亲（两边互选），可以是学校录取（学生和学校互相有偏好），也可以是医院分配住院医师（医生与医院互选）等，也可以是房产的卖家和买家。事实上，只要是在容许双方自由互选的市场化场景中，这个稳定的概念就有其意义。

六十多年前，大卫·盖尔（David Gale）和劳埃德·沙普利（Lloyd Shapley），在他们的经典论文《大学录取与婚姻稳定》中，为稳定匹配发明了一个朴素却影响深远的算法：延迟接受算法（Deferred Acceptance）。

延迟接受算法非常具有“人情味”：如同在集体求婚的现场

由一方先“表白”。比如让所有求婚者同时向自己最心仪的对象表白。
被表白的一方先“暂时保留”目前最好的一位，其余都婉拒。
被拒的那些人转身去找自己的下一志愿再表白。
重复：被表白的一方总是“暂时保留最好”，直到再也没有新的表白出现。
最后，所有“暂时保留”都变成“正式接受”，配对完成。

注意，被表白的一方可能有多次选择的机会。最终保留的，总是所有向自己表白的中最中意的那一位。

比如，甲、乙、丙三位男生；青、蓝、橙三位女生。
第一轮：三位男生各自找第一志愿，女生们各留“当前最喜欢”的一个。
被拒的男生第二轮去找自己的第二志愿……
若某一对“互相被暂存”，除非后来来了她/他更心仪的对象，否则这一对会保持到终局。
最终任何想“私奔”的人都会发现：要么自己更中意的人已经拿到了更喜欢的人，要么也不愿意放弃当前对象。这就是“没有诱人的私奔可能”——稳定。

这个算法的好处有三。第一，这样得到的结果一定稳定，不会出现“台下私奔”的可能；第二，由谁先表白，谁就更占便宜：如果是“求婚者先表白”，结果对求婚者“最优”（表白者的竞争对手可能正在向其他人表白），对被求婚者而言则是“最差中的最好”（仍然稳定，但站在被求婚者视角不算理想，因为最理想的可能已经对别人表白）；第三，操作直观，像比一场无规则的相亲会，这样的过程秩序会更好。

你也许会问：为什么“稳定”这么重要？因为一旦不稳定，人就有动力“私下改约”。市场就会解体：形如一张大网的不稳定配对，很容易在暗处被一对对自愿跑单者撕裂。二十世纪中期的美国医疗系统就吃过这个亏：医院和医学生为了抢先纷纷提前签约，签得越来越早，甚至还没毕业就谈完。但因为双方信息不足、悔约不断，人人焦虑。后来引入基于“延迟接受”的全国性统一匹配，才把“抢跑”刹住，市场重新安稳下来。很多城市的义务教育学区派位、大学专业调剂、研究生导师-学生配对，也都用到了这类思路。

再回到前面的婚宴坐席排位。假如你让“嘉宾先选座”，那最终安排会更有利于嘉宾；若改成“桌位先挑人”（比如主持人按主桌喜好先定），而不是先匹配人再确定桌位，则更有利于桌位一方。我们也可以根据“谁更弱势、谁的信息更少、谁承担更大风险”，来决定把“先表白”的主动权交给谁。所以，优化算法从来不是价值中立的工具——它自身的过程总是包含了作者关心的价值观。

当然，现实并不总是如童话般理想且简单：

一对情侣要在同一城市甚至同一家单位？这叫“耦合偏好”，直接把问题的难度“抬高一个数量级。很多应用系统为此在“延迟接受”的骨架上舔加了大量细节。
名额不止一个怎么办？学校/医院往往是“多对一”匹配（有配额）。算法可以自然扩展：把“座位数”看作“同一对象的多个位置”，仍然“暂存最好、其余婉拒”，一样能收敛到稳定结果。
有人没有明确排序、或“无所谓”时？就需要处理“并列”与“随机打破并列”，否则可能出现“卡在原地”的情况。
策略问题：延迟接受对“先表白的一方”是真实申报最优（如学生先报，学生诚实报志愿总是最好），但对另一方不保证——这就是为什么很多政策把“主动权”给相对弱势那边，鼓励他们诚实表达偏好，减少“志愿表演”。

值得注意的是，系统的稳定并不等于不同于稳定的其它价值的整体最优，或者每个人都得到最优。有时为了稳定，你不得不接受某些人的遗憾。换句话说，稳定是一种“可持续”的公平，是不给任何两个人一个立刻背叛系统的理由，不是让每个人瞬间最开心。在容易“私下改约”的世界里，这种公平常常比每一个都最开心更重要，更珍贵。

从婚宴、相亲到教育与医疗，稳定匹配背后潜伏着一条更宽的行业 – 市场设计。经济学家阿尔文·罗斯（Alvin Roth）把这些算法从思维实验带进系统工程，把“怎么排座”变成“如何让一个大系统稳定地运转”。如前面所说，这类系统可以出现在很多不同的场景和不同的优化目标中：

学校选择：把“就近优先、兄弟姐妹就读、特长生”等政策翻译成可比较的优先级，再让延迟接受去跑。
实习/住院医师分配：在“多对一”和“耦合”的复杂度里，仍尽量保证稳定与透明。
肾脏互惠交换：不是简单的“两边互选”，而是把不匹配的供受体组成“交换环”，让本来互相帮不上忙的人，通过三人或多人互换，间接成全彼此

上面这些场景，已超出“婚姻稳定”的基本模型，却继承了“没有任何参与者愿意退出”的精神。

所以，算法并不总是冷冰冰的公式。它像一位有经验的主持人，懂得“谁要先发言”、“谁需要安心感”、“怎样避免尴尬”。它既关心效率（尽量多成对、多达成愿望），也关心人心（不给背约的理由）。“把价值观嵌入算法”并非简单空洞的口号，而是每一道选择的细节背后都为我们最初的优化目标驱动 – 例如“稳定”：谁先表白、如何打破并列、怎样公开偏好与规则、遇到耦合如何照顾、是否允许“等候名单”滚动等。

回到婚宴的坐席，一次看似离散甚至随机的排座，背后也嵌入了我们对公平与秩序的选择。你可以追求“眼前满意度最大化”，也可以追求“没有人想离席”的稳态。人类社会的很多问题，终究要靠这种可被解释、可被执行、可被信任的程序来维持 — 不论是红娘，还是交通规则。

小实验：

挑一组“双方各 4 人”的小配对，随便写下每个人的偏好顺序（尽量不要出现完全一致的偏好）。