MATH239 : stable marriage.pdf
Document Summary
Given n men and n women, each rank the n members of the opposite gender. Goal: pair up the men and women so that there is no jealousy. Jealousy occurs when a pair both prefer each other over their current partner. Proposal: each man proposes to the highest-ranking woman who has not rejected him. Rejection: each woman says maybe to the highest-ranking proposal received, and rejects the rest of the proposals. Repeat the proposal/rejection process until a perfect matching is obtained. Key: for each woman, the ranks of the rejected proposals are lower than the maybe , and ultimately lower than the accepted proposal. So lucas must have been rejected by nina. If we instead run the algorithm by having the women propose, then every woman winds up at least as happy as in the original algorithm, and every man winds up at least as unhappy.
