Growth of Strategy Sets, Entropy, and Nonstationary Bounded Recall
AbstractOne way to express bounded rationality of a player in a game theoretic models is by specifying a set of feasible strategies for that player. In dynamic game models with finite automata and bounded recall strategies, for example, feasibility of strategies is determined via certain complexity measures: the number of states of automata and the length of recall. Typically in these models, a fixed finite bound on the complexity is imposed resulting in finite sets of feasible strategies. As a consequence, the number of distinct feasible strategies in any subgame is finite. Also, the number of distinct strategies induced in the first T stages is bounded by a constant that is independent of T. In this paper, we initiate an investigation into a notion of feasibility that reflects varying degree of bounded rationality over time. Such concept must entail properties of a strategy, or a set of strategies, that depend on time. Specifically, we associate to each subset Ψ i of the full (theoretically possible) strategy set a function y i from the set of positive integers to itself. The value y i(t) represents the number of strategies in Ψ i that are distinguishable in the first t stages. The set Ψ i may contain infinitely many strategies, but it can differ from the fully rational case in the way y i grows reflecting a broad implication of bounded rationality that may be alleviated, or intensified, over time. We examine how the growth rate of y i affects equilibrium outcomes of repeated games. In particular, we derive an upper bound on the individually rational payoff of repeated games where player 1, with a feasible strategy set Ψ 1, plays against a fully rational player 2. We will show that the derived bound is tight in that a specific, and simple, set Ψ 1 exists that achieves the upper bound. As a special case, we study repeated games with non-stationary bounded recall strategies where the length of recall is allowed to vary in the course of the game. We will show that a player with bounded recall can guarantee the minimax payoff of the stage game even against a player with full recall so long as he can remember, at stage t, at least K log(t) stages back for some constant K >0. Thus, in order to guarantee the minimax payoff, it suffices to remember only a vanishing fraction of the past. A version of the folk theorem is provided for this class of games.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by The Center for the Study of Rationality, Hebrew University, Jerusalem in its series Discussion Paper Series with number dp411.
Length: 38 pages
Date of creation: Nov 2005
Date of revision:
bounded rationality; strategy set growth; strategic complexity; nonstationary bounded recall; repeated games; entropy;
Other versions of this item:
- Neyman, Abraham & Okada, Daijiro, 2009. "Growth of strategy sets, entropy, and nonstationary bounded recall," Games and Economic Behavior, Elsevier, vol. 66(1), pages 404-425, May.
- Abraham Neyman & Daijiro Okada, 2005. "Growth of Strategy Sets, Entropy, and Nonstationary Bounded Recall," Levine's Bibliography 122247000000000920, UCLA Department of Economics.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Robert J. Aumann & Lloyd S. Shapley, 2013.
"Long Term Competition -- A Game-Theoretic Analysis,"
Annals of Economics and Finance,
Society for AEF, vol. 14(2), pages 627-640, November.
- Lehrer, Ehud, 1988. "Repeated games with stationary bounded recall strategies," Journal of Economic Theory, Elsevier, vol. 46(1), pages 130-144, October.
- Gossner, Olivier & Vieille, Nicolas, 2002.
"How to play with a biased coin?,"
Games and Economic Behavior,
Elsevier, vol. 41(2), pages 206-226, November.
- O. Gossner & N. Vieille, 1999. "How to play with a biased coin ?," THEMA Working Papers 99-31, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
- Gossner, O. & Vieille, N., 1999. "How to play with a biased coin?," Papers 99-31, Paris X - Nanterre, U.F.R. de Sc. Ec. Gest. Maths Infor..
- Olivier Gossner & Penelope Hernandez & Abraham Neyman, 2004.
"Optimal Use of Communication Resources,"
Discussion Paper Series
dp377, The Center for the Study of Rationality, Hebrew University, Jerusalem.
- Neyman, Abraham, 1985. "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters, Elsevier, vol. 19(3), pages 227-229.
- Ben-Porath Elchanan, 1993. "Repeated Games with Finite Automata," Journal of Economic Theory, Elsevier, vol. 59(1), pages 17-32, February.
- Neyman, Abraham & Okada, Daijiro, 2000. "Repeated Games with Bounded Entropy," Games and Economic Behavior, Elsevier, vol. 30(2), pages 228-247, February.
- Abraham Neyman & Daijiro Okada, 2000. "Two-person repeated games with finite automata," International Journal of Game Theory, Springer, vol. 29(3), pages 309-325.
- Aumann, Robert J., 1997. "Rationality and Bounded Rationality," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 2-14, October.
- Ron Peretz, 2007. "The Strategic Value of Recall," Discussion Paper Series dp470, The Center for the Study of Rationality, Hebrew University, Jerusalem.
- Abraham Neyman, 2008.
"Learning Effectiveness and Memory Size,"
Discussion Paper Series
dp476, The Center for the Study of Rationality, Hebrew University, Jerusalem.
- Ron Peretz, 2011. "Correlation through Bounded Recall Strategies," Discussion Paper Series dp579, The Center for the Study of Rationality, Hebrew University, Jerusalem.
- Ron Peretz, 2007. "The Strategic Value of Recall," Levine's Bibliography 122247000000001774, UCLA Department of Economics.
- Peretz, Ron, 2012. "The strategic value of recall," Games and Economic Behavior, Elsevier, vol. 74(1), pages 332-351.
- Ron Peretz, 2013. "Correlation through bounded recall strategies," International Journal of Game Theory, Springer, vol. 42(4), pages 867-890, November.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ilan Nehama).
If references are entirely missing, you can add them using this form.