The stable marriages problem
In a community of n men and n women each person ranks those of the opposite sex according to his or her preference for a marriage partner. The problem is to marry oft' all members of the community in such a way that the set of marriages is stable. The set is unstable if a man and a woman exist who are not married to each other but prefer each other to their actual mates.
Gale & Shapley11
1
1have described the following algorithm to solve the problem:
To start, let each boy propose to his favourite girl. Each girl who
receives more than one proposal rejects all but her favourite from amongst those who have proposed to her. However, she does not accept him yet, but keeps him on a string to allow for the possibility that someone better may come along later.
We are now ready for the second stage. Those boys who were
rejected now propose to their second choices. Each girl receiving proposals chooses her favourite from the group consisting of the new proposers and the boy on her string, ifany. Sherejects all the rest and again keeps the favourite in suspense.
We proceed in the same manner. Those who are rejected at the second stage propose to their next choices, and the girls again reject all but the best proposal they have had so far.
Eventually ...every girl will have received a proposal, for as long as any girl has not been proposed to there will be rejections and new proposals, but since no boy can propose to the same girl more than once, every girl is sure to get a proposal in due time. As soon as the last girl gets her proposal the 'courtship' is declared over, and each girl is now required to accept the boy on her string.
Provide brief justification for the following claims:
The algorithm provides a stable set of marriages.
The algorithm also works if the number of males does not equal the number of females.
The algorithm has complexity O(n
1
).
The algorithm rejects men only from women that they could not possibly be married to under any stable matching. That is, that any man is at least as well-off as he would be under any other stable marriage. The algorithm is callifd man-optimal for this reason. A woman-optimal set of marriages is, of course, obtained by getting the women to propose to the men.