Rationality and bounded information in repeated games, with application to the iterated Prisoner's Dilemma

Actions in a repeated game can in principle depend on all previous outcomes. Given this vast policy space, human players may often be forced to use heuristics that base actions on incomplete information, such as the outcomes of only the most recent trials. Here it is proven that such bounded rationality is often fully rational, in that the optimal policy based on some limited information about the game's history will be universally optimal (i.e., within the full policy space), provided that one's opponents are restricted to using this same information. It is then shown how this result allows explicit calculation of subgame-perfect equilibria (SPEs) for any repeated or stochastic game. The technique is applied to the iterated Prisoner's Dilemma for the case of I-back memory. Two classes of SPEs are derived, which exhibit varying degrees of (individually rational) cooperation as a result of repeated interaction. (C) 2004 Elsevier Inc. All rights reserved.