Limits of correlation in repeated games with bounded memory

Abstract We study repeated games in which each player i is restricted to (mixtures of) strategies that can recall up to k i stages of history. Characterizing the set of equilibrium payoffs boils down to identifying the individually rational level (“punishment level”) of each player. In contrast to the classic folk theorem, in which players are unrestricted, punishing a bounded player may involve correlation between the punishers' actions. We show that the extent of such correlation is at most proportional to the ratio between the recall capacity of the punishers and the punishee. Our result extends to a few variations of the model, as well as to finite automata.