Should I remember more than you? Best responses to factored strategies
- PDF / 377,581 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 157 Views
Should I remember more than you? Best responses to factored strategies René Levínský1
· Abraham Neyman2 · Miroslav Zelený3
Accepted: 26 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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 ϕ : 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 ϕ(h). In this case we say that ϕ is a factor of a strategy and that the strategy is ϕ-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 ϕ is recursive if its value at history h that follows history h is a function of ϕ(h) and the incremental information h \ h. For example, in a repeated game with perfect monitoring, a factor ϕ is recursive if its value ϕ(a1 , . . . , at ) on a finite string of action profiles (a1 , . . . , at ) is a function of ϕ(a1 , . . . , at−1 ) and at .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 ϕ is recursive, then for every profile of ϕ-factored strategies there is a pure ϕ-factored strategy that is a best reply, and if the stochastic game has finitely many states and actions and the factor ϕ has a finite range then there is a pure ϕ-factored strategy that is a best reply in all the discounted games with a sufficiently large discount factor. Keywords Bounded rationality · Factored strategies · Bounded recall strategies · Finite automata
ˇ Grant 17-19672S and by the Ministry of Education, René Levínský: Research was supported by GACR Youth and Sports of the Czech Republic through the project S H A R E − C Z + (C Z .02.1.01/0.0/0.0/ 16_013/0001740). Abraham Neyman: Research was supported in part by Israel Science Foundation grant 1123/06. Miroslav Zelený: Research was supported by MSM research project 0021620839 financed by ˇ Grant 17-19672S. MSMT and GACR Extended author information available on the last page of the article
123
R. Levínský et al.
1 Introduction There are two widely studied approaches to modeling strategies of bounded complexity in repeated games. One approach is to assume that players have stationary bounded recall Aumann (1981), Lehrer (1988), Aumann and Sorin (1989). Such players have imperfect consciousness of the actual stage of the game, and their actions in the current stage game rely only on the signals, e.g., players’ actions, of the last k rounds. The strategies of such players are called stationary bounded recall strategies, henceforth, SBR strategies. The other approach is to assume that players have stationary finite memory Neyman (1985), Rubinstein (1986), Abreu and Rubin
Data Loading...
