Stable Matching
Table of Contents
1. The Stable Matching Problem
Suppose an employment system wishes to match \(n\) jobs with \(n\) candidates such that each job would be matched with one candidate. Each job has an ordered preference list of candidates that it wants, and each candidate has a similar preference list for all the jobs. We want to match up these jobs with candidates in a "good" way.
Define a rogue couple in a matching as a job and candidate pair who prefer each other to their current partners. In other words, a rouge couple means that the matching is not "good" since it has room for improvement. We define a matching to be good, or stable, if it has no rogue couples.
Such an algorithm does exist, and it has been used for many decades by the National Resident Matching Program in the United States to match medical school students to residency training programs in teaching hospitals.
2. Propose-and-Reject Algorithm
The propose-and-reject algorithm [Gale-Shapley] is an iterative algorithm. We call each iteration one "day" for ease of understanding:
REPEAT
1. Each job makes an offer to the highest ranked candidate on its list who hasn't rejected it yet.
2. Each candidate says "maybe" (puts it on hold) to the job they rank best among their offers, and rejects the others.
3. If a job was rejected, it crosses that candidate off its list.
UNTIL no rejections occur.
OUTPUT resulting matching.
Jobs (Proposers)
Candidates (Receivers)
Algorithm Log
3. Analysis
There are three questions that we need to answer in order to verify this algorithm:
- Does the algorithm always terminate?
- Does it always output a matching?
- Is the matching always stable?
3.1. Termination
Theorem: The algorithm always terminates.
Proof: On every day when the algorithm doesn't terminate, at least one candidate is crossed off a job's list. Since the total length of all the lists is \(n^2\), this means the algorithm must terminate in at most \(n^2\) iterations (days).
3.2. Improvement Lemma
At this point, it is helpful to introduce the following lemma, which we will call the Improvement Lemma:
Lemma: Suppose job \(J\) offers to candidate \(C\) on day \(k\). Then on every day \(i \geq k\), \(C\) has on hold an offer from a job she likes at least as much as \(J\).
Proof: We proceed by induction on the day \(i\), with \(i \geq k\). The base case of when \(i=k\) holds, as she will choose the best among her offers.
Now suppose that the claim is true for some arbitrary \(i \geq k\). We would like to prove the claim for day \(i+1\). By our induction hypothesis, on day \(i\), \(C\) had an offer in hand from job \(J'\) which she likes at least as much as \(J\) (note that \(J'\) may be \(J\)). According to the algorithm, \(J'\) proposes to \(C\) again on day \(i+1\). Therefore, at the end of day \(i+1\), \(C\) will have in hand either \(J'\) or an offer from a job she likes even more: in both cases, she likes this job at least as much as \(J\). This completes the inductive step, and we are done. \(\square\)
3.3. Matching
Theorem: The algorithm always outputs a matching.
Proof: We proceed by contradiction. Suppose that some job \(J\) is not matched at the end of the algorithm.
Then \(J\) must have made an offer to every candidate — and got rejected. By the Improvement Lemma, every candidate therefore has an offer at termination. So, \(n\) candidates have offers from \(n-1\) jobs, which is a contradiction! \(\square\)
3.4. Stability
Theorem: The output matching is always stable.
Proof: Suppose that the output matching is:
\begin{align} \mathcal{M} = \{ \dots (J, C), \dots , (J',C'), \dots \} \notag \end{align}and \(J\) likes \(C'\) more than \(C\).
By the algorithm, \(J\) proposed to \(C'\) before proposing to \(C\), and got rejected. By the Improvement Lemma, \(C'\) must like \(J'\) at least as much as \(J\), and therefore they are not a rogue couple. Since \(J\) and \(C'\) were arbitrary, we know that there does not exist any rogue couples. \(\square\)
4. Optimality
The thing is, there may be multiple stable matchings for a problem. In other words, we can define some level of optimality to the stable matching our algorithm finds. In fact, it appears that the algorithm favors the party that is proposing, and disadvantages the party that is doing the rejecting.
More specifically, for a job \(J\), the optimal candidate for \(J\) is the best candidate \(J\) has in any stable matching. It follows that the job-optimal matching is the stable matching in which each job is matched with its optimal candidate.
Theorem: The matching output of the algorithm is job-optimal.
Proof: It is sufficient to prove that \(\forall k \geq 0 \: P(k)\), where \(P(k)\) means that on day \(k\), no job gets rejected by its optimal candidate — in other words, each job ends up with its optimal candidate. We proceed by induction on \(k\).
The base case \(k=0\) is true since there are no rejections on day 0.
Next, suppose that there are no such rejections of the job's optimal candidate through day \(k\). We now want to prove that the same happens on day \(k+1\).
Suppose for contradiction that job \(J\) gets rejected by its optimal candidate \(C^*\) in favor for some job \(J^*\). Since \(C^*\) is optimal for \(J\), there exists a stable matching as follows:
\begin{align} \mathcal{M} = \{ \dots (J, C^*), \dots , (J^*, C), \dots \} \notag \end{align}We know that \(C^*\) prefers \(J^*\) to \(J\) because \(J\) was rejected in favor of \(J^*\). By the inductive hypothesis, \(J^*\) has not yet been rejected by its optimal candidate. Hence, since \(J^*\) is offering to \(C^*\) now, \(J^*\) must like \(C^*\) at least as much as its optimal candidate, hence at least as much as \(C\). But \(C\) is supposed to be the optimal candidate for \(J^*\), which is a contradiction! Therefore, the algorithm must always output the job-optimal matching. \(\square\)