Game theory -  A Tutorial

Jean Walrand

Finitely Repeated Prisoner’s Dilemma

Assume that Alice and Bob repeat the game below N times and that their goal is to minimize the sum of their costs.  Thus, if Alice gets 2, 5, 1, 2, 4 over 5 steps, her total cost is 2 + 5 + 1 + 2 + 4.

Fact: The only subgame perfect Nash equilibrium (SPE) is for each player to choose D at each step, no matter what the other player does.

A strategy (that defines what any player should do at any given time, given his previous actions and those of the other players.

An SPE is a strategy for each player such that no player has an incentive to deviate unilaterally, at any time of the game.  That is, the strategy always remains a Nash equilibrium for the remainder of the game.

To establish the fact, observe that at the last step, step N, the players face a static prisoner’s dilemma game for which the only Nash equilibrium is (D, D). Thus, at step N, both players choose D, no matter what happened before.  Now consider step N - 1.  Since step N is already decided, we can repeat the argument for step N - 1.  Repeating the argument, we see by backward induction that the fact is indeed true.