Stable matching problem

The problem of finding a matching with no blocking pair: two unmatched participants who would both prefer each other to their assigned partners.

Connect

Deferred acceptance algorithm: An iterative procedure in which one side proposes and the other tentatively holds its favorite offers. Its proposal-and-rejection process finds a stable matching.
Matching: A set of pairings in which each participant appears in at most one pair. Stable matching adds a preference-based condition to this basic assignment structure.
National Resident Matching Program: The U.S. system that matches medical residents with residency programs using an algorithm based on deferred acceptance. It applies stable matching to residency placements with program capacities and applicant rankings.
Maximum matching: A matching containing the greatest possible number of edges in a graph. Maximizing the number of pairs does not ensure that no blocking pair exists.
David Gale: An American mathematician whose work included game theory, optimization, and matching theory. He co-authored the foundational existence result for stable matchings.
Blocking pair: A pair of participants who prefer each other over their assigned partners, or over remaining unmatched. Stability means no such pair can disrupt the proposed assignment.
Bipartite graph: A graph whose vertices divide into two sets, with edges running only between the sets. Two-sided matching problems represent possible partnerships as edges between distinct groups.
School choice: The design of systems that assign students to schools using priorities, capacities, and submitted preferences. Stable matching models inform how student-school assignments are designed and evaluated.
Maximum-weight matching: A matching that maximizes the sum of weights assigned to its selected edges. Optimizing total score can produce an outcome that participants have incentives to leave.
Lloyd Shapley: An American mathematician and economist known for contributions to game theory and cooperative game theory. His joint 1962 paper established the deferred acceptance method and stable matching existence.