Two-Sided Matching and the Deferred Acceptance Algorithm

Core Idea

In two-sided matching markets, such as doctors and hospitals or students and schools, participants on each side have preferences over the other side and prices do not clear the market. A matching is stable if no pair of agents would both rather be matched to each other than to their assigned partners. David Gale and Lloyd Shapley showed in 1962 that a stable matching always exists in the basic model and that their deferred acceptance algorithm finds one. The matching it produces is the best stable matching for every member of the proposing side, and truthful reporting is a dominant strategy for that side.

How It's Best Learned

Give students a three-by-three set of preference lists and have them run deferred acceptance by hand, round by round, recording tentative holds and rejections. Then have them check every possible blocking pair in the result and in an alternative matching. Finally, swap which side proposes and compare the outcomes, which shows that the choice of proposing side matters.

Common Misconceptions

• A stable matching gives everyone their first choice. (Stability only rules out pairs who would both rather be together; many agents may get lower-ranked partners.)
• In deferred acceptance, a receiver who accepts an offer is bound to it. (Acceptances are tentative; a receiver keeps the best offer so far and drops it if a preferred proposer arrives later, which is why the algorithm is called deferred acceptance.)
• Deferred acceptance makes truthful reporting a dominant strategy for everyone. (It is strategy-proof for the proposing side only; no stable mechanism is strategy-proof for both sides in general.)

Explainer

Many markets match people rather than sell goods at a price. Medical graduates are matched to hospital residencies, students to public schools, and workers to some jobs. Each side has preferences over the other, and a match requires both. The design question is how to turn preference lists into an assignment that participants will accept.

The key requirement is stability. A matching is stable if there is no blocking pair: no proposer and receiver who both prefer each other to the partners they were assigned. If a blocking pair exists, its members have reason to break away and make a private deal, and the assignment can unravel.

David Gale and Lloyd Shapley, in their 1962 article "College Admissions and the Stability of Marriage," proved that a stable matching always exists in the basic model and gave a procedure that finds one, now called deferred acceptance. It runs in rounds. Each unmatched proposer applies to the most preferred receiver who has not yet rejected them. Each receiver looks at everyone who has applied, including the one held from the last round, keeps the best acceptable applicant, and rejects the rest. Rejected proposers move down their lists. The process ends when no one is rejected, and the tentative holds become final.

Why is the result stable? Suppose proposer P prefers receiver R to P's final partner. Then P applied to R earlier and was rejected, which happens only if R was holding someone R liked better. R's final partner is at least as good as that applicant, so R does not want P. No blocking pair can exist.

The algorithm has two further properties. The result is proposer-optimal: every proposer gets the best partner they could have in any stable matching, and every receiver gets the worst. And it is strategy-proof for proposers, as later shown by Lester Dubins and David Freedman and by Alvin Roth: no proposer can gain by misreporting preferences. Roth also showed that no stable mechanism is strategy-proof for both sides.

These ideas moved into practice. The National Resident Matching Program uses an applicant-proposing variant, and several large school districts, including New York City, adopted deferred acceptance for school choice. Roth and Shapley shared the 2012 Nobel Memorial Prize in Economic Sciences for the theory of stable allocations and the practice of market design.