Should I remember more than you? Best responses to factored strategies
2020
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,$$
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)$$
. 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'$$
that follows history h is a function of
$$\varphi (h)$$
and the incremental information
$$h'\setminus h$$
. For example, in a repeated game with perfect monitoring, a factor
$$\varphi $$
is recursive if its value
$$\varphi (a_1,\ldots ,a_t)$$
on a finite string of action profiles
$$(a_1,\ldots ,a_t)$$
is a function of
$$\varphi (a_1,\ldots ,a_{t-1})$$
and
$$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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
0
Citations
NaN
KQI