Content deleted Content added
→Properties of the Gale-Shapley pairing: (it would be the reverse, of course, if the roles of "male" and "female" participants in the algorithm were interchanged) |
Add pseudocode |
||
Line 14:
'''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 Matching Algorithm==
{{wikicode}}
'''function''' stableMatching {
Initialize all ''m'' <math>\in</math> M and ''w'' <math>\in</math> W to ''free''
'''while''' <math>\exists</math> ''free'' man ''m'' who still has a woman w to propose to {
w = m's highest ranked such woman
'''if''' w is ''free''
engage (m, w)
'''else''' some pair (m', w) already exists
'''if''' w prefers m to m'
(m, w) become ''married''
m' becomes ''free''
'''else'''
(m', w) remain ''married''
}
}
==Properties of the Gale-Shapley pairing==
| |||