Stable Matching (Gale–Shapley)
Edit two-sided preferences, replay deferred acceptance, inspect blocking pairs and compare proposer-optimal stable outcomes.
By Riano · Published · Updated · Report a correction
Stable Matching: why an acceptance can change
Imagine three mentors and three learners. Everyone ranks every person on the opposite side, and each person can have one partner. Filling every place does not settle the problem: two people might both prefer to leave their assigned partners and work together. Stable matching asks whether any such pair remains. This explorer uses neutral names A, B, C and X, Y, Z so either side can make proposals.
A certificate based on two preferences
An unpaired combination is a blocking pair when both people prefer each other to their current situations. In this module, being unmatched ranks below every possible partner. Rank 1 means a first choice. A held pair does not block itself.
ranka(x) < ranka(M(a))
and rankx(a) < rankx(M(x)).
The green connections are engagements held for now. Dashed red connections identify blocking pairs in the current partial matching, rather than invalid edges. At the initial empty matching, every one of the 3 × 3 = 9 combinations blocks: both endpoints would prefer a partner to being unmatched. Only a completed matching with zero blocking pairs is labelled stable.
Deferred acceptance, one proposal at a time
- Choose the lowest-named free person on the proposing side.
- That person proposes to the next name on their ranking that they have not already tried.
- A free receiver holds the proposal. An engaged receiver keeps whichever proposer they rank higher, freeing the other person.
- Continue until nobody on the proposing side is free.
Rejections are counted as proposals too. Each proposer tries each receiver at most once, so there are at most n2 proposals; here that upper bound is nine. With equally sized groups and complete strict rankings, the process terminates with everyone matched. A receiver only trades upward. If a proposer preferred someone to their final partner, that earlier option was tried and rejected, so the receiver ended with someone they prefer. This rules out a blocking pair.
Predict the six-proposal competition
Use these original rankings, written from best to worst. X ranks B above A, which is the reason the first engagement can change.
| Left | Ranking | Right | Ranking |
|---|---|---|---|
| A | X, Y, Z | X | B, A, C |
| B | X, Z, Y | Y | A, C, B |
| C | Y, X, Z | Z | C, B, A |
- A proposes to X; X provisionally accepts A.
- B proposes to X; X prefers B, replacing A. Only B–X is held.
- A next proposes to Y, who accepts.
- C proposes to Y, who keeps the preferred A.
- C tries X, who keeps the preferred B.
- C proposes to Z, completing A–Y, B–X, C–Z.
After proposal 2, the four blocking pairs are A–Y, A–Z, C–Y and C–Z. After proposal 6 there are none. A would prefer X to Y, but X prefers B to A. B already has their first choice. C would prefer Y or X to Z, but both receivers prefer their held partners. This checks the final certificate independently of the animation.
Reproduce the replacement, then reverse the roles
Open the Stable Matching interactive module. Its controls operate on the rankings shown beside each participant.
- Select Competition under Scenario and Left (A, B, C) under Proposing side. Press Reset.
- Set Proposal step to 2. Confirm one held pair, four blocking pairs and the message that X switches from A to B.
- Press Finish. The displays show six proposals, three held pairs and zero blocking pairs. Press Play after Reset to replay at one proposal per second; Pause freezes the current step.
- Select Multiple stable outcomes, then Finish. Left proposes yields A–X, B–Y, C–Z in three proposals. Change Proposing side to Right (X, Y, Z) and Finish: A–Y, B–X, C–Z is also stable after three proposals. The lists stay unchanged; only the proposing side changes.
- Return to Competition and Left. Open Edit rankings, set A preference to Z > X > Y, then Finish. All left participants receive their first choices: A–Z, B–X, C–Y, with three proposals and no blocking pairs.
- Toggle Show blocking pairs, pan the graph and press Reset view. These presentation controls preserve the matching. Reset restarts the current ranking problem; selecting a scenario loads that scenario's original lists.
Stable does not mean equally happy
The module fixes the groups at three people each and permits only strict complete rankings, represented by one of six permutations. It does not model ties, unacceptable partners, unequal group sizes or colleges with several seats. Those require additional rules. The school-allocation motivation does not make this a policy model for actual admissions.
For strict complete lists, deferred acceptance gives each proposer their best partner among stable matchings. That is a restriction to stable outcomes, not a guarantee of everyone's first choice or a maximization of total happiness. The Multiple stable outcomes scenario makes the asymmetry visible: A and B receive first choices when the left proposes, while X and Y receive first choices when the right proposes. Both outcomes have zero blocking pairs.
In contrast, Bipartite Matching maximizes the number of compatible pairs without ranking preferences. Replay order changes intermediate engagements. The final proposer-optimal result for these strict rankings does not depend on which free proposer is selected first. The display checks all nine possible pairs after every proposal, which is practical for this small teaching example rather than a claim about an optimized large-scale implementation.
Read the original idea and its guarantees
These readings establish the matching model and its guarantees. The preference tables, six-proposal trace and interactive experiments in this article are original examples, checked separately against every possible complete pairing.
- David Gale and Lloyd S. Shapley, College Admissions and the Stability of Marriage, RAND P-2240 (1961). The original working paper introduces stable assignments and deferred acceptance. The full paper is available from RAND.
- A Course in Networks and Markets, Chapter 14: Two-sided Matchings. Sections 14.1–14.3 give the blocking-pair definition, termination and stability arguments, and the proposer-optimality guarantee. Its presentation can skip proposals that would be immediately rejected; this module records those rejections explicitly. The examples and control sequence above are specific to Riano.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Stable Matching (Gale–Shapley) module.
Try Stable Matching (Gale–Shapley) on Riano →