Animate the Gale-Shapley algorithm and explore stable matching step by step
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).
Step through the algorithm one proposal at a time. 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. Green highlights show current matches; red strikethroughs show rejections.
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. Click "New Instance" to generate fresh random preferences and watch how the algorithm adapts.