ECON 219 Lecture Notes - Lecture 19: Time Complexity, Stable Marriage Problem, Antibody
10
ECON 219 Full Course Notes
Verified Note
10 documents
Document Summary
: you have a&b and c&d matched, but a would rather be with d, and. Matching can always be found, and the matching is stable 2 properties with. Gale shapely algorithm: example: 10 men and 10 women want stable matching. Each man ranks the women in order of preference. Each women ranks the men in order of preference. 1) each man proposes to the woman on the top of his list of preferences. 2) once this is done, the women look at the proposals received (if only 1 proposal they say yes, if they receive more they reject all but their top suitor) Every man who is not matched proposes to his most preferred women who has not already rejected him. She accepts if she is unmatched, or if she prefers him over her current partner, or she will reject him.
