Alumni Changing the World

René Levínský: “Should I Remember More than You? On the Best Response to Factor-based Strategies.”

Room 403, 4th floor

Abstract:

In 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 φ-factor-based. 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₁,…,a_t) on a finite string of action profiles (a₁,…,a_t) is a function of φ(a₁,…,a_t−1) and a_t, 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.