Stable Matching: The Gale-Shapley Algorithm

The problem: no wandering eyes allowed

Take two equal-sized groups — say, n applicants and n hospitals — each with a ranked preference list over the other side. A matching pairs every member of one group with exactly one member of the other. It is stable if there is no blocking pair: two people who are not matched to each other but who would both rather be matched to each other than to their current partners. If a blocking pair exists, the matching is fragile — those two have every incentive to defect together, whatever the official assignment says. David Gale and Lloyd Shapley proved in 1962 that a stable matching always exists for any set of preferences, and gave a constructive algorithm to find one — work that, extended by Alvin Roth to real-world market design, earned Shapley and Roth the 2012 Nobel Memorial Prize in Economics.

Deferred acceptance, step by step

The algorithm runs in rounds. Every unmatched proposer (say, applicant) proposes to the highest-ranked receiver (hospital) it has not yet proposed to. Each receiver looks at everyone who proposed to it this round plus anyone it is already tentatively holding, and keeps only its single favourite, rejecting the rest — even if that means dropping someone it accepted in an earlier round. Rejected proposers cross that receiver off their list and propose to their next choice in the following round. This repeats until every proposer is tentatively held by some receiver, at which point every tentative engagement becomes final.

while some proposer p is free and has not proposed to everyone:
    r = p's most-preferred receiver not yet proposed to
    p proposes to r
    if r is free:
        r tentatively accepts p
    elif r prefers p to its current tentative match p':
        r rejects p', tentatively accepts p     // p' becomes free again
    else:
        r rejects p                              // p tries its next choice
return the tentative matches — now final and stable

The word deferred is the key idea: a receiver's acceptance is always provisional until the very end, so a proposer can be "bumped" by a better offer at any point, but a receiver never permanently commits until no better proposal can possibly arrive. This is exactly why the process cannot cycle forever — every rejection permanently removes one proposer-receiver pair from consideration, and there are only n² such pairs, so the algorithm terminates in at most n² proposals.

Why the result has no blocking pairs

Suppose applicant A ends up matched to hospital H, but A actually prefers some other hospital H′ more. The algorithm guarantees A proposed to H′ at some point before reaching H (proposers always work down their list in order), and H′ rejected A — which only happens if H′ was already (tentatively or finally) holding someone it prefers over A. Since a receiver's held match can only improve over time, H′ still prefers its final match over A at the end. So A and H′ cannot form a blocking pair: whichever of the two evaluates the potential switch unfavourably blocks it. Running this argument over every applicant proves the final matching is stable.

Proposer-optimal, receiver-pessimal

The algorithm is not symmetric, and the asymmetry has real consequences. The side that proposes ends up with the best partner it could possibly have in any stable matching, while the side that receives ends up with its worst stable partner. Flip who proposes and you generally get a different — still stable — matching, better for the new proposers and worse for the new receivers. This is not a footnote: when the US National Resident Matching Program redesigned its algorithm in the 1990s with Roth's help, having medical students (rather than hospitals) act as the proposing side was a deliberate choice to make outcomes more favourable to applicants.

Frequently asked questions

Try it live

Everything above runs in your browser — open Stable Matching and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.