Overview
Deferred acceptance (DA), also called the Gale–Shapley algorithm, is a procedure for matching two sides of a market—such as students to schools or residents to hospitals—using rank-ordered preferences and capacities. It proceeds in rounds of proposals and tentative holds; acceptances are “deferred” until the process ends. The DA algorithm produces a stable matching: there is no student–school pair that would prefer each other over their assigned outcomes (a “blocking pair”). In student-proposing form, truthfully ranking schools is a safe strategy for students (strategy-proofness), and the outcome is the best stable assignment for them among all stable assignments. DA is the workhorse mechanism in modern market design for school admissions and medical residencies.
Origins and Credit
David Gale and Lloyd Shapley introduced the algorithm and the stability concept in 1962. Alvin Roth later showed that versions of DA could explain and improve real labor markets (e.g., medical residency matches) and helped redesign school choice systems to use DA. Shapley and Roth received the 2012 Nobel Prize in Economics for this work on stable allocations and market design.
Core Idea and Mechanics
Inputs:
- Each participant on the proposing side (e.g., students) submits a strict ranking of options on the receiving side (e.g., schools).
- Each option on the receiving side has a capacity and an ordering over proposers. In school choice, this is a priority rule (siblings, neighborhood, lottery tie-breaks), not a preference per se.
Student-proposing DA proceeds as follows:
- Round 1: Each student “proposes” to their first-choice school. Each school tentatively holds up to its capacity the highest-priority proposers and rejects the rest.
- Round 2: Rejected students propose to their next-choice school. Schools consider new proposers together with any they were holding, keep the highest-priority up to capacity, and reject the rest.
- Continue: Repeat until no rejections occur. Tentative holds become final assignments.
Two central properties follow (under standard conditions like strict preferences/priorities and no couples):
- Stability: No blocking pair exists. There is no student who prefers a school that has either an open seat or has admitted someone with lower priority, and that school does not prefer (by its priority) that student to an admitted one.
- Proposer optimality and strategy-proofness: Among all stable matchings, the DA outcome is the proposers’ (students’) most preferred. Reporting true preferences is a dominant strategy for proposers; they cannot improve their assignment by misreporting.
Key Assumptions and Conditions
- Two-sided matching with capacities: Each seat can accept at most one proposer; each school has a fixed number of seats.
- Ordinal inputs only: No money changes hands; both sides provide rank orderings (or priorities) over the other side.
- Responsive/prioritized choice on the receiving side: A school’s choice over sets of students is consistent with its priority ordering and capacity (substitutability), ensuring existence of a stable match.
- Strict rankings or tie-breaking: When indifferences exist (ties), a tie-breaking rule (often lottery-based) is applied; properties like strategy-proofness refer to the induced mechanism.
- No couples (or special handling): Joint preferences of couples can break standard guarantees; real systems use extensions with weaker theoretical properties.
Implications
- Fairness via stability: Eliminates justified envy: no student with higher priority is denied a seat in favor of a lower-priority student at a school they prefer.
- Safe to “rank sincerely” for proposers: Students should list schools in true order of preference; strategic rank-ordering does not help them under student-proposing DA.
- Distributional pattern: Proposers do weakly better than in any other stable matching; receivers do weakly worse. This makes the choice of proposing side a policy decision.
- Robust implementability: DA handles large markets and complex priority structures and is highly resistant to manipulation, enabling transparent public processes.
- Predictable enrollment: The “rural hospitals theorem” (in many-to-one settings) implies the set of filled positions and number of matches are invariant across stable matchings, aiding capacity planning.
Example in Practice
Citywide high school assignment with student-proposing DA. Students submit rankings of schools; each school has capacity and priorities (siblings, zone, then lottery). The DA algorithm runs:
- In early rounds, popular schools tentatively hold top-priority applicants and reject others, who move down their lists.
- As rejections propagate, less popular schools fill, possibly displacing lower-priority tentative holds with higher-priority late proposers.
- When no further rejections occur, assignments finalize.
Operational consequences: students maximize their chance of a desirable seat by ranking sincerely; ranking a “safety” school high does not protect them beyond what their priority already provides. Compared with the Boston mechanism, DA reduces the penalty for optimism and produces stable assignments that withstand appeals based on priority violations.
Limitations and Common Misunderstandings
- Not necessarily Pareto efficient overall: Some unstable assignments can make everyone better off than a stable one; DA prioritizes stability over potential efficiency gains that violate priorities.
- Strategy-proofness is one-sided: Only the proposing side has dominant-strategy truth-telling. If the receiving side can misreport preferences (or if priorities are manipulable), they may gain.
- Ties and randomness: Tie-breaking lotteries can materially affect outcomes; while the mechanism remains stable relative to broken ties, ex post fairness perceptions may vary.
- Couples and complementarities: Joint preferences can cause nonexistence of a stable matching or computational challenges; practical systems adopt heuristics.
- Choice of proposer matters: School-proposing DA is stable but tends to favor schools over students. Policy makers typically choose student-proposing to protect families.
- Inputs must reflect true priorities: If priority rules omit relevant factors (e.g., specialized program fit), stability may not align with substantive fairness or mission goals.
Related Concepts (names only)
Stable Matching; Strategy-Proofness; Boston Mechanism; Top Trading Cycles; Rural Hospitals Theorem; Matching with Contracts.
