the alpha and omega : topic:game theory

A perspective on the viability of applying game theory to business

Mahalanobis — 2007-03-29T22:15:00Z

Excerpt 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. Lets 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

Sense of justice discovered in the brain

Mahalanobis — 2006-10-06T19:03:00Z

New 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]

Brain scans reveal men's pleasure in revenge

Mahalanobis — 2006-01-19T22:28:08Z

New 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.

Game Theory in Movies

Mahalanobis — 2005-11-24T08:59:49Z

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

Ultimatum Bargaining and Subgame Perfection

MephistoS — 2005-10-19T17:32:27Z

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.

A few words on Evolutionary Game Theory

MephistoS — 2005-09-26T22:26:24Z

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.

Cheating Viruses and Game Theory

Mahalanobis — 2005-08-22T02:20:19Z

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 otherssuckerswhose 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 its 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 dont always pay.

Here is how he estimated the payoffs:
"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 prisoners 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 s₂, so that T = 1 + s₂. So the fitness of the cheater relative to the cooperator is T/R, when the cheaters are rare. The value of s₂ can be determined from experimental data. My colleagues and I set the equation, T/R = (1 + s₂)/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 + s₂)/1 = 1.99, and s₂ = 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 suckers payoff, S = 1 s₁. Here we set P/S = (1 c)/( 1 s₁) 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 s₁. 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. This 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 prisoners 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.

Costly but 'worthless' gifts facilitate courtship

Mahalanobis — 2005-08-02T14:04:26Z

New 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|

The Theory of Play

Mahalanobis — 2005-03-26T07:23:17Z

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

When it pays to play along...

Mahalanobis — 2005-03-17T19:00:36Z

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

Rubinstein-Stahl Bargaining Game

Mahalanobis — 2004-12-31T22:56:16Z

Recently, Tyler Cowen pointed to a 'Rubinstein bargaining game where players fail to reach an agreement, thereby eating up more and more of the pie. Each individual plays "chicken" and hopes the other will give in.'

Here is a nice and simple example of the Rubinstein bargaining game (taken from a game theory midterm exam (University of Texas at Austin); thanks to co-blogger Michael Sigmund for the promt delivery) :

Consider the following three-period, alternating game:

In period one, player 1 makes an offer (m₁) to player 2. Player 2 has the option of accepting the offer or rejecting the offer. If player 2 accepts, the players receive the payoffs (1 - m₁, m₁) and the game ends. If player 2 rejects, the game moves on to period two. {m_. ∈ [0,1], δ ∈ (0,1)}

In period two, player 2 makes an offer (m₂) to player 1. Player 1 has the option of accepting the offer or rejecting the offer. If player 1 accepts, the players receive the payoffs (δm₂, δ(1-m₂)) and the game ends. If player 1 rejects, the game moves on to period three.

In period three, player 1 makes an offer (m₃) to player 2. Player 2 has the option of accepting the offer or rejecting the offer. If player 2 accepts, the players receive the payoffs (δ²(1-m₃), δ²m₃) and the game ends. If player 2 rejects, the game ends and the players receive (0.0).

Finding the subgame perfect equilibrium:

Start with the 3^rd period. Player 1 offers m₃. If player 2 accepts, u₁ = δ²(1-m₃), u₂ = δ²m₃. If player 2 rejects, u₁=u₂=0. The subgame perfect equilibrium for this stage is m₃=0, accept m₃ ≥ 0. u₁ = δ², u₂ = 0.

Now in the 2^nd period, player 2 offers m₂. If player 1 accepts, u₁ = δm₂, u₂ = δ(1-m₂). If player 1 rejects, they go on to the 3^rd period where u₁ = δ² and u₂ = 0. The subgame perfect equilibrium for this stage is accept m₂ ≥ δ, m₂ = δ. u₁ = δ², u₂ = δ(1 - δ).

Now in the 1^st period, player 1 offers m₁. If player 2 accepts, u₁ = (1-m₁, u₂ = m₁). If player 2 rejects, they go on to the 2^nd period where u₁ = δ² and u₂ = δ(1-δ). The subgame perfect equilibrium for this stage is m₁ = δ(1- δ), accept m₁ ≥ δ(1 - δ). u₁ = 1 - δ(1 - δ), u₂ = δ(1 - δ).

The subgame perfect equilibrium is [m₁ = δ(1 - δ), accept m₂ ≥ δ, m₃ = 0], [accept m₁ ≥ δ(1 - δ), m₂ = δ accept m₃ ≥ 0].

Question of the day: In the subgame perfect equilibrium one player has a higher payoff regardless of δ. Which player is it?

Answer: Player 1 has a higher payoff than player 2 if 1 - δ(1 - δ) > δ(1- δ). This occurs if 2δ² - 2δ + 1 > 0, which is true for any δ ≥ 0. Player 1 always has a higher payoff.

"Cooperators were too nice; they died out"

Mahalanobis — 2004-12-01T01:29:48Z

If you've ever been tempted to drop a friend who tended to freeload, then you have experienced a key to one of the biggest mysteries facing social scientists, suggests a study by UCLA anthropologists.

"If the help and support of a community significantly affects the well-being of its members, then the threat of withdrawing that support can keep people in line and maintain social order," said Karthik Panchanathan, a UCLA graduate student whose study appears in Nature. "Our study offers an explanation of why people tend to contribute to the public good, like keeping the streets clean. Those who play by the rules and contribute to the public good will be included and outcompete freeloaders."

This finding -- at least in part -- may help explain the evolutionary roots of altruism and human anger in the face of uncooperative behavior, both of which have long puzzled economists and evolutionary biologists, he said.

Click here to read the whole story.

New Tack Wins Prisoner's Dilemma

Mahalanobis — 2004-10-13T20:35:25Z

Wired: Proving that a new approach can secure victory in a classic strategy game, a team from England's Southampton University has won the 20th-anniversary Iterated Prisoner's Dilemma competition, toppling the long-term winner (Tit for Tat) from its throne.

The 2004 competition had 223 entries, with each player playing all the other players in a round robin setup. Teams could submit multiple strategies, or players, and the Southampton team submitted 60 programs. These were all slight variations on a theme and were designed to execute a known series of five to 10 moves by which they could recognize each other. Once two Southampton players recognized each other, they were designed to immediately assume "master and slave" roles -- one would sacrifice itself so the other could win repeatedly.

If the program recognized that another player was not a Southampton entry, it would immediately defect to act as a spoiler for the non-Southampton player. The result is that Southampton had the top three performers -- but also a load of utter failures at the bottom of the table who sacrificed themselves for the good of the team. Another twist to the game was the addition of noise, which allowed some moves to be deliberately misrepresented. In the original game, the two prisoners could not communicate. But Southampton's design lets the prisoners do the equivalent of signaling to each other their intentions by tapping in Morse code on the prison wall.

Graham Kendall noted that there was nothing in the competition rules to preclude such a strategy, though he admitted that the ability to submit multiple players means it's difficult to tell whether this strategy would really beat Tit for Tat in the original version. But he believes it would be impossible to prevent collusion between entrants. "Ultimately," he said, "what's more important is the research." Full Story

via GeekPress

Econ 69

Mahalanobis — 2004-09-09T00:41:08Z

{Example stolen from Albert Cohen)

Two girls, Player 1 and Player 2, are attempting to win the affection of a young man, so they plan an evening for their sweetheart (simultaneously). There are three choices:

A cheap but fun date at a sports bar,
an evening where the lady wears a sexy dress and they go to the opera,
or the lady ignores him and doesn't call.

The game is such that the man generally prefers Player 1 to Player 2, as evidenced by the payoffs given in the bi-matrix below, he prefers the sexy dress and opera, has hardly any interest in sports, but is partially intrigued if one or both of the ladies ignores him. The payoff consists of the young man spending his ≤ 8 hours of leisure time the next day ~~sleeping~~* shopping with them (separately), and so the payoff is in hours:

What will happen from a game theoretic perspective and what do you think will be the outcome of an experimental analysis? [VERIFY]

Impetus by Jacqueline Mackie Paisley Passey

related items:
The Economics of Faking Orgasm
The Economics of Strategic Virginity Loss
Romance in the Information Age

*I guess the utility function wouldn't be well-behaved.

Goodbye, Shizuo Kakutani

Mahalanobis — 2004-08-21T01:24:00Z

The mathematician Shizuo Kakutani has died at the age of 92. One tool he developed, known as the Kakutani fixed-point theorem, was a key step in the original proof of the existence of Nash equilibria, the theorem for which John Forbes Nash received his Nobel Prize. Dr. Kakutani's theorem is also used to prove a famous 1954 theorem by the economists Kenneth J. Arrow and Gérard Debreu, which says that there are prices for goods that balance supply and demand in a complex economy.

In economics the most frequent technique for establishing the existence of solutions to an equilibrium system of equations consists of setting up the problem as the search for a fixed point of a suitably constructed function or correspondence
f : A → A from some set A ⊂ Rⁿ into itself. A vector x ∈ A is a fixed point of f(.)
if x = f(x) or, in the correspondence case, if x ∈ f(x).

The reason for proceeding in this, often roundabout, way is that important mathematical theorems for providing the existence of fixed points are readily available. The most important fixed point theorem is Brouwer's (deals with functions); the extention of this theorem to correspondences is given by Kakutani's fixed point theorem.

Real world examples: (1) Take two equal size sheets of paper, one lying directly above the other. If you crumple the top sheet, and place it on top of the other sheet, then Brouwer's fixed point theorem says that there must be at least one point on the top sheet that is directly above the corresponding point on the bottom sheet. (2) Take a map of the city in which you live. Now lay the map down on the floor. There exists at least one point on the map which tells the location of the corresponding point below it on the floor.

Warm-up: Brouwers fixed point theorem in dimension one:

Let f : [0, 1] → [0, 1] be a continuous function. Then, there exists a fixed point, i.e. there is a x* in [0, 1] such that f (x*) = x*.

Proof: There are two essential possibilities:

if f(0) = 0 or if f(1) = 1, then we are done.
if f(0) ≠ 0 and f(1) ≠ 1, then define F(x) =f(x) - x. In this case:
F(0) = f(0) - 0 =f(0) > 0
F(1) = f(1) - 1 < 0
So F: [0, 1] → R, where F(0)·F(1) < 0. As f(.) is continuous, then F(.) is also continuous. Then by using the Intermediate Value Theorem (IVT), there is a x* in [0, 1] such that F(x*) = 0. By the definition of F(.), then F(x*) = f (x*) - x* = 0, thus f (x*) = x*.

NB: The IVT was freely used by mathematicians of the 18th century (including Euler and Gauss) without any consideration of its validity. In fact, the first analytical proof was not offered until 1817 by Bolzano in a paper that also contains the first appearance of a somewhat modern definition of continuity.

Getting down to business: Kakutani's fixed point theorem:

Suppose that A ⊂ Rⁿ is a nonempty, compact, convex set, and that f : A → A is an upper hemicontinuous correspondence from A into itself with the property that the set f(x) ⊂ A is nonempty and convex for every x ∈ A. Then f(.) has a fixed point; that is, there is an x ∈ A such that x ∈ f(x).

NB: A set in Rⁿ is compact ⇔ it is closed and bounded (Heine-Borel Covering Theorem). A set A in n-dimensional space is called a convex set if the line segment joining any pair of points of A lies entirely in A. Given a set A in n-dimensional space and the closed set Y in k-dimensinal space, the correspondence f : A → Y is upper hemicontinuous (uhc, usc (upper semi continuous)) if it has a closed graph and the images of compact sets are bounded, that is, for every compact set B ⊂ A the set f(B) = {y ∈ Y: y ∈ f(x) for some x ∈ B} is bounded.

Example:

(a) A fixed point exists
(b) The convex-valuedness assumption is indispensable.

Click here for a nice introduction to game theory (see 1.3 Existence of Nash Equilibrium).

via Alex Tabarrok (Kakutani is at rest)

References:
Microeconomic theory, A. Mas-Colell, M. Whinston, J. Green
Understanding Analyisis, Steven Abbott
Lebesgue Integration on Euclidean Space, Frank Jones
A First Course in Optimization Theory, Rangarajan K. Sundaram

NB: I am back to Vienna & blogging. Stay tuned!