## You are here

Homestable marriage problem

## Primary tabs

# stable marriage problem

The *stable marriage problem* is a problem in combinatorial optimization proposed and solved by Gale and Shapley. We will present the problem in concrete terms, interpret it in graph-theoretical terms, then solve it.

In a small town there are $n$ men and $n$ women who wish to be wed. Each person would be happy to be married to any of the people of the opposite sex but has a definite preference ranking of the possible marriage partners. If marriages are arranged arbitrarily, some of the marriages can be unstable in the following sense. Suppose Alice marries Bob and Carol marries Dave. If Alice prefers Dave to Bob and Dave prefers Alice to Carol, then Alice and Dave will have an affair; in this situation, we say that the marriages of Alice and Dave are *unstable*. The stable marriage problem is to determine whether all people can be married with all marriages stable.

$\xymatrix{\text{Alice}\ar@{-}[r]\ar@{.}[rd]^{{\text{tryst}}}&\text{Bob}\\ \text{Carol}\ar@{-}[r]&\text{Dave}}$ |

Here is a graph-theoretical interpretation of the problem. Let $G=K_{{n,n}}$ be a complete bipartite graph with partition $V(G)=A\coprod B$, and let $G^{{\prime}}$ be the directed $G$, that is, $G$ with each undirected edge $uv$ replaced by the directed edges $\vec{uv}$ and $\vec{vu}$. Let $w\colon E(G^{{\prime}})\to\{1,\dots,n\}$ be a weight function on $G^{{\prime}}$ such that all the edges out of a vertex are assigned distinct weights. A matching $\mathcal{M}\subset E(G)$ is *unstable* if there exist edges $st$, $uv$ in $\mathcal{M}$ with $s$, $u$ both in $A$ or both in $B$ such that $w(sv)>w(st)$ and $w(vs)>w(vu)$, and is *stable* otherwise. Find a stable perfect matching of $G$.

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 married. Each woman who was rejected 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 married. 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.

We claim that all of the marriages are stable. To see this, consider again the example of Alice and Bob and Carol and Dave.

$\xymatrix{\text{Alice}\ar@{-}[r]&\text{Bob}\\ \text{Carol}\ar@{-}[r]&\text{Dave}}$ |

Suppose Alice prefers Dave to Bob. Since Alice proposed first to her favorites and only moved down the list when she was rejected, Dave must have rejected Alice’s proposal. Hence Dave must prefer Carol to Alice. Similarly, if Carol prefers Bob to Dave, then Bob prefers Alice to Carol. Hence both marriages are stable: each woman is either satisfied with her marriage or is unable to find a man willing to have an affair.

We can also argue for stability from the men’s perspective. For example, suppose Bob prefers Carol to Alice. This means that had Carol proposed to him, he would have said yes to Carol and rejected Alice. Since he didn’t reject Alice, it must be the case that Carol never proposed to him. But she did propose to Dave, so she must prefer Dave to Bob. Similar remarks hold for Dave. Again either a man is satisfied with his marriage or is unable to find a woman willing to have an affair; therefore, all marriages are stable.

# References

- 1
D. Gale and L.S. Shapley,
*College admissions and the stability of marriage*, American Mathematical Monthly 69 (1962), no 1., 9–15.

## Mathematics Subject Classification

90C27*no label found*05C85

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Making the algorithm more clear

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.