一、一次实习分配

你、同事小周和小林是三个实习生,要被分到三家公司 A、B、C,每家公司只有一个名额。

每个人都有自己对公司的排序,每家公司也有自己对实习生的排序:

学生 第一志愿 第二志愿 第三志愿
你 A B C
小周 A C B
小林 A B C
公司 最想要 其次 最不想要
A 小林 你 小周
B 你 小周 小林
C 小周 小林 你

现在要给每个学生分配一家公司。这里没有价格,也不能用钱来调节,只有两边的排序。

先别往下读。请你想一想:如果分成 (你—C,小周—B,小林—A),会出什么问题?

我们来看。你分到 C(你的第三志愿),可是你更想去 B;而 B 呢?B 分到的是小周,B 的排序里,你排在小周前面。所以你和 B 都觉得:如果我们俩直接配对,都比现在好。 你们会私下撇开分配,自己配对。

这样的一对(一个学生和一家公司,互相更想要对方,而不是现在的配对),叫阻塞对。(这里还有第二个阻塞对:小周更想去 C,而 C 更想要小周,不想要现在的你。)

一个分配,如果没有任何阻塞对,就叫稳定的。 稳定,意思是:没有人有动力私下推翻它。

这和分钱不同:这里没有"钱"这个共同的度量,只有排序。

二、延迟接受算法

怎么找一个稳定的分配?Gale 和 Shapley 1962 年给出了一个很简单的办法,叫延迟接受(deferred acceptance)。

规则是这样的(这里让学生"求",公司"挑"):

每一轮:每个还没有被留下的学生,向自己名单上最靠前、还没求过的公司求一次。每家公司,把手里所有的求者(包括上一轮暂时留下的那位)放在一起,只暂时留下自己最想要的那一位,拒绝其他人。被拒绝的学生,下一轮求下一个志愿。直到没有人被拒绝为止。

注意"暂时留下":公司没有立刻答应,只是先把最好的留在手里,如果后面来了更好的,可以换掉。这就是"延迟"。

我们用上面的例子走一遍:

  • 第 1 轮:你、小周、小林,三个人的第一志愿都是 A,三个人都向 A 求。A 最想要小林,留下小林,拒绝你和小周。
  • 第 2 轮:你被拒了,求第二志愿 B;小周被拒了,求第二志愿 C。B 只有你一个求者,留下;C 只有小周一个求者,留下。
  • 没有人再被拒绝。结束。

结果:小林—A,你—B,小周—C。

延迟接受:学生一轮一轮地求,公司先"暂时留着"最好的

这个分配稳定吗?我们检查:小林分到了第一志愿,没有动力。你分到 B(第二志愿),你更想去 A,可是 A 更想要小林,不想要你,不构成阻塞。小周分到 C(第二志愿),更想去 A,可是 A 最不想要小周,也不构成阻塞。没有阻塞对。 稳定。(我还用程序把这三个学生所有 6 种分法都检验了一遍:这个例子里,稳定的分法只有这一个。)

为什么算法的结果一定是稳定的

一个简单的论证:假设最后有一个阻塞对(学生 s 和公司 c),也就是 s 更喜欢 c,胜过现在的分配,而 c 更喜欢 s,胜过现在的分配。

  • s 更喜欢 c,而算法里 s 是按志愿顺序求的,所以 s 一定早就向 c 求过,并且被拒绝了(或者后来被换掉了)。
  • 被 c 拒绝,说明当时 c 手里有一个比 s 更好的人。
  • 而公司手里"暂时留下"的人,只会越换越好,不会变差。所以 c 最后得到的人,一定也比 s 好。
  • 这就和"c 更喜欢 s,胜过现在的分配"矛盾。

所以,不存在阻塞对。算法一定会结束,也一定稳定。

⚠️ 这里第一次读会觉得别扭。 你会想:被拒绝的学生,最后会不会没有地方去?

在我们的小例子里,每个学生都列了所有公司,人数和名额一样多,每个人最后都有一家。更一般的情形(人数和名额不一样多,或者有人不愿去某些公司),算法一样适用,只是有的人会留下来"没配上";Gale 和 Shapley 的原文,讲的就是大学录取:每所学校有多个名额。

三、不止一个稳定分配

上面的例子里,稳定的分法只有一个。换一组偏好,会出现多个。

学生的排序:

  • 你:A、B、C;小周:B、C、A;小林:C、A、B。

公司的排序:

  • A:小周、小林、你;B:小林、你、小周;C:你、小周、小林。

这时有 三个稳定的分配(我用程序把 6 种分法都检验过):

  1. 你—A,小周—B,小林—C。 每个学生都拿到第一志愿;公司呢?A 得到的是它的第三选择(你),B 得到的也是第三选择(小周),C 得到的也是第三选择(小林)。
  2. 你—B,小周—C,小林—A。 每个人都是第二志愿,每家公司也是第二选择。
  3. 你—C,小周—A,小林—B。 每个学生都是第三志愿;每家公司都拿到第一选择。

同一组偏好,三种稳定的分法:一方好,另一方就差

学生"求"的算法,得到的是第 1 个(学生最满意的稳定分配)。把角色对调,让公司来"求",得到的是第 3 个(公司最满意的)。

这是 Gale 和 Shapley 证明的一个结论:“求"的一方,在所有稳定的分配里,得到的是对自己最好的那个。 也就是说,稳定并不等于公平,谁先提出,谁占便宜。

我们可以用一个比喻来记它:延迟接受像一场"先到先得"的舞会邀请。 主动邀请的一方,每一轮都先问自己最想邀请的人;被邀请的一方只能挑选、留下最好的。结果主动邀请的一方,整体上总是更满意。

四、说真话还是耍心眼

延迟接受算法有一个很好的性质:对"求"的一方,说真话是最好的。 也就是说,学生如实列出自己的排序,比任何谎报都不差。(Dubins 和 Freedman 1981 年,Roth 1982 年证明了这一点,据二手转述。)

我们在第一个例子里验证一个谎报:你谎报成 B、A、C(把 B 放第一)。

  • 第 1 轮:你向 B 求,小周、小林向 A 求。A 留下小林,拒绝小周。
  • 第 2 轮:小周求 C,留下。

结果:你—B。和说真话得到的一样(也是 B)。没有得到更好的。

但是,被"求"的一方(公司)谎报,有可能得到更好的结果。 看一个例子。

学生:你 B、C、A;小周 B、A、C;小林 A、B、C。公司:A:小周、你、小林;B:小林、小周、你;C:小林、你、小周。

如果大家都说真话,学生求婚:第 1 轮,你和小周都求 B,小林求 A。B 更想要小周(比你好),留下小周,拒绝你;你第 2 轮求 C。结果:小周—B,小林—A,你—C。(B 得到的是它的第二选择。)

如果 B 谎报成"小林、你、小周”(把你放到小周前面):第 1 轮,B 在你和小周之间,选了你,拒绝小周。第 2 轮,小周求 A;A 更想要小周,留下小周,拒绝小林。第 3 轮,小林求 B;B 更想要小林,留下小林,拒绝你。第 4 轮,你求 C。结果:小林—B,小周—A,你—C。 B 得到了它真正的第一选择小林。

所以,对被求的一方,说真话并不总是最好的。延迟接受并不是对所有人都防操纵。

五、学校选择:为什么波士顿换了办法

匹配的想法,不只用在婚姻和实习上。学校选择是另一个重要的用途:每个孩子填报志愿,每所学校按规则(比如住得近、有兄弟姐妹在校)给孩子排序。

美国的波士顿,曾经长期使用一种办法,叫波士顿机制(也叫"即时接受"):

第一轮:每个孩子先去自己的第一志愿。学校名额不够时,按学校的排序留下优先的孩子。这一轮分到的,当场就是最终结果,不会再被换掉。 没分到的孩子,进入第二轮,在剩下的名额里,按第二志愿再来一次……

关键区别是:第一轮分到的,是最终的、不会被换掉。 所以,如果你的第一志愿很抢手,你填它,可能什么都得不到,而你的第二、第三志愿,早被别人的第一志愿占满了。

看一个例子(三个学生,三所学校,每所一个名额):

  • 学生:你 A、B、C;小周 A、B、C;小林 B、A、C。
  • 学校的排序:A:小周、你、小林;B:你、小林、小周;C:你、小周、小林。

波士顿机制,你说真话:第 1 轮,你和小周都填 A,小林填 B。A 更想要小周,当场分给小周;B 只有小林,分给小林。你被留下,只剩 C,你分到 C(最差的)。

波士顿机制,你谎报成"B、A、C"(把 B 放第一):第 1 轮,你和小林都填 B,B 更想要你,分给你;小周分到 A;小林被拒,只剩 C。你分到 B。 你耍了心眼,从 C 变成 B。而说真话的小林,因此从 B 掉到了 C,吃了亏。

延迟接受,你说真话:第 1 轮,你和小周求 A,小林求 B。A 暂时留下小周,拒绝你;B 暂时留下小林。第 2 轮,你求 B;B 比较你和小林,更想要你,留下你,拒绝小林;小林第 3 轮求 A,A 比较小周和小林,更想要小周,拒绝小林;第 4 轮,小林求 C。结果:小周—A,你—B,小林—C。 你说真话就拿到了 B,不需要谎报。

Abdulkadiroğlu 和 Sönmez 2003 年把学校选择当作一个机制设计的问题来分析(美国 American Economic Review,93 卷 3 期,729–747 页),分析了波士顿等地的办法。2005 年,波士顿学校委员会投票,改用延迟接受机制,理由之一就是它简化了家长的策略选择:家长不用再为"怎么填才不吃亏"费脑筋。(据二手转述。)

六、不用钱的交换:首选交易环

还有一种匹配,不是"两边配对",而是一群人,每人手里有一件东西,想互相换,比如换房子,或者换肾。没有钱,只有每个人对东西的排序。

Shapley 和 Scarf 1974 年的"首选交易环"(top trading cycles)办法是这样的:

每个人指向自己最想要的东西的主人。大家的指向里,一定会有一个环(可能是自己指自己)。环里的人,按指向互相交换,然后离场。剩下的人,重复。

我们看一个例子:你有房子 a,小周有 b,小林有 c。排序:你 b、c、a;小周 c、a、b;小林 b、a、c。

  • 第 1 轮:你指向小周(想要 b),小周指向小林(想要 c),小林指向小周(想要 b)。小周和小林互相指向,成环:小周拿到 c,小林拿到 b,两人离场。
  • 第 2 轮:只剩你。b、c 都不在了,你只能要自己的 a。你留着 a。

结果:小周得到 c(第一志愿),小林得到 b(第一志愿),你保留了 a。

肾脏交换里,用到类似的想法(Roth、Sönmez 和 Ünver 2004 年,QJE 119 卷 2 期,457–488 页,据文献目录)。大意是:病人和愿意捐肾、但血型不匹配的亲属,组成一"对";环里的每一对,给下一对的病人捐肾,所有人都得到一个匹配的肾。

七、证据:现实里在用

理论预测。 延迟接受得到稳定的分配,求的一方最占便宜,对求的一方说真话最优;波士顿机制鼓励谎报。

证据。

  • 理论的出处。 Gale 和 Shapley 1962 年在《美国数学月刊》(American Mathematical Monthly,69 卷 1 期,9–15 页):《大学录取与婚姻的稳定》。
  • 医学生分配。 Roth 1984 年在《政治经济学杂志》(Journal of Political Economy,92 卷 6 期,991–1016 页)研究了美国医学实习生的分配市场的演变,发现当时使用的清算办法,和 Gale–Shapley 算法密切相关(据二手转述)。Roth 和 Peranson 1999 年在《美国经济评论》(89 卷 4 期,748–780 页)讲了为美国医生匹配市场重新设计的工程问题。
  • 学校选择。 Abdulkadiroğlu 和 Sönmez 2003 年(见上节),以及 2005 年波士顿的改变(据二手转述,一篇工作稿说,这个转变与"诚实的家长在波士顿机制下吃亏"这个论证有关)。
  • 诺贝尔奖。 2012 年的诺贝尔经济学奖,授予了 Shapley 和 Roth,表彰稳定分配的理论和市场设计的实践。

局限。 稳定只看排序,不看"差多少":一个人觉得第一志愿远远好于第二,和觉得差不多,在算法里没有区别。真实的匹配里,有名额的限制、夫妻一起找工作、孩子的兄弟姐妹优先等复杂规则。

分歧。 稳定是不是最该追求的目标,是价值判断。有人更看重"总体满意度最高",有人看重"弱势孩子的机会",有人看重"防止操纵"。不同目标,会推荐不同的机制。事实层面的问题,是各种机制在现实中到底会带来怎样的分配,这需要数据。

八、常见的误用

  • “稳定的分配是公平的。” 不对。求的一方得到对自己最好的稳定分配,另一方得到最差的。
  • “稳定的分配只有一个。” 不一定。我们看到的第二个例子,有三个。
  • “延迟接受对所有人都防谎报。” 不对。对求的一方说真话最好;对被求的一方,谎报有时有利。
  • “排序里每个志愿的差距一样大。” 不一定。稳定匹配只用排序,不看差距。
  • “没有钱就没法有效率地分配。” 不对。首选交易环等机制,不用钱也能做出有效率的交换。

九、小结

  • 阻塞对:一个学生和一家公司,互相更想要对方,胜过现在的配对。稳定:没有阻塞对。
  • 延迟接受:学生一轮轮求,公司暂时留下最好的,拒绝其余。一定会结束,结果一定稳定。
  • 例子一:你—B,小周—C,小林—A,稳定,且是唯一的稳定分配。
  • 例子二:同一组偏好有三个稳定分配;谁"求",谁拿到对自己最好的那个,另一方拿到最差的。
  • 说真话:对求的一方,说真话最好;对被求的一方,谎报有时有利(B 的例子)。
  • 学校选择:波士顿机制第一轮分到的是最终的,鼓励谎报;延迟接受不用谎报。波士顿 2005 年改用延迟接受。
  • 首选交易环:每个人指向最想要的东西的主人,成环就换;不用钱,也能有效交换。
  • 证据:医生匹配、学校选择、肾脏交换;2012 年诺贝尔奖。

回到那三个实习生。下次你面对一个"没有价格,只有排序"的分配,请想一想:有没有一对人,私下配对会比现在更好?这个分配规则,是不是让每个人说真话最划算?谁"先求",对结果有多大影响?

思考题

  1. 第一个例子里,分配 (你—A,小周—C,小林—B)。它稳定吗?找出阻塞对。
  2. 第二个例子(三个稳定分配的那个),让公司来"求",用延迟接受算出结果。是三个里的哪一个?
  3. 波士顿机制的例子里,如果小周谎报(把 B 放第一),会怎样?小周能得到更好的结果吗?
  4. 第一个例子里,验证:你把志愿谎报成 B、A、C,在延迟接受下,你的结果是什么?是不是比说真话更好?
  5. 首选交易环:你有房子 a,小周有 b,小林有 c。排序:你 c、b、a;小周 c、a、b;小林 a、b、c。算出结果。
  6. 想一个生活里"有排序、没价格"的匹配(相亲、选课、宿舍分配……),说说现实里用的办法鼓励不鼓励说真话,可能出现哪种"耍心眼"。

思考题提示

  1. 小林分到 B,更想去 A,而 A 更想要小林胜过你,所以 (小林,A) 是阻塞对:小林和 A 都更想要对方。所以不稳定。(你分到 A,你自己满意。小周分到 C,更想去 A,但 A 不想要小周,不构成阻塞。)
  2. 公司求:A 求第一选择小周,B 求小林,C 求你。三家公司向三个不同的学生求,没有冲突,每个学生被一家公司求,暂时留下,一轮结束。结果:A—小周,B—小林,C—你,也就是 (你—C,小周—A,小林—B),是第 3 个(公司最满意的)。
  3. 小周的志愿原来是 A、B、C。若谎报成 B、A、C:第 1 轮,小周、小林求 B,你求 A。B 更想要小林胜过小周,分给小林;A 更想要你,分给你;小周被拒,第 2 轮小周分到 C,小周得到 C。而说真话时,小周得到 A。所以谎报更差。
  4. 你谎报成 B、A、C:第 1 轮,你求 B,小周、小林求 A。A 更想要小林,拒绝小周;第 2 轮,小周求 C,留下。结果:你—B,和说真话时一样(也是 B)。没有更好。
  5. 第 1 轮:你指向小林(想要 c),小周指向小林(想要 c),小林指向你(想要 a)。你和小林互相指向,成环:你拿到 c,小林拿到 a。第 2 轮:只剩小周,小周只能要自己的 b。结果:你得 c,小林得 a,小周保留 b。
  6. 开放题。例:选课系统。如果是"先到先得",大家会抢早点登录,谎报或者提前囤;如果是"按志愿排序、统一分配",要看排序的规则。如果系统规定"第一志愿未录取、第二志愿的名额也可能被占满",学生就会耍心眼:把一个保险的选项提前。