Content deleted Content added
Tags: Reverted Visual edit |
Undid revision 1129174084 by RadioactiveBoulevardier (talk) I deliberately used the more current, non-sexist, non-heteronormative, non-triggering (I could cite specifics) and non-misleading (because who but a cult would actually marry batches of people in this way) terminology. Please do not change it back. |
||
Line 4:
==Background==
{{main|
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.
| |||