about me
game theory
... more
Subscribe Weblog


game theory

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 (m1) 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 - m1, m1) 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 (m2) 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 (δm2, δ(1-m2)) and the game ends. If player 1 rejects, the game moves on to period three.

In period three, player 1 makes an offer (m3) 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 (δ2(1-m3), δ2m3) 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 3rd period. Player 1 offers m3. If player 2 accepts, u1 = δ2(1-m3), u2 = δ2m3. If player 2 rejects, u1=u2=0. The subgame perfect equilibrium for this stage is m3=0, accept m3 ≥ 0. u1 = δ2, u2 = 0.

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

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

The subgame perfect equilibrium is [m1 = δ(1 - δ), accept m2 ≥ δ, m3 = 0], [accept m1 ≥ δ(1 - δ), m2 = δ accept m3 ≥ 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 - 2δ + 1 > 0, which is true for any δ ≥ 0. Player 1 always has a higher payoff.

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

Hey, trust me...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

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

skakutaniThe 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 ⊂ Rn 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.

brouwerReal 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: Brouwer’s 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:
  1. if f(0) = 0 or if f(1) = 1, then we are done.
  2. 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 ⊂ Rn 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 Rn 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.


(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)

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!

For all you budding Kasparovs out there, a team of cognitive scientists has worked out how to think like a chess grand master. As those attending this week's Cognitive Science Society meeting in Chicago, Illinois, were told, the secret is to try to knock down your pet theory rather than finding ways to support it - exactly as scientists are supposed to do. Click here to read the full story.

via Tyler Cowen

Scientists at work


related items:
World Chess Boxing Organisation

... that's the question.

telegraph: The EU constitution is 'unfair', according to game theorists:
{FYI: story first appeared on PhysicsWeb on May 28, 2004}

The European Constitution is unscientific, will not achieve the objective of "one person one vote", and will give Germany undue influence, according to a new analysis. <>

The claims, in the journal Physics World, are made by Dr Karol Zyczkowski, a physicist, and Dr Wojciech Slomczynski, a mathematician, both from the Jagiellonian University in Krakow, and are backed by about 50 scientists across Europe.

Overall, the constitution favours the biggest and smallest states in a systematic way. "The medium-sized states are losers," said Dr Slomczynski. "The vote of a citizen in one country ought to be the same as for any other member state and this is strongly violated both in the voting system of the Treaty of Nice and in the constitution.<>

The scientists use a branch of mathematics called game theory to calculate how much power each country will have to sway the Council of Ministers if the new constitution is adopted, where a double majority is required to pass a vote – more than 15 states (out of 25, with two more soon) and 65 per cent of the bloc's population.

They report that the UK's voting power will drop from being the same as that of Germany, when the Treaty of Nice is introduced in November, to about 70 per cent of German voting power under the new constitution, reflecting the relative population size.

Although it seems right to weight votes by the population, it gives an individual in a big country more power than one in a small country, according to game theory analysis of fair voting published in 1949 by Lionel Penrose (father of the eminent British mathematician, Sir Roger).

He pointed out that voting power is not the same thing as voting weight: in a body with two members, one with 51 votes and one with 49, the latter appears to have almost the same weight but ends up with no power if there is a majority vote rule.

To represent true voting power, Penrose devised the "square root law", where the influence of each country is proportional to the square root of its population size.

The scientists have adopted this law to propose what has been nicknamed "the Jagiellonian Compromise": EU citizens would have the same voting power if each member state were given a weight that was proportional to the square root of its population, and if new legislation required 62 per cent of the votes at the council. The result would be to give all citizens equal influence, regardless of their home country.

related items:
Voting in the EU: The square root system of Penrose and a critical point
(Karol Zyczkowski, Wojciech Slomczynski)
Open Letter to the EU - Scientists for a Democratic Europe

fakeorgThis paper models love-making as a signaling game. In the act of love-making, man and woman send each other possibly deceptive signals about their true state of ecstasy. Each has a prior belief about the others's state of ecstasy. These prior beliefs are associated with the other's sexual response capacity, which varies in different ways for men and woman over the life-cycle. The model predicts that love, formally defined as a mixture of altruism and possessiveness, increases the probability of faking ecstasy, but more so for woman than for men, and age has a greater effect on the probability of faking if the partners are in love than if they are not. These predictions are tested with data from the 2000 Orgasm Survey [sic!]. Besides supporting the predictions, the data also reveal a positive relationship between education and the tendency to fake.

Here is the executive summary (Slate).

Econoblogs mentioning this paper: Mit dem Kopf voran (March 22), Law and Economics (March 20), Marginal Revolution (January 31 via Newmark's Door)

Great read! (but using "little omega" to denote a random variable is definitely a crime ;-D.)

A classic example of the volunteer's dilemma is the 1954 murder of Kitty Genovese in New York. She was stabbed to death in the courtyard of her appartment while 38 neighbours watched and heard her cries.

Here (p. 128) you can read the game theoretic explanation of the happening. German Version: kgenovese (gif, 31 KB) (old homework of mine, the instructor mentioned the Genovese case after we handed in our home exercise - so googling the answer wasn't really an option ;-D)