Stable matching problem: Difference between revisions

Revision as of 12:58, 2 October 2006

Revision as of 12:59, 2 October 2006

Line 36:

The pairing generated by the Gale-Shapley algorithm has a number of interesting properties. In particular, we can show that, in some sense, the Gale-Shapley pairing, in the form presented here, is '''male-optimal''' and '''female-pessimal''' (it would be the reverse, of course, if the roles of "male" and "female" participants in the algorithm were interchanged). To see this, consider the definition of a '''feasible marriage'''. We say that the marriage between man A and woman B is feasible if there exists a stable pairing in which A and B are married. When we say a pairing is male-optimal, we mean that every man is paired with his highest ranked feasible partner. Similarly, a female-pessimal pairing is one in which each female is paired with her lowest ranked feasible partner.

<math>Box</math>''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 any male-optimal pairing is female-pessimal. Consider any woman W paired to a man M in any stable, male-optimal pairing, G (for example, a Gale-Shapley pairing). Also consider an arbitrary stable pairing S. Because G is male-optimal, M prefers W to his match in S. Because S is stable, W must prefer her match in S to M. Thus women will always prefer their match in any stable pairing over their match in a male-optimal pairing. Thus, the Gale-Shapley pairing is female-pessimal because it is male-optimal (see above) .<math>\Box</math>