|
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  men and  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.
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \text{Alice}\ar@{-}[r]\ar@{.}[rd... ...text{tryst}} & \text{Bob} \ \text{Carol}\ar@{-}[r] & \text{Dave} } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/8259/l2h/img3.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \text{Alice}\ar@{-}[r]\ar@{.}[rd... ...text{tryst}} & \text{Bob} \ \text{Carol}\ar@{-}[r] & \text{Dave} } } \end{xy}$") Here is a graph-theoretical interpretation of the problem. Let  be a complete bipartite graph with partition
 , and let  be the directed  , that is,  with each undirected edge  replaced by the directed edges  and  . Let
 be a weight function on  such that all the edges out of a vertex are assigned distinct weights. A matching
 is unstable if there exist edges  ,  in
 with  ,  both in  or both in  such that
 and
 , and is stable otherwise. Find a stable perfect matching of  .
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.
- 1
- D. Gale and L.S. Shapley, College admissions and the stability of marriage , American Mathematical Monthly 69 (1962), no 1., 9-15.
|
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \text{Alice}\ar@{-}[r] & \text{Bob} \ \text{Carol}\ar@{-}[r] & \text{Dave} } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/8259/l2h/img25.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \text{Alice}\ar@{-}[r] & \text{Bob} \ \text{Carol}\ar@{-}[r] & \text{Dave} } } \end{xy}$")