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

René Levínský (), Abraham Neyman () and Miroslav Zelený ()
Additional contact information
Abraham Neyman: The Hebrew University of Jerusalem
Miroslav Zelený: Charles University, Faculty of Mathematics and Physics

International Journal of Game Theory, 2020, vol. 49, issue 4, No 9, 1105-1124

Abstract: 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 $$\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.

Keywords: Bounded rationality; Factored strategies; Bounded recall strategies; Finite automata (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-020-00733-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:49:y:2020:i:4:d:10.1007_s00182-020-00733-1

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-020-00733-1

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().