Growth of Strategy Sets, Entropy, and Nonstationary Bounded Recall

One way to express bounded rationality of a player in a game theoretic models is by specifying a set of feasible strategies for that player. In dynamic game models with finite automata and bounded recall strategies, for example, feasibility of strategies is determined via certain complexity measures: the number of states of automata and the length of recall. Typically in these models, a fixed finite bound on the complexity is imposed resulting in finite sets of feasible strategies. As a consequence, the number of distinct feasible strategies in any subgame is finite. Also, the number of distinct strategies induced in the first T stages is bounded by a constant that is independent of T. In this paper, we initiate an investigation into a notion of feasibility that reflects varying degree of bounded rationality over time. Such concept must entail properties of a strategy, or a set of strategies, that depend on time. Specifically, we associate to each subset Ψ i of the full (theoretically possible) strategy set a function y i from the set of positive integers to itself. The value y i (t) represents the number of strategies in Ψ i that are distinguishable in the first t stages. The set Ψ i may contain infinitely many strategies, but it can differ from the fully rational case in the way y i grows reflecting a broad implication of bounded rationality that may be alleviated, or intensified, over time. We examine how the growth rate of y i affects equilibrium outcomes of repeated games. In particular, we derive an upper bound on the individually rational payoff of repeated games where player 1, with a feasible strategy set Ψ 1 , plays against a fully rational player 2. We will show that the derived bound is tight in that a specific, and simple, set Ψ 1 exists that achieves the upper bound. As a special case, we study repeated games with non-stationary bounded recall strategies where the length of recall is allowed to vary in the course of the game. We will show that a player with bounded recall can guarantee the minimax payoff of the stage game even against a player with full recall so long as he can remember, at stage t, at least K log(t) stages back for some constant K >0. Thus, in order to guarantee the minimax payoff, it suffices to remember only a vanishing fraction of the past. A version of the folk theorem is provided for this class of games.