Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
→Optimality of the solution: Fixed grammar Tags: Mobile edit Mobile app edit Android app edit |
||
Line 55:
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'' among all stable matchings. Similarly, if the women propose then the resulting matching is the ''best for all women'' among all stable matchings. These two matchings are the top and bottom elements of a larger structure on all stable matchings, 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)
Since B is a stable matching, ''m''<sub>2</sub> must be matched in B to some woman he prefers to ''w''<sub>1</sub>, say ''w''<sub>3</sub>. This means that in A, ''m''<sub>2</sub> has visited ''w''<sub>3</sub> before arriving at ''w''<sub>1</sub>, which means that ''w''<sub>3</sub> has rejected him. By similar considerations, and since the graph is finite, we must eventually have a directed cycle in which each man was rejected in A by the next woman in the cycle, who rejected him in favor of the next man in the cycle. But this is impossible since such "cycle of rejections" cannot start anywhere: suppose by contradiction that it starts at e.g. ''m''<sub>0</sub> - the first man rejected by his adjacent woman (''w''<sub>1</sub>). By assumption, this rejection happens only after ''m''<sub>2</sub> comes to ''w''<sub>1</sub>. But this can happen only after ''w''<sub>3</sub> rejects ''m''<sub>2</sub> - contradiction to ''m''<sub>0</sub> being the first.
| |||