稳定匹配：为什么先提议的一方更有利

八个人，每个人心里都有一份固定的偏好名单。把名单一个字都不改，只换一组人先发出邀请，最后竟能得到两套不同的配对，而且两套都“稳定”。

月下老人翻婚书、系红绳，故事把姻缘交给一种预先安排好的秩序。《定婚店》一类传说里的这个意象，换到数学中，就变成了一个可以明确检验的问题：如果没有谁预先指定答案，人们按各自的偏好行动，能不能找到不会被另一对人共同推翻的安排？^[3]

稳定，要排除的是一对阻挡者

设甲、乙已经配好，丙、丁也已经配好。如果甲更喜欢丁，丁也更喜欢甲，两人就都愿意离开当前搭档，改为选择彼此。这一对没有配在一起、却相互更愿意换到一起的人，叫作阻挡对。

只要还存在阻挡对，安排就不稳定；一对也找不出来，才满足稳定性。单方面更喜欢别人不够，双方都愿意换，才会形成阻挡。

这个目标不要求人人拿到第一名，也不把所有人的满意程度加成一个总分。先把“稳定”说清楚，才知道算法究竟要解决什么。

一组叫东、南、西、北，另一组叫春、夏、秋、冬。每行从左到右，表示第1到第4选择，没有并列，每个人也都列出另一组的全部成员。

这里已经藏着一个小麻烦：东最喜欢夏，夏最喜欢西，西最喜欢春；春又最喜欢北，北最喜欢冬，冬最喜欢南，南最喜欢春。秋的第一选择也是北。没有任何两个人互为第一选择，所有人同时如愿从一开始就办不到。

1962年，Gale与Shapley发表《大学录取与婚姻的稳定性》，给出后来常称为延迟接受的办法。^[1]

关键在“暂留”。先答应，并不锁死后面的选择；如果收到更喜欢的邀请，可以更新暂留对象。反过来，提议者不会反复找同一个已经拒绝自己的人。

第一轮，东找夏，南与西都找春，北找冬。春比较南与西，留下排名更靠前的西，拒绝南。接下来就出现一串连锁反应。

最后是东—春、南—夏、西—秋、北—冬。东、南、西都拿到自己的第2选择，北拿到第1选择。这一轮共发生7次提议。

名单不变，重新开始。春找北，夏找西，秋也找北，冬找南。北更喜欢春，拒绝秋。

第二轮，秋找第2选择南；南已经暂留冬，又把冬排在秋前面，所以仍拒绝秋。第三轮，秋找到东，才被暂留。

最后变为东—秋、南—冬、西—夏、北—春。这次有6次提议，结局与前一次不同。

把每个人的结果与其名单名次放在一起，差别会比“看起来谁开心”清楚得多。

第一套里，东当然想找自己的第1选择夏，可夏把现任南排在东前面，因此不会与东组成阻挡对。第二套里，情况也一样：东更想找夏，夏却更喜欢现任西。

按完整名单检查所有没有配在一起的组合，两套都不存在阻挡对。在这份四对人的例子里，枚举24种完整匹配，恰好只有这两种稳定结果。

算法也解释了为什么能稳定。若一个提议者最后仍更喜欢另一位接收者，他在轮到当前搭档以前必然已向那人提议，并遭到拒绝。接收者往后只会换成更喜欢的人，因此最终不会又愿意回头与他共同离开现任。

提议者被拒以后，名次只能往后走；接收者更新暂留对象，名次却只会向前走。看过程，好像等待更占便宜，定理给出的比较却很有意思。

在经典的一对一、人数相同、偏好完整且严格的模型中，提议方每个人得到的，是他在所有稳定匹配中能得到的最好对象；接收方每个人得到的，则是自己在所有稳定匹配中相对最差的对象。

这不表示提议者一定拿到全体第1选择。东在第一套里仍只拿到春，但在这份名单允许的稳定结果中，春已经比另一套的秋更好。

背后还有一个重要性质：在这套算法运行时拒绝过某位提议者的接收者，不可能与他出现在任何稳定匹配里。因此，继续往下找，没有丢掉一个原本能够得到的稳定对象。

每人至多向另一组的n个人各提议一次，总提议次数不超过n²，过程会结束。在这里改变结果的，是哪一组负责提议；固定提议方与严格名单后，调换该组内部的处理先后，不会改变提议方最优的稳定结果。

这套思想可以进入住院医师与医院、学生与学校等分配问题。2012年，Shapley与Roth因稳定分配理论及市场设计实践的相关贡献获得诺贝尔经济学奖。1962年论文的另一位作者Gale已于2008年去世。^[2]

真实分配会多出名额、不完整名单、并列偏好、夫妻共同申请等条件，规则需要据此设计，不能把四对人的定理直接照搬到所有市场。

现实关系里的心意也会变化，人们会沟通、退出，或重新认识自己的偏好。数学里的“稳定”，负责的是排除给定名单中的共同改配动机；生活里想要怎样的关系，还包含这份名单没有替人决定的内容。