Extensive Form Representation of a Four Stage "Centipede" Game

In game theory, the centipede game, first introduced by Rosenthal (1981), is an extensive form game in which two players take turns choosing either to take a slightly larger share of a slowly increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot, one receives slightly less than if one had taken the pot. Although the traditional centipede game had a limit of 100 rounds (hence the name), any game with this structure but a different number of rounds is called a centipede game. The unique subgame perfect equilibrium (and every Nash equilibrium) of these games dictates that the first player take the pot on the very first round of the game; however in empirical tests relatively few players do so. The Centipede game is commonly used in introductory game theory courses and texts to highlight the concept of backward induction and the iterated elimination of dominated strategies, which provide a standard way of providing a solution to the game. Image File history File links Download high resolution version (2496x832, 6 KB)An extensive form diagram of the centipede game. ... Image File history File links Download high resolution version (2496x832, 6 KB)An extensive form diagram of the centipede game. ... It has been suggested that Game tree be merged into this article or section. ... Game theory is often described as a branch of applied mathematics and economics that studies situations where players choose different actions in an attempt to maximize their returns. ... It has been suggested that Game tree be merged into this article or section. ... Subgame perfect equilibrium is an economics term used in game theory to describe an equilibrium such that players strategies constitute a Nash equilibrium in every subgame of the original game. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ... A central concept in science and the scientific method is that all evidence must be empirical, or empirically based, that is, dependent on evidence or consequences that are observable by the senses. ... In game theory, backward induction is one of dynamic programming algorithms used to compute subgame perfect equilibria in sequential games. ... In game theory, dominance occurs when one strategy is better or worse than another regardless of the strategies of a players opponents. ...

Explanation of the rules

One easy way to understand how the game is played is as follows: Consider two players X and Y. At the start of the game, player X has two small piles of coins in front of him; very small indeed in fact, as one pile contains only two coins and the other pile has no coins at all. As a first move, X must make a decision between two choices: he can either take the larger pile of coins (at which point he must also give the smaller pile of coins to the other player) or he can push both piles across the table to player Y. Each time the piles of coins pass across the table, one coin is added to each pile, such that on his first move, Y can now pocket the larger pile of 3 coins, giving the smaller pile of 1 coin to player X or he can pass the two piles back across the table again to X, increasing the size of the piles to 4 and 2 coins.

The game continues for either a fixed period of 100 rounds or until a player decides to end the game by pocketing a pile of coins.

Representing the game in the diagramatical form above, passing the coins across the table is represented by a move of R (ie going across the row of the lattice) (sometimes also notated by A for Across) and pocketing the coins is a move D (ie Down the lattice. The numbers 1 and 2 along the top of the diagram show the alternating decision-maker between two players denoted here as 1 and 2, and the numbers at the bottom of each branch show the payout for players 1 and 2 respectively.

Since the longer the game continues, the higher the piles become, one would intuitively think that the game should continue for the full 100 rounds. However, analysis shows a different outcome; namely that the best decision for the first player is to pocket the pile of two coins on the first round, as explained below:

Equilibrium analysis and backward induction

In the centipede game, a Pure strategy consists of a set of actions (one for each choice point in the game, even though some of these choice points may never be reached) and a Mixed strategy is a probability distribution over the possible pure strategies. There are several pure strategy Nash equilibria of the centipede game and infinitely many mixed strategy Nash equilibria. However, there is only one subgame perfect equilibrium (a popular refinement to the Nash equilibrium concept). A pure strategy is a term used to refer to strategies in Game theory. ... In game theory a mixed strategy is a strategy which chooses randomly between possible moves. ... In game theory, the Nash equilibrium (named after John Nash) is a kind of optimal strategy for games involving two or more players, whereby the players reach an outcome to mutual advantage. ... Subgame perfect equilibrium is an economics term used in game theory to describe an equilibrium such that players strategies constitute a Nash equilibrium in every subgame of the original game. ...

In the unique subgame perfect equilibrium, each player chooses to defect at every opportunity. This, of course, means defection at the first stage as well, which is also true of every Nash equilibria of the game. In the Nash equilibria, however, the actions that would be taken after the initial choice points, even though they are never reached since the first player defects immediately, may be cooperative.

Determining that defection by the first player is the unique subgame perfect equilibrium and required by any Nash equilibrium can be established by backward induction. Suppose two players reach the final round of the game; the second player will do better by defecting and taking a slightly larger share of the pot. Since we suppose the second player will defect, the first player does better by defecting in the second to last round, taking a slightly higher payoff than she would have received by allowing the second player to defect in the last round. But knowing this, the second player ought to defect in the third to last round, taking a slightly higher payoff than she would have received by allowing the first player to defect in the second to last round. This reasoning proceeds backwards through the game tree until one concludes that the best action is for the first player to defect in the first round. The same reasoning can apply to any node in the game tree. Subgame perfect equilibrium is an economics term used in game theory to describe an equilibrium such that players strategies constitute a Nash equilibrium in every subgame of the original game. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ... In game theory, backward induction is one of dynamic programming algorithms used to compute subgame perfect equilibria in sequential games. ... It has been suggested that Game tree be merged into this article or section. ...

In the example pictured above, this reasoning proceeds as follows. If we were to reach the last round of the game, Player 2 would do better by choosing d instead of r. However, given that 2 will choose d, 1 should choose D in the second to last round, receiving 3 instead of 2. Given that 1 would choose D in the second to last round, 2 should choose d in the third to last round, receiving 2 instead of 1. But given this, Player 1 should choose D in the first round, receiving 1 instead of 0.

There are a large number of Nash equilibria in a centipede game, but in each, the first player defects on the first round and the second player defects in the next round frequently enough to dissuade the first player from passing. Being in a Nash equilibrium does not require that strategies be rational at every point in the game as in the subgame perfect equilibrium. This means that strategies that are cooperative in the never-reached later rounds of the game could still be in a Nash equilibrium. In the example above, one Nash equilibrium is for both players to defect on each round (even in the later rounds that are never reached). Another Nash equilibrium is for player 1 to defect on the first round, but pass on the third round and for player 2 to defect at any opportunity. In game theory, the Nash equilibrium (named after John Nash) is a kind of optimal strategy for games involving two or more players, whereby the players reach an outcome to mutual advantage. ...

Empirical results

Several studies have demonstrated that the Nash equilibrium (and likewise, subgame perfect equilibrium) play is rarely observed. Instead, subjects regularly show partial cooperation, playing "R" (or "r") for several moves before eventually choosing "D" (or "d"). It is also rare for subjects to cooperate through the whole game. For examples see McKelvey and Palfrey (1992) and Nagel and Tang (1998). As in many other game theoretic experiments, scholars have investigated the effect of increasing the stakes. As with other games, for instance the ultimatum game, as the stakes increase the play approaches (but does not reach) Nash equilibrium play. The Ultimatum game is an experimental economics game in which two parties interact anonymously and only once, so reciprocation is not an issue. ...

Explanations of empirical results

Since the empirical studies have produced results that are inconsistent with the traditional equilibrium analysis, several explanations of this behavior have been offered. Rosenthal (1981) suggested that if one has reason to believe her opponent will deviate from Nash behavior, then it may be advantageous to not defect on the first round.

One reason to suppose that people may deviate from the equilibria behavior is if some are altruistic. The basic idea is that if you are playing against an altruist, that person will always cooperate, and hence, to maximize your payoff you should defect on the last round rather than the first. If enough people are altruists, sacrificing the payoff of first-round defection is worth the price in order to determine whether or not your opponent is an altruist. Nagel and Tang (1998) suggest this explanation. For the ethical doctrine, see Altruism (ethics). ...

Another possibility involves error. If there is a significant possibility of error in action, perhaps because your opponent has not reasoned completely through the backward induction, it may be advantageous (and rational) to cooperate in the initial rounds.

It can also be argued by the untility functions of the subjects as a weighted sum of "winning" and "getting the maximum coins". If the utility function of the subject is 100% of "winning", then the subject should follow the Nash behavior and deviate on the first round. However if the utility function of the subject is 100% of "getting the maximum coins", he/she should continue the game as much as possible.

Significance

Like the Prisoner's Dilemma, this game presents a conflict between self-interest and mutual benefit. If it could be enforced, both players would prefer that they both cooperate throughout the entire game. However, a player's self-interest or players' distrust can interfere and create a situation where both do worse than if they had blindly cooperated. Although the Prisoner's Dilemma has received substantial attention for this fact, the Centipede Game has received relatively less. Will the two prisoners cooperate to minimize total loss of liberty or will one of them, trusting the other to cooperate, betray him so as to go free? In game theory, the prisoners dilemma is a type of non-zero-sum game in which two players can cooperate with...

Additionally, Binmore (2005) has argued that some real-world situations can be described by the Centipede game. One example he presents is the exchange of goods between parties that distrust each other. Another example Binmore likens to the Centipede game is the mating behavior of an hermaphroditic sea bass which are hermaphrodites and take turns exchanging eggs to fertilize. In these cases, we find cooperation to be abundant.

Since the payoffs for some amount of cooperation in the Centipede game are so much larger than immediate defection, the "rational" solutions given by backward induction can seem paradoxical. This, coupled with the fact that experimental subjects regularly cooperate in the Centipede game has prompted debate over the usefulness of the idealizations involved in the backward induction solutions, see Aumann (1995, 1996) and Binmore (1996). In game theory, backward induction is one of dynamic programming algorithms used to compute subgame perfect equilibria in sequential games. ...

See also

• Backwards induction
• Experimental economics
• Unexpected hanging paradox

In game theory, backward induction is one of dynamic programming algorithms used to compute subgame perfect equilibria in sequential games. ... Experimental economics is the use of experimental methods to evaluate theoretical predictions of economic behaviour. ... This article or section is in need of attention from an expert on the subject. ...

References

• Aumann, R. (1995), “Backward Induction and Common Knowledge of Rationality”, Games and Economic Behavior 8: 6-19.
• --- (1996), “A Reply to Binmore”, Games and Economic Behavior 17: 138-146.
• Binmore, K. (2005), Natural Justice, Oxford University Press.
• --- (1996), “A Note on Backward Induction”, Games and Economic Behavior 17: 135-137.
• McKelvey, R. and T. Palfrey (1992) "An experimental study of the centipede game," Econometrica 60(4), 803-836.
• Nagel, R. and F.F. Tang (1998), "An Experimental Study on the Centipede Game in Normal Form - An Investigation on Learning," Journal of Mathematical Psychology 42, 356-384.
• Rosenthal, R. (1981), "Games of Perfect Information, Predatory Pricing, and the Chain Store," Journal of Economic Theory 25, 92-100.

External links

• EconPort article on the Centipede Game