IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v156y2015icp246-268.html
   My bibliography  Save this article

Algorithmic rationality: Game theory with costly computation

Author

Listed:
  • Halpern, Joseph Y.
  • Pass, Rafael

Abstract

We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the existence of a Nash equilibrium) no longer hold. Nevertheless, we can use the framework to provide psychologically appealing explanations of observed behavior in well-studied games (such as finitely repeated prisoner's dilemma and rock–paper–scissors). Furthermore, we provide natural conditions on games sufficient to guarantee that equilibria exist.

Suggested Citation

  • Halpern, Joseph Y. & Pass, Rafael, 2015. "Algorithmic rationality: Game theory with costly computation," Journal of Economic Theory, Elsevier, vol. 156(C), pages 246-268.
    • Handle: RePEc:eee:jetheo:v:156:y:2015:i:c:p:246-268
    DOI: 10.1016/j.jet.2014.04.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053114000611
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2014.04.007?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kreps, David M. & Milgrom, Paul & Roberts, John & Wilson, Robert, 1982. "Rational cooperation in the finitely repeated prisoners' dilemma," Journal of Economic Theory, Elsevier, vol. 27(2), pages 245-252, August.
    2. Burkhard C. Schipper & Martin Meier & Aviad Heifetz, 2007. "Unawareness, Beliefs and Games," Working Papers 235, University of California, Davis, Department of Economics.
    3. Neyman, Abraham, 1985. "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters, Elsevier, vol. 19(3), pages 227-229.
    4. Prasad, Kislaya, 2009. "The rationality/computability trade-off in finite games," Journal of Economic Behavior & Organization, Elsevier, vol. 69(1), pages 17-26, January.
    5. Myerson, Roger B, 1979. "Incentive Compatibility and the Bargaining Problem," Econometrica, Econometric Society, vol. 47(1), pages 61-73, January.
    6. Aumann, Robert J, 1987. "Correlated Equilibrium as an Expression of Bayesian Rationality," Econometrica, Econometric Society, vol. 55(1), pages 1-18, January.
    7. Mark Walker & John Wooders, 2001. "Minimax Play at Wimbledon," American Economic Review, American Economic Association, vol. 91(5), pages 1521-1538, December.
    8. Matthew Rabin, 1998. "Psychology and Economics," Journal of Economic Literature, American Economic Association, vol. 36(1), pages 11-46, March.
    9. Forges, Francoise M, 1986. "An Approach to Communication Equilibria," Econometrica, Econometric Society, vol. 54(6), pages 1375-1385, November.
    10. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    11. Eli Ben-Sasson & Adam Tauman Kalai & Ehud Kalai, 2006. "An Approach to Bounded Rationality," Discussion Papers 1439, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    12. Herbert A. Simon, 1955. "A Behavioral Model of Rational Choice," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 69(1), pages 99-118.
    13. Amparo Urbano & Jose Vila, 2004. "Computationally restricted unmediated talk under incomplete information," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 23(2), pages 283-320, January.
    14. Megiddo, Nimrod, 1989. "On computable beliefs of rational machines," Games and Economic Behavior, Elsevier, vol. 1(2), pages 144-169, June.
    15. Heifetz, Aviad & Meier, Martin & Schipper, Burkhard C., 2007. "Unawareness, Beliefs and Games," Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems 196, Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich.
    16. Sendhil Mullainathan, 2002. "A Memory-Based Model of Bounded Rationality," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 117(3), pages 735-774.
    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. Jung S You, 2021. "Random Actions in Experimental Zero-Sum Games," Journal of Economics and Behavioral Studies, AMH International, vol. 13(1), pages 69-81.
    2. Emara, Noha & Owens, David & Smith, John & Wilmer, Lisa, 2017. "Serial correlation in National Football League play calling and its effects on outcomes," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 69(C), pages 125-132.
    3. Valerio Capraro & Joseph Y Halpern, 2019. "Translucent players: Explaining cooperative behavior in social dilemmas," Rationality and Society, , vol. 31(4), pages 371-408, November.
    4. Blume, Lawrence & Easley, David & Kleinberg, Jon & Kleinberg, Robert & Tardos, Éva, 2015. "Introduction to computer science and economic theory," Journal of Economic Theory, Elsevier, vol. 156(C), pages 1-13.
    5. Ying-Fang Kao & Ragupathy Venkatachalam, 2021. "Human and Machine Learning," Computational Economics, Springer;Society for Computational Economics, vol. 57(3), pages 889-909, March.
    6. Eveline Leeuwen & Mark Lijesen, 2016. "Agents playing Hotelling’s game: an agent-based approach to a game theoretic model," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 57(2), pages 393-411, November.
    7. Emara, Noha & Owens, David & Smith, John & Wilmer, Lisa, 2014. "Minimax on the gridiron: Serial correlation and its effects on outcomes in the National Football League," MPRA Paper 58907, University Library of Munich, Germany.
    8. Riedl, Anna & Vervaeke, John, 2022. "Rationality and Relevance Realization," OSF Preprints vymwu, Center for Open Science.

    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. Sent, Esther-Mirjam, 2004. "The legacy of Herbert Simon in game theory," Journal of Economic Behavior & Organization, Elsevier, vol. 53(3), pages 303-317, March.
    2. Jehiel, Philippe, 2005. "Analogy-based expectation equilibrium," Journal of Economic Theory, Elsevier, vol. 123(2), pages 81-104, August.
    3. Yuval Salant & Jörg L. Spenkuch, 2021. "Complexity and Choice," CESifo Working Paper Series 9239, CESifo.
    4. Spiegler, Ran, 2005. "Testing threats in repeated games," Journal of Economic Theory, Elsevier, vol. 121(2), pages 214-235, April.
    5. Aumann, Robert J., 1997. "Rationality and Bounded Rationality," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 2-14, October.
    6. Joseph Y. Halpern, 2007. "Computer Science and Game Theory: A Brief Survey," Papers cs/0703148, arXiv.org.
    7. Joshua M. Epstein, 2007. "Agent-Based Computational Models and Generative Social Science," Introductory Chapters, in: Generative Social Science Studies in Agent-Based Computational Modeling, Princeton University Press.
    8. van Damme, E.E.C., 1995. "Game theory : The next stage," Other publications TiSEM 7779b0f9-bef5-45c7-ae6b-7, Tilburg University, School of Economics and Management.
    9. Ho, Teck-Hua, 1996. "Finite automata play repeated prisoner's dilemma with information processing costs," Journal of Economic Dynamics and Control, Elsevier, vol. 20(1-3), pages 173-207.
    10. repec:dau:papers:123456789/8159 is not listed on IDEAS
    11. Beal, Sylvain & Querou, Nicolas, 2007. "Bounded rationality and repeated network formation," Mathematical Social Sciences, Elsevier, vol. 54(1), pages 71-89, July.
    12. Horaguchi, Haruo, 1996. "The role of information processing cost as the foundation of bounded rationality in game theory," Economics Letters, Elsevier, vol. 51(3), pages 287-294, June.
    13. Hubie Chen, 2013. "Bounded rationality, strategy simplification, and equilibrium," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 593-611, August.
    14. Anderlini, Luca, 1998. "Forecasting errors and bounded rationality: An example," Mathematical Social Sciences, Elsevier, vol. 36(2), pages 71-90, September.
    15. , & ,, 2013. "Implementation of communication equilibria by correlated cheap talk: The two-player case," Theoretical Economics, Econometric Society, vol. 8(1), January.
    16. Hernández, Penélope & Urbano, Amparo, 2008. "Codification schemes and finite automata," Mathematical Social Sciences, Elsevier, vol. 56(3), pages 395-409, November.
    17. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    18. Rabin, Matthew, 2000. "Inference by Believers in the Law of Small Numbers," Department of Economics, Working Paper Series qt4sw8n41t, Department of Economics, Institute for Business and Economic Research, UC Berkeley.
    19. Gagen, Michael, 2013. "Isomorphic Strategy Spaces in Game Theory," MPRA Paper 46176, University Library of Munich, Germany.
    20. 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.
    21. Wichardt, Philipp C., 2010. "Modelling equilibrium play as governed by analogy and limited foresight," Games and Economic Behavior, Elsevier, vol. 70(2), pages 472-487, November.

    More about this item

    Keywords

    Costly computation; Bounded rationality;

    JEL classification:

    • D80 - Microeconomics - - Information, Knowledge, and Uncertainty - - - General
    • D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search; Learning; Information and Knowledge; Communication; Belief; Unawareness

    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:eee:jetheo:v:156:y:2015:i:c:p:246-268. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622869 .

    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.