Stable matching problem: Difference between revisions

Revision as of 07:30, 30 July 2005

Revision as of 07:31, 30 July 2005

Line 15:

'''The marriages are stable:''' At the end, it is not possible for a man and a woman (call them Alice and Bob) to both prefer each other to their current partners. This is easy to show. 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 (since women only switch partners to increase their happiness). If Alice rejected his proposal, she was already with someone she liked more than Bob.

==Stable Matchingmatching Algorithmalgorithm==

'''function''' stableMatching {