Gale–Shapley algorithm: Difference between revisions

Revision as of 03:01, 27 July 2022

Revision as of 23:40, 23 December 2022

Line 4:

==Background==

{{main|stableStable matchingmarriage problem}}

The stable matching problem, in its most basic form, takes as input equal numbers of two types of participants ({{mvar|n}} men and {{mvar|n}} women, or {{mvar|n}} medical students and {{mvar|n}} internships, for example), and an ordering for each participant giving their preference for whom to be matched to among the participants of the other type. A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one. A matching is ''not'' stable if:

Line 47:

==Optimality of the solution==

{{main|Lattice of stable matchings}}

[[File:DA-men-optimality.png|thumb|Proof that deferred acceptance is optimal for men]]

The existence of different stable matchings raises the question: which matching is returned by the Gale–Shapley algorithm? Is it the matching better for men, for women, or the intermediate one? In the above example, the algorithm converges in a single round on the men-optimal solution because each woman receives exactly one proposal, and therefore chooses that proposal, ensuring that each man has an accepted offer, ending the match.