IDEAS home Printed from https://ideas.repec.org/p/pri/metric/78_2016.html
   My bibliography  Save this paper

A "Pencil Sharpening" Algorithm for Two Player Stochastic Games with Perfect Monitoring

Author

Listed:
  • Dilip Abreu

    (Princeton University)

  • Benjamin Brooks

    (Becker Friedman Institute and Univ ersity of Chicago)

  • Yuliy Sannikov

    (Princeton University)

Abstract

We study the subgame perfect equilibria of two player stochastic games with perfect monitoring and geometric discounting. A novel algorithm is developed for calculating the discounted payoffs that can be attained in equilibrium. This algorithm generates a sequence of tuples of payoffs vectors, one payoff for each state, that move around the equilibrium payoff sets in a clockwise manner. The trajectory of these "pivot" payoffs asymptotically traces the boundary of the equilibrium payoff correspondence. We also provide an implementation of our algorithm, and preliminary simulations indicate that it is more efficient than existing methods. The theoretical results that underlie the algorithm also yield a bound on the number of extremal equilibrium payoffs.

Suggested Citation

  • 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..
    • Handle: RePEc:pri:metric:78_2016
    as

    Download full text from publisher

    File URL: http://detc.princeton.edu/wp-content/uploads/2016/11/wp078_2016_Abreu_Brooks_Sannikov_A-Pencil-Sharpening-Algorithm.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Ethan Ligon & Jonathan P. Thomas & Tim Worrall, 2000. "Mutual Insurance, Individual Savings and Limited Commitment," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 3(2), pages 216-246, April.
    2. Lars Ljungqvist & Thomas J. Sargent, 2004. "Recursive Macroeconomic Theory, 2nd Edition," MIT Press Books, The MIT Press, edition 2, volume 1, number 026212274x, December.
    3. Atkeson, Andrew, 1991. "International Lending with Moral Hazard and Risk of Repudiation," Econometrica, Econometric Society, vol. 59(4), pages 1069-1089, July.
    4. Richard Ericson & Ariel Pakes, 1995. "Markov-Perfect Industry Dynamics: A Framework for Empirical Work," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 62(1), pages 53-82.
    5. Kenneth L. Judd & Sevin Yeltekin & James Conklin, 2003. "Computing Supergame Equilibria," Econometrica, Econometric Society, vol. 71(4), pages 1239-1254, July.
    6. Abreu, Dilip & Pearce, David & Stacchetti, Ennio, 1986. "Optimal cartel equilibria with imperfect monitoring," Journal of Economic Theory, Elsevier, vol. 39(1), pages 251-269, June.
    7. Avinash Dixit & Gene M. Grossman & Faruk Gul, 2000. "The Dynamics of Political Compromise," Journal of Political Economy, University of Chicago Press, vol. 108(3), pages 531-568, June.
    8. Johannes Hörner & Takuo Sugaya & Satoru Takahashi & Nicolas Vieille, 2011. "Recursive Methods in Discounted Stochastic Games: An Algorithm for δ→ 1 and a Folk Theorem," Econometrica, Econometric Society, vol. 79(4), pages 1277-1318, July.
    9. Abreu, Dilip & Sannikov, Yuliy, 2014. "An algorithm for two-player repeated games with perfect monitoring," Theoretical Economics, Econometric Society, vol. 9(2), May.
    10. Mailath, George J. & Samuelson, Larry, 2006. "Repeated Games and Reputations: Long-Run Relationships," OUP Catalogue, Oxford University Press, number 9780195300796.
    11. Narayana R. Kocherlakota, 1996. "Implications of Efficient Risk Sharing without Commitment," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 63(4), pages 595-609.
    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. Susanne Goldlücke & Sebastian Kranz, 2018. "Discounted stochastic games with voluntary transfers," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(1), pages 235-263, July.
    2. Āzacis, Helmuts & Vida, Péter, 2019. "Repeated implementation: A practical characterization," Journal of Economic Theory, Elsevier, vol. 180(C), pages 336-367.
    3. Suehyun Kwon, 2019. "Dynamic IC and dynamic programming," CESifo Working Paper Series 7564, CESifo.
    4. Jose Miguel Abito & Cuicui Chen, 2021. "How much can we identify from repeated games?," Economics Bulletin, AccessEcon, vol. 41(3), pages 1212-1222.

    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. Kimmo Berg, 2016. "Elementary Subpaths in Discounted Stochastic Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 304-323, September.
    2. Dilip Abreu & Benjamin Brooks & Yuliy Sannikov, 2020. "Algorithms for Stochastic Games With Perfect Monitoring," Econometrica, Econometric Society, vol. 88(4), pages 1661-1695, July.
    3. Kimmo Berg & Gijs Schoenmakers, 2017. "Construction of Subgame-Perfect Mixed-Strategy Equilibria in Repeated Games," Games, MDPI, vol. 8(4), pages 1-14, November.
    4. Doraszelski, Ulrich & Escobar, Juan F., 2012. "Restricted feedback in long term relationships," Journal of Economic Theory, Elsevier, vol. 147(1), pages 142-161.
    5. Krueger, Dirk & Uhlig, Harald, 2006. "Competitive risk sharing contracts with one-sided commitment," Journal of Monetary Economics, Elsevier, vol. 53(7), pages 1661-1691, October.
    6. Kimmo Berg & Markus Kärki, 2018. "Critical Discount Factor Values in Discounted Supergames," Games, MDPI, vol. 9(3), pages 1-17, July.
    7. Johannes Horner & Takuo Sugaya & Satoru Takahashi & Nicolas Vieille, 2009. "Recursive Methods in Discounted Stochastic Games: An Algorithm for delta Approaching 1 and a Folk Theorem," Cowles Foundation Discussion Papers 1742, Cowles Foundation for Research in Economics, Yale University, revised Aug 2010.
    8. 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.
    9. Gary Gorton & Ping He, 2023. "Optimal monetary policy in a collateralized economy," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 75(1), pages 55-89, January.
    10. , & ,, 2015. "A folk theorem for stochastic games with infrequent state changes," Theoretical Economics, Econometric Society, vol. 10(1), January.
    11. Susanne Goldlücke & Sebastian Kranz, 2018. "Discounted stochastic games with voluntary transfers," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(1), pages 235-263, July.
    12. Mitri Kitti, 2013. "Conditional Markov equilibria in discounted dynamic games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 78(1), pages 77-100, August.
    13. Kimmo Berg & Mitri Kitti, 2014. "Equilibrium Paths in Discounted Supergames," Discussion Papers 96, Aboa Centre for Economics.
    14. Kam, Timothy & Stauber, Ronald, 2016. "Solving dynamic public insurance games with endogenous agent distributions: Theory and computational approximation," Journal of Mathematical Economics, Elsevier, vol. 64(C), pages 77-98.
    15. Goldlücke, Susanne & Kranz, Sebastian, 2012. "Infinitely repeated games with public monitoring and monetary transfers," Journal of Economic Theory, Elsevier, vol. 147(3), pages 1191-1221.
    16. Doraszelski, Ulrich & Escobar, Juan F., 2019. "Protocol invariance and the timing of decisions in dynamic games," Theoretical Economics, Econometric Society, vol. 14(2), May.
    17. Doraszelski, Ulrich & Pakes, Ariel, 2007. "A Framework for Applied Dynamic Analysis in IO," Handbook of Industrial Organization, in: Mark Armstrong & Robert Porter (ed.), Handbook of Industrial Organization, edition 1, volume 3, chapter 30, pages 1887-1966, Elsevier.
    18. Juan Passadore & Juan Xandri, 2019. "Robust Predictions in Dynamic Policy Games," 2019 Meeting Papers 1345, Society for Economic Dynamics.
    19. Árpád Ábrahám & Sarolta Laczó, 2018. "Efficient Risk Sharing with Limited Commitment and Storage," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 85(3), pages 1389-1424.
    20. Bethune, Zachary & Hu, Tai-Wei & Rocheteau, Guillaume, 2018. "Indeterminacy in credit economies," Journal of Economic Theory, Elsevier, vol. 175(C), pages 556-584.

    More about this item

    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
    • D90 - Microeconomics - - Micro-Based Behavioral Economics - - - General

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:pri:metric:78_2016. 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: Bobray Bordelon (email available below). General contact details of provider: https://edirc.repec.org/data/exprius.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.