Stable matching problem: Difference between revisions

Revision as of 07:31, 30 July 2005

Revision as of 04:04, 19 September 2005

Line 7:

In 1962, Gale and 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.

This algorithm guarantees that:

Line 13:

'''Everyone gets married:''' Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.

'''The marriages are stable:''' AtLet theAlice end,be ita iswoman notand possibleBob forbe a man. and aThey womanare (calleach thempaired/partnered/married, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob) to both prefer each other toover their current partners. This

Proof isof easy to show.stability: If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, (sinceand womentherefore onlydoesn't switchlike partnersBob tomore increasethan theirher happiness)current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.

==Stable matching algorithm==