Lesson plan
Gale–Shapley algorithm
In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm, propose-and-reject algorithm, or Boston Pool algorithm ) is an algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962 in The American Mathematical Monthly, although it had been used for the National Resident Matching Program since 1952 despite lacking the theoretical foundation. Shapley and Alvin E. Roth (who pointed out its prior application) won the 2012 Nobel Prize in Economics for work including this algorithm. It had been said that Gale would have been the third co-recipient of the Prize, if he were alive. The stable matching problem seeks to pair up equal numbers of participants of two types, using preferences from each participant. The pairing must be stable: no pair of matched participants should mutually prefer each other to their assigned match. In each round of the Gale–Shapley algorithm, unmatched participants of one type propose a match to the next participant on their preference list. Each proposal is accepted if its recipient prefers it to their current match. The resulting procedure is a truthful mechanism from the point of view of the proposing participants, who receive their most-preferred pairing consistent with stability.…
Article summary
In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm, propose-and-reject algorithm, or Boston Pool algorithm ) is an algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962 in The American Mathematical Monthly, although it had been used for the National Resident Matching Program since 1952 despite lacking the theoretical foundation. Shapley and Alvin E. Roth (who pointed out its prior application) won the 2012 Nobel Prize in Economics for work including this algorithm. It had been said that Gale would have been the third co-recipient of the Prize, if he were alive. The stable matching problem seeks to pair up equal numbers of participants of two types, using preferences from each participant. The pairing must be stable: no pair of matched participants should mutually prefer each other to their assigned match. In each round of the Gale–Shapley algorithm, unmatched participants of one type propose a match to the next participant on their preference list. Each proposal is accepted if its recipient prefers it to their current match. The resulting procedure is a truthful mechanism from the point of view of the proposing participants, who receive their most-preferred pairing consistent with stability.…
Key claims
- date of death: 2008 — source: Wikipedia, revision 1377920781, retrieved 2026-10-20 · confidence 0.95
- publication date: 1962 — source: Wikipedia, revision 1377920781, retrieved 2026-10-20 · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the date of death is "2008". What evidence would count against this claim?
- The record states that the publication date is "1962". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia, “Gale–Shapley algorithm”, revision 1377920781, retrieved 2026-10-20 https://en.wikipedia.org/w/index.php?oldid=1377920781
Key claims and bibliography are generated from the same tracked claims and sources as the article page.