Content deleted Content added
same change as in main |
|||
Line 48:
==Optimality of the solution==
{{main|Lattice of stable matchings}}
[[File:DA-men-optimality.png|thumb|Proof that deferred acceptance is optimal for men]]
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 selects that proposal as her best choice, 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'' 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) to ''m''<sub>2</sub> (this is denoted by the red arrow from ''w''<sub>1</sub> to ''m''<sub>2</sub>).
| |||