Should I remember more than you? Best responses to factored strategies

In this paper we offer a new, unifying approach to modeling strategies of bounded complexity. In our model, the strategy of a player in a game does not directly map the set H of histories to the set of her actions. Instead, the player’s perception of H is represented by a map $$\varphi :H \rightarrow X,$$ φ : H → X , where X reflects the “cognitive complexity” of the player, and the strategy chooses its mixed action at history h as a function of $$\varphi (h)$$ φ ( h ) . In this case we say that $$\varphi $$ φ is a factor of a strategy and that the strategy is $$\varphi $$ φ -factored. Stationary strategies, strategies played by finite automata, and strategies with bounded recall are the most prominent examples of factored strategies in multistage games. A factor $$\varphi $$ φ is recursive if its value at history $$h'$$ h ′ that follows history h is a function of $$\varphi (h)$$ φ ( h ) and the incremental information $$h'\setminus h$$ h ′ \ h . For example, in a repeated game with perfect monitoring, a factor $$\varphi $$ φ is recursive if its value $$\varphi (a_1,\ldots ,a_t)$$ φ ( a 1 , … , a t ) on a finite string of action profiles $$(a_1,\ldots ,a_t)$$ ( a 1 , … , a t ) is a function of $$\varphi (a_1,\ldots ,a_{t-1})$$ φ ( a 1 , … , a t - 1 ) and $$a_t$$ a t .We prove that in a discounted infinitely repeated game and (more generally) in a stochastic game with finitely many actions and perfect monitoring, if the factor $$\varphi $$ φ is recursive, then for every profile of $$\varphi $$ φ -factored strategies there is a pure $$\varphi $$ φ -factored strategy that is a best reply, and if the stochastic game has finitely many states and actions and the factor $$\varphi $$ φ has a finite range then there is a pure $$\varphi $$ φ -factored strategy that is a best reply in all the discounted games with a sufficiently large discount factor.