Watch the deferred acceptance algorithm pair members of Group A with Group B. Free proposers propose to their next-favourite choice each round; receivers tentatively hold the best offer and reject the rest, until every pair is stable and no one wants to swap.
The Gale-Shapley deferred acceptance algorithm always terminates in a stable matching: no man-woman pair would both prefer each other over their current partners. The animation shows tentative matches (violet), rejections (red, fading), and the final stable result (green).
Adjust the number of pairs (N) and press "New random preferences" to generate fresh preference lists. Click "Step" to advance one proposal round at a time, or "Auto-run" to watch it play out at the chosen speed until a stable matching is reached.
This exact algorithm allocates over 40,000 medical residents to hospitals in the United States every year through the National Resident Matching Program, and variants of it assign students to public schools in cities like New York and Boston.
This simulation models the stable marriage problem, formalized in 1962 by mathematicians David Gale and Lloyd Shapley in their paper "College Admissions and the Stability of Marriage." Given N members of Group A and N members of Group B, each with a ranked preference list over the other side, a matching is "stable" if there is no pair who both prefer each other to their assigned partners. The deferred acceptance algorithm constructs such a matching by having proposers repeatedly propose to their next-favourite unrejected choice, while receivers tentatively hold the best offer received so far and reject the rest — continuing until every proposer is matched.
Beyond its elegant mathematics, stable matching underlies some of the most consequential algorithms in modern life: it assigns medical residents to hospitals through the National Resident Matching Program, allocates students to public schools in cities such as New York and Boston, and powers kidney exchange programs that find chains of compatible donor-patient pairs. The work earned Lloyd Shapley and market designer Alvin Roth the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design."
Stable matching is a pairing between two equal-sized groups, each member holding a ranked preference list over the other side, such that no two unmatched people would both rather be paired with each other than with their current partners. Such an unstable pair is called a "blocking pair." The Gale-Shapley theorem proves that a stable matching always exists for any set of preference lists and can be found by the deferred acceptance algorithm, regardless of how the preferences are structured.
Every unmatched member of the proposing group (Group A) proposes to the highest-ranked member of Group B they have not yet proposed to. Each member of Group B compares all proposals received in that round (plus any partner they are currently holding) and tentatively accepts the one it ranks highest, rejecting the rest. Rejected proposers move on to their next choice in the following round. This repeats until every proposer is matched — no one is ever accepted permanently until the very end, hence "deferred" acceptance.
Choose the number of pairs with the "Pairs (N)" slider and click "New random preferences" to generate fresh random preference lists for both groups. Press "Step" to advance exactly one proposal round, watching violet lines form as tentative matches and red dashed lines flash for rejections, or press "Auto-run" to let the algorithm run automatically at your chosen speed until the stable matching (shown in green) is reached.
The most famous application is the National Resident Matching Program, which has assigned over a million new doctors to U.S. hospital residency programs since the 1950s (the algorithm was independently discovered by economist Alvin Roth to closely resemble a mechanism hospitals had already been using). Variants also run school-choice systems in New York City, Boston, and other districts to match students to schools, and kidney exchange programs use related matching theory to find long chains of compatible living-donor transplants that save thousands of lives.
Lloyd Shapley, who co-developed the algorithm with David Gale in 1962 purely as a mathematical curiosity, and economist Alvin Roth, who later applied it to design real-world matching markets such as kidney exchanges and school-choice systems, jointly received the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design." It remains a landmark example of abstract mathematics finding direct, life-saving practical application decades after its discovery.
When Group A does the proposing, the resulting stable matching is provably the best possible stable outcome for every member of Group A simultaneously — no other stable matching could give any proposer a partner they prefer more. Symmetrically, it is the worst stable outcome for every member of Group B, since receivers can only be matched with someone at least as good as their outcome under any other stable matching. Which side proposes therefore has a real distributional consequence, even though every stable matching is "fair" in the sense of having no blocking pairs.
Yes, for the proposing side: it is a dominant strategy for every member of Group A to submit their true, honest preference list, since no strategic misrepresentation can ever produce a better outcome for a proposer than truth-telling under this algorithm. However, the same guarantee does not hold for the receiving side (Group B) — in some cases a receiver could theoretically obtain a better partner by strategically rejecting a proposal they would have accepted under truthful preferences, though doing so requires detailed knowledge of everyone else's preferences that is rarely available in practice.
When Group A and Group B are different sizes, the algorithm still produces a stable matching, but the larger group necessarily has some members left unmatched. When individuals have ties in their preference lists (indifference between two or more options), the classical stability guarantee can weaken, and researchers have developed several tie-breaking variants — strong, weak, and super stability — each with different existence and complexity properties, an active area of algorithmic game theory research today.