by Haim Shapira
Let’s consider the following case (and for the sake of simplicity and demonstration, I’ve narrowed things down to three men and three women only).
Men’s preferences:
Ron: Nina, Gina, Yoko
John: Gina, Yoko, Nina
Paul: Yoko, Nina, Gina
Women’s preferences:
Nina: John, Paul, Ron
Gina: Paul, Ron, John
Yoko: Ron, John, Paul
In my example, every man prioritized a different woman and each woman chose a different man, but not only are there no matches made in heaven here, there’s also reason to worry. I’m sure you know why.
The prospective spouses will only be very happy and enjoy bliss if the man who is the first choice of each woman thinks that she is the woman of his dreams – for example, if Paul loves Gina and she loves him in return; if Nina is crazy about Ron and he worships her; and if John is prince charming to Yoko, who is the woman to die for. In that case we may get the following table of preferences:
Men’s preferences:
Ron: Nina, Gina, Yoko
John: Yoko, Nina, Gina
Paul: Gina, Yoko, Nina
Women’s preferences:
Nina: Ron, John, Paul
Gina: Paul, Ron, John
Yoko: John, Ron, Paul
And what if the three men chose the same woman?
Men’s preferences:
Ron: Nina, Gina, Yoko
John: Nina, Gina, Yoko
Paul: Nina, Yoko, Gina
What do you think should Zoe do?
And what if the three women submit identical lists?
Women’s preferences:
Nina: Ron, John, Paul
Gina: Ron, John, Paul
Yoko: Ron, John, Paul
Zoe may have a lot of troubles…
Now let’s assume that we have 10 women and 10 men. Which is better, having more people receive their first or at least second choice, or having as few people as possible matched with their last choices?
There are no clear-cut answers to this question.
Zoe, however, is a practical woman. She knows that bliss for all was never guaranteed, so she set herself a much more modest goal. Her challenge is to match couples that would remain stable and not cheat on each other.
What does this mean in practical terms? Well, to prevent cheating, Zoe must make sure that she doesn’t form a pair of couples in which there’s a strong attraction outside one of the bonds. Paul and Nina, and Ron and Gina, would be a case in point. Let’s assume that Paul likes Gina more than he does his wife Nina; and Gina likes Paul more than she does her good old Ron. That combination should make cheating inevitable. Note that there shouldn’t be a problem if Paul likes Gina more than his wife as long as Gina loves her husband and not Paul: she’d simply reject Paul’s approaches.
Incidentally, if Paul wants Gina more than he wants his wife Nina, and Gina feels the same toward Paul and doesn’t like her husband Ron, and if Ron prefers Nina to Gina and Nina favours Ron to Paul, this is very easily solved. All we need to do is break up the old couples (Paul and Nina, and Ron and Gina) and create two new and much happier pairs: Ron and Nina, and Paul and Gina.
The Stable Marriage (Gale–Shapley) Algorithm
In 1962 the distinguished American mathematician and 2012 Nobel Prize-winning economist Lloyd Shapley and the late American mathematician and economist David Gale (we met him in the chapter about the Chomp game; see page 33) demonstrated how any given equally sized groups of men and women can be paired up so that no one cheats. It’s very important to understand that their algorithm doesn’t guarantee happiness, only stability. Thus, it may well be that Nina is married to Paul while dreaming about John, but the algorithm guarantees that John loves his wife more than he does Nina. This isn’t to say that John is happily married and he may even dream of another woman; but if so, the algorithm makes sure that that woman prefers her husband to him. And so on …
The Gale–Shapley algorithm is quite simple and comprises a finite number of iterations (rounds). Let’s see how it works with an example of four men (Brad Pitt, George Clooney, Russell Crowe and Danny DeVito) and four women (Scarlett Johansson, Rihanna, Keira Knightley and Adriana Lima). The algorithm will work in the same way for any equal number of women and men.
The following table represents the men’s preferences:
1 2 3 4
Brad Scarlett Keira Adriana Rihanna
George Adriana Rihanna Scarlett Keira
Danny Rihanna Scarlett Adriana Keira
Russell Scarlett Adriana Keira Rihanna
And the women’s choices are as follows:
1 2 3 4
Scarlett Brad Russell George Danny
Adriana Russell Brad Danny George
Rihanna Brad Russell George Danny
Keira Brad Russell Danny George
Instead of explaining the algorithm, let me show you how it works in practice.
In the first round, each man offers himself to the woman on the top of his list. Thus, Brad and Russell approach Scarlett, Danny goes for Rihanna, and George calls Adriana.
Each woman then chooses the man who is highest on her list – that is, if there are more suitors than one. If only one suitor applies, that’s her date even if the man is ranked low in her list of choices; and if none does, she remains single in this round. This is why Scarlett chooses Brad, whom she rated higher than Russell.
Let us look at the couples formed so far. Remember, this is temporary: they are only engaged, not married.
Brad–Scarlett, George–Adriana, Danny–Rihanna
In the next round, men who have no partner yet offer themselves to the woman who hasn’t turned them down yet and is highest on their list. The only unmatched man is Russell (who, incidentally, played Nobel prize laureate John Forbes Nash in Ron Howard’s film), and he offers himself to Adriana.
Since Adriana wanted Russell more than George, she calls off her engagement with George and announces her engagement to Russell. Now we have the following couples:
Brad–Scarlett, Russell–Adriana, Danny–Rihanna
The only lonely man now is George (Sic transit gloria mundi), who offers himself to Rihanna, who gladly accepts because on her list he was rated higher (and is taller) than Danny. Thus:
Brad–Scarlett, Russell–Adriana, George–Rihanna
The legendary DeVito is alone now. He calls Scarlett, but she prefers Brad. Another round, and nothing changes. Next, Danny takes a bet on Adriana, but she’s happy with Russell. Deeply depressed and on the verge of crisis, Danny tries his luck with Keira, and she welcomes him into her arms. She has been so lonely for so long that even Danny would do.
The algorithm ends when all the men are hitched (and clearly all women are engaged too at this stage, because the two groups were equal in number). The finalists, therefore, are:
Brad–Scarlett, Russell–Adriana,
George–Rihanna, Danny–Keira
And they all lived happily (or at least in wonderful stability) ever after.
It’s quite easy to accept that the pairs formed with the Gale– Shapley algorithm will remain stable; but to remove all doubt, let’s prove it. If you, my reader, are not too fond of logical analyses and proofs and if you believe that the Gale–Shapley algorithm works flawlessly, you’re welcome to move right to the next chapter.
Glad to see you stayed for this. Here goes:
This proof comprises three stages: 1) We’ll see that the algorithm reaches an end; 2) We’ll prove that everyone is matched (good news, no?); and 3) We’ll prove that the matches are stable.
1 Clearly, the algorithm can’t run indefinitely. In the worstcase scenario, all men offer themselves to all the women.
2 Clearly the number of engaged men will always equal the number of engaged women. It’s also clear that once a woman is engaged, she remains engaged (even if not to the same man). It’s also impossible for any member of any group to remain unengaged at the end of the process.
Suffice it to say that if Ron writes ‘Nina’ in his list of preferences (even if she’s his last choice), if no other man wants her Ron will have her in the end. Thus, this algorithm makes sure no one is left unpaired.
3 Does this algorithm also guarantee the stability of the couples? Yes – and we shall prove this. Suppose Yoko is John’s spouse and Nina is Paul’s. Is it possible for Yoko to prefer Paul and for Paul to like Yoko better than their current partner, which would bring us to the verge of betrayal?
Below, we’ll assume that it is possible, and then hit a snag – a logical contradiction that will prove it’s actually impossible.
Let’s assume there is instability – that we have two couples, Paul–Nina and John–Yoko, where Paul wants Yoko and she wants him more than either wants their current spouse. According to the algorithm, Paul should have offered himself to Yoko before he went to see Nina (because Yoko, according to our assumption, was rated higher on his original list). Now, two things can happen: (a) Yoko accepts Paul; (b) Yoko rejects Paul.
If (a), why is Yoko not living with Paul? Well, it’s because she chose someone she’d rated higher – John, or someone else. In any case, if she’s with John now, it means that he was rated higher than Paul. Here’s the promised logical contradiction. If (b), Yoko rejects Paul because she has a better man – John, or anyone – but the fact that she is with John now proves that John has been rated higher than Paul, and again the original assumption is contradicted.
In summary: the algorithm ends, everyone has a spouse, and the couples are stable.
What happens when women choose men according to their preferences? The actors’ example will produce exactly the same couples. This is because we have only one stable match here.
This, however, is not always the case. When there’s more than one stable arrangement, different couples are formed when women make the choices.
‘It is a mistake to speak of a bad choice in love, since as soon as a choice exists, it can only be bad.’
Marcel Proust
War of the Sexes: Round 2
It’s time to return to the example that started this chapter and to remind ourselves of each gender’s preferences:
Men’s preferences:
Ron: Nina, Gina, Yoko
John: Gina, Yoko, Nina
Paul: Yoko, Nina, Gina
Women’s preferences:
Nina: John, Paul, Ron
Gina: Paul, Ron, John
Yoko: Ron, John, Paul
A second’s thought will clearly reveal that this case requires only one round. Men present themselves to their first choices and the couples formed are: Ron–Nina, John–Gina and Paul– Yoko. That’s all. Clearly, they are all stable, because all men have found the ladies of their dreams. For men, this is the optimal solution. The women, however, ended with their last choice. They can’t be happy.
If the women offered themselves, a single round would produce the following couples: Yoko–Ron, Gina–Paul and Nina–John. Here too every woman wins her favourite man, while the men have to spend the rest of their lives with their last choice.
Thus we understand that this game gives an edge to the party that offers itself in the first round.
(Incidentally, we have here another stable pairing: Nina–Paul, Gina–Ron and Yoko–John. You’re welcome to examine that stability – that is, to check that cheating won’t take place here.)
Footballers without Models
The Gale–Shapley algorithm isn’t complicated, but it isn’t trivial either. If we drop the two genders assumption and suppose that four footballers have to spend the night before an important match two in a room, we might not find a stable solution with regard to choice of compatible room mate.
These are the footballers and their preferences:
1 2 3
Ronaldo Messi Pele Maradona
Messi Pele Ronaldo Maradona
Maradona Ronaldo Messi Pele
Pele Ronaldo Messi Maradona
Check this and you’ll see that no pairing would be stable here.
And the Nobel Goes to …
There are many ways in which the Gale–Shapley algorithm can be used. The most famous of these uses is the application of medical school graduates to hospitals for their internship. I would bet you’ve already guessed that hospitals won the role of first proposer (and certain legal suits on the issue are still pending). Another important application of ‘stable marriage’ is in assigning users to servers in Internet service.
In 2012 Roth and Shapley won a Nobel prize for their work on the Theory of Stable Allocations and the Practice of Market Design, based on the Gale–Shapley algorithm.
Gale passed away in 2008 and thus never received the prize, while Alvin E Roth won an award after finding other important applications for the Gale–Shapley algorithm. Roth is also the founder of the New England Program for Kidney Exchange.
* A utility function is a measure of preferences. It assigns numerical values, named ‘utilities’, to all possible outcomes. The preferred outcomes will get higher numbers. Different people are assumed to have different utility functions.
Intermezzo
THE GLADIATORS GAME
The Gladiators Game is one of my favourites. I always use it when I teach probabilities or Game Theory. This difficult exercise is mostly recommended for real maths enthusiasts.
The game goes like this. There are two groups of gladiators – A(thenians) and B(arbarians). Let’s suppose that Group A comprises 20 gladiators and Group B 30 gladiators. Each gladiator has an identifying number, a positive integer, that denotes his strength (let’s say it’s the number of kilograms he can lift). The gladiators fight each other in duels. Their winning probabilities are as follows: when a gladiator whose power is 100 fights a gladiator with a power of 150, his odds are 100 divided by (100 + 150) because the stronger a gladiator is, the better are his winning chances. If the duelling gladiators are of equal force, their winning chance is 50 per cent, of course, and the larger the gap between them the better are the odds for the stronger gladiator.
Both groups have a coach who decides on the order gladiators will be sent into the ring but who only makes this decision once. He may decide to send his strongest guy first or last but, in any event, whoever wins a duel goes back to the end of the line and waits for his turn there – you can’t have your strongest gladiator fighting all the time. Now, when a fight ends, the loser is eliminated from the competition, while the winner absorbs the loser’s strength – that is, when Gladiator 130 beats Gladiator 145, the latter is taken out of the game while the former is re-christened Gladiator 275. The game ends when one of the groups runs out of fighting gladiators, which naturally makes it the losing group.
So what would be the best strategy here? What should be the order of fighters in the ring? (Take a moment to think about this before you go on reading.)
The answer is quite surprising: you don’t need a coach at all. The order of the fighters can’t change the odds in any way. The odds of winning are equal to the combined strength of a team of gladiators divided by the combined strength of both teams put together.
Prove it! (Hint: Don’t start with the general case! – that would be difficult. Start with one Athenian gladiator and two Barbarians; then check what would happen in the case of two Athenian gladiators and two Barbarians … I hope you’ll find the pattern. You can also try to solve this by the method of induction.)
I can’t say that this exercise offers any important insight for team sports coaches. Clearly, coaches are important, though sometimes that importance is slightly overrated.
Chapter 6
THE GODFATHER AND THE PRISONER’S DILEMMA
I devote this chapter to the most popular game in the entire Game Theory repertoire – the Prisoner’s Dilemma. We’ll review every aspect of the game, including the ‘iterated’ Prisoner’s Dilemma version, and learn something really important: that egoistical behaviour is not only morally problematic but in many situations it’s
also strategically unwise.
The most famous and popular game in Game Theory is the Prisoner’s Dilemma. This evolved from an experiment that Melvin Dresher and Merrill Flood conducted for the RAND Corporation in the 1950s. Its name is based on a story that Albert Tucker told in a 1950 lecture on that experiment at Stanford University’s Psychology Department. Countless articles, books and doctorate dissertations have been written about the subject, and I believe that only a few people, even outside academia, will never have heard of it.
In a popular version of the game, let’s consider two guys, evocatively named A and B. Having been arrested, they are now in custody, and the police suspect they have committed a terrible crime, but they have no tangible proof of this. Thus, the police need them to talk, preferably about each other. Now, detainees A and B are told that if they both decide to keep silent, both will have to serve a one-year prison sentence on a lighter charge such as a burglary or some other misdemeanour. The prosecutors offer them a deal: if one of them betrays the other, he will go free immediately; the other, however, will serve a 20-year sentence for the now provable crime. If each incriminates the other, they will both serve 18 years (they get a 10 per cent discount for aiding the prosecution). The detainees have been separated and must make their decision in ignorance of the other, namely they cannot know of the decision of the other until they have irrevocably made theirs.
The following table sums up the rules of the game (figures are prison years):
Prisoner B
Is Silent Betrays
Prisoner A Is Silent 1, 1 20, 0
Betrays 0, 20 18, 18
