Gladiators, Pirates and Games of Trust

by Haim Shapira

  That scene is in the film for a reason. The story has a parallel situation in Game Theory. Read on.

  MATCHMAKING STRATEGIES

  Imagine 30 men and 30 women in a room from which they are supposed to emerge in pairs. For clarity’s sake, the pairing mechanism is strictly heterosexual. Each man has a note with a digit on it – 1 through 30. The men survey the women and select their favourite one. (Of course, you may imagine a game in which women survey the men and select their favourite one. In any event, remember: this is just a game.) Then, each man sends a note with his number to the lady of his choice. The women who receive the notes must choose the man they like the most from among those who have offered themselves. Women who received several notes must choose one; and a woman who has received a single note must pair up with the sender.

  In an ideal world the outcome should be quite obvious: the men choose a different woman each, every woman receives a single note, and so the game ends. Reality, however, is far from this ideal. Very often, when I introduce this game, people tell me, ‘Aha! I know what’s going to happen. There’ll always be one woman who receives all the men’s notes.’ However, let’s not jump to such uncomfortable conclusions. Aristotle said that the truth is always somewhere between the extremes, but rarely right in the middle.

  I once presented this game to the employees of a hitech company. One of the participants (with a PhD in mathematics) raised her hand and said she knew this game perfectly well and had been thinking about it for several years. She shared her insights with us, saying that in an average situation (only she knew what she meant by that) the number of women who receive notes will be roughly the square root(!) of the number of participating women. I didn’t inquire further into the square-root formula because I didn’t want to lose control of my lecture, but let’s honour her and assume that, indeed, five women receive notes. Yes, I know that the square root of 30 is larger than 5, but we must remember that women come in integers. In this case, the average number of notes per woman is 6, though this tells us nothing about distribution. Now, the women who have received notes must choose their favourite man, pair up with him, and take him up to the roof where a big party is being thrown for all the newly formed couples.

  After they leave the room, the game continues in very much the same way, with the remaining 25 men and 25 women.

  If it weren’t for our human repression mechanisms, those who remained in the room would have been deeply depressed already at this early stage of the game. At this point, all the men in the room know that they won’t win the woman they truly desire, because she didn’t want them and is probably dancing now on the rooftop with the man she did choose. So now I have an opportunity to give a brief psychology class. It will be a very concise but profound lesson, and its basic idea is: ‘Every time a friend succeeds, I die a little.’ End of class. The women left in the room have good reason to feel down as well, because they know now that no man really wanted them. After all, the first-choice women are now partying on the roof. This is very sad. Luckily for us, we do have excellent repression responses, and so the game goes on as if nothing untoward had happened.

  Now, the remaining 25 men send notes to the ladies they choose from the remaining 25. Suppose 11 women receive notes, and each of those now chooses her favourite man. The number of players declines again and again, and so it goes until no one is left in the room.

  Thus the story ends with 30 perfect pairs. All clear and simple so far. Or is it?

  Well, not really. To demonstrate the complexity, I’ll personally participate in the game. As I walk into the room, I’m overjoyed when I see a very pretty woman sitting there among the participants. Let’s call her A (short for Angelina Jolie or Adriana Lima or Anna Karenina, for example). I fancy her, of course, and so instinctively it seems that sending my note to her would be a good idea. But should I really? Remembering the sad story of Nash’s friends in that pub, I realize that I should think again. If I like her so much, it stands to reason that many other men like her too, which means that she’ll be receiving not only my note, but almost all 30. Thus, the chances that she’d choose me in return are actually quite slim. I’ll probably be turned down and move to the next round, in which case I’ll go for my second choice, whom we shall name most romantically: B. Again, it’s very likely that I won’t win B’s heart, because most of the men that A rejected before will now aim at the lovely Ms B. Thus I’ll keep falling and sinking, and might even end up in Z’s arms.

  OK. We’ve all got the idea. So how should I play this game? What would be the most reasonable strategy? What does it depend on? If opting for my first choice is too risky, perhaps I should compromise a little in the first round and choose D, who was actually my fourth choice.

  A Yiddish saying goes: ‘If you don’t compromise a little in the beginning, you’ll make a huge compromise in the end.’

  It’s decided then: I choose D. But wait! What if everyone else is familiar with the tip I just gave you and all send their notes to women who are a bit lower in their charts? In this case, there is a good chance that A-for-Angelina will actually receive no notes. It would be a shame not to use that to my advantage! Remember how the cinematic Nash convinced his friends to compromise a little to win the blonde?

  Important tip Before making a decision, ask yourself what would happen if everyone shared your views. And remember that not everyone shares your views.

  The truth is that this could develop into something even more interesting. Suppose all the men in the room, except one boy named Johnny, took classes in Game Theory, decisionmaking and even multivariable optimization. Trying to figure out what to do, they are all busy making complicated calculations. They tell themselves: ‘We should not be sending our note to A because, for the aforementioned reasons, she wouldn’t choose us – we’d be relegated to the next round, where we wouldn’t be much better off. And so on. While the men all think like that, Johnny doesn’t use his thinking app. Weighing options is not an option for him. Johnny simply looks around him, sees A, decides he likes what he sees, sends her a note, and actually wins her simply because he was the only one who proposed. (Incidentally, this story could explain some of the odd couples you may know.)

  Yes, Johnny won A precisely because he lacked sophistication. When I give workshops for executives, I enjoy presenting them with an equivalent economic model where the least clever player (I cast myself in this role) makes the highest profit when competing against rather clever players (the execs).

  THE NASH EQUILIBRIUM (AND THE BRAVE LIONESS)

  This seems like the right time to define one of the most basic concepts in Game [was: Games] Theory: the Nash Equilibrium. Let me define it slightly imprecisely (slight imprecision sometimes helps in avoiding protracted explanations):

  The Nash Equilibrium is a situation in which no player benefits from changing their current strategy, assuming they can control only their own decisions.

  We could put it this way:

  The Nash Equilibrium is a set of strategies which none of the players would change, assuming that they can control only their own decisions, even if they had known the strategies of the other players in advance.

  The strategy of compromising in the matchmaking game, for example, is not a Nash Equilibrium, because if all the players were to make compromises, you should not: you should actually send your note to A.

  I’m certain that you, my intelligent reader, have already realized that if all players were to send their notes to A, that would not be the Nash Equilibrium either.

  And how about the dinner with friends who share the bill? Would ordering the cheap dishes be the Nash Equi- librium? How about the expensive dishes? What if everyone orders the most expensive dish on the menu – is that the Nash Equilibrium? Think it through until you’re sure of the answer.

  Finally, here’s yet another example that sheds some light on the Nash Equilibrium concept. It comes from the field of animal behaviour. It seems easier to speak about animals because, in
a way, animals seem rational – that is, all but one animal, the human being, who often acts irrationally. This is why analysing human behaviour is more difficult than analysing the behaviour of other species.

  This example is taken from a scene I accidentally saw on a TV science channel. It showed a single lioness attacking a herd of about 100 buffaloes which – surprise, surprise – fled the assailant one and all. As any intelligent person would, I asked myself, why did they run? Clearly, a hundred buffaloes are stronger than one lioness. All they need to do is turn around and gallop in her direction, and we would have had ourselves a lioness carpet within minutes.

  Why didn’t they do that? I wondered, but then I remembered Nash. Running from the lioness is a perfect case of the Nash Equilibrium. Let me explain. Suppose all the buffaloes run from the lioness and only one of them – I’ll name him George – thinks: ‘Hey, I’m being filmed here for the science channel, which has a very high rating (George is a prairie buffalo, so he isn’t that rating savvy), so I can’t be seen fleeing. What if my grandsons are watching?’ (If George is anything like me, he might also be worried that his mother could be watching.) And so our dear George decides to turn around and lash at the prowling lioness. Did he make a wise and correct decision? Absolutely not. This decision was not only wrong, but also the last one George ever made. The lioness was indeed startled at first when she saw her steak running towards her plate, but she soon recovered from the shock, and George was gone within minutes. When the entire herd is running away from the lioness, the best strategy is to run along. This strategy must not be changed! In this case, therefore, fleeing is the Nash Equilibrium.

  Now, let us suppose that the herd of buffaloes decided to counter-attack the lioness. This would not be the Nash Equilibrium, because if it’s known in advance that the herd is about to attack the lioness, the buffalo who does not join them will clearly benefit. After all, even if the entire herd is on the attack, some of the buffaloes still risk getting wounded or worse. And so we may see buffalo Reginald call from the rear to his assaulting comrades: ‘Oh, my shoelace just came undone. I can’t join you on this attack. Just go on without me!’ Reginald benefits because he takes no chances.

  Running away from the lioness is the Nash Equilibrium. When everyone is running away, every single buffalo would benefit from running along, provided he can make decisions only about himself. This, indeed, is what we often see in nature. At the same time, attacking the lioness is not the Nash Equilibrium, because when everyone goes on the assault, this is a perfect time to tie your shoelaces. This is why we rarely see such counter-attack strategies in nature.

  Does a similar thing happen when a single terrorist or a small group of terrorists manages to hijack a plane with numerous passengers on board?

  World War Two documentaries time and again show endless rows of German POWs marching in the snow, guarded only by two sluggish Red Army soldiers. Why did the Germans not attack their guards? I often wondered. Is it possible that the Russian soldiers explained to the German prisoners that attacking them would be deviating from the Nash Equilibrium, even though Nash hadn’t yet figured it out himself? (Remember that, while they are forbidden to speak, the POWs can control only their own decisions.)

  The nice thing about the Nash Equilibrium is that many games, regardless of their starting point, eventually end up at the Nash Equilibrium point. To some extent, this is bound up with the very definition of the Nash Equilibrium – a kind of stable situation which, once attained, is maintained by players for ages. Naturally, this is only true when there’s no external intervention and other players can’t be affected.

  How, then, are we to explain hyenas, who behave quite unlike those buffaloes? Hyena packs were often seen attacking solitary lions or other animals that are bigger and stronger than they are. After all, attacking a lion might not benefit the hyenas. That is, it may certainly serve them as a group, but when it comes to each hyena making its personal decision individually, it would be better off stopping to tie its shoes. So why and how do they organize and attack the lion together? This dilemma really troubled me, because the hyenas behaved as if they’d never heard about Nash … and that’s just pure ignorance!

  The science channel came to my rescue once more. A documentary showed a pack of hyenas forming a circle before going on a hunting expedition, and moving their bodies in unison while howling and making other noises, just like basketball teams do. They drive themselves into ecstasy and launch the attack while foaming at the mouth – that is, they attack together only after the betrayal strategy is no longer an option, because when you’re ecstatic about something, you can’t betray your peers … and that’s a fact. This may explain the source of hunting and war dances in ancient tribes. When a group of people decides to hunt an elephant, or even a scarier animal like a mammoth, they must drive themselves into ecstasy first. Otherwise, each individual would naturally think to himself: ‘A mammoth? Forget it, man. Things might get messy. Don’t shoot your arrows at it and put away your spears. It isn’t worth it.’ But if they all thought like that, they’d never be able to hunt themselves a tasty mammoth and they’d probably die of starvation. Humans need to cooperate and so, like the hyenas, they form a circle, dance with their spears in hand, get ecstatic, and then go hunting.

  Still, we should remember that not only with humans, but with animals too, things are never as simple as they seem. One of the most popular YouTube clips in 2008, ‘Battle in Kruger’, was an amateur video clip showing a group of African lionesses isolating a buffalo calf and pushing it toward the river, where they could feast on his flesh. Then, just as the lionesses started sharpening their knives, a crocodile stormed out of the river and attempted to grab the poor calf for himself. The lionesses fought back and reclaimed the baby buffalo. But seconds before it turned into an afternoon snack, the buffalo herd returned(!), lashed at the lionesses, drove them away, and rescued the calf – making it a happy ending (for the buffaloes).

  How is this explained? I don’t know. Buffaloes rarely talk to the media.

  In any case, we should always remember this wonderful piece of advice (particularly if you go on reading this book):

  Most things are more complicated than they seem, even if you think you understand this sentence.

  Let’s return to the matchmaking problem. One of the questions that all the partner-choosing game players should ask themselves is: What’s my goal? What do I expect to achieve from this game? The truth is that this is a good question to ask about any game.

  Knowing your goal before determining the strategy is crucial. I often saw people starting games without defining their goals first. Remember what the Cheshire Cat told Alice: if you don’t care where you’re going, ‘then it doesn’t matter which way you go.’ Your goal is most relevant when you choose your strategy or, if you will, your path. If, for example, a player in a partner-choosing game follows the Cesare Borgia principle, O Cesare o niente (‘Cesare or nothing’) – that is, he wants A to himself no matter what – then his strategy is obvious. He should send his note to Angelina and pray hard. There’s no other way. If he doesn’t send his note to her, he definitely won’t win her. He’ll certainly not attain his goal.

  Players with such a utility function* enjoy risks. On the other hand, if a player’s goal is merely not to end up with Z – that is, anything goes but Z (a risk-aversion player) – his optional strategy is clear too. Suppose that Y is one notch higher than Z on the chart of desire. The risk-hater should start by sending his note to Y – that is, in the first round. Still, things, as always, are more complicated than they seem at first glance. What if many other players should decide that their utility function is ‘anything but Z’? In that case Y will receive a bunch of notes she never expected (and wonder what made her so popular all of a sudden).

  Not only is it not clear how this game should be played, but it isn’t easy to put even its basic assumptions into words. What’s the distribution of the men’s taste in women? In the two
extreme cases, all men either rank all the women the same, or there’s a total ranking chaos, but both these assumptions are, of course, unrealistic. The actual distribution must be somewhere in between. And how does the men’s self-esteem factor in? Also, what’s the distribution of the men in terms of risk-taking? In short, a lot of preparation is required and many unknowns need to be settled here before we can even begin to solve this game mathematically.

  The Bible says that God created the whole world in seven days. According to Jewish tradition, ever since then He has been busy matching pairs. You can guess how difficult it’s going to be ensuring the right match for everyone. Still, if God is involved, there may be a light at the end of the tunnel after all.

  THE STABLE MARRIAGE PROBLEM

  (ON LOVING COUPLES, CHEATING AND NOBEL PRIZES)

  Matchmaker’s Problem

  Zoe the Matchmaker has a list of 200 clients – 100 men and 100 women. Each woman presents Zoe with a list of the 100 men arranged in her order of preference. Topping the list is Prince Charming, followed by her lesser choices all the way down to the 100th. The 100 men on Zoe’s list have all done the same with the women’s list, rating them by order of preference.

  Zoe is now supposed to match each client with a member of the opposite sex and make sure they all marry, build a home, and live relatively happily ever after. Clearly, some of her clients are not going to end up with their first choice. If one man on the list was selected first by two or more women, someone will have to settle for less. Yet even if no man is chosen by more than one woman as her perfect match, and no woman is preferred by more than one man, bliss is not guaranteed.