Neyman A, Levinsky R, ZELENY MIROSLAV.

Should I Remember more than you?? – on the best response to factored based strategies. 2014.

AbstractIn this paper we offer a new approach to modeling strategies of bounded complexity, the so-called factor-based strategies. In our model, the strategy of a player in the multi-stage game does not directly map the set of histories H to the set of her actions. Instead, the player’s perception of H is represented by a factor ϕ : H → X, where X reflects the “cognitive complexity” of the player. Formally, mapping ϕ sends each history to an element of a factor space X that represents its equivalence class. The play of the player can then be conditioned just on the elements of the set X. From the perspective of the original multi-stage game we say that a function ϕ from H to X is a factor of a strategy σ if there exists a function ω from X to the set of actions of the player such that σ = ω ◦ ϕ. In this case we say that the strategy σ is ϕ-factorbased. Stationary strategies and strategies played by finite automata and strategies with bounded recall are the most prominent examples of factor-based strategies. In the discounted infinitely repeated game with perfect monitoring, a best reply to a profile of ϕ-factor-based strategies need not be a ϕ-factor-based strategy. However, if the factor ϕ is recursive, namely, its value ϕ(a(1), . . . , a(t)) on a finite string of action profiles (a(1), . . . , a(t)) is a function of ϕ(a(1), . . . , a(t−1)) and at, then for every profile of factor-based strategies there is a best reply that is a pure factor-based strategy. We also study factor-based strategies in the more general case of stochastic games.

paper