Centipede Game (game Theory) - Equilibrium Analysis and Backward Induction

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

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 (even though they are never reached since the first player defects immediately) 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 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.

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.