Centipede game


In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an 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 on the next round, one receives slightly less than if one had taken the pot on this round. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.
The unique subgame perfect equilibrium of these games indicates that the first player take the pot on the very first round of the game; however, in empirical tests, relatively few players do so, and as a result, achieve a higher payoff than the payoff predicted by the equilibria analysis. These results are taken to show that subgame perfect equilibria and Nash equilibria fail to predict human play in some circumstances. 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 show a standard way of providing a solution to the game.

Play

One possible version of a centipede game could be played as follows:
The addition of coins is taken to be an externality, as it is not contributed by either player.

Formal Definition

The centipede game may be written as where and. Players and alternate, starting with player, and may on each turn play a move from with a maximum of rounds. The game terminates when is played for the first time, otherwise upon moves, if is never played.
Suppose the game ends on round with player making the final move. Then the outcome of the game is defined as follows:
Here, denotes the other player.

Equilibrium analysis and backward induction

Standard game theoretic tools predict that the first player will defect on the first round, taking the pile of coins for himself. In the centipede game, a pure strategy consists of a set of actions 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.
In the unique subgame perfect equilibrium, each player chooses to defect at every opportunity. This, of course, means defection at the first stage. In the Nash equilibria, however, the actions that would be taken after the initial choice opportunities may be cooperative.
Defection by the first player is the unique subgame perfect equilibrium and required by any Nash equilibrium, it 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 he 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.
For a game that ends after four rounds, 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, receiving 4 coins instead of 3. 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. 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.

Empirical results

Several studies have demonstrated that the Nash equilibrium play is rarely observed. Instead, subjects regularly show partial cooperation, playing "R" for several moves before eventually choosing "D". It is also rare for subjects to cooperate through the whole game. For examples see McKelvey and Palfrey and Nagel and Tang. 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 Nash equilibrium play.

Explanations

Since the empirical studies have produced results that are inconsistent with the traditional equilibrium analysis, several explanations of this behavior have been offered. Rosenthal suggested that if one has reason to believe his 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 equilibrium 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 suggest this explanation.
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 to cooperate in the initial rounds.
However, Parco, Rapoport and Stein illustrated that the level of financial incentives can have a profound effect on the outcome in a three-player game: the larger the incentives are for deviation, the greater propensity for learning behavior in a repeated single-play experimental design to move toward the Nash equilibrium.
Palacios-Huerta and Volij find that expert chess players play differently from college students. With a rising Elo, the probability of continuing the game declines; all Grandmasters in the experiment stopped at their first chance. They conclude that chess players are familiar with using backward induction reasoning and hence need less learning to reach the equilibrium. However, in an attempt to replicate these findings, Levitt, List, and Sadoff find strongly contradictory results, with zero of sixteen Grandmasters stopping the game at the first node.

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.
Additionally, Binmore 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 a hermaphroditic sea bass which takes 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 and Binmore.