Mathematical matchmaking

By Burkard Polster and Marty Ross

The Age, 16 June 2008

Each year, about 50 000 divorces are granted in Australia. Can all this turmoil and unhappiness be avoided? What if we employed a mathematical matchmaker? Well, that might help …

We shall describe some beautiful mathematics, collectively known as marriage theorems. These theorems show how, at least theoretically, we can achieve the noble goal of matrimonial harmony.

We’ll consider the simplest situation. Imagine a Town whose population consists of exactly half women and half men, all of whom know each other. Each man is asked to rank all the women in order of preference, and each woman all the men. (Yes, we can also consider gay marriage theorems, but that is a story for a less controversial day). Then, the job of the mathematical matchmaker is to pair the men and women in a manner that somehow respects these preferences.

Of course, it is not likely that everyone can obtain their first preference. Chances are, the Town will have an equivalent of George Clooney, and only one woman will get him. So, what can we hope to achieve?

Imagine starting with any pairing of the townspeople, and then let us ask what might lead to divorce. So, Angelina may prefer the attractive George to her husband Brad, but this would not normally be a problem. However, if it is also the case that George prefers Angelina to his wife Jennifer, then we have a recipe for divorce.

Such a pairing of the Townsfolk, giving rise to a man and a woman who prefer each other to their assigned partners, is called unstable. And now it is very simple to state a marriage theorem, discovered by the mathematicians David Gale and Lloyd Shapley: there is always a stable pairing of all the townsfolk.

At first glance this is a surprising theorem, but it is actually easy to prove. If we allow the women to propose to the men, we work to satisfy as many of their first preferences as possible (with a nod to the men’s preferences). Then, of the women left, we try to satisfy their second preferences, and so on, until all the women are engaged.

But, there is a catch: the promised pairing will not be unique. For example, if we allow the men to propose to the women we will again get a stable pairing. And, the pairing will likely be completely different, more amenable to the men. The moral? If your heart is set on George Clooney, don’t wait for him to propose to you!

Is this all too reminiscent of Jane Austen? In fact, such “marriages” are now very common. For example, in many countries graduating medical students rank the hospitals at which they hope to do their internship. And, after extensive interviewing, each hospital ranks the applying students. Then, our marriage theorem can be applied to give a stable pairing.

But who does the proposing? In America, it used to be the hospitals. However, after a heated debate, there is now a matching process that favours the students. And in Victoria? Our matchmaker is the Postgraduate Medical Council of Victoria, but we do not know whom they favour. Demonstrating a coyness worthy of a Jane Austin heroine, they have refused to tell us anything of the methods they employ.