Skip to content

Stable Matching

Introduction

The stable matching problem is a classic problem in combinatorial optimization and cooperative game theory. Compared to traditional graph matching problems, stable matching introduces individual preferences and stability constraints, making algorithm design rely more on preference orders rather than pure graph structure. In the model of the stable matching problem, each individual has preferences over potential matching partners, and the stable matching problem aims to establish a stable matching relationship among them. In a stable matching, there is no group of individuals who would collude to deviate from the current matching outcome because they could obtain a better choice. Stable matching and related problems are widely applied in scenarios such as labor markets, school admissions, and medical resource allocation.

The most common stable matching problem in algorithm competitions is the one-to-one matching in two-sided markets, i.e., the stable marriage problem. This article will focus on the stable marriage problem and its algorithms.

Stable Marriage Problem

The stable marriage problem is the earliest studied stable matching problem. Similar to bipartite graph matching, it can be described as a matching problem in the marriage market: Suppose there are a number of men and women, each with a preference order over the opposite sex. The goal is to find a matching such that no man and woman would prefer to abandon their current partners and choose each other.

Problem Description

The matching market consists of a set of men \(M\) and a set of women \(W\). Each individual has a strict preference order over the opposite sex:

  • For each man \(m\in M\), there exists a strict total order \(\preceq_m\) on the set \(W\cup\{m\}\);
  • For each woman \(w\in W\), there exists a strict total order \(\preceq_w\) on the set \(M\cup\{w\}\).

In addition to comparing among the opposite sex, each individual also includes themselves in this preference order. This means that an individual will only accept a match with an opposite-sex partner ranked above themselves; such partners are called acceptable. Clearly, the preference order of unacceptable opposite-sex partners is irrelevant; in principle, it suffices to provide the preference order only among acceptable opposite-sex partners. Thus, preferences that include unacceptable partners are also called preferences with incomplete lists.

Example

Suppose \(m\) is a man, \(w_1,w_2,w_3\) are three women, and the preference relation \(w_1\prec_m m \prec_m w_2\prec_m w_3\) holds. Then, man \(m\) prefers being single to matching with woman \(w_1\); prefers matching with woman \(w_2\) to being single; and prefers matching with woman \(w_3\) to matching with woman \(w_2\). For man \(m\), woman \(w_1\) is unacceptable, while women \(w_2,w_3\) are acceptable.

A matching \(\mu:M\cup W\rightarrow M\cup W\) in the market must satisfy the following properties:

  • Each individual can only match with an opposite-sex partner or themselves, i.e., for all \(m\in M\), \(\mu(m)\in W\cup\{m\}\), and for all \(w\in W\), \(\mu(w)\in W\cup\{w\}\).
  • The matching is mutual, i.e., for all \(i\in M\cup W\), \(i = \mu(\mu(i))\).

A matching \(\mu\) may contain two types of instabilities:

  • If there exists an individual \(i\in M\cup W\) such that \(\mu(i)\prec_i i\), i.e., individual \(i\) prefers being single to their current partner, then \(i\) is called a blocking individual of matching \(\mu\).
  • If there exists a pair of opposite-sex individuals \(m\in M\) and \(w\in W\) such that \(\mu(m)\prec_m w\) and \(\mu(w)\prec_w m\), i.e., man \(m\) and woman \(w\) prefer each other to their current partners, then \((m,w)\) is called a blocking pair of matching \(\mu\).

A matching \(\mu\) is called stable if it has neither blocking individuals nor blocking pairs. In a stable matching, no one can disrupt the current situation: single individuals cannot find anyone willing to be with them; married individuals are neither willing to divorce and become single nor can they find anyone willing to elope with them.

The stable matching problem asks: For any given set of preference orders, does a stable matching always exist? If so, how can such a stable matching be found?

Gale–Shapley Algorithm

In 1962, Gale and Shapley proposed the deferred acceptance algorithm, which can find a stable matching for any given set of preference orders. Therefore, a stable matching always exists.

The Gale–Shapley algorithm has two symmetric versions: men-proposing and women-proposing. Taking the men-proposing Gale–Shapley algorithm as an example, the algorithm proceeds as follows:

  1. At the start of the algorithm, each woman is considered to hold a proposal request from herself, and each man is marked as active.
  2. Each active man proposes to his most preferred acceptable woman to whom he has not yet proposed; if no such woman exists, no action is taken. Regardless of whether they propose, all men are marked as inactive.
  3. A woman who receives new proposal requests compares them with the one she currently holds, keeps only the most preferred one (which may be herself), and rejects all other proposals. Men who are rejected are marked as active again.
  4. Repeat the previous two steps until no active men remain. At this point, women accept the proposal requests they currently hold. The resulting matching is a stable matching.

Since each man proposes to each woman at most once, the algorithm terminates in \(O(|M||W|)\) time.

A reference implementation is as follows:

Reference implementation for template problem SPOJ STABLEMP - Stable Marriage Problem 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#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;
}

Properties of Stable Matchings

Stable matchings have good theoretical properties. First, the Gale–Shapley algorithm constructively proves that a stable matching always exists.

Theorem 1 (Gale and Shapley, 1962)

The Gale–Shapley algorithm yields a stable matching. Therefore, a stable matching exists.

Proof

A man will not propose to a woman he finds unacceptable, and a woman will immediately reject a proposal from a man she finds unacceptable. Therefore, in the final matching, matched men and women must be mutually acceptable, so there cannot be any blocking individuals. To prove it is a stable matching, it suffices to show that there are no blocking pairs.

Proof by contradiction. Suppose \((m,w)\) is a blocking pair. Then, before man \(m\) proposed to \(\mu(m)\), he must have already proposed to \(w\). However, since woman \(w\) rejected \(m\), she must have received a proposal from someone she prefers more, say \(m'\). If \(m'\neq \mu(w)\), then woman \(w\) prefers \(\mu(w)\) over \(m'\). Thus, woman \(w\) must prefer her final partner \(\mu(w)\) over \(m\). This contradicts \((m,w)\) being a blocking pair. Therefore, the matching is stable.

Corollary

If \(|M|=|W|\) and all opposite-sex individuals are acceptable, then there exists a stable perfect matching.

In the Gale–Shapley algorithm, proposals can be made by men or by women. In general, the stable matchings obtained by the two versions of the Gale–Shapley algorithm are not the same. In fact, the stable matching obtained by the men-proposing Gale–Shapley algorithm is the most favorable for all men among all stable matchings; conversely, the women-proposing version yields the most favorable matching for all women.

Theorem 2 (Gale and Shapley, 1962)

Let \(\mu_M\) and \(\mu_W\) be the stable matchings obtained by the men-proposing and women-proposing Gale–Shapley algorithms, respectively. For any stable matching \(\mu\), \(\mu(m)\preceq_m\mu_M(m)\) holds for all \(m\in M\), and \(\mu(w)\preceq_w\mu_W(w)\) holds for all \(w\in W\).

Proof

By symmetry, it suffices to prove \(\mu(m)\preceq_m\mu_M(m)\) for all \(m\in M\). To this end, consider the men-proposing Gale–Shapley algorithm and denote \(k(m,w)\) as the round in which woman \(w\) rejects man \(m\)'s proposal. This round is well-defined for all \((m,w)\) satisfying \(\mu_M(m)\prec_m w\).

Suppose \(\mu_M\) is not the most favorable for all men, i.e., there exists a stable matching \(\mu\) and a man \(m\in M\) such that \(\mu_M(m)\prec_m\mu(m)\). Since matching \(\mu_M\) is stable, we have \(m\preceq_m\mu_M(m)\prec_m\mu(m)\), so \(\mu(m)\) is a woman, and \(k(m,\mu(m))\) is well-defined. Thus, let \(m\) be the man with the smallest \(k(m,\mu(m))\) among all such men. Suppose during the algorithm, when woman \(w=\mu(m)\) rejected man \(m\), she held a proposal from man \(m'\), i.e., \(m=\mu(w)\prec_w m'\). Since \(\mu\) is a stable matching, \((w,m')\) cannot be a blocking pair, and since \(\mu(m')\neq w\), we have \(w\prec_{m'}\mu(m')\). Since in the Gale–Shapley algorithm, woman \(w\) may not hold \(m'\)'s proposal until the end, we have \(\mu_M(m')\preceq_{m'}w\prec_{m'}\mu(m')\). Now, \(k(m',\mu(m'))\) is well-defined. Moreover, since \(w\prec_{m'}\mu(m')\), woman \(\mu(m')\) must have rejected \(m'\)'s proposal before \(w\) held \(m'\)'s proposal, i.e., \(k(m',\mu(m')) < k(m,\mu(m))\). This contradicts the choice of \(m\). Therefore, by contradiction, \(\mu_M\) is the stable matching most favorable for all men.

A matching market may have an exponential number of stable matchings. Let \(\mathcal S\) be the set of all stable matchings. On this set, two partial orders can be defined:

  • \(\mu_1\preceq_M\mu_2\) if and only if \(\mu_1(m)\preceq_m\mu_2(m)\) for all \(m\in M\);
  • \(\mu_1\preceq_W\mu_2\) if and only if \(\mu_1(w)\preceq_w\mu_2(w)\) for all \(w\in W\).

These partial orders indicate that the matching outcome is better for all men and all women, respectively. In general, two stable matchings may not be comparable. However, any two stable matchings induce a decomposition as shown in the figure, such that in the three resulting parts, \(\mu_1\preceq_M\mu_2\), \(\mu_1=\mu_2\), and \(\mu_2\preceq_M\mu_1\) hold, respectively. Note that although not explicitly drawn, the part where \(\mu_1=\mu_2\) includes the case of matching to oneself (i.e., being unmatched).

This decomposition relies on the following lemma:

Lemma (Knuth, 1976)

Let \(\mu_1\) and \(\mu_2\) be two stable matchings. Let \(M(\mu_i)=\{m\in M : \mu_j(m)\prec_m\mu_i(m)\}\) and \(W(\mu_i)=\{w\in W:\mu_j(w)\prec_w\mu_i(w)\}\) be the sets of men and women who prefer the matching outcome in \(\mu_i\), where \(i,j=1,2\) and \(i\neq j\). Then, \(\mu_1\) and \(\mu_2\) are both bijections between \(M(\mu_1)\) and \(W(\mu_2)\), and also between \(M(\mu_2)\) and \(W(\mu_1)\).

Proof

Let \(m\in M(\mu_1)\). Since \(m\preceq_m \mu_2(m)\prec_m\mu_1(m)\), we have \(\mu_1(m)\in W\). Let \(w=\mu_1(m)\). Because \(\mu_2(w)\neq m\), and \(\mu_2(w)\prec_w m\) would imply \((m,w)\) is a blocking pair for \(\mu_2\), we have \(\mu_1(w)=m\prec_w\mu_2(w)\). That is, \(w\in W(\mu_2)\). This shows \(\mu_1(M(\mu_1))\subseteq W(\mu_2)\). By symmetry, we also have \(\mu_2(W(\mu_2))\subseteq M(\mu_1)\). Since \(\mu_1\) and \(\mu_2\) are injective, \(|M(\mu_1)|=|W(\mu_2)|\) and these mappings are surjective. Thus, \(\mu_1\) and \(\mu_2\) are bijections between \(M(\mu_1)\) and \(W(\mu_2)\). Similarly, they are also bijections between \(M(\mu_2)\) and \(W(\mu_1)\).

This lemma shows that the partially ordered sets \((\mathcal S,\preceq_M)\) and \((\mathcal S,\preceq_W)\) are dual to each other. Moreover, under each partial order, the set \(\mathcal S\) forms a lattice. Since \(\mathcal S\) is finite, these lattices must have a greatest and a least element. These extremal elements are precisely the stable matchings obtained by the two versions of the Gale–Shapley algorithm mentioned earlier.

Theorem 3 (Conway and Knuth, 1976)

The partially ordered sets \((\mathcal S,\preceq_M)\) and \((\mathcal S,\preceq_W)\) are dual lattices. Moreover, \(\mu_M\) and \(\mu_W\) are the greatest and least elements of \((\mathcal S,\preceq_M)\), respectively, and also the least and greatest elements of \((\mathcal S,\preceq_W)\), respectively.

Proof

According to the lemma, it is easy to show that the two partial orders are dual. If \(\mu_1\preceq_M\mu_2\), then \(M(\mu_1)=\varnothing\); by the lemma, \(W(\mu_2)=\varnothing\), which means \(\mu_2\preceq_W\mu_1\). The converse holds similarly. This shows they are dual. Combined with Theorem 2 above, we obtain that \(\mu_M\) and \(\mu_W\) are the extremal elements of the two partial orders. The proposition also requires proving that the two partial orders are lattices. By symmetry, it suffices to prove that \((\mathcal S,\preceq_M)\) is a lattice. By the symmetry of meet and join operations, it suffices to prove that the join of stable matchings is still a stable matching. Formally, for any \(\mu_1,\mu_2\in\mathcal S\), we need to show that the matching \(\mu=\mu_1\lor_M\mu_2\), defined by \(\mu(m)=\mu_1(m)\lor_m\mu_2(m)\) for all \(m\in M\) (where \(\lor_m\) is the join operation under the total order \(\preceq_m\), i.e., the one \(m\) prefers more), is a stable matching.

Using the notation from the lemma. For \(i\in M(\mu_1)\cup W(\mu_2)\), we have \(\mu(i)=\mu_1(i)\); otherwise, \(\mu(i)=\mu_2(i)\). Since \(\mu_1\) and \(\mu_2\) are stable and have no blocking individuals, \(\mu\) also has no blocking individuals. Suppose \((m,w)\) is a blocking pair for \(\mu\). If \(m\in M(\mu_1)\), then \(\mu_2(m)\prec_m\mu_1(m)=\mu(m)\prec_m w\). Now, if \(w\in W(\mu_2)\), then \(\mu_1(w)=\mu(w)\prec_w m\), so \((m,w)\) is a blocking pair for \(\mu_1\), a contradiction; otherwise, \(w\in W\setminus W(\mu_2)\), we have \(\mu_2(w)=\mu(w)\prec_w m\), so \((m,w)\) is a blocking pair for \(\mu_2\), also a contradiction. Similarly, the case \(m\in M\setminus M(\mu_1)\) leads to a contradiction. By contradiction, such a blocking pair does not exist. Therefore, \(\mu_1\lor_M\mu_2\) is a stable matching. The proposition is proved.

Finally, across all stable matchings, the sets of unmatched men and women are fixed.

Theorem 4 (McVitie and Wilson, 1970)

Let \(\mu_1\) and \(\mu_2\) be two stable matchings. Then, the sets of fixed points of \(\mu_1\) and \(\mu_2\) are the same.

Proof

Suppose there exists \(m\in M\) such that \(\mu_1(m)=m\) and \(\mu_2(m)\neq m\) for some \(\mu_1,\mu_2\in\mathcal S\). Then, \(m\in M(\mu_2)\). By the lemma, \(m=\mu_1(m)\in W(\mu_1)\), which contradicts \(m\in M\). Therefore, no such \(m\in M\) exists. Similarly, no such \(w\in W\) exists. Hence, any two stable matchings must have the same set of fixed points.

In addition to the properties discussed in this section, stable matchings also have good strategic properties. For these topics, refer to the literature provided at the end.

Stable matching and similar problems also appear in many other contexts.

College Admissions Problem

If the one-to-one matching restriction in the stable marriage problem is relaxed to allow many-to-one matching, we obtain the college admissions problem. Here, a college can admit multiple students, as long as it does not exceed its quota; however, a student is still allowed to enroll in at most one college. Similar scenarios appear in company recruitment, hospital residency matching, etc.

For such problems, the Gale–Shapley algorithm still applies. For example, in the student-proposing Gale–Shapley algorithm, a college can maintain a waitlist of length not exceeding its quota, and whenever the number of applications exceeds the quota, it rejects the least preferred student. The discussions about the properties of stable matchings still apply in this context. In particular, the version corresponding to Theorem 4 is that across all stable matchings, the number of students a school can admit is fixed. This is also known as the rural hospitals theorem. It implies that no matter how the matching mechanism is changed, as long as the outcome is stable, rural hospitals that cannot fill their positions will never be able to recruit enough doctors.

Stable Roommates Problem

If the condition of matching only opposite-sex individuals in the stable marriage problem is relaxed, we obtain the stable roommates problem. Here, initially there are only a number of students who need to pair up as roommates. For this problem, a stable matching may not exist. Irving proposed an algorithm in 1985 that solves this problem in \(O(n^2)\) time.

House Allocation Problem

In the stable marriage problem, two groups of individuals have preferences over each other, so it is a two-sided matching problem. Additionally, one can consider one-sided matching problems. A common scenario is the house allocation problem. There are \(n\) residents, each owning a house. Each resident has a strict preference over all houses. The goal is to reassign these houses to the residents such that no resident receives a house worse than their initial one, and there is no group of residents who can privately exchange houses to achieve a more satisfactory outcome. For this problem, the Top Trading Cycle algorithm can solve it in \(O(n^2)\) time. Such problems also appear in scenarios like kidney exchanges.

Exercises

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用