Stable matching problem: Difference between revisions

Revision as of 17:39, 26 September 2006

Revision as of 17:48, 26 September 2006

Line 5:

==Solution==

In 1962, [[David Gale]] and [[Lloyd Shapley|Shapley]] proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an [[algorithm]] to do so.

The '''Gale-Shapley algorithm''' involves a number of "rounds" (or "[[iteration]]s") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed, and she accepts or rejects him based on whether she is already engaged to someone she prefers. If she is unengaged, or engaged to a man lower down her preference list than her new suitor, she accepts the proposal (and in the latter case, the other man becomes unengaged again). Note that only women can switch partners to increase their happiness.