Stable marriage problem

A matching problem in which participants rank potential partners and a matching is stable when no unmatched pair would both prefer each other to their assigned partners.

Gale–Shapley algorithm: An iterative matching algorithm in which one side proposes and the other tentatively accepts its preferred offers. Its deferred-acceptance procedure finds a stable matching for the problem.
Matching theory: The mathematical study of pairing members of two or more groups under specified constraints. The stable marriage problem is a foundational model within this broader subject.
National Resident Matching Program: The U.S. system that matches medical residency applicants with residency programs using submitted preferences. Its modern design uses matching theory to coordinate a large two-sided market.
Maximum matching: A matching containing the greatest possible number of edges in a graph. Maximizing the number paired does not ensure that no pair prefers to deviate.
Strategy-proofness: A property of a mechanism in which participants cannot gain by misreporting their preferences. Deferred acceptance protects proposers from beneficial misreports under standard assumptions, but not every participant.
Deferred acceptance: A matching procedure in which tentative agreements persist until displaced by a more preferred option. This is the proposal-and-rejection mechanism underlying Gale–Shapley matching.
Bipartite graph: A graph whose vertices divide into two sets, with edges only between the sets. Potential pairings connect the two sides of the matching problem.
School choice: The allocation of students to schools under capacity limits, eligibility rules, and priority rankings. Stable matching ideas help analyze how priorities and family preferences shape assignments.
Pareto efficiency: A state is Pareto efficient when no feasible change benefits someone without harming anyone else. A stable matching need not be the only efficient outcome, and stability is a different criterion.
Manipulability of stable matching mechanisms: The possibility that a participant can obtain a preferred outcome by submitting a false preference ranking. Stability alone does not prevent strategic reporting by all sides.

Linked from 12 pages