The Gale–Shapley Algorithm

Propose, hold, reject

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Deferred acceptance: apply, hold the best, reject the rest, repeat.
• It always ends with a stable matching, within n² applications.
• The applying side gets its best stable outcome.

Steps

1. Deferred acceptance
2. Count the applications
3. Who benefits?
4. Schools propose
5. Watch deferred acceptance
6. Can lying help?