The Value of Recall

This work studies two-person zero-sum repeated games in which at least one of the players is restricted to (mixtures of) bounded recall strategies. A (pure) k recall strategy is a strategy that relies only on the last k periods of history. This work improves previous results [2, 4] on repeated games with bounded recall by extending the range of settings for which we can approximate the value. Bounded recall is one of the alternatives proposed by Aumann [1] to model limited rationality in repeated games. Lehrer [2] studied infinitely repeated two-player zero-sum games where both players have bounded recall. Neyman and Okada [3, 4] study a setting in which one player is bounded while the other is fully rational. In [4] they examine specifically the case of bounded recall. The current work extends results of both [2] and [4]. Apparently, in all previous works, the limited player secures the minimax payoff by playing an oblivious1 strategy. Our main result follows this line:2 Theorem 1.1. Let G =< I, J, g> be a two-player zero-sum game in strategic normal form. For every sequence of positive integers {Tk}∞k=1 and every h 6= log2 I, if limk→∞ log2 Tk k = h, the