The Gale–Shapley (1962) algorithm for one-to-one matching with strict preferences. Each round has two phases: unmatched proposers make offers, then each receiver keeps the best offer it holds and rejects the rest. Edit the preferences below to build your own market.
Proposing side
Market
proposaltentatively heldrejectedfinal match
Preference lists (most preferred first)
xproposal this roundxheldxalready rejected
Edit the market
One agent per line: name: first, second, third, …. Both sides need the same number of agents (2–8), and each list must rank everyone on the other side exactly once.
What to notice
Proposers move down, receivers move up. A proposer only ever proposes further down its list; a receiver's tentative partner only ever improves. This monotonicity is why the algorithm stops after at most n² proposals.
Stability. Suppose proposer p prefers receiver r to p's final partner. Then p proposed to r earlier and was rejected, which happens only when r holds someone it likes better. Since r's partner only improves, r ends up with someone it prefers to p. So (p, r) cannot be a blocking pair.
Who proposes matters. Proposer-proposing DA yields the stable matching that every proposer weakly prefers to any other stable matching. It is also the worst stable matching for every receiver. Switch the proposing side above and compare the outcome tables.
Incentives. Reporting truthfully is a dominant strategy for proposers (Dubins–Freedman 1981; Roth 1982) but not for receivers. No stable mechanism is strategy-proof for both sides.
Use ←→ to step and space to play. Built for teaching by Peter Shum.