Gale–Shapley algorithm

Rare card · No. 63787

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...

Read on Wikipedia