IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp435.html
   My bibliography  Save this paper

Complexity and Effective Prediction

Author

Listed:
  • Abraham Neyman
  • Joel Spencer

Abstract

Let G = (I,J,g) be a two-person zero-sum game. We examine the two-person zero-sum repeated game G(k,m) in which player 1 and 2 place down finite state automata with k,m states respectively and the payoff is the average per stage payoff when the two automata face off. We are interested in the cases in which player 1 is "smart" in the sense that k is large but player 2 is "much smarter" in the sense that m>>k. Let S(g) be the value of G were the second player is clairvoyant, i.e., would know the player 1's move in advance. The threshold for clairvoyance is shown to occur for m near min(|I|, |J|)^k. For m of roughly that size, in the exponential scale, the value is close to S(g). For m significantly smaller (for some stage payoffs g) the value does not approach S(g).

Suggested Citation

  • Abraham Neyman & Joel Spencer, 2006. "Complexity and Effective Prediction," Discussion Paper Series dp435, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    • Handle: RePEc:huj:dispap:dp435
    as

    Download full text from publisher

    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp435.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Abraham Neyman, 2008. "Learning Effectiveness and Memory Size," Discussion Paper Series dp476, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    2. Abraham Neyman, 1998. "Finitely Repeated Games with Finite Automata," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 513-552, August.
    3. Abraham Neyman & Daijiro Okada, 2000. "Two-person repeated games with finite automata," International Journal of Game Theory, Springer;Game Theory Society, vol. 29(3), pages 309-325.
    4. Ben-Porath Elchanan, 1993. "Repeated Games with Finite Automata," Journal of Economic Theory, Elsevier, vol. 59(1), pages 17-32, February.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Abraham Neyman, 2008. "Learning Effectiveness and Memory Size," Levine's Working Paper Archive 122247000000001945, David K. Levine.
    2. Ron Peretz, 2011. "Correlation through Bounded Recall Strategies," Discussion Paper Series dp579, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    3. Olivier Gossner & Penélope Hernández & Ron Peretz, 2016. "The complexity of interacting automata," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 461-496, March.
    4. Ron Peretz, 2013. "Correlation through bounded recall strategies," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(4), pages 867-890, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hernández, Penélope & Solan, Eilon, 2016. "Bounded computational capacity equilibrium," Journal of Economic Theory, Elsevier, vol. 163(C), pages 342-364.
    2. Hernández, Penélope & Urbano, Amparo, 2008. "Codification schemes and finite automata," Mathematical Social Sciences, Elsevier, vol. 56(3), pages 395-409, November.
    3. Bavly, Gilad & Neyman, Abraham, 2014. "Online concealed correlation and bounded rationality," Games and Economic Behavior, Elsevier, vol. 88(C), pages 71-89.
    4. Abraham Neyman, 2008. "Learning Effectiveness and Memory Size," Discussion Paper Series dp476, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    5. Olivier Gossner & Penélope Hernández & Ron Peretz, 2016. "The complexity of interacting automata," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 461-496, March.
    6. Renault, Jérôme & Scarsini, Marco & Tomala, Tristan, 2008. "Playing off-line games with bounded rationality," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 207-223, September.
    7. Sylvain Béal, 2010. "Perceptron versus automaton in the finitely repeated prisoner’s dilemma," Theory and Decision, Springer, vol. 69(2), pages 183-204, August.
    8. Olivier Compte & Andrew Postlewaite, 2007. "Effecting Cooperation," PIER Working Paper Archive 09-019, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 29 May 2009.
    9. O. Gossner, 2000. "Sharing a long secret in a few public words," THEMA Working Papers 2000-15, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    10. GOSSNER, Olivier, 1998. "Repeated games played by cryptographically sophisticated players," LIDAM Discussion Papers CORE 1998035, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Daijiro Okada & Abraham Neyman, 2004. "Growing Strategy Sets in Repeated Games," Econometric Society 2004 North American Summer Meetings 625, Econometric Society.
    12. 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.
    13. Béal, Sylvain, 2007. "Perceptron Versus Automaton∗," Sonderforschungsbereich 504 Publications 07-58, Sonderforschungsbereich 504, Universität Mannheim;Sonderforschungsbereich 504, University of Mannheim.
    14. Gilad Bavly & Abraham Neyman, 2003. "Online Concealed Correlation by Boundedly Rational Players," Discussion Paper Series dp336, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    15. GOSSNER, Olivier & HERNANDEZ, Pénélope, 2001. "On the complexity of coordination," LIDAM Discussion Papers CORE 2001047, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Andriy Zapechelnyuk, 2008. "Better-Reply Dynamics with Bounded Recall," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 869-879, November.
    17. Ron Peretz, 2011. "Correlation through Bounded Recall Strategies," Discussion Paper Series dp579, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    18. Bavly, Gilad & Peretz, Ron, 2019. "Limits of correlation in repeated games with bounded memory," Games and Economic Behavior, Elsevier, vol. 115(C), pages 131-145.
    19. Ueda, Masahiko, 2023. "Memory-two strategies forming symmetric mutual reinforcement learning equilibrium in repeated prisoners’ dilemma game," Applied Mathematics and Computation, Elsevier, vol. 444(C).
    20. Compte, Olivier & Postlewaite, Andrew, 2015. "Plausible cooperation," Games and Economic Behavior, Elsevier, vol. 91(C), pages 45-59.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp435. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.