# 3. Stable Matchings

### The Problem

The problem of pairing up people and/or resources shows up a lot:

- Matching students who graduate high school to seats in various colleges.
- Matching students who graduate college to employers for jobs, internships, residencies, and so on.
- Getting actors and actresses to commit to work together for films amidst various constraints.
- Matching organ donors to patients accounting for constraints of compatibility and timing.
- Matching men and women in a dating/marriage market.

We are going to look at one particular abstraction that captures many of the scenarios above (among others). Suppose we have a set V = \{m_1, \ldots, m_n\} of n men and W = \{w_1, \ldots, w_n\} of n women, where each man (respectively, woman) has a strict and complete ranking over the women (respectively, men). Our goal is to find a *matching* between the men and the women, which is to say, a bijection between V and W.

Now, a natural question at this point is: what kind of matchings do we want to find? Unconstrained, there are plenty of matchings that we can choose from. Which one is the “best”?

Upon a moment’s reflection you might come up with several ideas. We are going to focus on a fundamental game-theoretic approach to identifying what we desire from the matchings we seek. What we will demand of the matching M that we seek is that there *is no man and woman who are unmatched in M who prefer each other over their matched partners*. To this end, we first define the notion of a blocking pair with respect to M:

The presence of a blocking pair (a,b) implies that the matching M is unlikely to “sustain”: a and b *both* have an incentive to break off the alliances suggested by the matching M and “elope” with each other instead. Thus, matchings that have blocking pairs are called **unstable**.

A matching without blocking pairs is called **stable**.

It’s easy to verify if a *given* matching M is stable: for all men m we look up all women w that m ranks higher than M(m), and check if w also ranks m higher than M(w): if yes, then we can declare M unstable since (m,w) is a blocking pair. If we find no blocking pairs after having checked all men m, then we can declare that M is stable.

This takes at most O(n^2) time, assuming that ranks can be retrieved in constant time. Thus we have the following.

The next natural questions are:

- Do stable matchings always exist?
- If yes: can we always find them efficiently?
- If not: can we efficiently find matchings that minimize the number of blocking pairs?

This is a good place to pause and ponder!

### Developing a Solution

It turns out that (somewhat surprisingly!) stable matchings indeed always exist!

The algorithm for finding a stable matching works as follows. To begin with, we say that all men and women are *single*, i.e, unmatched to anyone so far.

Anticipating our need for stability, we take a greedy approach: the men attempt to match up to their best option by *proposing* to them. But notice that this may not be immediately workable: possibly multiple men have the same choice for their top option. This puts the ball in the woman’s court, so to speak, and again in the interest of being eventually stable, it’s intuitive that the woman will choose to align with the best offer she has among the proposals she’s recieved.

Also, since we finally want everyone to be matched, we will also ensure that proposals are not rejected simply because they seem unattractive in absolute terms: if a woman who’s single recieves one or more proposals, she will accept the best among them, no matter how good or bad they are.

After one round of proposals, the situation is as follows:

- some women (say W_\star \subseteq W) recieved one or more proposals and picked the best offer, and are no longer single;
- some women (say W_0 = W \setminus W_\star) recieved no proposals and are still single;
- some men (say V_\star \subseteq V) had their proposals accepted and they are no longer single ;
- some men (say V_0 = V \setminus V_\star) were turned down and are still single.

If W_0 = \emptyset, that’s… well, that’s awesome, because what that means is all men had distinct choices for their top preference, and so V_0 = \emptyset as well and we already have a matching where everyone has their best possible match: so this is clearly very stable and we are done.

On the other hand, it’s possible that W_0 \neq \emptyset, which is to say that some women are still single, and therefore there are some single men as well. Now, to make progress, single men go back to the drawing board and propose *again*. Now, a natural question at this point is the following:

Should the currently single men try their luck again with women who’ve rejected them?

Well, since they were rejected for good reason (said women had better offers), and the reason has not gone away, it is clearly a waste of time for men to go back to women who’ve rejected them. So what they do instead is to propose to the *next best option*. Now: what if their next best option is *not* a single woman? Well, suppose m decides to not approach w because w is matched to some m^\star in the first round. Then m will eventually be matched to someone who’s worse than w, and *if* w happened to prefer m over m^\star, then (m,w) will eventually be a blocking pair.

However, recall that this is exactly the situation we want to avoid. So we’re going to have m propose to their next best option *irrespective* of whether they are single or not. From the woman’s perspective, they are going to recieve proposals again, and we’ll let them pick the best offer, *even if it means breaking off their current engagement*.

After this second round of proposals we again have some single men and women, and some engagements. Note that the following invariant is true:

Any woman who was not single at the end of the first round remains engaged at the end of the second round as well.

Men, on the other hand, may become single again. At this point, we simply continue as before: at the end of every round, the single men continue to propose to their current best option, and the women continue to accept the best offer that they have. We continue this until there are no single men left.

### The Algorithm and its Properties

Here’s pseudocode (borrowed from Wikipedia) summarizing the algorithm, which is due to Gale and Shapley. The version below is morally equivalent to our description above, except that all proposals happen one by one, and it turns out that this way of looking at it simplifies the analysis.

```
is
algorithm stable_matching and w ∈ W to free
Initialize m ∈ M while ∃ free man m who has a woman w to propose to do
on m's list to whom m has not yet proposed
w := first woman if ∃ some pair (m', w) then
if w prefers m to m' then
' becomes free
m
(m, w) become engagedend if
else
(m, w) become engagedend if
repeat
```

It turns out that this procedure:

- terminates in finite time (in fact, after O(n^2) proposals have been made)
- outputs a perfect matching M between the men and the women that has
**no blocking pairs**.

The first property follows from the fact that men never propose twice to the same woman, so the number of proposals made is \leqslant n^2 . Also note that no man m is rejected by *all* women: this can only happen if all the women have found better engagements (which are necessarily distinct — notice that the set of engagments at any stage of the algorithm always forms a valid matching), but there are only n-1 men other than w: so this is not feasible.

So we know that the `while`

loop terminates, and that once it does we have a matching M.

It remains to show that M is stable. But if M has a blocking pair (m,w), then w was proposed to by m before m proposed to M(w), and since (m,w) are not matched in M, it must be the case that w prefers M(w) over m, so (m,w) cannot be a blocking pair after all.

This brings us to the following claim:

The output of the Gale-Shapley algorithm has a couple of interesting properties. First off, it turns out that the output is not just stable, but also qualitatively very good. Let us define, for a man m, their optimal match as the best woman that m can be matched to in any stable matching. It turns out that M matches all men to their optimal matches!

Also, the output of GS is *weakly Pareto optimal*, which is to say that there is *no matching* (stable or otherwise), where *all* the men are better off.

We state these claims above without proof. The interested reader should look them up!

### References

Numberphile video about the algorithm