stable marriage Flashcards
The stable marriage problem i
s to match up the men and
women in a way that is stable. Such a matching is stable if there is no unmatched
man-woman pair, (x, y), such that x and y would prefer to be married to each other
than to their spouses. That is, it would be unstable if x preferred y over his wife
and y preferred x over her husband. (
The Proposal Algorithm
A round begins with an unmatched man making a proposal to the female highestranked on his list. If she is unmatched, then she accepts his proposal and the round
ends. If, on the other hand, she is matched, then she accepts his proposal only if
she ranks him higher than her current partner. In the case when the woman receiving the proposal is already matched, then whichever man she rejects repeats the
computation for this round, making a proposal to the next woman on his list (his
highest-ranked woman that he has not previously proposed to). Thus, a round continues in this way, consisting of a series of proposals and it ends when a previously
unmatched woman accepts a proposal. This proposal algorithm continues performing such rounds until all the men and women are matched.
