The Gale-Shapley Theorem states that for any stable marriage problem, in which each member of two equal-sized groups ranks every member of the other group by preference, a stable matching always exists, meaning a pairing under which no two people who are not matched to each other would both prefer each other to their assigned partners, and such a matching can be produced by the deferred acceptance algorithm. Named for David Gale and Lloyd Shapley, it is a foundational existence result of matching theory.
Facts
StatementA stable matching always exists, and the Gale-Shapley algorithm finds one. 1 Connections
In Branch
Source Gale-Shapley algorithm (Wikipedia)
Proved By
Source Gale-Shapley algorithm (Wikipedia)
Sources
1. Gale-Shapley algorithm (Wikipedia)
Lead section
It is named for David Gale and Lloyd Shapley, who published it in 1962 in The American Mathematical Monthly, although it had been used for the National Resident Matching Program since 1952 despite lacking the theoretical foundation.
Solution section
A stable matching always exists, and the algorithmic problem solved by the Gale-Shapley algorithm is to find one.
In Group: Mechanism Design, Section: Solution
In 1962, David Gale and Lloyd Shapley proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable.
In Branch: Game Theory, Article text
In mathematics, economics, and computer science, the Gale-Shapley algorithm (also known as the deferred acceptance algorithm, propose-and-reject algorithm, or Boston Pool algorithm) is an algorithm for finding a solution to the stable matching problem.
Proved By: Lloyd Shapley, Lead
In 1962, David Gale and Lloyd Shapley proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.