School Choice Mechanism
Deferred Acceptance · Top Trading Cycles · Boston
A city wants to let families apply to public schools by preference. Families submit ranked lists; schools carry priority orders (sibling preferences, walk-zone, lottery). Who gets which seat? The answer depends on which mechanism the district runs — and the choice has real consequences for stability, strategy-proofness, and whose children end up where. This page walks through the Gale-Shapley deferred-acceptance mechanism (Abdulkadiroğlu & Sönmez 2003), top trading cycles, and the priority-based Boston mechanism whose documented failures drove the 2005 reform.
Problem context
Students, schools, priorities, preferences
A school district has a set of public schools, each with limited capacity. Every student (really, every family on behalf of their child) submits a ranked preference list over schools. Each school has a priority order over students determined by district policy — typically a combination of sibling priority, walk-zone priority, and a random tie-breaking lottery. The operational problem is to produce a single assignment: every student gets at most one seat, every school respects its capacity, and ideally the result is fair, stable, and strategy-proof.
The mathematical framing comes from Gale & Shapley (1962) on the college-admissions and stable-marriage problems, and was brought into public-schools-assignment practice by Abdulkadiroğlu & Sönmez (2003). Their key observation: the Boston Public Schools' historical mechanism — which processed first-choice applications first and only considered lower-ranked choices after — was not strategy-proof. Families who understood how it worked gamed their preference lists; families who did not (disproportionately low-income and new-immigrant households) reported sincere preferences and ended up with worse outcomes.
New York City's Department of Education adopted a student-proposing deferred-acceptance mechanism for its high-school match in 2003 (Abdulkadiroğlu, Pathak & Roth, 2005, AER). Boston Public Schools followed in 2005, after an extensive public process that included direct input from the research team. Alvin Roth shared the 2012 Nobel Prize in Economic Sciences with Lloyd Shapley “for the theory of stable allocations and the practice of market design,” citing school choice among the signature applications.
Reform timeline
Multi-stakeholder framing
The three mechanisms
DA, TTC, and Boston — different designs, different consequences
| Symbol | Definition | Domain |
|---|---|---|
| I | Set of students | |I| = n |
| S | Set of schools | |S| = m |
| qs | Capacity of school s | ℕ⁺ |
| ≻i | Strict preference order of student i over schools | total order on S |
| ≻s | Priority order of school s over students | total order on I (after tie-breaking) |
| μ | Matching: function I → S ∪ {∅} | |μ-1(s)| ≤ qs |
2. Each school s tentatively accepts its top qs proposers by ≻s; rejects the rest.
3. Rejected students propose to their next-preferred school.
4. Repeat steps 2–3 until no student is rejected.
// Properties (Gale-Shapley 1962; Roth 1982):
// - Produces a STABLE matching (no student-school blocking pair)
// - STRATEGY-PROOF for students (truthful reporting is a dominant strategy)
// - Student-optimal among stable matches
// - NOT Pareto-efficient (TTC dominates on efficiency)
2. Identify a cycle (must exist in a finite directed graph where every node has out-degree 1).
3. Each student in the cycle is assigned the school she points to; remove them from the problem.
4. Reduce school capacities; if capacity reaches 0, remove that school. Repeat from step 1.
// Properties (Abdulkadiroğlu & Sönmez 2003):
// - Pareto-EFFICIENT (no student can be made better off without making another worse off)
// - STRATEGY-PROOF for students
// - NOT always stable (may produce blocking pairs)
Round 2: With remaining capacity, fill from second-choice applicants in priority order.
...
Round k: Fill remaining capacity from k-th-choice applicants until nothing remains.
// Properties — the reason this mechanism was replaced:
// - NOT strategy-proof — ranking a popular school first is risky
// - NOT stable in general
// - Rewards families who understand the mechanism; punishes sincere families
// - Abdulkadiroğlu-Pathak-Roth-Sönmez (2005 AER) showed this in the BPS data and drove the 2005 reform
The core tradeoff between DA and TTC is stability vs. efficiency. DA is stable (no student and school can both prefer each other to their current match), which matters for legal and political legitimacy. TTC is Pareto-efficient but can produce unstable matches in which a student and school who prefer each other end up separated. Most US school districts chose DA, prioritising stability and the simpler legal story.
The impossibility (Roth, 1982): no mechanism is simultaneously stable, Pareto-efficient, and strategy-proof for students. Any district must give up at least one. DA gives up efficiency; TTC gives up stability; Boston gave up strategy-proofness. The third is the worst choice because it penalises the least-informed families.
Interactive comparison
Run all three mechanisms on the same instance; compare outcomes
DA vs TTC vs Boston
About the solver. Preferences and priorities are drawn randomly, with a Boston-flavoured bias that makes 1–2 schools substantially more popular than others (this is where the Boston mechanism's manipulability matters most). The DA and Boston implementations follow the textbook pseudocode. TTC builds the student-school pointer graph and detects cycles iteratively. All three mechanisms are polynomial in (n, m) for the no-indifferences case.
Solution interpretation
What to look for when you compare
DA produces the same or more first-choice assignments than TTC in most random instances, though TTC can overtake DA on specific instances because it is Pareto-efficient. The gap is usually small; both are far better than Boston on truthful reports.
Boston's first-choice count looks good when families report truthfully — but the mechanism gives families an incentive to lie about their first choice if they fear rejection there. In real deployments, sophisticated families routinely misreported; the apparent first-choice rate was inflated because families only ranked schools where their priority was high enough to guarantee admission.
TTC can produce blocking pairs: a student i and a school s can both prefer each other to i's TTC assignment and s's current roster. This is the stability failure that made US districts choose DA over TTC despite TTC's efficiency advantage.
Walk-zone priorities substantially reshape the match. Adding a walk-zone bump for students living near a school concentrates neighbourhood students at that school — reducing travel time but also reducing cross-neighbourhood integration. This is a policy choice, not a technical one.
Limitations & Critique
What the mechanisms cannot fix
Boston-mechanism manipulability — the historical lesson
The original Boston mechanism was not a neutral algorithm: families who understood it manipulated their preference rankings to secure a good school, while families who reported sincerely were punished. This was a documented, racially-patterned equity failure, not an abstract theoretical concern. The reform history is the lesson.
Preferences are not welfare
Mechanisms optimise stated preferences. What families can rank is constrained by the information they have, the commute they can manage, and the schools they even know about. Children from households without internet access or English-language fluency systematically submit shorter, less-informed lists — and get worse matches even under strategy-proof mechanisms.
Stability vs. efficiency is a real sacrifice
DA gives up Pareto-efficiency in exchange for stability. In some instances a student could be made strictly better off without hurting anyone — but DA leaves that student worse off. TTC would fix it but produces unstable matches. The Roth (1982) impossibility is unavoidable.
Ties in priorities — single-tie-breaking distorts
Real priority orders have ties (many students share walk-zone priority). Converting to a strict order requires tie-breaking — single (one lottery number per student across all schools) or multiple (one per school). Single tie-breaking is computationally simpler but creates welfare loss; multiple can help but can also produce blocking pairs. There is no neutral choice.
Neighbourhood segregation is not dissolved by any mechanism
No school-choice mechanism corrects underlying residential segregation. Walk-zone priorities concentrate neighbourhood students; pure-lottery systems split siblings and expand commutes. District-level design choices — which schools exist where, how they are funded — drive integration outcomes far more than mechanism choice.
Strategic schools, not just strategic families
Selective-admissions schools, charter networks, and private-school opt-outs operate outside the district match. The optimality theorems assume all schools participate; in practice the highest-capacity schools often do not, and the district match is the residual. The stability and efficiency claims apply only to the subset that did participate.
Extensions & variants
Active research directions
EADAM & efficiency-adjusted DA
Kesten (2010) proposes efficiency-adjusted DA with consent, recovering Pareto improvements when students voluntarily waive priorities.
Diversity constraints
Reserve seats for disadvantaged students; choice functions that respect affirmative-action policy. Kominers & Sönmez (2016); Kojima (2012).
Strategy-proofness in the large
As n grows, many mechanisms become approximately strategy-proof even if not exactly so. Azevedo & Budish (2019).
Tie-breaking design
Single vs. multiple tie-breaking has measurable welfare effects. Abdulkadiroğlu, Pathak & Roth (2009).
Strategic schools
When schools can misreport capacities or priorities, stability can break down. Sönmez (1997).
Integer-programming formulations
Capacitated two-sided matching as ILP for additional constraints (racial balance, grade distribution). Agarwal, Ashlagi, Azevedo, Featherstone & Karaduman (2021).
Dynamic assignment
Transfer requests, late arrivals, and multi-year matching. Dur, Kesten & Ünver (2019).
Chicago, New Orleans, Denver
Each district has extended the framework with local constraints: Chicago's selective-enrollment schools, New Orleans' post-Katrina universal enrollment, Denver's charter-district integration.
Key references
Cited above · DOIs where available
Related applications
Sister matching-market problems on this site