stable marriage problem

The stable marriage problem is a problem in combinatorial optimization proposed and solved by 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.

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 $\overrightarrow{uv}$ and $\overrightarrow{vu}$. Let $w:E(G^{\prime })\to \{1,\mathrm{\dots },n\}$ be a weight function on $G^{\prime }$ such that all the edges out of a vertex are assigned distinct weights. A matching $ℳ\subset E(G)$ is unstable if there exist edges $st$, $uv$ in $ℳ$ 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.

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.

Title	stable marriage problem
Canonical name	StableMarriageProblem
Date of creation	2013-03-22 16:10:26
Last modified on	2013-03-22 16:10:26
Owner	mps (409)
Last modified by	mps (409)
Numerical id	5
Author	mps (409)
Entry type	Topic
Classification	msc 90C27
Classification	msc 05C85
Defines	unstable
Defines	stable