The Dating Game

Imagine that you are a matchmaker, with 100 female clients and 100 male clients. Each of the women gives you a complete list of the 100 men, ordered according to preference, starting with her first choice, then second choice, and so on. Each of the men has given you a list of women ranked similarly. Your job is to arrange 100 happy marriages.

Known as the stable marriage problem, this exercise is a classic combinatorial problem involving matching. It is clear that everyone is not guaranteed to get their first choice. If a particular man, for example, is the first choice of more than one woman, only one can be matched with him, and the other women have to make do with less.

So, rather than guaranteeing happiness to everyone, the challenge is to come up with stable pairings. In other words, once the matchmaker has arranged the marriages, there should be no man who says to another woman, "You know, I love you more than the woman I was matched with—let's run away together!" where the woman agrees, because she loves the man more than her husband. This should also be true for a woman making a similar proposal to man.

As we shall see, it is always possible for a matchmaker to arrange such a group of stable marriages, regardless of the preference lists of the men and women. An algorithm to solve the stable marriage problem first appeared in an article by David Gale and Lloyd Shapley in the American Mathematical Monthly in 1962 under the title "College Admissions and the Stability of Marriage." Interestingly, this algorithm is used to match hospitals to medical interns and by the world's largest dating service.

Preferences

Suppose that there are n men and n women. Each woman has her own ranked preference list of all the men; each man has his own ranked preference list of the women. The lists have no ties; the rank-ordered lists are in decreasing order of preference.

How do we pair the men and women off? What criteria come to mind?

There is more than one notion of what constitutes a "good" pairing. For example, we could aim for maximizing total satisfaction, maximizing minimum satisfaction, minimizing the maximum difference in mate ranks, or maximizing the number of people who get their first choice. We will, however, ignore the issue of what is "equitable."

Suppose that we pair off all the men and women. Suppose then that some man and some woman prefer each other to the people with whom they are paired. They will be called a rogue couple. We define a stable pairing of men and women to be one that contains no rogue couples.

This notion of stability is an important criterion. Without it, there is little use in aiming for fairness. So, any reasonable list of criteria for a good pairing must include stability. In essence, a set of pairings is doomed if it contains a rogue couple.

More formally, given a set of n men and n women, marry them off in pairs after each man has ranked the women in order of preference from 1 to n (w₁, . . . w_n) and each woman has done likewise (m₁, . . . m_n). If the resulting set of marriages contains no pairs of the form (m_i, w_j), (m_k, w_l) such that m_i prefers w_l to w_j and w_i prefers m_i to m_k, the marriage is said to be stable.

Example

Suppose that five men and five women each give a list of their preferences, in order. The following table shows the preferences of each man and woman.

The following pairings (m_i, w_j) include no rogue couples: (1, 5), (2, 2), (3, 4), (4, 3), and (5, 1).

Does every set of preference lists have a stable pairing?

To answer this question, let us first consider the idea of allowing the pairs to keep breaking up and reforming until they become stable. Can you argue that the couples will not continue breaking up and reforming forever?

Consider the case of bisexual dating, in which gender is not a factor in any given pairing. In this situation, we can set up a case in which there is no stable pairing. For example, suppose that, among four people, person 1 has an ordered list with preferences {2, 3, 4}, person 2 has the preference list {3, 1, 4}, and person 3 has the preference list {1, 2, 4}. Persons 2 and 3 constitute a rogue couple, with respect to person 1.

The key idea is that any proof that male-female (heterosexual) couples do not break up and reform forever must contain a step that fails in the bisexual case. In other words, if we have a proof idea that works equally well in the heterosexual and bisexual versions, then our idea is not adequate to show the couples eventually stop.

Traditional Marriage Algorithm

Let us consider one way in which to accomplish a stable pairing. We call it the traditional marriage algorithm (TMA) and proceed in rounds. In essence, the idea is to match an eligible man to the highest ranked woman on his list who will have him. We say "who will have him" because some women ranked high on his list may already be "engaged" to people they prefer over him. From the woman's viewpoint, she can give a tentative "yes" (or maybe) to a suitor if he's on her list, but she can always dump him later in favor of someone better (higher on her list).

In the first round, each man proposes to his first-choice woman. Each of the women receives either no proposal (if she was not the first choice of any man), one proposal (if she was the first choice of exactly one man), or more than one proposal (if many men find her to be their first choice).

For a women, if no one proposes, there's no need to worry. A man will eventually propose in some future round. If exactly one man proposes to a woman, the woman tentatively accepts his proposal and the pair is considered to be engaged. If more than one man proposes, the woman responds affirmatively to the one highest on her list and rejects the others.

So, after the first round, some men may be engaged whereas the others have been rejected. In the second round, the engaged men stick with the women to whom they originally proposed and the rejected men make another round of proposals. This time, in the case of multiple proposals, each engaged woman can dump her fiancé if she receives a proposal from a man higher on her list than the man to whom she is engaged, and she can then become engaged to the higher-ranked man. Thus, a man who is happily engaged at the end of a previous round may find himself abruptly dumped and back on the market again.

This continues round after round until finally there is no one left to propose or be proposed to.

Algorithm

For each day that some man gets a "no" do:

• Morning
  • Each woman stands on her balcony.
  • Each man proposes under the balcony of the most desirable woman whom he has not yet crossed off his list.
• Afternoon (for those women with at least one suitor)
  • To today's best suitor: "Maybe, come back tomorrow."
  • To any others: "No, I will never marry you."
• Evening
  • Any rejected man crosses the women off his list.
  • If no man gets a "no," each woman marries the man to whom she just said "maybe."

Example

• On day 1, m₁ goes to w₃, m₂, m₄, and m₅ go to w₁, and m₃ goes to w₄; m₁ and m₃ get maybes, m₂ and m₄ get rejected, and m₅ gets a maybe.
• On day 2, m₁ and m₄ go to w₃, m₃ goes to w₄, m₂ goes to w₂, and m₅ goes to w₁; m₁ gets rejected, m₂, m₃, m₄, and m₅ get maybes.
• On day 3, m₁ and m₂ go to w₂, m₃ goes to w₄, m₄ goes to w₃, and m₅ goes to w₁; m₁ gets rejected, m₂, m₃, m₄, and m₅ get maybes.
• On day 4, m₁ goes to w₅, m₂ go to w₂, m₃ goes to w₄, m₄ goes to w₃, and m₅ goes to w₁; everyone gets a maybe.

Hence, the final pairings are {1, 5}, {2, 2}, {3, 4}, {4, 3}, and {5, 1}.

Exercise

Find a stable pairing for the following set of preferences.

Pair Improvement

Does the traditional marriage algorithm always terminate? For example, we might encounter a situation in which the algorithm does not specify what to do next or it might keep on going for an infinite number of days. To show this can't happen, we'll make use of the following "improvement lemma".

Lemma. If a woman engaged to a man at some point, then she will always be engaged to someone at least as good as that man. She would let go of him only in order to say "maybe" to someone better.

Proof. Let q be the day that she first gets m on a string. If the lemma is false, there must be a smallest k such that the woman has some m* inferior to m on day q + k.

One day earlier, she has someone as good as m. Hence, a better suitor than m* returns the next day. She will choose the better suitor contradicting the assumption that her prospects went below m on day q + k.

Corollary. Each woman will marry her absolute favorite of the men who visit her during the traditional marriage algorithm.

Lemma. No man can be rejected by all the women.

Proof. Suppose man m is rejected by all n women. At that point, each woman must have a suitor other than m (by the improvement lemma, once a woman has a suitor she will always have at least one). The n women have n suitors, and m is not among them. Thus, there are at least n + 1 men. Contradiction.

So, if there are 100 men and 100 women, each man can make only 100 proposals. During each round, some man proposes, reducing the finite "supply" of proposals by at least one. If the rounds continue long enough, then the supply of proposals will decrease to zero, and the game of "musical chairs" must come to an end because there is no one left to propose.

We also know that everyone gets paired off. Because the number of men equals the number of women, the only way for a man to remain eligible at the end is for there to be an unengaged woman who rejects him. However, the only rejections come from women who are engaged.

How efficient is the TMA algorithm? In other words, can we answer the question: Is there a fast algorithm that, given any set of input lists, will output a stable pairing?

Theorem. The TMA always terminates in at most n² days.

Proof. A "master list" of all n of the men lists starts with a total of n times n = n² women on it.

Each day that at least one man gets a "no," at least one woman gets crossed off the master list.

Therefore, the number of days is bounded by the original size of the master list. In fact, because each list never drops below 1, the number of days is bounded by n(n – 1) < n².

Marriage Stability

Now, we know that TMA will terminate and produce a pairing. But is it stable?

Suppose there exists a man m and a woman w such that they prefer each other over their own spouses. Because m prefers w over his own spouse, then he must have proposed to her before proposing to his own spouse. So there are two possibilities of what happened at the time of that proposal.

One possibility is that w rejected m, which means that she was already engaged to someone she preferred over m (she had scratched m off her list). Therefore, she must be married either to that person or to someone else who was on her list at the time of the proposal. Therefore, she could not prefer m to her own spouse, contradicting our assumption.

The other possibility is the w accepted m, but dumped him later. Because she would have dumped him only in order to become engaged to someone with a higher rank on her list, she must not prefer m over her own spouse, again contradicting the assumption.

In both cases, the assumption is contradicted. So, there cannot exist a man m and a woman w such that they prefer each other over their own spouses. Therefore, the arrangement is stable.

More formally, we have the following theorem.

Theorem. Let T be the pairing produced by TMA. Then, T is stable.

Proof. Let m and w be any couple in T.

Suppose m prefers w* to w. We will argue that w* prefers her husband to m.

During TMA, m proposed to w* before he proposed to w. Hence, at some point w* rejected m for someone she preferred. By the improvement lemma, the person she married was also preferable to m.

Thus, every man will be rejected by any woman he prefers to his wife.

Hence, T is stable.

Optimal and Pessimal Pairings

Who is better off in the traditional marriage algorithm, the men or the women? Note that in TMA the men do the asking (pursuing) and the women merely respond.

Let us start with defining what we mean when we say "the optimal woman for man m." It is not good enough to say simply, "The woman at the top of _m_'s list."

A man's optimal woman is the highest ranked woman for whom there is some stable pairing in which the man gets her. She is the best woman he can conceivably get in a stable world. Presumably, she might be better than the woman he gets in the stable pairing output by TMA.

A man's pessimal woman is the lowest ranked woman for whom there is some stable pairing in which the man gets her. She is the worst woman he can conceivably get in a stable world.

A pairing is male-optimal if every man gets his optimal mate. This is the best of all possible stable worlds for every man simultaneously. A pairing is male-pessimal if every man gets his pessimal mate. This is the worst of all possible stable worlds for every man simultaneously.

A pairing is female-optimal if every woman gets her optimal mate. This is the best of all possible stable worlds for every woman simultaneously. A pairing is female-pessimal if every woman gets her pessimal mate. This is the worst of all possible stable worlds for every woman simultaneously.

Here is the bottom line: The traditional marriage algorithm always produces a male-optimal, female-pessimal pairing. Because the unengaged women in the algorithm accept any proposal, the men end up happier on average.

As an example, suppose there are 5 men and 5 women, and suppose that each man has a different first choice. Then they will all get their first choice, regardless of the preferences of the women.

Theorem. TMA produces a male-optimal pairing.

Proof. Suppose, for a contradiction, that some man gets rejected by his optimal woman during TMA. Let t be the earliest time at which this happened.

In particular, at time t, some man m got rejected by his optimal woman w because she said "maybe" to a preferred m*. By the definition of t, m* had not yet been rejected by his optimal woman, and so m* likes w at least as much as his optimal woman.

There must exist a stable paring S in which m and w are married, as given by the definition of optimality. But m* wants w more than his wife in S, and w wants m* more than her husband in S, so S is not stable. Contradiction.

Theorem. TMA produces a female-pessimal pairing.

Proof. We know that it is male-optimal. Suppose there is a stable pairing S where some woman w does worse than in T.

Let m be her mate in T; let m* be her mate in S.

By assumption, w likes m better than her mate in S. Since TMA is male-optimal, m likes w better than his mate in S. Therefore, S is not stable. Contradiction.

Example

The following example demonstrates that whoever does the proposing gets the better deal.

Suppose that Bob's choice is Carol, and Ted's first choice is Alice, while Carol's first choice is Ted, and Alice's first choice is Bob. When the men propose in the first round, Bob proposes to Carol and Ted proposes to Alice. Because each woman received exactly one proposal, they each accept. Bob and Ted get their first choice, while Carol and Alice get their second choice.

If the women propose instead, Carol would propose to Ted and Alice would propose to Bob. Because Ted and Bob each get one proposal, they have to accept. Carol and Alice get their first choice, while Bob and Ted get their second choice.

Exercise

For the following list of preferences, find the male optimal stable matching (men proposing) and the female optimal stable mapping (women proposing).

Medical Choices

Interestingly, the TMA algorithm is used every year to match graduating medical students to hospitals. When a student finishes medical school and wants to specialize in, say, cardiology, she interviews for cardiology residency programs at hospitals across the country. After all the interviews, makes a list of the programs she visited, in order of preference. Each of the medical programs, after having interviewed many candidates for the job, makes a similar list of students. Everyone sends their list to be processed by computer, which matches students and jobs. The hospitals play the role of the men in the TMA algorithm. No medical program or student is guaranteed their first choice. The matching is done to achieve stability, so that no student and hospital can successfully conspire to outwit the national medical establishment.

It is also said that the largest, most successful dating service in the world uses a computer to run TMA for pairing clients!

The stable marriage problem and its variants are a rich source of problems and ideas that illustrate both the design and analysis of efficient algorithms. Much effort has gone into developing alternative methods and better compromises to overcome, for practical and political reasons, the asymmetry inherent in the original TMA algorithm, as introduced by Gale and Shapley.

References

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

Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structures and Algorithms. MIT Press, 1989