IDEAS home Printed from https://ideas.repec.org/a/the/publsh/1302.html
   My bibliography  Save this article

An algorithm for two-player repeated games with perfect monitoring

Author

Listed:
  • Abreu, Dilip

    () (Department of Economics, Princeton University)

  • Sannikov, Yuliy

    () (Department of Economics, Princeton University)

Abstract

Consider repeated two-player games with perfect monitoring and discounting. We provide an algorithm that computes the set V* of payoff pairs of all pure-strategy subgame perfect equilibria with public randomization. The algorithm provides significant efficiency gains over the existing implementations of the algorithm from Abreu, Pearce and Stacchetti (1990). These efficiency gains arise from a better understanding of the manner in which extreme points of the equilibrium payoff set are generated. An important theoretical implication of our algorithm is that the set of extreme points E of V* is finite. Indeed, |E| ≤ 3|A|, where A is the set of action profiles of the stage game.

Suggested Citation

  • Abreu, Dilip & Sannikov, Yuliy, 2014. "An algorithm for two-player repeated games with perfect monitoring," Theoretical Economics, Econometric Society, vol. 9(2), May.
  • Handle: RePEc:the:publsh:1302
    as

    Download full text from publisher

    File URL: http://econtheory.org/ojs/index.php/te/article/viewFile/20140313/10806/321
    Download Restriction: no

    References listed on IDEAS

    as
    1. Cho, Myeonghwan, 2011. "Public randomization in the repeated prisoner's dilemma game with local interaction," Economics Letters, Elsevier, vol. 112(3), pages 280-282, September.
    2. Gilli, Mario, 1999. "On Non-Nash Equilibria," Games and Economic Behavior, Elsevier, vol. 27(2), pages 184-203, May.
    3. Ben-Porath, Elchanan & Kahneman, Michael, 1996. "Communication in Repeated Games with Private Monitoring," Journal of Economic Theory, Elsevier, pages 281-297.
    4. Itay P. Fainmesser, 2012. "Community Structure and Market Outcomes: A Repeated Games-in-Networks Approach," American Economic Journal: Microeconomics, American Economic Association, vol. 4(1), pages 32-69, February.
    5. Vega-Redondo, Fernando, 2006. "Building up social capital in a changing world," Journal of Economic Dynamics and Control, Elsevier, vol. 30(11), pages 2305-2338, November.
    6. JÊrÆme Renault & Tristan Tomala, 1998. "Repeated proximity games," International Journal of Game Theory, Springer;Game Theory Society, pages 539-559.
    7. Markus Kinateder, 2006. "Repeated Games Played in a Network," UFAE and IAE Working Papers 674.06, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    8. Myeonghwan Cho, 2014. "Cooperation in the repeated prisoner's dilemma game with local interaction and local communication," International Journal of Economic Theory, The International Society for Economic Theory, vol. 10(3), pages 235-262, September.
    9. David Miller & Nageeb Ali, 2008. "Cooperation and Collective Enforcement in Networked Societies," 2008 Meeting Papers 970, Society for Economic Dynamics.
    10. Joyee Deb, 2008. "Cooperation and Community Responsibility: A Folk Theorem for Repeated Matching Games with Names," Working Papers 08-24, New York University, Leonard N. Stern School of Business, Department of Economics.
    11. Glenn Ellison, 1994. "Cooperation in the Prisoner's Dilemma with Anonymous Random Matching," Review of Economic Studies, Oxford University Press, vol. 61(3), pages 567-588.
    12. McBride, Michael, 2006. "Imperfect monitoring in communication networks," Journal of Economic Theory, Elsevier, vol. 126(1), pages 97-119, January.
    13. Takahashi, Satoru, 2010. "Community enforcement when players observe partners' past play," Journal of Economic Theory, Elsevier, vol. 145(1), pages 42-62, January.
    14. Matthew O. Jackson & Tomas Rodriguez-Barraquer & Xu Tan, 2012. "Social Capital and Social Quilts: Network Patterns of Favor Exchange," American Economic Review, American Economic Association, vol. 102(5), pages 1857-1897, August.
    15. Alexander Wolitzky, 2013. "Cooperation with Network Monitoring," Review of Economic Studies, Oxford University Press, vol. 80(1), pages 395-427.
    16. Michihiro Kandori, 1992. "Social Norms and Community Enforcement," Review of Economic Studies, Oxford University Press, vol. 59(1), pages 63-80.
    17. Michi Kandori, 2010. "Social Norms and Community Enforcement," Levine's Working Paper Archive 630, David K. Levine.
    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. Hörner, Johannes & Takahashi, Satoru & Vieille, Nicolas, 2014. "On the limit perfect public equilibrium payoff set in repeated and stochastic games," Games and Economic Behavior, Elsevier, vol. 85(C), pages 70-83.
    2. Azacis, Helmuts & Vida, Péter, 2015. "Repeated Implementation," Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems 518, Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich.
    3. Kimmo Berg, 2017. "Extremal Pure Strategies and Monotonicity in Repeated Games," Computational Economics, Springer;Society for Computational Economics, vol. 49(3), pages 387-404, March.
    4. Philipp Renner & Simon Scheidegger, 2017. "Machine learning for dynamic incentive problems," Working Papers 203620397, Lancaster University Management School, Economics Department.
    5. Dilip Abreu & Benjamin Brooks & Yuliy Sannikov, 2016. "A “Pencil Sharpening†Algorithm for Two Player Stochastic Games with Perfect Monitoring," Working Papers 78_2016, Princeton University, Department of Economics, Econometric Research Program..
    6. Kimmo Berg & Mitri Kitti, 2014. "Equilibrium Paths in Discounted Supergames," Discussion Papers 96, Aboa Centre for Economics.

    More about this item

    Keywords

    Repeated games; perfect monitoring; computation;

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games

    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:the:publsh:1302. 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: (Martin J. Osborne). General contact details of provider: http://econtheory.org .

    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.

    We have no references for this item. You can help adding them by using 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.