首页study计算机科学CS70离散数学
  • 这一节我们将用之前的知识用于解决一些实际的问题。

# 稳定匹配问题(The Stable Matching Problem，亦称为stable marriage problem)

# 问题描述

  • 现在有nn名男性与nn名女性需要互相匹配
  • 已知：
    • 每位男性根据对所有女性的心仪程度从高至低进行排名；
    • 每位女性根据对所有男性的心仪程度从高至低进行排名。
  • 由此，我们需要找到一个最佳匹配（即尽量让每一位男性与女性互相找到最心仪的对象）
  • 当然，稳定匹配问题也不局限于男女匹配，在现实中也有实习生与公司的匹配，学生与学校的匹配等。

# 提议-拒绝算法(亦称Gale–Shapley算法，The Propose-and-Reject Algorithm)

  • 为了形象化地表示这个算法，我们举一个例子：
  • 假设有4位男性(编号1,2,3,41,2,3,4)和4位女性(编号A,B,C,DA,B,C,D)，他们各自的心仪排名如下：
    • 11：A≻B≻C≻DA\succ B \succ C\succ D
    • 22：B≻A≻C≻DB\succ A \succ C\succ D
    • 33：B≻C≻A≻DB\succ C \succ A\succ D
    • 44：B≻A≻D≻CB\succ A \succ D\succ C
    • AA：4≻2≻3≻14\succ 2 \succ 3\succ 1
    • BB：2≻1≻3≻42\succ 1 \succ 3\succ 4
    • CC：1≻2≻3≻41\succ 2 \succ 3\succ 4
    • DD：4≻1≻2≻34\succ 1 \succ 2\succ 3
  • 现在进行匹配：
    • 首先，让四位女性站在四个固定的地方，让四位男性根据自己心仪排名的第一位进行配对：
AA BB CC DD
11 2,3,42,3,4
  • 接着，对于每位有候选男性的女性，根据自己的心仪排名，在候选男性中选择一位作为暂定匹配者，而拒绝其他所有男性；
AA BB CC DD
11 22,33,44
  • 然后，被淘汰的所有男性将被拒绝的女性从心仪排名中划去，再继续找排名往后一位的女性；
  • 由此循环，直到每个男性都找到匹配的女性：
    • 第二轮后：
    AA BB CC DD
    11,44 22 33
    • 第三轮后：
    AA BB CC DD
    44 22,11 33
    • 第四轮后：
    AA BB CC DD
    44 22 33,11
    • 第五轮后：
    AA BB CC DD
    44,33 22 11
    • 最终结果：
    AA BB CC DD
    44 22 11 33
  • 事实上，这个算法提出者之一Shapley也获得了2012年诺贝尔经济学奖（Gale没获奖是因为当时他已经去世了...）
  • 那么，这个算法到底有什么用呢？（也就是说，它能够解决什么样的问题？）

# 现实的例子：住院医师匹配(The Residency match)

  • 参考：NRMP the MATCH
  • 简单来说，美国大约在100年前开始施行住院医师培训项目，但由于住院实习岗位供大于求，所以各个医院开始越来越早地给医学生发offer；而后美国医学协会(American Medical Association)介入，限制医学院不能提供大四以前学生的信息。
  • 然而这造成了更混乱的结果——各大医院为了招到足够的住院实习生，开始给医学生发放超短期offer（有时甚至只有几个小时）
  • 为解决这一问题，在上世纪50年代，美国医学协会国家发动住院医师匹配项目(NRMP)，让医院与医师互相排名，再相互匹配。最终用到的算法就是Gale-Shapley算法。

# 提议-拒绝算法的性质

# 提议-拒绝算法是有穷的

  • 证明（还是以上面的男女配对为例）：
    • 因为在经过一轮配对后，男性的心仪排名表中至少会有一位女性被划去，所以最多经过n2+1n^2+1轮循环，配对一定会终止。

# 提议-拒绝算法是“好”的

  • 首先，我们得定义怎样才算是“好”。从问题出发，我们认为“稳定”是衡量算法好坏的标准。这里的“稳定”是指：
    • 对于任意一对非配对的男女，他们不会觉得彼此互相选择会更好（即对彼此的排名都没有现有伴侣的高）
    • 如果出现互相选择会更好的一对男女，就把他们称为 异常配对(rogue couple)。
    • 当然配对的男女可能对彼此的排名都比较靠后，要是他们更心仪的对象都有了更好的选择
  • 那么，经过上述算法后的稳定匹配一定存在吗？
    • 表面上似乎确实存在，只要将异常配对都重新配对上不就行了……吗？并不！
      • 因为配对一对异常配对后，可能会产生更多的异常配对，导致陷入死循环。
    • 不过，对于上述男女配对的问题，确实存在稳定的配对，而根本原因在于男性和女性这两种类型（即待分类的对象必须属于两个不同的类型）
  • 下面我们会进行更加严谨的证明。

# 对提议-拒绝算法的分析

  • 经过观察我们发现，在上述男女配对中，男性的选择总是越来越糟的（排名越来越后），而女性的选择总是越来越好的（排名越来越前）
  1. 改进引理(Improvement Lemma) ： 如果男性JJ在第kk天向女性CC求婚，那么在之后的每一天CC都至少有一个和JJ一样好的暂留选择。
    • 可以使用归纳法证明（过程略，因为比较直接）
  2. 基于上述引理，我们就可以对以下引理进行证明：提议-拒绝算法总能做到互相匹配。
    • 证明过程：
      • 假设提议-拒绝算法结束后，有男性JJ未配对，那么也就是说他向所有nn个女性求婚但都被拒绝了；
      • 由改进引理，这nn个女性既然拒绝了JJ，就说明她们都至少各自有一个比JJ更好的选择；
      • 那么这nn个女性就有nn个比JJ更好的男性和她们配对，也就是至少有n+1n+1位男性，这就推出了矛盾。
  3. 最终定理：由提议-拒绝算法得到的匹配是稳定的。
    • 我们可以直接证明，在提议-拒绝算法得到的结果中，没有男性会在异常配对里。
    • 假设在结果中的一个配对(J,C)(J,C)，其中JJ对C∗C^*的喜好程度高于CC；
    • 那么因为C∗C^*在JJ的心仪排名中靠在CC之前，所以JJ一定先选择了C∗C^*；
    • 但是由结果可知JJ被拒绝了，再由改进引理可知，C∗C^*已经有了比JJ更好的选择；
    • 所以C∗C^*不会舍弃结果分配的对象而选择JJ，所以(J,C∗)(J,C^*)不是一个异常配对；
    • 因为所有男性都不在异常配对里，所以最终得到的匹配就是稳定的。

# 最优化

  • 让我们重新思考一下由提议-拒绝算法得到的匹配结果——它到底让谁的选择最优？有时在同一条件下会产生多种稳定的配对方案，那么对每个配对者而言，哪种方案对他们是最优的呢？
  • 先对每个女性的最优配对选择进行定义：对于一个给定的女性CC而言，她的最优配对选择是所有稳定配对方案中CC的配对者之中排名最高的哪位男性。
    • 然后可以定义 基于女性的最优配对方案 ：在此方案中，每个女性的配对选择都是最优的。
  • 类似的，我们也可以对每个男性的最优配对选择以及基于男性的最优配对方案进行定义，就不赘述了。
  • 当然，我们同样可以定义男性/女性的最劣配对选择与方案。
  • 有了这些定义，我们就可以得到一个重要结论：
    • 由提议-拒绝算法得到的配对方案是基于男性的最优配对方案，也是基于女性的最劣配对方案。
  • 下面对这个命题进行证明：
    • 先证明“ 由提议-拒绝算法得到的配对方案是基于男性的最优配对方案 ”：
      • 假设提议-拒绝算法得到的配对方案不是是基于男性的最优配对方案，那么就存在若干轮配对，在这些配对中，一些男性被他的最优配对选择拒绝了。
      • 设kk为其中最早的一轮，在这一轮中，男性JJ被他的最优配对选择C∗C^*拒绝了，而C∗C^*选择了J∗J^*为暂留对象。
      • 根据最优配对选择的定义，一定存在一个配对方案，其中JJ与C∗C^*配对，而J∗J^*与其他女性配对。
      • 下面我们证明J∗J^*与C∗C^*是异常配对：
      • 首先，能够确定C∗C^*的心仪列表中J∗J^*的排名比JJ更高；另外，由于kk是最早的一轮，所以在第kk轮之前，J∗J^*并没有被他的最优配对选择拒绝（即还没找到最优配对选择）；
      • 那么既然在第kk轮J∗J^*向C∗C^*求婚，那么C∗C^*在J∗J^*心仪列表中的排名就至少在他的最优配对选择之上。
      • 所以J∗J^*和C∗C^*就是异常配对，那么得到的配对方案就是不稳定的，推得矛盾。
    • 所以提议-拒绝算法得到的配对方案是基于男性的最优配对方案。
    • 再证明“ 由提议-拒绝算法得到的配对方案是基于女性的最劣配对方案 ”：
      • 假设提议-拒绝算法得到的配对方案不是是基于女性的最劣配对方案，并假定方案中JJ与CC配对。
      • 那么就存在另一个配对方案，其中J∗J^*与CC配对，而JJ与C′C'配对，其中J∗J^*在CC的心仪列表中排名比JJ低。
      • 那么CC就更喜欢JJ，而JJ在CC和C′C'中也更喜欢CC，因为在基于男性的最优配对方案中他与CC配对。
      • 那么JJ与CC就是另一个配对方案的异常配对，得到矛盾。
    • 所以提议-拒绝算法得到的配对方案是基于女性的最劣配对方案。
  • 证明完成。
  • 这个结论同时也告诉我们，这个算法的决定权还是掌握在男性（第一步做出选择）的一方。

# 参考文献和书籍

D. Gale and L.S. Shapley, “College Admissions and the Stability of Marriage,” American Mathematical
Monthly 69 (1962), pp. 9–14
D. Gusfield and R.W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989.