Stable matching problem: Difference between revisions

Revision as of 15:41, 6 May 2006

Revision as of 20:14, 9 June 2006

Line 40:

''Proof that the Gale-Shapley pairing is male-optimal:'' We go by contradiction. Suppose the pairing generated by the Gale-Shapley algorithm were not male-optimal. Let T be the first iteration where a man is rejected by his optimal partner. Let man M be one man who is rejected by his optimal partner, woman W, during this iteration. Then woman W must have rejected man M for some other man, man Z. Further, since this is the first iteration where a man is rejected by his optimal partner, woman W must be at least as high on man Z's preference list as his optimal partner. Also note that, since woman W is man M's optimal partner, there exists some stable pairing S where man M is paired with woman W. Then, in pairing S, woman W prefers man Z to man M (since she rejected M for Z in the Gale-Shapley algorithm) and man Z prefers woman W to his partner in S, since he likes woman W at least as much as his optimal partner and, by our definition of optimal, he could not be paired with anyone better than this. But then, by definition, this pairing is unstable, since man Z and woman W prefer each other to their partners in S. We have reached a contradiction, so the Gale-Shapley algorithm must produce a male-optimal pairing. <math>\Box</math>

''Proof that the Gale-Shapley pairing is female-pessimal:'' We can show this using the fact that theany Galemale-Shapleyoptimal pairing is malefemale-optimal (see above)pessimal. Again,Consider we go by contradiction. Suppose there were a stable pairing S where aany woman W is paired withto a man ZM whoin sheany likesstable, lessmale-optimal thanpairing, theG man(for sheexample, is paired with by thea Gale-Shapley algorithm,pairing). manAlso M.consider an Wearbitrary knowstable thepairing Gale-ShapleyS. Because algorithmG is male-optimal, and since it pairs man M with womanprefers W, she must beto his optimal woman, and therefore,match in S,. heBecause canS onlyis be paired with someone lower on his preference list than womanstable, W. must Further,prefer weher alreadymatch knowin thatS woman W prefers manto M. toThus manwomen Z,will withalways whomprefer shetheir is pairedmatch in S.any stable So,pairing Sover istheir unstablematch sincein Wa andmale-optimal M would rather be with each other than with their partnerspairing. Thus, we have a contradiction and the Gale-Shapley algorithmpairing produces ais female-pessimal pairing.because it is male-optimal (see above) .<math>\Box</math>

==Applications==