Content deleted Content added
m v2.04b - Fix errors for CW project (DEFAULTSORT missing for titles with special letters) |
Added corollary of sex-specific optimality; optimality for one sex implies worst possible outcome for the other |
||
Line 49:
The existence of different stable matchings raises the question: which matching is returned by the Gale-Shapley algorithm? Is it the matching better for men, for women, or the intermediate one? In the above example, the algorithm converges in a single round on the men-optimal solution because each woman receives exactly one proposal, and therefore chooses that proposal, ensuring that each man has an accepted offer, ending the match.
This is a general fact: the Gale-Shapley algorithm in which men propose to women ''always'' yields a stable matching that is the ''best for all men'' and ''worst for all women'' among all stable matchings. Similarly, if the women propose then the resulting matching is the ''best for all women'' and ''worst for all men'' among all stable matchings. These two matchings are the top and bottom elements of the [[lattice of stable matchings]].
To see this, consider the illustration at the right. Let A be the matching generated by the men-proposing algorithm, and B an alternative stable matching that is better for at least one man, say ''m''<sub>0</sub>. Suppose ''m''<sub>0</sub> is matched in B to a woman ''w''<sub>1</sub>, which he prefers to his match in A. This means that in A, ''m''<sub>0</sub> has visited ''w''<sub>1</sub>, but she rejected him (this is denoted by the green arrow from ''m''<sub>0</sub> to ''w''<sub>1</sub>). ''w''<sub>1</sub> rejected him in favor of some man that she prefers, say ''m''<sub>2</sub>. So in B, ''w''<sub>1</sub> is matched to ''m''<sub>0</sub> but "yearns" (wants but unmatched) for ''m''<sub>2</sub> (this is denoted by the red arrow from ''w''<sub>1</sub> to ''m''<sub>2</sub>).
| |||