Content deleted Content added
→Application: removed copyvio (from the referenced source) |
Tag: Reverted |
||
Line 57:
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>).
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, otherwise the algorithm will not terminate: 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.
== Strategic considerations ==
| |||