稳定匹配

引入

稳定匹配问题（stable matching problem）是组合优化和合作博弈论中的经典问题．相较于传统的图论匹配问题，稳定匹配引入了个体偏好和稳定性的限制，这使得算法设计更多地依赖于偏好顺序而非单纯的图结构．稳定匹配问题的模型中，每个个体对潜在的匹配对象具有偏好，而稳定匹配问题希望能在它们之间建立一种稳定的匹配关系．一个稳定的匹配中，不存在任何一组个体，会因为能得到更优的选择而合谋偏离当前的匹配结果．稳定匹配及其相关问题广泛地应用于劳动力市场、学校录取、医疗资源分配等场景中．

算法竞赛中最常出现的稳定匹配问题是双边市场的一对一匹配，即稳定婚姻问题．本文将重点介绍稳定婚姻问题及其算法．

稳定婚姻问题

稳定婚姻问题是最早研究的稳定匹配问题．类似于二分图匹配，它可以描述为婚恋市场上的匹配问题：假设有男士和女士若干，每个人都对异性有一组偏好顺序，目标是找到一种匹配方式，使得没有一对男女更愿意抛弃各自的匹配对象而选择彼此．

问题描述

匹配市场由若干男士 MM 和若干女士 WW 构成．每个人都对异性有严格的偏好顺序：

  • 对于每位男士 m∈Mm\in M，都存在集合 W∪{m}W\cup\{m\} 上一个严格的全序 ⪯m\preceq_m；
  • 对于每位女士 w∈Ww\in W，都存在集合 M∪{w}M\cup\{w\} 上一个严格的全序 ⪯w\preceq_w．

除了在异性之间相互比较之外，每个人还会将自身加入到这个偏好顺序中．这表示，这个人只会接受与排在自身前面的异性匹配；这些异性称为 可接受的（acceptable）．显然，不可接受的异性的偏好顺序是无足轻重的；原则上，只需要给出可接受的异性之间的偏好顺序即可．所以，这些存在不可接受异性的偏好也称为列表不完整的偏好（preferences with incomplete lists）．

例子

假设 mm 是一位男士，w1,w2,w3w_1,w_2,w_3 是三位女士，且有偏好关系 w1≺mm≺mw2≺mw3w_1\prec_m m \prec_m w_2\prec_m w_3 成立．那么，男士 mm 相对于和女士 w1w_1 匹配，更喜欢单身；相对于单身，更喜欢和女士 w2w_2 匹配；相对于和女士 w2w_2 匹配，更喜欢和女士 w3w_3 匹配．对于男士 mm，女士 w1w_1 就是不可接受的，女士 w2,w3w_2,w_3 就是可接受的．

市场上的一个 匹配 μ:M∪W→M∪W\mu:M\cup W\rightarrow M\cup W 需要满足如下性质：

  • 每个人只能匹配异性或其自身，即对所有 m∈Mm\in M 都有 μ(m)∈W∪{m}\mu(m)\in W\cup\{m\} 且对所有 w∈Ww\in W 都有 μ(w)∈W∪{w}\mu(w)\in W\cup\{w\}．
  • 匹配是相互的，即对所有 i∈M∪Wi\in M\cup W 都有 i=μ(μ(i))i = \mu(\mu(i))．

一个匹配 μ\mu 中可能存在两种不稳定因素：

  • 如果存在个体 i∈M∪Wi\in M\cup W 使得 μ(i)≺ii\mu(i)\prec_i i，也就是说，相对于当前的匹配对象，个体 ii 宁愿单身，那么，就称 ii 是匹配 μ\mu 的 阻塞个体（blocking individual）．
  • 如果存在一对异性 m∈Mm\in M 和 w∈Ww\in W 使得 μ(m)≺mw\mu(m)\prec_m w 且 μ(w)≺wm\mu(w)\prec_w m，也就是说，相对于当前各自的匹配对象，男士 mm 和女士 ww 更希望和对方在一起，那么，就称 (m,w)(m,w) 是匹配 μ\mu 的 阻塞对（blocking pair）．

如果一个匹配 μ\mu 既不存在阻塞个体，也不存在阻塞对，就称匹配 μ\mu 是 稳定的（stable）．稳定匹配中，所有人都无法破坏当前的局面：单身的人找不到愿意同他在一起的人；结婚的人既不愿意离婚单身，也找不到愿意同他私奔的人．

稳定匹配问题就是在问：对于任意给定的一组偏好顺序，是否都存在一个稳定匹配？如果是，如何求出这样的稳定匹配？

Gale–Shapley 算法

Gale 和 Shapley 在 1962 年提出了 延迟接受算法（deferred acceptance algorithm），可以对任意给定的一组偏好顺序求出一个稳定匹配．因此，稳定匹配一定是存在的．

Gale–Shapley 算法有两个对称的版本，分别由男士求婚和女士求婚．以男士求婚的 Gale–Shapley 算法为例，算法流程如下：

  1. 算法开始时，每位女士都视为保留着她对其自身的求婚请求，每位男士都标记为活跃的．
  2. 活跃的男士会向他可接受但是尚未求婚过的女士中最喜欢的那位求婚；如果这样的女士不存在，就无需进行任何操作．无论求婚与否，将所有男士都标记为不活跃的．
  3. 收到新的求婚请求的女士，会将他们与之前保留的求婚请求比较，只保留其中最喜欢的那一个（可能是她自身），并拒绝所有其他的求婚请求．将遭到拒绝的男士恢复标记为活跃的．
  4. 重复前两个步骤，直到没有活跃的男士为止．此时，女士接受她们当前保留的求婚请求．这样得到的匹配结果，就是一个稳定匹配．

由于每位男士向每位女士至多求婚一次，算法在 O(∣M∣∣W∣)O(|M||W|) 时间内一定会结束．

参考实现如下：

模板题 SPOJ STABLEMP - Stable Marriage Problem 参考实现 
#include <iostream>
#include <queue>
#include <vector>

// Solver for stable marriage problems.
// Assume strict preferences with incomplete lists.
struct StableMatching {
  int nx, ny;
  std::vector<std::vector<int>> pref_x,
      pref_y;  // Preferences: preferred first, only acceptable.
  std::vector<int> match_x, match_y;  // Matching: -1 means unmatched.

  StableMatching(int nx, int ny)
      : nx(nx),
        ny(ny),
        pref_x(nx),
        pref_y(ny),
        match_x(nx, -1),
        match_y(ny, -1) {}

  // Gale-Shapley algorithm.
  // Complexity: O(nx * ny).
  void solve() {
    // Compute Y's ranks over X.
    std::vector<std::vector<int>> ranks(ny, std::vector<int>(nx));
    for (int j = 0; j != ny; ++j) {
      for (int i = 0; i != pref_y[j].size(); ++i) {
        ranks[j][pref_y[j][i]] = nx - i;
      }
    }
    // Initialize.
    std::vector<int> waitlist(ny);  // Best proposal rank for j in Y.
    std::vector<int> ids(nx);       // Next j in Y for i in X to propose to.
    std::queue<int> q;              // Currently active i's in X.
    for (int i = 0; i != nx; ++i) q.push(i);
    // Loop.
    while (!q.empty()) {
      auto i = q.front();
      q.pop();
      auto j = pref_x[i][ids[i]++];
      if (ranks[j][i] > waitlist[j]) {
        if (waitlist[j]) q.push(pref_y[j][nx - waitlist[j]]);
        waitlist[j] = ranks[j][i];
      } else {
        q.push(i);
      }
    }
    // Output.
    for (int j = 0; j != ny; ++j) {
      if (waitlist[j]) {
        int i = pref_y[j][nx - waitlist[j]];
        match_x[i] = j;
        match_y[j] = i;
      }
    }
  }
};

void solve() {
  // Input.
  int n;
  std::cin >> n;
  StableMatching solver(n, n);
  for (int j = 0, x; j < n; ++j) {
    auto& cur = solver.pref_y[j];
    std::cin >> x;
    for (int i = 0; i < n; ++i) {
      std::cin >> x;
      cur.push_back(x - 1);
    }
  }
  for (int i = 0, y; i < n; ++i) {
    auto& cur = solver.pref_x[i];
    std::cin >> y;
    for (int j = 0; j < n; ++j) {
      std::cin >> y;
      cur.push_back(y - 1);
    }
  }
  // Solve the problem.
  solver.solve();
  // Output.
  for (int i = 0; i < n; ++i) {
    std::cout << (i + 1) << ' ' << (solver.match_x[i] + 1) << '\n';
  }
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  for (; t; --t) {
    solve();
  }
  return 0;
}

稳定匹配的性质

稳定匹配有着良好的理论性质．首先，Gale–Shapley 算法构造性地证明，稳定匹配一定存在．

定理 1（Gale and Shapley, 1962）

Gale–Shapley 算法得到的是一个稳定匹配．因此，稳定匹配存在．

证明

男士不会对他不接受的女士求婚，女士也会立即拒绝她不接受的男士的求婚．因此，最终互相匹配的男士和女士一定是彼此接受的，不可能存在阻塞个体．要证明它是稳定匹配，只需要说明不存在阻塞对．

反证法．假设 (m,w)(m,w) 是一个阻塞对．那么，在男士 mm 向 μ(m)\mu(m) 求婚之前，他一定已经向 ww 求过婚．但是，既然女士 ww 拒绝了 mm，她一定是收到了她更喜欢的人 m′m' 的求婚请求．如果 m′≠μ(w)m'\neq \mu(w)，那么，女士 ww 相对于 m′m' 只会更喜欢 μ(w)\mu(w)．由此，相对于 mm，女士 ww 一定更喜欢最终的匹配对象 μ(w)\mu(w)．这与 (m,w)(m,w) 是阻塞对矛盾．所以，匹配是稳定的．

推论

如果 ∣M∣=∣W∣|M|=|W| 且所有异性都是可接受的，那么，存在一个稳定的完美匹配．

Gale–Shapley 算法中，可以由男士求婚，也可以由女士求婚．一般情况下，这两个版本的 Gale–Shapley 算法得到的稳定匹配并不相同．事实上，由男士求婚的 Gale–Shapley 算法得到的稳定匹配是所有稳定匹配中，对于男士最有利的；反之亦然．

定理 2（Gale and Shapley, 1962）

设 μM\mu_M 和 μW\mu_W 分别是由男士和女士求婚的 Gale–Shapley 算法得到的稳定匹配．对于任何稳定匹配 μ\mu，都有 μ(m)⪯mμM(m)\mu(m)\preceq_m\mu_M(m) 对于所有 m∈Mm\in M 成立，且 μ(w)⪯wμW(w)\mu(w)\preceq_w\mu_W(w) 对所有 w∈Ww\in W 成立．

证明

根据对称性，只需要证明 μ(m)⪯mμM(m)\mu(m)\preceq_m\mu_M(m) 对于所有 m∈Mm\in M 成立．为此，仍然考虑由男士求婚的 Gale–Shapley 算法，并记 k(m,w)k(m,w) 为女士 ww 拒绝男士 mm 的求婚时，算法进行到的轮次．这个轮次对于所有满足 μM(m)≺mw\mu_M(m)\prec_m w 的 (m,w)(m,w) 都是良定义的．

假设 μM\mu_M 并非对所有男士都最有利的，也就是说，存在稳定匹配 μ\mu 和男士 m∈Mm\in M 使得 μM(m)≺mμ(m)\mu_M(m)\prec_m\mu(m) 成立．由于匹配 μM\mu_M 是稳定的，就有 m⪯mμM(m)≺mμ(m)m\preceq_m\mu_M(m)\prec_m\mu(m)，所以 μ(m)\mu(m) 是女士，一定有良定义的 k(m,μ(m))k(m,\mu(m))．于是，不妨设 mm 恰为所有这样的男士中，k(m,μ(m))k(m,\mu(m)) 最小的那个．设算法过程中，女士 w=μ(m)w=\mu(m) 拒绝男士 mm 时保留的是男士 m′m' 的求婚请求，也就是说，m=μ(w)≺wm′m=\mu(w)\prec_w m'．由于 μ\mu 是稳定匹配，(w,m′)(w,m') 不能是阻塞对，又有 μ(m′)≠w\mu(m')\neq w，所以，w≺m′μ(m′)w\prec_{m'}\mu(m')．由于 Gale–Shapley 算法过程中，女士 ww 未必会保留 m′m' 的求婚请求到最后，所以 μM(m′)⪯m′w≺m′μ(m′)\mu_M(m')\preceq_{m'}w\prec_{m'}\mu(m')．此时，k(m′,μ(m′))k(m',\mu(m')) 是良定义的．而且，由于 w≺m′μ(m′)w\prec_{m'}\mu(m')，所以，女士 μ(m′)\mu(m') 拒绝 m′m' 的求婚请求之后，才会有 ww 保留 m′m' 的求婚请求，也就是说，k(m′,μ(m′))<k(m,μ(m))k(m',\mu(m')) < k(m,\mu(m))．这与 mm 的选取相矛盾．所以，根据反证法，μM\mu_M 是对所有男士最有利的稳定匹配．

一个匹配市场可能存在指数级数量的稳定匹配．设 S\mathcal S 为全体稳定匹配的集合．在这个集合上，可以定义两个偏序：

  • μ1⪯Mμ2\mu_1\preceq_M\mu_2，当且仅当 μ1(m)⪯mμ2(m)\mu_1(m)\preceq_m\mu_2(m) 对所有 m∈Mm\in M 都成立；
  • μ1⪯Wμ2\mu_1\preceq_W\mu_2，当且仅当 μ1(w)⪯wμ2(w)\mu_1(w)\preceq_w\mu_2(w) 对所有 w∈Ww\in W 都成立．

这两个偏序分别表示匹配结果对于所有男士和所有女士都更优．一般地，两个稳定匹配未必是可比的．但是，任意两个稳定匹配都诱导如图所示的分解，使得分解所得的三个部分中，分别成立 μ1⪯Mμ2\mu_1\preceq_M\mu_2，μ1=μ2\mu_1=\mu_2 和 μ2⪯Mμ1\mu_2\preceq_M\mu_1．注意，尽管没有直接绘制出，但是 μ1=μ2\mu_1=\mu_2 的那一部分其实包含了匹配到自身（即未匹配）的情形．

配图：stable match decompose

这一分解依赖于如下的引理：

引理（Knuth, 1976）

设 μ1\mu_1 和 μ2\mu_2 是两个稳定匹配．设 M(μi)={m∈M:μj(m)≺mμi(m)}M(\mu_i)=\{m\in M : \mu_j(m)\prec_m\mu_i(m)\} 和 W(μi)={w∈W:μj(w)≺wμi(w)}W(\mu_i)=\{w\in W:\mu_j(w)\prec_w\mu_i(w)\} 分别为更偏好 μi\mu_i 中的匹配结果的男士和女士的集合，其中，i,j=1,2i,j=1,2 且 i≠ji\neq j．那么，μ1\mu_1 和 μ2\mu_2 都是 M(μ1)M(\mu_1) 与 W(μ2)W(\mu_2) 之间的双射，也都是 M(μ2)M(\mu_2) 与 W(μ1)W(\mu_1) 之间的双射．

证明

设 m∈M(μ1)m\in M(\mu_1)．由于 m⪯mμ2(m)≺mμ1(m)m\preceq_m \mu_2(m)\prec_m\mu_1(m)，所以 μ1(m)∈W\mu_1(m)\in W．令 w=μ1(m)w=\mu_1(m)．因为 μ2(w)≠m\mu_2(w)\neq m，而 μ2(w)≺wm\mu_2(w)\prec_w m 又意味着 (m,w)(m,w) 是 μ2\mu_2 的阻塞对，所以，μ1(w)=m≺wμ2(w)\mu_1(w)=m\prec_w\mu_2(w)．也就是说，w∈W(μ2)w\in W(\mu_2)．这说明，μ1(M(μ1))⊆W(μ2)\mu_1(M(\mu_1))\subseteq W(\mu_2)．由对称性，还可以建立 μ2(W(μ2))⊆M(μ1)\mu_2(W(\mu_2))\subseteq M(\mu_1)．由于 μ1\mu_1 和 μ2\mu_2 都是单射，所以，∣M(μ1)∣=∣W(μ2)∣|M(\mu_1)|=|W(\mu_2)| 且这两个映射都是满射．这就说明，μ1\mu_1 和 μ2\mu_2 都是 M(μ1)M(\mu_1) 与 W(μ2)W(\mu_2) 之间的双射．同理，它们也都是 M(μ2)M(\mu_2) 与 W(μ1)W(\mu_1) 之间的双射．

这一引理说明，偏序集 (S,⪯M)(\mathcal S,\preceq_M) 和 (S,⪯W)(\mathcal S,\preceq_W) 互为 对偶．而且，在每个偏序下，集合 S\mathcal S 都构成一个 格．因为 S\mathcal S 是有限的，这两个格一定存在最大元和最小元．这两个最值元素，分别就是前文提到的两个版本的 Gale–Shapley 算法所得到的稳定匹配．

定理 3（Conway and Knuth, 1976）

偏序集 (S,⪯M)(\mathcal S,\preceq_M) 和 (S,⪯W)(\mathcal S,\preceq_W) 是相互对偶的格．而且，μM\mu_M 和 μW\mu_W 分别是 (S,⪯M)(\mathcal S,\preceq_M) 的最大元和最小元，也分别是 (S,⪯W)(\mathcal S,\preceq_W) 的最小元和最大元．

证明

根据引理，容易说明两个偏序集是对偶的．如果 μ1⪯Mμ2\mu_1\preceq_M\mu_2，这说明 M(μ1)=∅M(\mu_1)=\varnothing；由引理，W(μ2)=∅W(\mu_2)=\varnothing，此即 μ2⪯Wμ1\mu_2\preceq_W\mu_1．反之亦然．这就说明两者互为对偶．再结合前文的定理 2，就得到 μM\mu_M 和 μW\mu_W 是两个偏序集的最值元素．命题中还需要证明的是，两个偏序集是格．由对称性，只需要证明 (S,⪯M)(\mathcal S,\preceq_M) 是格．再根据交和并运算的对称性，只需要证明稳定匹配的并仍然是稳定匹配．形式化地，对于任意 μ1,μ2∈S\mu_1,\mu_2\in\mathcal S，需要证明对于所有 m∈Mm\in M 都满足 μ(m)=μ1(m)∨mμ2(m)\mu(m)=\mu_1(m)\lor_m\mu_2(m) 的匹配 μ=μ1∨Mμ2\mu=\mu_1\lor_M\mu_2 是稳定匹配，其中，∨m\lor_m 是全序 ⪯m\preceq_m 下的并运算（即两者中 mm 更喜欢的那个）．

仍采用引理中的记号．对于 i∈M(μ1)∪W(μ2)i\in M(\mu_1)\cup W(\mu_2)，有 μ(i)=μ1(i)\mu(i)=\mu_1(i)；否则，有 μ(i)=μ2(i)\mu(i)=\mu_2(i)．由于 μ1\mu_1 和 μ2\mu_2 都是稳定的，不存在阻塞个体，μ\mu 也同样如此．假设 (m,w)(m,w) 是 μ\mu 的阻塞对．如果 m∈M(μ1)m\in M(\mu_1)，那么，μ2(m)≺mμ1(m)=μ(m)≺mw\mu_2(m)\prec_m\mu_1(m)=\mu(m)\prec_m w．此时，如果 w∈W(μ2)w\in W(\mu_2)，那么，μ1(w)=μ(w)≺wm\mu_1(w)=\mu(w)\prec_w m，所以，(m,w)(m,w) 是 μ1\mu_1 的阻塞对，矛盾；否则，w∈W∖W(μ2)w\in W\setminus W(\mu_2)，有 μ2(w)=μ(w)≺wm\mu_2(w)=\mu(w)\prec_w m，所以，(m,w)(m,w) 是 μ2\mu_2 的阻塞对，也矛盾．类似地，m∈M∖M(μ1)m\in M\setminus M(\mu_1) 的情形也只能导出矛盾．由反证法可知，这样的阻塞对不存在．所以，μ1∨Mμ2\mu_1\lor_M\mu_2 是稳定匹配．命题得证．

最后，在所有稳定匹配中，未匹配的男士和女士的集合都是固定的．

定理 4（McVitie and Wilson, 1970）

设 μ1\mu_1 和 μ2\mu_2 是两个稳定匹配．那么，μ1\mu_1 和 μ2\mu_2 的不动点集合相同．

证明

假设存在 m∈Mm\in M 使得 μ1(m)=m\mu_1(m)=m 且 μ2(m)≠m\mu_2(m)\neq m 对某组 μ1,μ2∈S\mu_1,\mu_2\in\mathcal S 成立．此时，有 m∈M(μ2)m\in M(\mu_2)．由引理可知，m=μ1(m)∈W(μ1)m=\mu_1(m)\in W(\mu_1)，这与 m∈Mm\in M 矛盾．所以，不存在这样的 m∈Mm\in M．同理，也不存在这样的 w∈Ww\in W．所以，任意两个稳定匹配的不动点集合必然相同．

除了本节讨论的这些性质外，稳定匹配还有一些良好的策略性质．关于这些内容，可以参见文末提供的文献．

相关问题

稳定匹配及其类似问题还出现在许多其他的情境中．

学院招生问题

如果将稳定婚姻问题中的一对一匹配的限制放宽，允许多对一匹配，就得到了 学院招生问题（college admissions problem）．此时，一个学院可以招收多名学生，只要不超过招生限额；但是，一名学生仍然只允许进入至多一个学院学习．类似的情景还出现在公司招聘、医院招收实习医生等场景中．

对于这类问题，Gale–Shapley 算法仍然适用．例如，由学生申请的 Gale–Shapley 算法中，学院可以维持一个不超过限额长度的候选名单（waitlist），每次只要在申请数量超过限额时，拒绝最差学生的申请即可．前文关于稳定匹配性质的讨论对于这一场景仍然适用．特别地，定理 4 对应的版本是，在所有稳定匹配中，学校能够招到的学生人数是固定的．这也称为 乡村医院定理（rural hospitals theorem）．因为它意味着，无论如何更改匹配机制，只要得到的结果是稳定的，那些招不满医生的乡村医院永远招不到人．

稳定室友问题

如果将稳定婚姻问题中，只能匹配异性的条件放宽，就得到了 稳定室友问题（stable roommates problem）．此时，初始只有若干名学生，需要两两结对成为室友．对于这类问题，稳定匹配未必存在．Irving 在 1985 年提出了可以在 O(n2)O(n^2) 时间内解决该问题的算法．

住房分配问题

稳定婚姻问题中，两组个体互相有偏好，所以是双边匹配问题．除此之外，还可以考虑单边匹配问题．一个常见的场景是 住房分配问题（house allocation problem）．有 nn 名居民，各自拥有一套住房．每人对所有住房有一个严格偏好．现在，要将这些住房重新分配给这些居民，要求每名居民都不能分配到比初始更差的住房，且不存在任何数量的居民，可以私自交换房产，得到更满意的结局．对于这一问题，可以通过 Top Trading Cycle 算法在 O(n2)O(n^2) 时间内解决．这类问题还出现在肾移植等场景中．

习题

参考资料与注释

上一节
380 一般图最大权匹配
下一节
382 Prüfer 序列

本文内容来自 OI Wiki《稳定匹配》；作者与修订历史见原文。AIOJ 对排版、站内链接和资源路径做了格式适配。

内容依 CC BY-SA 4.0 与 SATA 许可共享；附加条款以原文声明为准。感谢 OI Wiki 作者与贡献者；请按 SATA 约定前往 OI Wiki 仓库 Star 支持。