Advanced Search
MyIDEAS: Login to save this paper or follow this series

Growth of Strategy Sets, Entropy, and Nonstationary Bounded Recall


Author Info

  • Abraham Neyman


  • Daijiro Okada



One 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 Info

If 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.
File URL:
Download Restriction: no

Bibliographic Info

Paper provided by The Center for the Study of Rationality, Hebrew University, Jerusalem in its series Discussion Paper Series with number dp411.

as in new window
Length: 38 pages
Date of creation: Nov 2005
Date of revision:
Handle: RePEc:huj:dispap:dp411

Contact details of provider:
Postal: Feldman Building - Givat Ram - 91904 Jerusalem
Phone: +972-2-6584135
Fax: +972-2-6513681
Web page:
More information through EDIRC

Related research

Keywords: bounded rationality; strategy set growth; strategic complexity; nonstationary bounded recall; repeated games; entropy;

Other versions of this item:

This paper has been announced in the following NEP Reports:


References listed on IDEAS
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.:
as in new window
  1. 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.
  2. Lehrer, Ehud, 1988. "Repeated games with stationary bounded recall strategies," Journal of Economic Theory, Elsevier, vol. 46(1), pages 130-144, October.
  3. Gossner, Olivier & Vieille, Nicolas, 2002. "How to play with a biased coin?," Games and Economic Behavior, Elsevier, vol. 41(2), pages 206-226, November.
  4. 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.
  5. Neyman, Abraham, 1985. "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters, Elsevier, vol. 19(3), pages 227-229.
  6. Ben-Porath Elchanan, 1993. "Repeated Games with Finite Automata," Journal of Economic Theory, Elsevier, vol. 59(1), pages 17-32, February.
  7. Neyman, Abraham & Okada, Daijiro, 2000. "Repeated Games with Bounded Entropy," Games and Economic Behavior, Elsevier, vol. 30(2), pages 228-247, February.
  8. Abraham Neyman & Daijiro Okada, 2000. "Two-person repeated games with finite automata," International Journal of Game Theory, Springer, vol. 29(3), pages 309-325.
  9. Aumann, Robert J., 1997. "Rationality and Bounded Rationality," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 2-14, October.
Full references (including those not matched with items on IDEAS)


Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Ron Peretz, 2007. "The Strategic Value of Recall," Discussion Paper Series dp470, The Center for the Study of Rationality, Hebrew University, Jerusalem.
  2. Abraham Neyman, 2008. "Learning Effectiveness and Memory Size," Discussion Paper Series dp476, The Center for the Study of Rationality, Hebrew University, Jerusalem.
  3. Ron Peretz, 2011. "Correlation through Bounded Recall Strategies," Discussion Paper Series dp579, The Center for the Study of Rationality, Hebrew University, Jerusalem.
  4. Ron Peretz, 2007. "The Strategic Value of Recall," Levine's Bibliography 122247000000001774, UCLA Department of Economics.
  5. Peretz, Ron, 2012. "The strategic value of recall," Games and Economic Behavior, Elsevier, vol. 74(1), pages 332-351.
  6. Ron Peretz, 2013. "Correlation through bounded recall strategies," International Journal of Game Theory, Springer, vol. 42(4), pages 867-890, November.


This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.


Access and download statistics


When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp411. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ilan Nehama).

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.