Gale–Shapley algorithm
It is named for David Gale and Lloyd Shapley, who published it in 1962, although it had been used for the National Resident Matching Program since the early 1950s.
Shapley and Alvin E. Roth (who pointed out its prior application) won the 2012 Nobel Prize in Economics for work including this algorithm.
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.
The stable matching problem, and the Gale–Shapley algorithm solving it, have widespread real-world applications, including matching American medical students to residencies and French university applicants to schools.
If such a pair exists, the matching is not stable, in the sense that the members of this pair would prefer to leave the system and be matched to each other, possibly leaving other participants unmatched.
However, this metaphor has been criticized as both sexist and unrealistic: the steps of the algorithm do not accurately reflect typical or even stereotypical human behavior.
[4][5] In 1962, David Gale and Lloyd Shapley proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable.
Once the algorithm terminates, the resulting matching can be read off from the array of employers for each applicant.
[10] Although this time bound is quadratic in the number of participants, it may be considered as linear time when measured in terms of the size of the input, two matrices of preferences of size
[12] The Gale–Shapley algorithm is a truthful mechanism from the point of view of the proposing side.
[13] However, it is possible for some coalition to misrepresent their preferences such that some proposers are better-off, and the others retain the same partner.
Under complete information, it is sufficient to consider misrepresentations of the form of truncation strategies.
Moreover, even after an agent sees the final matching, they cannot deduce a strategy that would guarantee a better outcome in hindsight.
Additionally, preference lists may be incomplete: if a university omits a student from their list, it means they would prefer to leave their quota unfilled than to admit that student, and if a student omits a university from their list, it means they would prefer to remain unadmitted than to go to that university.
[6] A form of the Gale–Shapley algorithm, performed through a real-world protocol rather than calculated on computers, has been used for coordinating higher education admissions in France since 2018, through the Parcoursup system.
It is important that this process performs a small number of rounds of proposals, so that it terminates before the start date of the schools, but although high numbers of rounds can occur in theory, they tend not to occur in practice.
[17] It has been shown theoretically that, if the Gale–Shapley algorithm needs to be terminated early, after a small number of rounds in which every vacant position makes a new offer, it nevertheless produces matchings that have a high ratio of matched participants to unstable pairs.
[18] Shapley and Roth were awarded the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design".
