Gale-Shapley Algorithm
Deferred Acceptance (DA) finds a stable matching — one with no blocking pairs. A blocking pair is two participants who both prefer each other over their current match.
Algorithm Steps:
- Each free proposer proposes to their most-preferred unproposed receiver
- Receiver tentatively accepts if free, or if they prefer the new proposer over current
- Rejected proposers become free and propose to their next choice
- Algorithm terminates when everyone is matched
Key Properties:
Stable Truthful for Proposers Proposer Optimal Receiver Pessimal
Nobel Prize 2012:
Alvin Roth & Lloyd Shapley received the Nobel Memorial Prize in Economic Sciences for the theory of stable allocations and the practice of market design.
Preference Tables
A-Proposes Result
B-Proposes Result
The Proposer Advantage
When running Gale-Shapley with different proposing sides on identical preferences, the outcomes differ systematically:
Proposer Optimality:
Proposers always receive their best partner in any stable matching. Receivers get their worst stable partner. This is the DA algorithm's most profound asymmetry.
Satisfaction Score:
Calculated as 1 - (average_rank - 1) / (n - 1), so getting your 1st choice = 1.0, last choice = 0.0.
Proposers: High satisfaction Receivers: Low satisfaction
Deferred Acceptance (DA)
Boston Mechanism
Top Trading Cycles (TTC)
School Choice: Algorithm Comparison
Three major algorithms for school assignment each make different trade-offs between stability, efficiency, and strategy-proofness.
DA (Student-Proposing)
Stable Strategy-proof Not Pareto optimal
Used in NYC high schools, Boston (after reform)
Boston Mechanism
Not stable Manipulable Can be efficient
Old Boston, some European cities — rewards strategic play
Top Trading Cycles
Not stable Pareto optimal Strategy-proof
Used in kidney exchange, house allocation problems
NRMP: The National Resident Matching Program
History: The NRMP has matched medical graduates to residency programs since 1952. Before it, hospitals competed chaotically — making offers years early and students accepting under pressure.
Timeline:
- 1952: First centralized match using a hospital-proposing algorithm
- 1984: Roth proved NRMP was equivalent to hospital-proposing DA (hospital-optimal)
- 1998: Switched to applicant-proposing DA — more fair to residents
- 2012: Alvin Roth wins Nobel Prize partly for this work
Couples Problem:
Couples who want to match at nearby hospitals create a constraint that can make stable matchings non-existent. The NRMP uses heuristics to handle this.
Many-to-One Matching:
Each hospital has multiple slots (quota). When hospitals propose, they can fill slots one at a time. The algorithm generalizes to ensure each hospital fills at most its quota slots.
DA Student-Proposing
DA School-Proposing
Boston Mechanism
Top Trading Cycles
Welfare Analysis: Key Insights
Monte Carlo simulation over random preference profiles reveals the expected performance of each algorithm.
Student-Proposing DA:
Maximizes student welfare among all stable matchings. No other stable mechanism gives all students a weakly better match.
Boston vs. DA:
Boston often gives more 1st-choice assignments (looks better superficially), but punishes students who don't strategize. Sophisticated students gain; unsophisticated lose.
Top Trading Cycles:
Pareto optimal — no student can be made better off without making another worse off. But may violate school priorities (not stable).
Nobel insight: Good market design requires understanding the incentive properties of mechanisms, not just average outcomes.