Stable matching

A matching in which no unmatched pair would both prefer each other to their assigned partners. It is stable relative to specified preference rankings.

Deferred acceptance algorithm: An iterative procedure in which one side proposes and the other tentatively accepts its most-preferred offer. Its rejection-and-proposal process produces a stable matching under standard preference assumptions.
National Resident Matching Program: The system that matches medical graduates to residency programs in the United States. Its matching procedure applies stable-matching ideas to a large, two-sided labor market.
David Gale: An American mathematician whose work included game theory, economics, and matching theory. He co-authored the 1962 paper that established existence of stable matchings.
Pareto efficiency: A state is Pareto efficient if no feasible change can improve someone’s outcome without worsening another’s. A stable matching need not be Pareto efficient under every model of preferences and feasible assignments.
Blocking pair: A pair not matched to each other whose members both prefer each other to their current assignments. The absence of such a pair is exactly what defines stability.
School choice: Systems for assigning students to schools under rules that may incorporate priorities and family preferences. Stable assignment methods offer one way to allocate school places without justified blocking pairs.
Lloyd Shapley: An American mathematician and economist known for contributions to game theory and cooperative economics. His joint work with Gale introduced the stable-marriage problem and its constructive solution.
Maximum-weight matching: A matching that maximizes the total weight of its selected edges in a weighted graph. It optimizes aggregate edge value rather than ruling out mutually preferred unmatched pairs.
Preference relation: A ranking or ordering that specifies which alternatives an agent prefers to others. Stability depends on comparing each participant’s assigned partner with potential alternatives.
Kidney exchange: The coordination of donors and patients into compatible kidney-transplant exchanges. Matching theory helps organize exchanges, though compatibility and cycles create constraints beyond basic stability.

Linked from 9 pages