about me
game theory
... more
Subscribe Weblog


game theory

chalkExcerpt of an interview with Nobel laureate Robert Aumann*:

Q: Game theory as a subject seems to have been rarely applied to real business situations. To what do you attribute this?

Prof. Aumann: That is absolutely incorrect. Game theory as a subject is very often applied to real business situations. There is a tremendous range of applications of game theory, both cooperative and non-cooperative. Game theory has been applied to law, auctions, matching markets, and all kinds of things. Let me just mention, for example, the matter of matching people to jobs, which is a tremendous field in which the prominent people are Alvin Roth, Marilda Sotomayor, David Gale, and Lloyd Shapley. There is also the very hot new topic of matching kidney donors to patients who need a transplant, in which game theory has been highly effective. Let me also mention something completely different, such as the issue of how to charge for telephone calls. In large organizations, such as government offices, universities, and corporations, they place a large number of phone calls. Although these days this is very cheap you still have to pay for it. And the question is how to do the charging, and this is something that is a matter of cooperative game theory. The first work on that was done by Billera and Heath in the late 1970s. There is a whole field called industrial organization, which is largely a matter of game theory. There is a tremendous amount of game theory that goes into the design and the question of strategy choice in auctions, for example. Around ten years ago, the U.S. Congress decided that it was no longer going to give away electromagnetic frequencies and that they wished to start auctioning them off. There was a big auction for frequencies that were to be used for cellular phones, called the “Spectrum Auction,” and the Federal Communications Commission (FCC) hired game theorists to design the auction. Communication corporations used other game theorists to advise them on their bidding strategies. This auction was a tremendous success for the FCC and the government. They were expecting U.S.$500 million and they actually got almost one hundred times that. They got U.S.$45 billion dollars out of this auction, and that is because of game theoretic design. The range of applications of game theory to real business situations is simply enormous, so what you suggest with your question is absolutely not the case.

Q: Then allow me to reword my question in another way. Are you happy with the proliferation of game theory in real business?

Prof. Aumann: Of course I am happy. It is an applied science, absolutely. It is amazing how useful it is, and for all kinds of things, such as traffic, arbitration, auctions, etc. There is a lot of useful work. Let me give you another example of how game theoretic principles have been applied to business. Let’s look at the example of “final offer arbitration.” In most arbitrations you have, say, an employer and the union, and they are fighting over a wage contract and the union threatens to strike. Let us say that after a long period of shadow boxing they agree to binding arbitration, where the union and the employers will present their demands (i.e., how much they are willing to accept or pay). The arbitrator will listen to both sides and he will usually arrive at some sort of a compromise, depending on how convinced he is of the merits of the cases that are presented by the two sides. So, what are the incentives in this case? The incentives are for both sides to exaggerate their claims. Let us say that the union is satisfied with a payment of 85. However, they know that if they ask for 85 they might get less, so they ask for more, just like in any other bargaining situation. So they ask for 110. On the other side, the employer might be willing to pay 65, but they also know that if they offer 65 they might end up having to pay more. So they offer 45. As for the arbitrator, his range of decisions has now become enormous, and that is not good for either side. Now there is an alternative scenario that has been suggested by game theorists, called “final offer arbitration,” which essentially means that the arbitrator is not allowed to compromise; he must choose one of the two positions, exactly as they have been presented by the different parties. Some might question the logic of such a process, since many believe that the arbitrator is there in order to compromise. But look at the incentives that this creates. The incentives are now the opposite of what they were in the classical kind of arbitration, because now each side is motivated to present as reasonable, as moderate, a claim as possible. If the union claims 110 and the employer decides to go to 65, the arbitrator will realize that given the details of the case, 65 is much more reasonable. The arbitrator cannot increase that, so he would award 65. Consequently, the union will decide not to make an unreasonable claim, and may even be willing to claim a little less than what it really wants. As a result, the offers of both sides would be very close to each other and the arbitrator will not have much work, as he will choose one of the two sides. The implication is that both sides become more truthful, and perhaps even a little more forthcoming. This is a very simple application of game theory, but it explains the basis of game theory, and that is to build a system where the sides have an incentive to do what you want them to do; in this case you want them to agree to be as close to each other as possible and give the arbitrator as much information as possible.

*Journal of Financial Transformation, April 2007

30600New Scientist: [U]sing a tool called the ultimatum game, researchers have identified the part of the brain responsible for punishing unfairness.

Previous brain imaging studies have revealed that part of the frontal lobes known as the dorsolateral prefrontal cortex, or DLPFC, becomes active when people face an unfair offer and have to decide what to do. Researchers had suggested this was because the region somehow suppresses our judgement of fairness.

But now, Ernst Fehr, an economist at the University of Zurich, and colleagues have come to the opposite conclusion – that the region suppresses our natural tendency to act in our own self interest. They used a burst of magnetic pulses called transcranial magnetic stimulation (TMS) – produced by coils held over the scalp – to temporarily shut off activity in the DLPFC. Now, when faced with the opportunity to spitefully reject a cheeky low cash offer, subjects were actually more likely to take the money. The researchers found that the DLPFC region's activity on the right side of the brain, but not the left, is vital for people to be able to dish out such punishment. "The DLPFC is really causal in this decision. Its activity is crucial for overriding self interest," says Fehr. When the region is not working, people still know the offer is unfair, he says, but they do not act to punish the unfairness.

Moral centre?

"Self interest is one important motive in every human," says Fehr, "but there are also fairness concerns in most people." "In other words, this is the part of the brain dealing with morality," says Herb Gintis, an economist at the University of Massachusetts in Amherst, US. "[It] is involved in comparing the costs and benefits of the material in terms of its fairness. It represses the basic instincts." Psychologist Laurie Santos, at Yale University in Connecticut, US, comments: "This form of spite is a bit of an evolutionary puzzle. There are few examples in the animal kingdom." The new finding is really exciting, Santos says, as the DLPFC brain area is expanded only in humans, and it could explain why this type of behaviour exists only in humans.

Fehr says the research has interesting implications for how we treat young offenders. "This region of the brain matures last, so if it is truly overriding our own self interest then adolescents are less endowed to comply with social norms than adults," he suggests. The criminal justice system takes into account differences for under-16s or under-18s, but this area fully matures around the age of 20 or 22, he says. [Source]

eshockNew Scientist: A lust for vengeance may be hardwired into the male brain. Scans of brain activity suggest that men experience greater satisfaction than women in seeing cheaters get their comeuppance – at least when the punishment is physical.

Tania Singer of University College London and colleagues used a functional magnetic resonance imaging (fMRI) machine to analyse the brain activity of 32 volunteers after their participation in a simple game, called the Prisoner's Dilemma. Click here to continue reading.

Avinash Dixit writes in Restoring Fun to Game Theory[1]: Many movies contain scenes that illustrate some aspect of strategic interaction. These scenes can be screened in class as an introduction to that topic, and a discussion can lead to theorectical analysis of it.

Brinkmanship: Many movies have scenes that deal with the question of how to get some vital information that only your adversary possesses because he knows that the threat of killing him in not credible. The situation plays out differently in High Wind in Jamaica, Crimson Tide, The Maltese Falcon, and The Gods Must Be Crazy... In The Maltese Falcon, the hero, Samuel Spade (played by Humphrey Bogart), is the only person who knows where the priceless gem-studded falcon is hidden, and the chief villain, Caspar Gutman (Sydney Greenstreet), is threatening him for his information. This produces a classic exchange, here cited from the book (Hammet 1930, 223-24) but reproduced almost verbatim in the movie.
Spade flung his words out with a brutal sort of carelessness that gave them more weight than they could have got from dramatic emphasis or from loudness. "If you kill me, how are you going to get the bird? If I know you can't afford to kill me till you have it, how are you going to scare me into giving it to you?"

Gutman cocked his head to the left and considered these questions. His eyes twinkled between puckered lids. Presently, he gave his genial answer: "Well, sir, there are other means of persuasion besides killing and threatening to kill."

"Sure," Spade agreed, "but they're not much good unless the threat of death is behind them to hold the victim down. See what I mean? If you try something I don't like I won't stand for it. I'll make it a matter of your having to call it off or kill me, knowing you can't afford to kill me."

"I see what you mean." Gutman chuckled. "That is an attitude, sir, that calls for the most delicate judgement on both sides, because, as you know, sir, men are likely to forget in the heat of action where their best interests lie and let their emotions carry them away."

Spade too was all smiling blandness. "That's the trick, from my side," he said, "to make my play strong enough that it ties you up, but yet not make you mad enough to bump me off against your better judgment."
The class discussion can explore the nature of these strategies. The scene can be seen as an example of Schelling's (1960, 17-18, [The Strategy of Conflict]) idea of the (strategic) rationality of (seeming) irrationality; Gutman is making his threat credible by pointing out that he might be irrationally. It is better seen as an example of the dynamic game of brinkmanship (Schelling 1960, ch.8; 1966, ch. 3). Both parties, by persisting in their actions--Gutman in his torture and Spade in his defiance--are raising the risk that Gutman may get angry and do something against his own rational interest. Each is exploring the risk tolerance of the other, in the hope that it is lower than his own risk tolerance so that the other will blink first. A more formal analysis of this in the context of the Cuban missile crisis is found in Dixit and Skeath (2004, ch. 14,[Games of Strategy]).
The scene from The Gods Must Be Crazy makes this escalation of risk more explicit. An assassination attempt on the dictator of an African country has failed, and one of the team of gunmen has been captured. He is being interrogated for the location of the group's headquaters and the leader. The scene is in the inside of the helicopter. The blindfolded gunman is standing with his back to the open door. Above the noise of the rotors, the army officer questions the gunman a couple of times and gets only shakes of the head. Then he simply pushes the gunman out the door. The scene switches to the outside of the helicopter, which we now see is just barely hovering above the ground, and the gunman has fallen [2 meters] on his back. The army officer appears at the door and says, "The next time it will be a little higher."
Brinkmanship arises in many economic contexts, most notably that of wage bargaining where the risk of a strike or of a lockout increases as protracted negotiations fail to produce results. Understanding the subtleties and the risks of this strategy is therefore an important part of an exonomist's education, and these movie scenes illustrate it in memorable ways.

Nash Equilibrium: ... The crucial scene from the movie, where Nash is supposed to have discovered his concept of equilibrium, shows him in a bar with three male friends. A blonde and her four brunette friends walk in. All four men would like to win the blonde's favour. However, if they all approach her, each will stand at best a one-fourth chance; actually, the movie seems to suggest that she whould reject all four. The men will have to turn to the brunettes, but then the brunettes will reject them also, because "no one likes to be second choice." In the movie, Nash says that the solution is for them all to ignore the blonde and go for the brunettes. One of the other men thinks this is just a ploy on Nash's part to get the others to go for the brunettes so he can be the blonde's sole suitor. If one thinks about the situation using game theory, the Nash character is wrong and the friend is right. The strategy profile where all men go for the brunettes is not a Nash equilibrium: Given the strategies of the others, any one of them gains by deviating and going for the blonde. In fact, Anderson and Engers [pdf, opens with errors] (2002) show that the game has multiple equilibria, but the only outcome that cannot be a Nash equilibrium is the supposedly brilliant solution found by the Nash character.

Mixed Strategies: The concept of mixed strategies is often initially counterintuitive. Although many situations in sports serve to introduce it, I like one scene from The Princess Bride, a whimsical comedy that has the added advantage of being a favorite teen movie. In this scene, the hero (Westley) challenges one of the villains (Vizzini) to a duel of wits. Westley will poison one of two wine cups without Vizzini observing this action and set one in front of each of them. Vizzini will decide from which cup he will drink; Westley then must drink from the other cup. Vizzini goes through a whole sequence of arguments as to why Westley would or would not choose to poison one cup or the other. Finally, he believes he knows which cup is safe and drinks from it. Westley drinks form the other. Just as Vizzini is laughing and advising Westley to "never go against a Sicilian when death is on the line," Vizzini drops dead.
Pause the videotape or disc at this point and have a brief discussion. The students will quickly see that each of Vizzini's arguments is inherently self-contradictory. If Westley thinks through to the same point that leads Vizzini to believe that a particular cup will contain the poison, he should instead put the poison in the other cup. Any systematic action can be thought through and defeated by the other player. Therefore, the only correct strategy is to be unsystematic or random.

Asymmetric Information: Actually, this is not the main point of the story. Resume the tape or disc. The princess is surprised to find that Westley had put the poison in the cup he placed closer to himself. "They were both poisoned," he replies. "I have been building up immunity to Iocaine for years." Thus the game being played was really one of asymmetric information; Vizzini did not know Westley's payoffs and did not think the strategy of poisoning both cups was open to him. At this point, you can show a clip from another movie classic, Guys and Dolls. Sky Masterson recalls advice from his father: "Son, no matter how far you travel, or how smart you get, always remember this: Some day, somewhere, a guy is going to come to you and show you a nice brand-new deck of cards on which the seal is never broken, and this guy is going to offer to bet you that the jack of spades will jump out of this deck and squirt cider in your ear. But son, do not bet him, for as sure as you do you are going to get an ear full of cider" (Runyon 1933 [1992]).

Dr. Strangelove. ... A good case can be made for screening the whole movie and discussing it.

[1] Journal of Economic Education, Summer 2005, Volume 36, Number 3

Consider the following version of the ultimatum bargaining game: Player 1 has the first move. He can choose how to divide a cake of size normalised to 1 and offer player 2 a part of this cake, say x, which is an element of the closed interval [0,1]. Player 2 gets to know player 1's offer and can accept the offer or reject it. If he accepts, he gets x and player 1 gets 1-x. If he rejects, both player get nothing.

My questions:
1. What is the Nash equilibrium of this game?
2. Is this Nash equilibrium subgame perfect*? Why (not)?

*A Nash equilibrium for an extensive form game (an extensive form with perfect information is basically a rooted tree with a partition of the set of moves) is subgame perfect if it induces a Nash equilibrium in every subgame.

About a month ago, Michael asked me to give my opinion on an article on cheating viruses and game theory. Coincidentally, I had to write a referee report on a paper about evolutionary game theory (EGT) only recently, so I have collected further material and ideas about this topic which I would like to share with you:

Jörgen Weibull's paper "What have we learned from Evolutionary Game Theory so far?" provides a great non-technical introduction to EGT. It gives a first idea of what EGT is all about. I very much appreciated the reference list of this paper as well. In Evolutionary game dynamic, Josef Hofbauer and Karl Sigmund dig a little deeper and provide some interesting insights into the relationship between systems of differential equations (inclusions) and special equilibrium refinements (notable ESS and ES). Finally, I would like to draw your attention to Daniel Friedman's paper "On economic applications of evolutionary game theory". This paper is also non-technical and its objective is to make the general ideas behind an evolutionary game theoretic model more tranparent. As the title suggests, Friedman gives a nice outline of how these ideas can be incorporated into economic models.

In a series of laboratory experiments, evolutionary biologist Paul Turner at Yale University (nice website) has now discovered cheaters among viruses. Turner applied game theory to the experimental evolution of a virus that preys on bacteria, the phi-6 bacteriophage. According to him, the study is the first to demonstrate the evolution of irrational, selfish behavior in a biological system.

In a featured article in the September-October 2005 issue of Amercian Scientist ($, 9 pages) he writes: The temptation to cheat appears to be a universal fact of life. In the struggle to survive and reproduce that drives evolution, selfish individuals may be favored over cooperators because they are more energy efficient. By definition, cheaters expend relatively little energy in a task because they specialize in taking advantage of others—“suckers”—whose efforts they co-opt to their own advantage. In certain animal species some males exert tremendous energy maintaining and defending territories to attract females. Meanwhile, the population may contain subordinate “sneaker” males that are uninterested in territory but linger at the boundaries and specialize in surreptitious copulations. This strategy is very successful for maintaining a subpopulation of sneakers, but it’s unlikely that the population will evolve to contain only cheaters because territorial males are most attractive to female mates. In general, cheaters are highly successful when they are rare because they frequently encounter suckers. The benefits of cheating wane as more individuals in the population opt to cheat. In the parlance of evolutionary biology, the success of cheaters should be governed by frequency-dependent selection. That is, some cost should be associated with a cheating strategy so that selfish individuals are at an advantage when they are rare, but disadvantaged when they are common.<> Our experiments suggest that yes, perhaps at this moment, there may be cheaters among the viruses vying for survival within and near your own cells. But in the long run, such crimes don’t always pay.

Here is how he estimated the payoffs:
payoffmatrix_turner"Experiments between cheating and cooperating viruses allow scientists to estimate the fitness payoffs for each of the strategies in a 2×2 matrix (right). In the prisoner’s dilemma, when two cooperators interact the reward is defined as R = 1. When a cheater meets a cooperator, the temptation to cheat, T, must exceed the reward for cooperating by some value, say s2, so that T = 1 + s2. So the fitness of the cheater relative to the cooperator is T/R, when the cheaters are rare. The value of s2 can be determined from experimental data. My colleagues and I set the equation, T/R = (1 + s2)/1, equal to the left y-intercept of the regression line for the data (see graph below).
The y-intercept represents the case where a cheater is very rare [...] and therefore guaranteed of interacting with cooperators. So an individual cheater receives the maximum benefit: T/R = (1 + s2)/1 = 1.99, and s2 = 0.99. When two cheaters meet, there is a loss of fitness, and the punishment for cheating is defined as P = 1 – c. A cooperator also loses fitness when interacting with a cheater and receives the “sucker’s payoff,” S = 1 – s1. Here we set P/S = (1 – c)/( 1 – s1) equal to the right y-intercept of the regression line, which represents the case when there is the greatest frequency of cheaters. Because our results found that the right y-intercept was a number greater than one, P had to be a value greater than S. However, the ratio cannot be solved because of two unknown variables, c and s1. We needed to devise an additional experiment to directly estimate P or S. We did this by measuring the growth rates of the cheaters and cooperators when co-infecting cells on their own. turner02This experiment mimics the situation when the cheater viruses take over the virus population. We found that the growth rate of the cheaters was 83 percent of the cooperators’ growth rate. So P = 1 – c = 0.83. We substitute the value c = 0.17 in the equation for P/S. It was then trivial to estimate the parameter s1, so we could fill in the payoff matrix. Because the cheater ultimately replaces the cooperator, while lowering the fitness of the population (see graph below, right), the results are consistent with the prisoner’s dilemma."

My take: It's entirely clear to me that in this setting cheaters can successfully displace cooperators, while simultaneously lowering the average fitness of the population. But are individual cheaters really acting irrationally? Plagued by a couple of other questions, I decided to forward the article to guest blogger Michael Sigmund who knows a heck of a lot more about game theory than I do. Here is his reply:

First, in the chapter "Cheaters Sometimes Prosper", the author sets up a game theory model and introduces the well-known prisoner's dilemma. Non-cooperative game theory has a clear solution for this game: Both players defect (if the payoff matrix has certain properties). So the strategy-pair (defection, defection) is caused by rationality of the players and not by the fact that defection offers the only possibility of obtaining the best pay-off. Behaving "collectively irrational" is an unusual phrase and could mean that the outcome of the prisoner's dilemma is not pareto-efficient. However, pareto-efficiency is an axiom commonly imposed on solution concepts of cooperative game theory which is something totally different. Moreover, I think that in order to model the evolution of the populations of the different virus types, we need concepts of evolutionary game theory. In particular we should use the concept of evolutionary stable strategies (ESS). Although this concept is correctly introduced on page 431 it isn't mentioned that it is a refinement of the Nash equilibrium which is the usual concept to solve the static one shot prisoner's dilemma.

Second, in the chapter "Game-Theory Solutions", he misses the key elements of an evolutionary game theoretic model. First of all, the author should have pointed out why we can model the evolution of a certain system by a game theoretic model. Especially the question of existence of an ESS is not mentioned. Without going into details, this describes the relation between stationary points (stationäre Punkte) and systems of differential equations.

Third, the concept to solve such games (ESS) is not mentioned explicitly in this chapter. In short an ESS gives the equilibrium frequency distribution of the virus types under a certain fitness matrix.

Finally the argument "our study was the first to demonstrate the evolution of irrational, selfish behavior in a biological system" is simply wrong. Viruses don't play strategies, hence they cannot show selfish behavior. The frequency distribution of the virus types is caused by the initial probability of the different types and by the payoffs (fitness matrix in general) if two viruses, possibly of different types are randomly matched.

winedateNew Scientist: Men who spend big money wining and dining their dates are not frittering away hard-earned cash. According to a pair of UK researchers, they are merely employing the best strategy for getting the girl without being taken for granted.<>

So he and Seymour built a model based on a series of dating decisions. In the model males had to decide what kind of gift to offer females – valuable, extravagant or cheap – based on how attractive he finds her. The females had to either accept or decline the gift and then decide whether to mate with the gift-giver – a decision also weighted on the 'attractiveness' of their prospective partner.

When they measured the different outcomes of all the steps, they found the best solution for the males was to give extravagant, but intrinsically value-free gifts (...) the vast majority of the time, while giving gifts of material value very occasionally.

The model showed that if males gave valuable gifts too often, the females would start to exploit them: the males have no clue as to the females’ real intentions in the model. Put simply, the females just take the diamonds and run. But when the gifts are worthless, an uninterested female has little incentive to accept, gaining no return on what could be just turn into the simple waste of an evening. Only girls who are serious would bother to go the distance. |Full Story|

Game Theory: Although only a slight variation of the older theory of games, it is this form given by Williams (1954) that has caught on. Theory of games (von Neumann and Morgenstern 1994) goes back in German to von Neumann (1928) who used the term Theorie der Gesellschaftsspiele (parlor games). Even earlier, Borel (1921) studied la théorie du jeu, which Savage (1953) translates as theory of play and which he regards as the beginning of the theory of games.

Source: First Occurrence of Common Terms in Probability and Statistics- A Second List, with Corrections (JSTOR), H. A. David, The American Statistician. See also First (?) occurrence of common terms in mathematical statistics, H. A. David, The American Statistician || *comments only on a few selected terms

A Reminder: 'Small groups of people are likely to be very cooperative, but as numbers increase so will cheating. If people are allowed to punish cheats cooperation will persist in larger groups. If they can also punish those who do not punish cheats then cooperation flourishes in groups with hundreds of members'. Full Story
via Arts & Letters Daily