医生匹配问题

有一家医院有n个医生和n个病人需要配对。每个医生都有一个病人偏好列表，表示他更愿意治疗哪些病人；每个病人也有一个医生偏好列表，表示他更愿意被哪些医生治疗。医院的目标是找到一种病人和医生都满意的稳定的匹配方式。
例如，假设有三个医生D1、D2、D3和三个病人P1、P2、P3，他们的偏好列表如下：

  • 医生偏好列表：

    • D1: P2 > P1 > P3
    • D2: P3 > P2 > P1
    • D3: P1 > P3 > P2

  • 病人偏好列表：

    • P1: D1 > D2 > D3
    • P2: D1 > D2 > D3
    • P3: D2 > D1 > D3

我们要如何找到一种“稳定”的匹配方式呢？这取决于我们如何定义“稳定”这个概念。我们可以尽量满足病人的偏好，或者尽可能使双方整体满意度更高。比如，我们尽量满足病人的偏好得到匹配{(D1, P1), (D2, P2), (D3, P3)}。然而，这种匹配并不稳定，因为D1和P2相对当前匹配对象更喜欢对方，他们可能会选择离开当前的配对关系“私奔”。因此，这种匹配方式并不理想。
受上面的讨论启发，我们可以定义“稳定匹配”这一概念。

定义 流氓对：如果存在一对医生和病人(D, P)，使得D更喜欢P而不是当前匹配的病人，同时P也更喜欢D而不是当前匹配的医生，那么我们称这对(D, P)为流氓对。
定义 稳定匹配：如果一种匹配不存在任何流氓对，那么我们称这种匹配为稳定匹配。

Gale-Shapley算法

Gale-Shapley算法是一种用于解决稳定匹配问题的经典算法。该算法的基本思想是让一方（例如医生）主动提出配对请求，而另一方（例如病人）则根据自己的偏好列表选择接受或拒绝请求。具体步骤如下：

  1. 初始化：所有医生和病人都处于未匹配状态。
  2. 医生提出请求：每个未匹配的医生向他偏好列表中排名最高且尚未提出请求的病人提出配对请求。
  3. 病人回应请求：每个病人收到医生的请求后，根据自己的偏好列表选择暂时接受最喜欢的医生的请求，并拒绝其他医生的请求。如果病人已经匹配了一个医生，但收到一个更喜欢的医生的请求，则她会拒绝当前的医生并暂时接受新的请求。
  4. 重复步骤2和3，直到所有医生都被匹配为止。这时，所有暂时接受的配对关系即为最终的稳定匹配。

对于上面的例子，如果让医生主动提出请求，Gale-Shapley算法的执行过程如下：

  • 第一次迭代：
    • D1向P2提出请求，D2向P3提出请求，D3向P1提出请求。
    • P1接受D3的请求，P2接受D1的请求，P3接受D2的请求。
    • 当前匹配：{(D1, P2), (D2, P3), (D3, P1)}
    • 所有医生都已匹配，算法结束。

最终的稳定匹配为{(D1, P2), (D2, P3), (D3, P1)}。
但如果让病人主动提出请求，得到的稳定匹配可能不同。例如：

  • 第一次迭代：
    • P1向D1提出请求，P2向D1提出请求，P3向D2提出请求。
    • D1接受P1的请求，拒绝P2的请求，D2接受P3的请求。
    • 当前匹配：{(D1, P1), (D2, P3)}
    • P2未匹配，继续下一轮。
  • 第二次迭代：
    • P2向D2提出请求。
    • D2拒绝P2的请求，因为她已经匹配了P3，而且更喜欢P3。
    • P2继续向下一个医生提出请求，即D3。
    • D3接受P2的请求。
    • 当前匹配：{(D1, P1), (D2, P3), (D3, P2)}
    • 所有病人都已匹配，算法结束。

最终的稳定匹配为{(D1, P1), (D2, P3), (D3, P2)}。
可以看到，不同的主动方会导致不同的稳定匹配结果。Gale-Shapley算法保证了无论哪一方主动提出请求，最终都能得到一个稳定的匹配结果。

算法分析

终结性

这一点很容易证明。每次迭代中，至少有一个医生向一个病人提出请求，而每个医生最多只能向n个病人提出请求，因此算法最多进行n^2次迭代，必然在有限步内终止。

存在性

在分析算法的稳定性之前，我们先要证明为什么这种稳定匹配必然存在。我们观察到，在每一次迭代的过程中，医生的选择在逐渐变差，而病人的选择在逐渐变好。具体来说：

改进定理 如果医生D在第k次迭代中向病人P提出请求，那么在接下来的每一天，P能接受的医生的排名不会低于D在P的偏好列表中的排名。

证明：使用数学归纳法。设迭代次数为i，i >= k。

  • 基础情况：当i = k时，D向P提出请求，P接受了D的请求，因此P能接受的医生的排名至少是D的排名。
  • 归纳假设：假设对于某个i >= k，P能接受的医生的排名至少是D的排名。
  • 归纳步骤：在第i + 1次迭代中，如果P收到一个新的医生请求，P会根据自己的偏好列表选择接受排名更高的医生。因此，P能接受的医生的排名不会低于D的排名。
  • 结论：根据数学归纳法，改进定理成立。

存在定理 Gale-Shapley算法总能找到一个匹配。

证明：使用反证法。设医生和病人数为n。假设算法结束时存在一个未匹配的医生D，那么他在迭代中已经向所有病人提出了总共n个请求，但都被拒绝了。根据改进定理，所有病人都接受了比D更喜欢的医生的请求，这样，当算法结束时，所有医生除了D之外都已经匹配了病人，因此医生总数应为n+1，矛盾。因此，算法总能找到一个匹配。

稳定性

稳定性定理 Gale-Shapley算法找到的匹配是稳定匹配。

证明：使用反证法。假设最终的匹配结果中存在一个流氓对(D, P)，即医生D更喜欢病人P而不是当前匹配的病人，同时病人P也更喜欢医生D而不是当前匹配的医生。不妨设D当前匹配的病人为P'，P当前匹配的医生为D'。有以下两点：

  1. 由于D更喜欢P而不是P'，根据Gale-Shapley算法的执行过程，D在某次迭代中向P提出了请求。
  2. 由于P更喜欢D而不是D'，根据Gale-Shapley算法的执行过程，P在收到D的请求时应该接受了D的请求，而不是当前匹配的医生D'。

这就导致了矛盾，因为P不可能同时接受D和D'的请求。因此，假设不成立，Gale-Shapley算法找到的匹配是稳定匹配。

综上，我们证明了Gale-Shapley算法能够在有限步内终止，并且总能找到一个稳定匹配。然而，我们还没解决另一个问题：这种稳定匹配是否唯一？如果不唯一，我们应当如何选择？

最优性

从上面的例子中可以看出，不同的主动方会导致不同的稳定匹配结果。那么，Gale-Shapley算法找到的稳定匹配是否具有某种最优性呢？答案是肯定的。
Gale-Shapley算法不仅能找到一个稳定匹配，而且还能保证对于主动提出请求的一方来说，所得到的稳定匹配是最优的。具体来说：

定义 最优稳定匹配：对于一方（例如医生）来说，如果在所有可能的稳定匹配中，他们所得到的匹配是他们偏好列表中排名最高的，那么我们称这种匹配为最优稳定匹配。
定义 最差稳定匹配：对于另一方（例如病人）来说，如果在所有可能的稳定匹配中，他们所得到的匹配是他们偏好列表中排名最低的，那么我们称这种匹配为最差稳定匹配。
最优性定理 在Gale-Shapley算法中，主动提出请求的一方（例如医生）所得到的稳定匹配是对他们来说的最优稳定匹配。

证明：使用反证法。假设存在另一种稳定匹配M'，使得某个医生D在M'中的匹配病人P'比在Gale-Shapley算法中得到的匹配病人P更好。根据Gale-Shapley算法的执行过程，D在某次迭代中向P'提出了请求，但被拒绝了。这意味着P'在收到D的请求时已经接受了另一个医生D'的请求，而根据稳定匹配的定义，P'更喜欢D'而不是D。因此，医生D'和病人P'构成了一个流氓对，这与假设的稳定匹配矛盾。因此，假设不成立，Gale-Shapley算法中主动提出请求的一方所得到的稳定匹配是最优稳定匹配。

另证：采用数学归纳法。设命题P(k)=“在前k次迭代中，所有提出请求的医生都得到了他们偏好列表中排名最高的病人”。我们需要证明对于任意k，命题P(k)成立。

  • 基础情况：当k=1时，所有医生都向他们偏好列表中排名最高的病人提出请求，因此命题P(1)成立。
  • 归纳假设：假设对于某个k >= 1，命题P(k)成立。
  • 归纳步骤：假设在k + 1次迭代中，第一次存在医生D向其最优病人P提出的请求被拒绝了，原因是P接受了另一个排名更高的医生D'的请求。根据最优稳定匹配的定义，对于P来说，D'比D更优，同时也必然存在一个稳定匹配，使得(D, P),(D', P')是其中的一对匹配关系。由于是第一次存在医生D的请求被拒绝，因此前k次迭代中，医生D'的请求尚未被拒绝过；同时在第k天，医生D'向P提出了请求，也就是说在D'的偏好中，P的排名不低于其最优病人的排名，也不低于P'的排名，因此D'更喜欢P而不是P'。同时，P更喜欢D'而不是D，因为P为了D'拒绝了D。因此，(D', P)构成了一个流氓对，这与稳定匹配的定义矛盾。因此，假设不成立，命题P(k + 1)成立。
  • 结论：根据数学归纳法，命题P(k)对于任意k成立。因此，Gale-Shapley算法中主动提出请求的一方所得到的稳定匹配是最优稳定匹配。

但是，对于被动接受请求的一方（例如病人）来说，所得到的稳定匹配并不一定是最优的。实际上，这种匹配可能是对他们来说最差的稳定匹配。

最差性定理 在Gale-Shapley算法中，被动接受请求的一方（例如病人）所得到的稳定匹配是对他们来说的最差稳定匹配。

证明：采用反证法。假设存在另一种稳定匹配M'，使得某个病人P在M'中的匹配医生D'比在Gale-Shapley算法中得到的匹配医生D更好。根据Gale-Shapley算法的执行过程，医生D'在某次迭代中向P提出了请求，而P拒绝了这个请求，选择了另一个医生D。这意味着在稳定匹配M'中，医生D和病人P构成了一个流氓对，这与假设的稳定匹配矛盾。因此，假设不成立，Gale-Shapley算法中被动接受请求的一方所得到的稳定匹配是最差匹配。

练习：

  • 考虑一种情况：如果存在一些医生或者病人宁可不匹配也不要和不喜欢的人匹配呢？如何定义“稳定匹配”？如何证明Gale-Shapley算法仍然能找到稳定匹配？

2026年2月6日。