Gale-Shapley Algorithm

The Gale-Shapley algorithm, also known as the deferred acceptance algorithm, is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley, who published it in 1962, although it had already been used for the National Resident Matching Program since 1952 without a theoretical foundation. Shapley and Alvin Roth, who pointed out its earlier application, won the 2012 Nobel Memorial Prize in Economic Sciences for work including this algorithm. In each round of the algorithm, unmatched participants of one type propose a match to the next participant on their preference list, and each proposal is accepted if its recipient prefers it to their current match, producing a pairing that is stable in that no two matched participants would both prefer each other over their assigned partners; the algorithm can be implemented to run in time quadratic in the number of participants, and its real-world applications include matching American medical students to residencies and French university applicants to schools.