Introduction
An intuitive way to think about stable marriages is as the product of a dating service. Imagine that a number of people sign up for a dating service. For the sake of argument, let’s let there be the same number of men and women. Also, we’ll assume that everyone is heterosexual. Now, let’s let every possible man-woman pair go out on a few dates to get to know each other. Then we’ll ask every man to rank every woman in order of preference. We won’t let him have any ties, and he has to rank every single woman in the dating service. We’ll have each woman do the same thing. If there is any way to pair them up without leaving the possibility for affairs, we will call that set of pairs a stable matching. An affair can occur if a man and a woman both like each other better than their assigned partners. For example, imagine that we only have four people (two men and two women), and they rank each other as follows:
Fred’s Preferences: 1. Wilma 2. Betty
Barney’s Preferences: 1. Betty 2. Wilma
Betty’s Preferences: 1. Barney 2. Fred
Wilma’s Preferences 1. Barney 2. Fred
Now, if we pair Fred with Wilma and Betty with Barney, there can be no affairs.
Fred and Betty will not have an affair, because both prefer their partners to
each other. Wilma and Barney will also not have an affair. Even though Wilma
prefers Barney to Fred, her assigned partner, Barney prefers his assigned partner,
Betty, to Wilma. So he would not be interested in having an affair with Wilma.
So, although it may be sad for Wilma, the matching above is stable.
An unstable matching will occur if we pair Wilma with Barney and Fred with Betty.
Fred and Wilma would not have an affair, since Wilma is happier with Barney
than with Fred, but Betty and Barney would have an affair, since Barney prefers
Betty to Wilma and Betty prefers Barney to Fred. But, since even one affair
would occur, the marriage is not stable.
Clearly there are some problems with the dating service analogy. Not everyone
in the world signs up for a dating service. So perhaps in the first case, where
Barney is paired with Betty, Betty meets someone else who was not signed up
for the dating service and runs off with him. Also, this definition of stable
marriages requires each man and woman to rank everyone of the opposite gender,
and does not allow ties. This assumption is an oversimplification of romance.
Perhaps Betty would prefer not to be married at all than to be stuck with Fred,
or perhaps she truly doesn’t care whether she gets Fred or Barney, and
we forced her to pick. Modifications to the stable marriage problem to deal
with ties and unacceptable partners will be discussed on later pages. Finally,
this scenario requires preferences to remain the same forever after the initial
pairing to avoid divorces or affairs. This requirement is obviously a problem
for romance, and could also be a problem for some of the real-world applications
of stable marriage problems discussed on later pages.
In David Gale and Lloyd Shapley’s 1962 paper, [GD1]
in which they introduce the stable marriage problem and an algorithm
for finding a stable marriage and prove that a stable marriage always exists,
they note that the stable marriage problem leads to some incredibly elegant
and tidy mathematics. “The argument,” of one of their theorems,
“is not carried out in mathematical symbols but in ordinary English; there
are no obscure or technical terms. Knowledge of calculus is not presupposed.
In fact, one hardly needs to know how to count. Yet any mathematician will immediately
recognize the argument as mathematical, while people without mathematical training
will probably difficulty in following the argument.”[GD1]
Work on the stable marriage problem ranges from the incredibly elegant, although
far from trivial work of Gale and Shapley to complicated, technical and hard
to follow discrete mathematics, computer science and algorithm analysis. I will
begin with simple, illustrative descriptions and proofs, and I will proceed
in later pages to a more technical discussion of algorithms and representations
of extensions of the stable marriage problem.