Matching & Mechanism Design

Animate the Gale-Shapley algorithm and explore stable matching step by step

Stable Matching

Two groups rank each other. Can you pair everyone up so that no two people would rather be with each other than with their partners? Always.

Gale-Shapley Algorithm

Press Step to make one proposal at a time, or Run All to finish. Green marks current matches and red strikethroughs mark rejections; New Instance deals fresh preferences.

Proposer Preferences

Alice:Elm St.Maple Ln.Pine Rd.Oak Ave.
Bob:Pine Rd.Maple Ln.Oak Ave.Elm St.
Carol:Maple Ln.Oak Ave.Pine Rd.Elm St.
Dave:Pine Rd.Elm St.Maple Ln.Oak Ave.

Accepter Preferences

Elm St.:CarolAliceBobDave
Oak Ave.:BobAliceDaveCarol
Pine Rd.:DaveCarolBobAlice
Maple Ln.:BobCarolAliceDave
Go deeper:Stable Matching

The stable matching problem asks: given two groups with ranked preferences over each other, can we find a matching where no pair would prefer to break their current matches to be together instead?

In 1962, David Gale and Lloyd Shapley proved the answer is always yes, and gave an elegant algorithm to find such a matching. Their work earned Shapley the 2012 Nobel Prize in Economics (shared with Alvin Roth, who applied the theory to real-world markets like medical residency matching and school choice).

Proposers (left) propose to their most preferred accepter who hasn't rejected them yet. Accepters hold the best proposal they've received and reject the rest.

Key insight: The algorithm always terminates with a stable matching. It is proposer-optimal — each proposer gets the best partner they could achieve in any stable matching.

Go deeper:Properties of Stable Matching
  • Stability — no blocking pair exists (no two people who would rather be matched to each other)
  • Proposer-optimal — the proposing side gets their best stable partner
  • Accepter-pessimal — the accepting side gets their worst stable partner
  • Strategy-proof for proposers — proposers can't benefit from misreporting their preferences
  • Polynomial time — at most n² proposals needed for n pairs

Key Takeaways

  • Stable matching always exists — Gale-Shapley guarantees it
  • Side matters — the proposing side gets the better deal
  • Real-world impact — used for medical residencies, school choice, organ donation

Spot a mistake or have an idea?

Search