23 - The repeated Prisoner’s Dilemma

Summary

So far, we have dealt with extensive form games in which all the paths had a finite length. Recall, however, that in Chapter 18 we also defined game trees with infinite paths. Such paths do not end with a leaf at which payoffs to the players are specified. Rather, payoffs are defined for each of the players for the entirety of each such an infinite path.

Despite the existence of such infinite paths, the concept of a strategy continues to be well defined: a player’s strategy is her strategy plan, describing how she will act if and when her turn comes to play at each of the nodes at which she is one of the active players. The concept of Nash equilibrium likewise remains well defined: a profile of the players’ strategies is a Nash equilibrium if the strategy of each player is a best reply, from her point of view, to the strategies of the other players.

As usual, a subgame commencing at a particular node is defined by a subtree for which that node serves as a root. Therefore, the concept of a subgame perfect equilibrium remains well defined: the strategy profile of the players is a subgame perfect equilibrium if the strategies induced by them in each subgame constitute a Nash equilibrium in that subgame. However, unlike for games with finite paths, when there are infinite paths in the game tree, a subgame perfect equilibrium cannot be found by backward induction. This is because an infinite path cannot be “folded” backwards, from the leaf to the root, since an infinite path does not have a leaf from which the “folding” can start. Accordingly, we must adopt other methods in order to find a subgame perfect equilibrium in a game with infinite paths.

Repeated games

An important class of games with an infinite horizon is that of repeated games. In a repeated game the players play a strategic form game over and over again. For example, in the repeated Prisoner’s Dilemma, the players play the Prisoner’s Dilemma repeatedly.