Andy 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:

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.