🏫

Public schools cannot auction seats to the highest bidder. Families rank schools, schools have priorities, and a mechanism assigns seats. The old Boston system quietly punished families who ranked honestly. Deferred acceptance fixed that.

School choice and design without money

Many important markets forbid prices: school seats, organ transplants, cadet postings. Deferred acceptance carries over from the marriage market to school choice, where it gives stable assignments and makes honest ranking a dominant strategy for families. This lesson stays with ordinary school choice; matching with wages, schedules, or other contract terms requires an extended model.

From earlier lessons

Two quick ones before we start.

Deferred acceptance produces a matching with no...

A mechanism is strategy-proof if telling the truth is...

Predict, then play

Three students, three schools with one seat each. Students have preferences; schools have priority orders. Run student-proposing deferred acceptance.

Why did that happen?

Take a guess, then reveal the reason

Two students want school A, but A has one seat and a priority order, so it keeps the higher-priority student and rejects the other, who then tries their next choice. That rejection cascades: the displaced student bumps someone at the next school, and so on, until everyone is placed with no lingering blocking pair. Because a student never loses a seat by aiming high first, listing schools in true order is always safe. The Boston mechanism lacked this property, so families had to strategize about where to rank popular schools.

The math

Definition, school choice

Treat students as proposers and school priority orders as the receiving side’s preferences. Student-proposing deferred acceptance yields a stable assignment (no student-school pair both prefer each other to their assignment) and is strategy-proof for students: truthful ranking is a dominant strategy. If agreements also specify wages, schedules, or other terms, each partner-term pair is a contract. Stability and cumulative-offer results in that richer setting require substitutable choice functions, which the school-seat game here does not model.

Run student-proposing DA. Round 1: $s_1 \to A$ , $s_2 \to A$ , $s_3 \to B$ . School $A$ holds its higher priority $s_2$ and rejects $s_1$ . Round 2: $s_1 \to B$ ; $B$ prefers $s_1$ to its current $s_3$ , so it swaps, rejecting $s_3$ . Round 3: $s_3 \to A$ , rejected (A keeps $s_2$ ). Round 4: $s_3 \to C$ , accepted. Final: $s_2 \to A$ , $s_1 \to B$ , $s_3 \to C$ , a stable assignment.

Contrast with TTC, which would maximize efficiency but can violate priorities. School districts that value respecting priorities (stability) choose DA; the choice between DA and TTC is a real design trade-off, not a matter of one dominating the other.

Work it out

Trace the rejection chain

Students propose to their top schools: $s_1$ and $s_2$ both go to $A$ , and $s_3$ goes to $B$ . School $A$ ranks $s_2 > s_1$ , so it tentatively holds $s_2$ and rejects $s_1$ .

$s_1$ now proposes to its second choice, $B$ , which already holds $s_3$ . Since $B$ ranks $s_1 > s_3$ , it swaps to $s_1$ and rejects $s_3$ . Displaced, $s_3$ proposes to $A$ , which keeps $s_2$ and rejects it; then $s_3$ proposes to $C$ , which accepts. The chain settles at $s_2 \to A$ , $s_1 \to B$ , $s_3 \to C$ . Every student ranked honestly, and none could have done better by lying, which is exactly the property the old Boston mechanism lacked.

Key idea

Student-proposing deferred acceptance gives a stable school assignment and makes truthful ranking a dominant strategy for students. Adding contract terms requires extra assumptions and a richer cumulative-offer model.

Check yourself

Check yourselfapply

Both s1 and s2 rank school A first, but A has one seat. How does deferred acceptance resolve it?

Check yourselfanalyse

Why is it safe for a family to rank schools honestly under deferred acceptance?

Check yourselfbrings back: top trading cycles

How does deferred acceptance for school choice differ from top trading cycles?

Sources

Hatfield, J. W., and Milgrom, P. R. (2005). Matching with contracts. American Economic Review, 95(4), 913-935.
Abdulkadiroğlu, A., and Sönmez, T. (2003). School choice: a mechanism design approach. American Economic Review, 93(3), 729-747.