AIOJ

Introduction

The stable matching problem is a classic problem in combinatorial optimization and cooperative game theory. Compared with traditional graph matching problems, stable matching introduces constraints on individual preferences and stability, making algorithm design rely more on preference orders than on graph structure alone. In the model of the stable matching problem, each individual has preferences over potential matching partners, and the problem seeks to establish a stable matching relationship among them. In a stable matching, no group of individuals can collude to deviate from the current matching outcome by obtaining better choices. Stable matching and related problems are widely used in labor markets, school admissions, medical resource allocation, and other settings.

The stable matching problem that appears most often in algorithm competitions is one-to-one matching in a two-sided market, namely the stable marriage problem. This article focuses on the stable marriage problem and its algorithms.

Stable marriage problem

The stable marriage problem was the first stable matching problem to be studied. Similar to bipartite matching, it can be described as a matching problem in a marriage market: suppose there are some men and some women, each with an ordered set of preferences over people of the opposite sex. The goal is to find a matching such that no man and woman would both prefer to abandon their current partners and choose each other.

Problem statement

The matching market consists of some men $M$ and some women $W$ . Everyone has a strict preference order over people of the opposite sex:

For each man $m\in M$ , there is a strict total order $\preceq_m$ on $W\cup\{m\}$ ;
For each woman $w\in W$ , there is a strict total order $\preceq_w$ on $M\cup\{w\}$ .

In addition to comparing members of the opposite sex, each person includes themself in this preference order. This means that the person accepts only matches with members of the opposite sex who appear before them; these members are called acceptable. Clearly, the preference order of unacceptable members of the opposite sex is irrelevant; in principle, it is enough to specify the preference order among acceptable members. Such preferences with unacceptable members are also called preferences with incomplete lists.

Example

Suppose $m$ is a man, $w_1,w_2,w_3$ are three women, and $w_1\prec_m m \prec_m w_2\prec_m w_3$ . Then man $m$ prefers being single to being matched with woman $w_1$ ; he prefers being matched with woman $w_2$ to being single; and he prefers being matched with woman $w_3$ to being matched 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 person can be matched only with a member of the opposite sex or themself: for every $m\in M$ , $\mu(m)\in W\cup\{m\}$ , and for every $w\in W$ , $\mu(w)\in W\cup\{w\}$ .
A matching is mutual: for every $i\in M\cup W$ , $i = \mu(\mu(i))$ .

A matching $\mu$ may have two kinds of instability:

If there is an individual $i\in M\cup W$ such that $\mu(i)\prec_i i$ , that is, individual $i$ would rather be single than remain with their current partner, then $i$ is called a blocking individual of matching $\mu$ .
If there is a man $m\in M$ and a woman $w\in W$ such that $\mu(m)\prec_m w$ and $\mu(w)\prec_w m$ , that is, man $m$ and woman $w$ would both rather be with each other than with their current partners, then $(m,w)$ is called a blocking pair of matching $\mu$ .

If a matching $\mu$ has neither a blocking individual nor a blocking pair, the matching $\mu$ is called stable. In a stable matching, no one can disrupt the current situation: a single person cannot find anyone willing to be with them, while a married person is neither willing to divorce and be single nor able to 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 finds a stable matching for any given set of preference orders. Therefore, a stable matching always exists.

The Gale–Shapley algorithm has two symmetric versions, with either men or women making proposals. Taking the version in which men propose as an example, the algorithm proceeds as follows:

At the beginning, each woman is regarded as holding a proposal from herself, and each man is marked active.
Each active man proposes to the most preferred woman among those he finds acceptable but to whom he has not yet proposed; if no such woman exists, no operation is needed. Regardless of whether they have proposed, mark all men inactive.
Each woman who receives new proposals compares them with the proposals she was already holding, keeps only the most preferred one (possibly herself), and rejects all other proposals. Mark the rejected men active again.
Repeat the first two steps until no man is active. The women then accept the proposals they are currently holding. The resulting matching is a stable matching.

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

The reference implementation is as follows:

Reference implementation for template problem 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;
}

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 produces a stable matching. Therefore, a stable matching exists.

Proof

A man never proposes to a woman he does not accept, and a woman immediately rejects a proposal from a man she does not accept. Therefore, every man and woman who are eventually matched must accept each other, so no blocking individual can exist. To prove that the matching is stable, it remains only to show that no blocking pair exists.

By contradiction, suppose that $(m,w)$ is a blocking pair. Then, before man $m$ proposed to $\mu(m)$ , he must have proposed to $w$ . Since woman $w$ rejected $m$ , she must have received a proposal from a man $m'$ whom she preferred. If $m'\neq \mu(w)$ , then woman $w$ can only prefer $\mu(w)$ to $m'$ . Thus, compared with $m$ , woman $w$ must prefer her final partner $\mu(w)$ . This contradicts $(m,w)$ being a blocking pair. Therefore, the matching is stable.

Corollary

If $|M|=|W|$ and every member of the opposite sex is acceptable, then a stable perfect matching exists.

The Gale–Shapley algorithm can have either men or women make proposals. In general, these two versions produce different stable matchings. In fact, the stable matching produced by the men-proposing version is the most favorable to men among all stable matchings; conversely, the women-proposing version is the most favorable to women.

Theorem 2 (Gale and Shapley, 1962)

Let $\mu_M$ and $\mu_W$ be the stable matchings produced by the men-proposing and women-proposing versions of the Gale–Shapley algorithm, respectively. For any stable matching $\mu$ , $\mu(m)\preceq_m\mu_M(m)$ holds for every $m\in M$ , and $\mu(w)\preceq_w\mu_W(w)$ holds for every $w\in W$ .

Proof

By symmetry, it is enough to prove that $\mu(m)\preceq_m\mu_M(m)$ holds for every $m\in M$ . For this purpose, again consider the men-proposing Gale–Shapley algorithm, and let $k(m,w)$ be the round in which the algorithm reaches the point when woman $w$ rejects man's $m$ proposal. This round is well-defined for every $(m,w)$ satisfying $\mu_M(m)\prec_m w$ .

Suppose that $\mu_M$ is not the most favorable for all men; that is, there is 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, $m\preceq_m\mu_M(m)\prec_m\mu(m)$ , so $\mu(m)$ is a woman and $k(m,\mu(m))$ is well-defined. Without loss of generality, choose $m$ to be the man among all such men for whom $k(m,\mu(m))$ is smallest. Let $w=\mu(m)$ be the woman who, when rejecting man's $m$ proposal during the algorithm, is holding a proposal from man $m'$ ; that is, $m=\mu(w)\prec_w m'$ . Since $\mu$ is stable, $(w,m')$ cannot be a blocking pair, and $\mu(m')\neq w$ , so $w\prec_{m'}\mu(m')$ . Since woman $w$ does not necessarily keep $m'$ 's proposal until the end of the Gale–Shapley algorithm, $\mu_M(m')\preceq_{m'}w\prec_{m'}\mu(m')$ . Thus, $k(m',\mu(m'))$ is well-defined. Moreover, because $w\prec_{m'}\mu(m')$ , woman $\mu(m')$ rejects $m'$ 's proposal before woman $w$ holds $m'$ 's proposal; in other words, $k(m',\mu(m')) < k(m,\mu(m))$ . This contradicts the choice of $m$ . Therefore, by contradiction, $\mu_M$ is the most favorable stable matching for all men.

A matching market may have exponentially many stable matchings. Let $\mathcal S$ be the set of all stable matchings. On this set, define two partial orders:

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

These two partial orders indicate that the matching outcome is better for all men and for all women, respectively. In general, two stable matchings need not be comparable. However, any two stable matchings induce the decomposition shown in the figure: 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 it is not drawn separately, the part where $\mu_1=\mu_2$ actually includes the cases of matching to oneself (that is, 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 their matches 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 both bijections 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)$ . Since $\mu_2(w)\neq m$ , while $\mu_2(w)\prec_w m$ would imply that $(m,w)$ is a blocking pair of $\mu_2$ , we have $\mu_1(w)=m\prec_w\mu_2(w)$ . In other words, $w\in W(\mu_2)$ . Thus, $\mu_1(M(\mu_1))\subseteq W(\mu_2)$ . By symmetry, we can also establish $\mu_2(W(\mu_2))\subseteq M(\mu_1)$ . Since $\mu_1$ and $\mu_2$ are both injective, $|M(\mu_1)|=|W(\mu_2)|$ and both maps are surjective. This shows that $\mu_1$ and $\mu_2$ are both bijections between $M(\mu_1)$ and $W(\mu_2)$ . Similarly, they are both 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 duals of each other. Moreover, under each partial order, $\mathcal S$ forms a lattice. Since $\mathcal S$ is finite, these two lattices have greatest and least elements. These two extremal elements are exactly the stable matchings produced by the two versions of the Gale–Shapley algorithm mentioned above.

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 respectively the greatest and least elements of $(\mathcal S,\preceq_M)$ , and respectively the least and greatest elements of $(\mathcal S,\preceq_W)$ .

Proof

By the lemma, it is easy to show that the two partially ordered sets 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 is analogous. This shows that the two are duals of each other. Together with Theorem 2 above, this gives that $\mu_M$ and $\mu_W$ are the extremal elements of the two partially ordered sets. It remains to prove in the proposition that the two partially ordered sets are lattices. By symmetry, it suffices to prove that $(\mathcal S,\preceq_M)$ is a lattice. By the symmetry of meet and join, 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 prove that the matching $\mu=\mu_1\lor_M\mu_2$ , defined by $\mu(m)=\mu_1(m)\lor_m\mu_2(m)$ for every $m\in M$ , is stable, where $\lor_m$ is the join under the total order $\preceq_m$ (that is, the one of the two that $m$ prefers).

We use the notation from the lemma. For $i\in M(\mu_1)\cup W(\mu_2)$ , $\mu(i)=\mu_1(i)$ ; otherwise, $\mu(i)=\mu_2(i)$ . Since $\mu_1$ and $\mu_2$ are both stable, neither has a blocking individual, and neither does $\mu$ . Suppose that $(m,w)$ is a blocking pair of $\mu$ . If $m\in M(\mu_1)$ , then $\mu_2(m)\prec_m\mu_1(m)=\mu(m)\prec_m w$ . If $w\in W(\mu_2)$ , then $\mu_1(w)=\mu(w)\prec_w m$ , so $(m,w)$ is a blocking pair of $\mu_1$ , a contradiction; otherwise, $w\in W\setminus W(\mu_2)$ , so $\mu_2(w)=\mu(w)\prec_w m$ , making $(m,w)$ a blocking pair of $\mu_2$ , also a contradiction. Similarly, the case $m\in M\setminus M(\mu_1)$ also leads to a contradiction. Therefore, by contradiction, no such blocking pair exists. Hence $\mu_1\lor_M\mu_2$ is stable. The proposition follows.

Finally, among 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 $\mu_1$ and $\mu_2$ have the same set of fixed points.

Proof

Suppose there is an $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)$ , contradicting $m\in M$ . Thus, no such $m\in M$ exists. Similarly, no such $w\in W$ exists. Therefore, any two stable matchings necessarily have the same set of fixed points.

Besides the properties discussed in this section, stable matchings also have other desirable strategic properties. See the references at the end of the article for more information.

Stable matching and similar problems also arise in many other settings.

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. A college may admit multiple students as long as it does not exceed its enrollment quota; however, a student may still enroll in at most one college. Similar situations arise in company recruitment, hospitals admitting interns, and other settings.

The Gale–Shapley algorithm still applies to these problems. For example, in the student-proposing Gale–Shapley algorithm, a college can maintain a waitlist whose length does not exceed its quota, rejecting the lowest-ranked student's application whenever the number of applications exceeds the quota. The discussion of stable matching properties above still applies to this setting. In particular, the corresponding version of Theorem 4 says that the number of students a school can admit is fixed among all stable matchings. This is also called the rural hospitals theorem. It means that regardless of how the matching mechanism is changed, as long as the result is stable, rural hospitals that cannot fill their positions will never fill them.

Stable roommates problem

If the restriction in the stable marriage problem that only members of the opposite sex may be matched is relaxed, we obtain the stable roommates problem. Initially there are only some students, who must be paired into roommates. A stable matching need not exist for this problem. In 1985, Irving proposed an algorithm that solves it in $O(n^2)$ time.

House allocation problem

In the stable marriage problem, the two groups of individuals have preferences for each other, so it is a two-sided matching problem. In addition, one-sided matching problems can be considered. A common example is the house allocation problem. There are $n$ residents, each of whom owns a house. Each person has a strict preference order over all houses. The houses are to be reassigned to the residents so that no resident receives a house worse than their initial one, and no group of residents can privately exchange houses to obtain a more satisfactory outcome. This problem can be solved in $O(n^2)$ time using the Top Trading Cycle algorithm. Similar problems also arise in settings such as kidney transplantation.

Exercises

References and notes

What Is an Algorithm: How to Find Stable Marriage Pairings - Matrix67
Gale–Shapley Algorithm: Finding Stable Matchings in a Bipartite Graph
Stable matching problem - Wikipedia
Lattice of stable matchings - Wikipedia
Stable roommates problem - Wikipedia
Top trading cycle - Wikipedia
Stable matching: Theory, evidence, and practical design - the 2012 Nobel Prize in Economics
Notes on Matching and Market Design by Xiang Sun
Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American mathematical monthly 69, no. 1 (1962): 9-15.
Irving, Robert W. "An efficient algorithm for the stable roommates problem." Journal of Algorithms 6, no. 4 (1985): 577-595.
Knuth, Donald Ervin. "Marriages stables." Technical report (1976).
McVitie, David G., and Leslie B. Wilson. "Stable marriage assignment for unequal sets." BIT Numerical Mathematics 10, no. 3 (1970): 295-309.
Roth, Alvin E., and Marilda Sotomayor. "Two-sided matching." Handbook of game theory with economic applications 1 (1992): 485-541.
Roth, Alvin E. "Deferred acceptance algorithms: History, theory, practice, and open questions." international Journal of game Theory 36, no. 3-4 (2008): 537-569

Stable Matching

Introduction

Stable marriage problem

Problem statement

Gale–Shapley algorithm

Properties of stable matchings

Related problems

College admissions problem

Stable roommates problem

House allocation problem

Exercises

References and notes