COMPSCI320 Chap.3 Stable Matching and the Gale-Shapley Algorithm
Stable Matching and the Gale-Shapley Algorithm
Stable matching introduces the full design cycle on one problem: state it precisely, give an algorithm, prove termination and correctness, and bound its work.
This chapter explains blocking pairs and stability, traces the hospital-proposing algorithm on a three by three instance, and shows how to prove statements about every stable matching by exhibiting a pair that would block.
The proposals are traced one at a time, with the response to each, so the monotone behaviour behind the termination proof is visible: hospitals move down their lists and students only trade up.
Two original practice questions then use the same facts to build an instance and to prove that the output is always a perfect matching.
Stable matching also introduces a habit used for the rest of the semester. Every algorithm comes with three claims, that it terminates, that its output is correct and that its work is bounded, and each claim needs its own short argument.
Learning to separate them here makes the later greedy and flow proofs easier to organise.
What this chapter covers
- 01
Perfect matchings and preference lists
- 02
Blocking pairs and stability
- 03
Proposals, holds and rejections
- 04
Termination after at most n squared proposals
- 05
Proof by an exhibited blocking pair
Worked example · free
Run hospital-proposing Gale-Shapley
- 1H1 proposes to S2, who is free and holds H1.
- 1H2 proposes to S2, who prefers H1 and rejects H2.
- 1H3 proposes to S1, who holds H3; H2 then proposes to S3, who holds H2.
- 1No pair prefers each other to their partners, so the matching is stable.
Key terms
- Stable Matching
- A perfect matching in which no hospital and student both prefer each other to their assigned partners.
- Blocking Pair
- An unmatched hospital and student who would each rather be matched to the other than to their current partners.
- Proposal Sequence
- The ordered list of offers a hospital makes, moving down its preference list after each rejection.
- Perfect Matching
- A matching in which every hospital and every student is paired with exactly one partner.
Stable Matching and the Gale-Shapley Algorithm FAQ
Is a matching stable if one person would like to switch?
Yes, it can still be stable. Stability only fails when two people would both rather be matched to each other. If a hospital prefers another student but that student prefers her current partner, the pair does not block, so the matching survives. The definition protects mutual preference, not the happiness of every individual.
Why does the hospital-proposing algorithm always stop?
A hospital never proposes to the same student twice, because it moves down its list after every rejection. With n hospitals and n students there are at most n times n possible proposals, so the loop must end. When it does, every hospital is matched, since a free hospital that had proposed to every student would contradict the count of matched students.
How do I prove that a pair appears in every stable matching?
Assume some stable matching leaves the pair apart and look at their partners in it. If the two rank each other above those partners, they form a blocking pair, contradicting stability. This proof by an exhibited blocking pair is the main technique of the first tutorial, and the same move proves many other statements about stable matchings.
Does the order in which free hospitals propose change the result?
No. The hospital-proposing algorithm returns the same stable matching whichever free hospital proposes next, so a different queue order changes the list of events but not the final pairs. In a trace you should still state the order you use, because the marker checks each proposal and response against it.
Exam move
Run the algorithm on two new instances with different queue orders and check that the final pairs agree. Then write two short proofs by contradiction, each naming the assumed failure, the pair you construct and the two preferences that make it block. Finally practise explaining why the loop terminates in one sentence.
A useful closing exercise is to change one preference in the worked instance and rerun the algorithm, noting which proposals change and whether the final matching moves at all.
Then run the algorithm with the students proposing instead and compare the two stable matchings you obtain; the comparison shows that one instance can have more than one stable matching and that the proposing side does at least as well under its own algorithm.
Working through Stable Matching and the Gale-Shapley Algorithm in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Stable Matching and the Gale-Shapley Algorithm question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
