IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v42y2013i3p639-671.html
   My bibliography  Save this article

Program equilibrium—a program reasoning approach

Author

Listed:
  • Wiebe Hoek
  • Cees Witteveen
  • Michael Wooldridge

Abstract

The concept of program equilibrium, introduced by Howard (Theory and Decision 24(3):203–213, 1988 ) and further formalised by Tennenholtz (Game Econ Behav 49:363–373, 2004 ), represents one of the most ingenious and potentially far-reaching applications of ideas from computer science in game theory to date. The basic idea is that a player in a game selects a strategy by entering a program, whose behaviour may be conditioned on the programs submitted by other players. Thus, for example, in the prisoner’s dilemma, a player can enter a program that says “If his program is the same as mine, then I cooperate, otherwise I defect”. It can easily be shown that if such programs are permitted, then rational cooperation is possible even in the one-shot prisoner’s dilemma. In the original proposal of Tennenholtz, comparison between programs was limited to syntactic comparison of program texts. While this approach has some considerable advantages (not the least being computational and semantic simplicity), it also has some important limitations. In this paper, we investigate an approach to program equilibrium in which richer conditions are allowed, based on model checking—one of the most successful approaches to reasoning about programs. We introduce a decision-tree model of strategies, which may be conditioned on strategies of others. We then formulate and investigate a notion of “outcome” for our setting, and investigate the complexity of reasoning about outcomes. We focus on coherent outcomes: outcomes in which every decision by every player is justified by the conditions in his program. We identify a condition under which there exist a unique coherent outcome. We also compare our notion of (coherent) outcome with that of (supported) semantics known from logic programming. We illustrate our approach with many examples. Copyright Springer-Verlag 2013

Suggested Citation

  • Wiebe Hoek & Cees Witteveen & Michael Wooldridge, 2013. "Program equilibrium—a program reasoning approach," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 639-671, August.
  • Handle: RePEc:spr:jogath:v:42:y:2013:i:3:p:639-671
    DOI: 10.1007/s00182-011-0314-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00182-011-0314-6
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s00182-011-0314-6?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. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, December.
    2. Ken Binmore, 1998. "Game Theory and the Social Contract - Vol. 2: Just Playing," MIT Press Books, The MIT Press, edition 1, volume 2, number 0262024446, December.
    3. Ken Binmore, 1994. "Game Theory and the Social Contract, Volume 1: Playing Fair," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262023636, December.
    4. Tennenholtz, Moshe, 2004. "Program equilibrium," Games and Economic Behavior, Elsevier, vol. 49(2), pages 363-373, November.
    5. Kalai, Adam Tauman & Kalai, Ehud & Lehrer, Ehud & Samet, Dov, 2010. "A commitment folk theorem," Games and Economic Behavior, Elsevier, vol. 69(1), pages 127-137, May.
    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. Caspar Oesterheld, 2019. "Robust program equilibrium," Theory and Decision, Springer, vol. 86(1), pages 143-159, February.

    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. Max Albert & Hartmut Kliemt, 2017. "Infinite Idealizations and Approximate Explanations in Economics," MAGKS Papers on Economics 201726, Philipps-Universität Marburg, Faculty of Business Administration and Economics, Department of Economics (Volkswirtschaftliche Abteilung).
    2. Larry Samuelson, 2016. "Game Theory in Economics and Beyond," Journal of Economic Perspectives, American Economic Association, vol. 30(4), pages 107-130, Fall.
    3. Thijssen, J.J.J., 2003. "Investment under uncertainty, market evolution and coalition spillovers in a game theoretic perspective," Other publications TiSEM 672073a6-492e-4621-8d4a-0, Tilburg University, School of Economics and Management.
    4. Karl Wärneryd, 2014. "Observable Strategies, Commitments, and Contracts," CESifo Working Paper Series 5089, CESifo.
    5. Muthoo, Abhinay, 2000. "On the foundations of basic property rights, Part I: A model of the state-of-nature with two players," Economics Discussion Papers 9986, University of Essex, Department of Economics.
    6. Louis Corriveau, 2012. "Game theory and the kula," Rationality and Society, , vol. 24(1), pages 106-128, February.
    7. Ley, Eduardo, 2006. "Statistical inference as a bargaining game," Economics Letters, Elsevier, vol. 93(1), pages 142-149, October.
    8. Keiki Takadama & Tetsuro Kawai & Yuhsuke Koyama, 2008. "Micro- and Macro-Level Validation in Agent-Based Simulation: Reproduction of Human-Like Behaviors and Thinking in a Sequential Bargaining Game," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 11(2), pages 1-9.
    9. Forges, Françoise, 2013. "A folk theorem for Bayesian games with commitment," Games and Economic Behavior, Elsevier, vol. 78(C), pages 64-71.
    10. Joseph Y. Halpern & Rafael Pass, 2018. "Game theory with translucent players," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(3), pages 949-976, September.
    11. Françoise Forges & Ulrich Horst & Antoine Salomon, 2016. "Feasibility and individual rationality in two-person Bayesian games," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 11-36, March.
    12. Laurie Bréban, 2018. "An Investigation into the Smithian System of Sympathy: from Cognition to Emotion," Post-Print hal-03904227, HAL.
    13. Luca Zarri, 2007. "Happiness, Morality and Game Theory," Chapters, in: Luigino Bruni & Pier Luigi Porta (ed.), Handbook on the Economics of Happiness, chapter 16, Edward Elgar Publishing.
    14. Michael Vlerick, 2020. "Towards Global Cooperation: The Case for a Deliberative Global Citizens' Assembly," Global Policy, London School of Economics and Political Science, vol. 11(3), pages 305-314, May.
    15. Pelle Hansen & David Rojo Arjona, 2011. "Prune or cut down: salience and Sugden’s The Economics of Rights, Co-operation and Welfare," International Review of Economics, Springer;Happiness Economics and Interpersonal Relations (HEIRS), vol. 58(1), pages 53-78, March.
    16. Laurie Bréban & Muriel Gilardone, 2019. "A missing touch of Adam Smith in Amartya Sen’s account of Public Reasoning: the Man Within for the Man Without," Economics Working Paper from Condorcet Center for political Economy at CREM-CNRS 2019-01-ccr, Condorcet Center for political Economy.
    17. Juan I. Block & David K. Levine, 2017. "A folk theorem with codes of conduct and communication," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 5(1), pages 9-19, April.
    18. Irene van Staveren, 2012. "An Evolutionary Efficiency Alternative to the Notion of Pareto Efficiency," Economic Thought, World Economics Association, vol. 1(1), pages 1-6, July.
    19. Peters, Michael & Troncoso-Valverde, Cristián, 2013. "A folk theorem for competing mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 953-973.
    20. Juan I Block & David K Levine, 2016. "A Folk Theorem with Codes of Conduct," Levine's Working Paper Archive 786969000000001323, David K. Levine.

    More about this item

    Keywords

    Program equilibrium; Non-cooperative games; Repeated games; Logic programming; Programs as strategies; Equality of programs; C7; C72; C6; C60; C62;
    All these keywords.

    JEL classification:

    • C7 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C6 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling
    • C60 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - General
    • C62 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium

    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:spr:jogath:v:42:y:2013:i:3:p:639-671. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.