GaleShapley

Gale-Shapley algorithm, or the Deferred Acceptance algorithm, is a solution to the stable matching problem introduced by David Gale and Lloyd Shapley in 1962. It finds a stable matching between two disjoint sets of agents, typically men and women, each with a ranked preference list over members of the other set. A matching is stable if there is no pair of agents who would both prefer to be with each other rather than with their assigned partners.

In the standard version, one side (the proposers) repeatedly proposes in order of their preferences to the members of the other side who have not yet rejected them. A recipient keeps the best proposal they have received so far and temporarily dumps others. Rejected proposers move on to the next person on their list. The process continues until every proposer is matched.

When finished, the resulting matching is stable: no two agents would prefer each other over their current partners. If the proposing side is fixed, the algorithm yields the best possible stable outcome for that side (and the worst for the other side) among all stable matchings; swapping the roles yields the opposite extreme. The algorithm runs in polynomial time, with O(n^2) proposals in the worst case for n pairs.

Extensions include many-to-one versions (hospital-residents), incomplete preference lists, ties, and variants with randomized tie-breaking. It has broad applications in market design, notably the National Resident Matching Program and school choice programs, and it is foundational in the study of stable matchings and lattice structure of outcomes.