Fork me on GitHub
Math for the people, by the people.

User login

stable marriage problem

Defines: 
unstable, stable
Type of Math Object: 
Topic
Major Section: 
Reference
Groups audience: 

Mathematics Subject Classification

90C27 no label found05C85 no label found

Comments

Since couples get "married" in this algorithm, it is not clear what should happen if a married man gets a proposal. Especially since the point of the algorithm is to prevent breakup of marriages. This is solved by couples getting "engaged", and an engagement can be broken. Here is alternative text:

To solve the problem, we return to the small town. First, each woman proposes to the man at the top of her list. Each man waits until everyone who is going to propose to him has done so, then says yes to his favorite out of the proposers and rejects the rest. These couples then get engaged. In the next round, each woman who is not engaged crosses out the top name on her list and proposes to her second choice. The men consider and respond to the offers as before, and any new couples formed get engaged. Engaged men who receive a proposal from a person they prefer dump their fiancé and enter a new engagement. Each woman will eventually find a man to accept her proposal, and each man will eventually receive a proposal. Thus this process guarantees that every person will find a spouse. At that point, each person marries the one they are engaged to.

We should also note that it is not necessary that all women propose at the same time. We will find a stable marriage if we pick in each round at random one woman who isn't engaged, and that woman proposes to the favourite among the men she hasn't proposed to yet. The man accepts the proposal if he isn't engaged, or is engaged to a woman who is lower in his preference. In practice, this makes the implementation simpler. The result will be a stable arrangement, but the actual marriages may be different.

We should also note that the roles of woman and men in the algorithm can be exchanged, which will often give different marriages.

Since there may be more than one possible solutions, we can try to find a solution that is optimal in some sense. For example, instead of a ranking each person could assign a score to each member of the opposite sex, and we could try to find the solution where the sum of scores is highest. If we allow negative scores and disallow marriages where one person gives their spouse a negative score, the existence of a solution is not guaranteed.

Subscribe to Comments for "stable marriage problem"