Growth of Strategy Sets, Entropy, and Nonstationary Bounded Recall

Abraham Neyman and Daijiro Okada

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 yi from the set of positive integers to itself. The value ψ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 yi grows reflecting a broad implication of bounded rationality that may be alleviated, or intensified, over time. We examine how the growth rate of yi 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.

November, 2005
Published in: