Gale–Shapley algorithm: Difference between revisions

Revision as of 09:05, 19 July 2024

Revision as of 21:08, 27 August 2024

Line 21:

In other words, a matching is stable when there is no pair (''A'', ''B'') where both participants prefer each other to their matched partners. If such a pair exists, the matching is not stable, in the sense that the members of this pair would prefer to leave the system and be matched to each other, possibly leaving other participants unmatched. A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one.{{r|gusfield-irving}}

The stable matching problem has also been called the ''stable marriage problem'', using a metaphor of marriage between men and women, and many sources describe the Gale–Shapley algorithm in terms of marriage proposals. However, this metaphor has been criticized as both sexist and unrealistic: the steps of the algorithm do not accurately reflect typical or even stereotypical human behavior.{{r|wagner|giagkousi}}

==Solution==