## Mixing doubles

Submitted by Marianne on August 14, 2012Andy Murray and Laura Robson took silver at Wimbledon in the London 2012 Olympics. Image: Christopher Johnson.

Andy Murray and Laura Robson made a good team at London 2012, bringing home silver in the mixed doubles. But how do you make sure that the competing pair is the best you can pick from the team? Perhaps players in the team should pair up with the person they feel they play best with and then the pairs should play an internal tournament to see which performs best.

This throws up a mathematical problem that comes up in many other contexts too. Can you pair all players in such a way that there aren't any two players who would have preferred each other to the partners they ended up with?

Let's assume that there are an equal number *N* of men and
women in the team. A set of pairings is called *unstable* if it
contains two pairings, say (Laura, Andy) and (Anne, Jamie), such that
Andy likes Anne better than he likes Laura, and Anne likes Andy better than she likes
Jamie. Otherwise the set is called *stable*. Our task is to find
a stable set of pairings.

First get every man to list the women in order of his
preference. Each woman must be on each man's list and there can be no
ties. The women list the men in order of preference in the same
way. No-one is allowed to change their minds about their preferences later on. Here is an example for *N*=3:

Men's preferences | Anne | Heather | Laura |

Andy | 1 | 2 | 3 |

Colin | 3 | 1 | 2 |

Jamie | 2 | 3 | 1 |

Women's preferences | Andy | Colin | Jamie |

Anne | 3 | 1 | 2 |

Heather | 2 | 3 | 1 |

Laura | 1 | 2 | 3 |

Here are three stable sets of pairings:

1. The women all get their first choice:

(Anne, Colin), (Heather, Jamie), (Laura, Andy)

2. The men all get their first choice:

(Anne, Andy), (Heather, Colin), (Laura, Jamie)

3. Each gets their second choice:

(Heather, Andy), (Laura, Colin), (Anne, Jamie)

And here's an example of an unstable set of pairings:

(Anne, Jamie), (Heather, Colin), (Laura, Andy)

Andy likes Heather better than Laura and Heather likes Andy better than Colin.

But can you find a stable set of pairings for any number *N* and any pattern of preferences? The answer is yes:

*Given any number N of men and women, each with a
preference list, we can always find a stable set of pairings.*

We'll prove this theorem by giving a method for pairing people off and then showing that the result is indeed a stable set of pairings. The method works in stages:

**Stage 1:** Each man offers to pair off with the woman on the
top of his list. Each woman who gets such offers rejects all but the
man with the best rank on her list. She does not agree to pair off
with him straight away, but keeps him waiting in the hope of doing
better (she might not have received an offer from the man at the top of her list).

**Stage 2:** Each rejected man now offers to pair off
with his
next-favourite choice. Each woman who gets offers rejects all but the
man with the best rank on her list (including the men who proposed in
the first round). She does not agree to pair off
with him straight away, but keeps him waiting in the hope of doing
better.

In subsequent stages the process continues until each woman has
received an offer. The process must end since no man may make an offer
to a woman who rejected him. As soon as every woman has received an
offer, all couples agree to pair off. (Here is an example of this process for *N*=4.)

We'll now show that the resulting set of pairings is stable. Suppose there are two pairs (Anne, Andy) and (Heather, Colin) such that Andy likes Heather better than Anne. This means that he must have made an offer to Heather before he made one to Anne and that Heather must have rejected him because someone she liked better made her an offer (either at the same stage as Andy or in a later round). This means that Heather likes Colin better than Andy. So the two pairs (Anne, Andy) and (Heather, Colin) cannot be a source of instability in the set of pairings. And since the same argument works for any two pairs, this shows that the set of pairings is stable.

As we've already seen in the example above, there can be several
stable sets of pairings. We call a stable set *optimal* for a
given individual if,
given any other stable set, that individual does not acquire a partner
with a better rating on his or her list. It turns out that this
algorithm for finding partners gives a stable set of pairings that's optimal for all those who do the
offering — in our example the men. If the women do the offering then
the algorithm gives a stable set of pairings that's optimal for all
the women.

The process can also be used if the number of men and women is not equal: some of the men or women will not have mates. And it can be used when "polygamy" is practiced and every woman can have more than one partner. In this case each woman has a quota and she keeps no more of the male proposers than her quota. The process then stops when each man has been accepted as a partner. Again, the resulting set of pairings is stable.

Is this algorithm really useful? The reader will probably have questioned whether it is reasonable to assume that players will never change their minds about their preferences. It certainly is not if the pairings are supposed to remain stable for a long period of time. People change their minds. However, for short term relationships the algorithm does have value. Here are two more examples of short term commitments, but notice that instead of men and women you apply the process with two disparate groups.

- Workers and tasks to be accomplished: A supervisor rates each worker on his or her ability to do each of the tasks; each employee rates the tasks according to preference. If there are more tasks than workers, practice polygamy: some of the more experienced workers could be given quotas and accept more than one task.
- The college admission system: students rank the colleges they would like to go to in order of preference and colleges do the same with the students that apply to them. Again polygamy is practiced as each college will offer places to more than one student.

### About this article

This article is based on the paper *College admissions and
stable marriages* by D. Gale and L. S. Shapely, published in the
*American Mathematical Monthly*.

Ellen Hetland Fenwick enjoys writing maths articles for the web site, QuirkyScience.com, which
she shares with her chemist cousin. She is currently reading *The Information* by
James Glick and *The Fabric of the Universe* by Brian Green.