Topic 03 — CS 70 Discrete Mathematics
Stable
Matching
A beautiful algorithmic problem with real-world consequence — the Gale-Shapley algorithm assigns medical residents to hospitals, students to schools, and more. We prove it always works, always terminates, and has deep optimality properties.
The Problem
We have n jobs and n candidates. Each job has a ranked preference list of all candidates, and each candidate has a ranked preference list of all jobs. We want to find a stable matching — a one-to-one pairing where nobody has an incentive to break their assigned pair.
Definitions
A matching is a set of (candidate, job) pairs such that each candidate appears in at most one pair and each job appears in at most one pair. A perfect matching pairs every candidate and every job.
A pair (c, j) is a rogue couple in a matching M if:
- c and j are not matched to each other in M,
- c prefers j over their current match in M, AND
- j prefers c over their current match in M.
Both parties have mutual incentive to abandon their current assignments.
A matching M is stable if it has no rogue couples. Neither party has mutual incentive to defect.
Optimal candidate for job j: The best candidate that j is paired with in any stable matching.
Optimal job for candidate c: The best job c is paired with in any stable matching.
Job-optimal: A matching where every job gets its optimal candidate.
Candidate-pessimal: A matching where every candidate gets their worst possible job across all stable matchings.
The Propose-and-Reject Algorithm (Gale-Shapley)
Worked Example (DIS 1B)
Job Preferences
| Job | 1st | 2nd | 3rd |
|---|---|---|---|
| 1 | A | B | C |
| 2 | B | A | C |
| 3 | A | B | C |
Candidate Preferences
| Candidate | 1st | 2nd | 3rd |
|---|---|---|---|
| A | 2 | 1 | 3 |
| B | 1 | 3 | 2 |
| C | 1 | 2 | 3 |
Afternoon: A receives offers from Job 1 and Job 3. A prefers Job 2 over both, but Job 2 didn't propose to A. Between Jobs 1 and 3: A prefers Job 1 (rank 2) over Job 3 (rank 3). A says maybe to Job 1, rejects Job 3. B receives offer from Job 2, says maybe.
Evening: Job 3 crosses off A.
Afternoon: A has only Job 1: says maybe. B receives offers from Job 2 and Job 3. B prefers Job 1 most, but Job 1 proposed to A. Between Jobs 2 and 3: B prefers Job 3 (rank 2) over Job 2 (rank 3). B says maybe to Job 3, rejects Job 2.
Evening: Job 2 crosses off B.
Afternoon: A: holds Job 2. B: holds Job 3. Job 1 is rejected by A.
Evening: Job 1 crosses off A.
Afternoon: A: holds Job 2 ✓. B: holds Job 1 ✓. C: receives Job 3, says maybe ✓.
No rejections! Algorithm terminates.
A ↔ Job 2, B ↔ Job 1, C ↔ Job 3
Verify stability: Check all unmatched pairs for rogue couples.
- (A, Job 1): A prefers Job 2 over Job 1. No rogue couple.
- (A, Job 3): A prefers Job 2 over Job 3. No rogue couple.
- (B, Job 2): B prefers Job 1 over Job 2. No rogue couple (B is with Job 1).
- (B, Job 3): B prefers Job 1 over Job 3. No rogue couple.
- (C, Job 1): Job 1 prefers A over C. No rogue couple.
- (C, Job 2): Job 2 prefers B over C. No rogue couple.
Stable! ✓
Termination
The propose-and-reject algorithm terminates in at most n² days.
Each day where a rejection occurs, at least one job crosses at least one candidate off its list permanently. There are n jobs, each with a list of n candidates, giving n² total crossings possible. Since at least one crossing happens per non-terminating day, the algorithm runs for at most n² days. ∎
The Improvement Lemma
Once a candidate c receives a proposal and says "maybe," every subsequent proposal c holds is at least as good (by c's preferences). Candidate c's situation can only improve or stay the same over time.
A candidate c replaces a current held proposal only when a better offer arrives. So the job on c's "string" at any point is at least as good as any previous job on c's string. ∎
Every job proposes to candidates in decreasing order of preference. Once rejected by a candidate, a job never proposes to that candidate again.
Correctness — The Output Is a Stable Matching
The propose-and-reject algorithm always outputs a perfect matching (every candidate and job is matched), and the matching is stable (no rogue couples).
Perfect: No candidate can be unmatched. If candidate c received no proposals, that means all n jobs skipped c — impossible since each job works through its entire list before c could be last for all of them. Formally: if c is unmatched, some job j is also unmatched (by counting). But j would have proposed to c eventually. Contradiction.
Stable: Suppose for contradiction that (c, j) is a rogue couple in the final matching M. So c is matched to some j' and j is matched to some c', where c prefers j over j' and j prefers c over c'. Since j prefers c over c', j must have proposed to c before proposing to c' (jobs go down their list). By the Improvement Lemma, when j proposed to c, either c rejected j immediately (meaning c already had something better than j — contradicting c preferring j over current j') or c held j and later upgraded to something better. Either way, c ended with something at least as good as j — contradicting c preferring j over current match. Contradiction! ∎
Optimality — Job Optimal, Candidate Pessimal
When jobs propose, the output matching is job-optimal: every job is matched with the best candidate it could get in any stable matching.
When jobs propose, the output matching is candidate-pessimal: every candidate is matched with the worst job they receive in any stable matching.
Key True/False Statements (DIS 1B)
"There is a stable matching instance where in the jobs-proposing algorithm, every job ends up with its least preferred candidate."
Example: n=2 jobs {1,2} and candidates {A,B}. Job 1: A>B. Job 2: B>A. Candidate A: 2>1. Candidate B: 1>2. Algorithm: Day 1: Job 1→A (A holds), Job 2→B (B holds). No rejections. Match: {1↔A, 2↔B}. Job 1 got A (top choice — wait, that's optimal). Try symmetric version where everyone's last choice forces it. The key insight: pessimal for candidates doesn't mean pessimal for jobs in the same matching.
"If job J and candidate C are each other's top choice, then J and C are paired in every stable matching."
Proof: Suppose some stable matching M has J paired with C' ≠ C and C with J' ≠ J. Since J prefers C over C' and C prefers J over J', the pair (C,J) is a rogue couple in M. Contradiction. So J and C must be together in every stable matching. ∎
"If J and C rank each other last, they cannot be paired in any stable matching."
Counterexample: With n=2: Jobs {1,2}, Candidates {A,B}. Job 1: A>B, Job 2: A>B. Candidate A: 1>2, Candidate B: 1>2. The only valid matching is {1↔A, 2↔B}. Job 2 and Candidate B are each other's last choice, yet they must be paired. It is stable (no rogue couple: (A,2) — A prefers 1, no issue).
Practice Problems
Claim: In any execution, if a candidate receives a proposal on day i, they receive a proposal on every subsequent day until termination.
Proof: By the Improvement Lemma, a candidate who holds offer from job j on day i will either continue holding j (j re-proposes), or upgrade to j' ≻ j (some j' proposes). In either case, they receive a proposal on day i+1. By induction on days, they receive a proposal every day after i until termination. ∎
2 jobs {A,B} and 2 candidates {X,Y}. Job A: X>Y. Job B: X>Y. Candidate X: B>A. Candidate Y: A>B.
Trace the algorithm and find the stable matching. Is it job-optimal? Is it candidate-pessimal?