Gale–Shapley algorithm

In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley. It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal. stable matching problem The stable matching problem, in its most basic form, takes as input equal numbers of two types of participants (n medical students and n internships, for example), and an ordering for each participant giving their preference for whom to be matched to among the participants of the other type. A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one. A matching is not stable if: In other words, a matching is stable when there is no pair (A, B) where both participants prefer each other to their matched partners. 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. 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. They presented an algorithm to do so. In 1984, Alvin E. Roth observed that essentially the same algorithm had already been in practical use since the early 1950s, in the National Resident Matching Program. The Gale–Shapley algorithm involves a number of "rounds" (or "iterations"). In terms of job applicants and employers, it can be expressed as follows: In each round, any subset of the employers with open job positions makes a job offer to the applicant they prefer, among the ones they have not yet already made an offer to. Each applicant who has received an offer evaluates it against their current position (if they have one).