Gale–Shapley algorithm

The Gale–Shapley algorithm finds a stable matching by having one side propose in turn while the other side tentatively keeps its most-preferred offer. It terminates with no unmatched pair that would both prefer each other to their assignments.

Deferred acceptance: A matching procedure in which tentative assignments can be displaced by later, more-preferred offers. This is the general process the algorithm uses as proposals arrive.
Proposer-optimal stable matching: A stable matching in which every proposer receives their best partner attainable across stable matchings. The proposing side receives its most favorable stable outcome.
National Resident Matching Program: The United States system that matches medical residents with residency programs using an algorithm based on deferred acceptance. It applies a proposer-oriented matching procedure to medical training placements.
David Gale: An American mathematician whose work included game theory, optimization, and stable matching. Gale co-authored the 1962 paper that introduced the stable marriage algorithm.
Stable matching: A matching with no pair of participants who would both prefer each other to their assigned partners. The algorithm’s central guarantee is that its final matching is stable.
Receiver-optimal stable matching: A stable matching in which every receiver receives their best partner attainable across stable matchings. Reversing the proposing side favors the other group among stable outcomes.
School choice: The design of systems that assign students to schools using family preferences and school priorities. Deferred acceptance provides a way to allocate seats while avoiding justified blocking claims.
Lloyd Shapley: An American mathematician and economist known for foundational contributions to game theory and matching theory. Shapley co-authored the algorithm’s original analysis with David Gale.
Blocking pair: A pair of unmatched participants who would both prefer each other to their current assignments. The proposal process rules out every blocking pair in the final matching.
Rural hospitals theorem: A theorem stating that unmatched participants and certain assignment counts are the same across stable matchings. It describes which features cannot change when the algorithm selects a different stable outcome.

Linked from 5 pages