IDEAS home Printed from https://ideas.repec.org/a/wly/emetrp/v88y2020i4p1661-1695.html

Algorithms for Stochastic Games With Perfect Monitoring

Author

Listed:
  • Dilip Abreu
  • Benjamin Brooks
  • Yuliy Sannikov

Abstract

We study the pure‐strategy subgame‐perfect Nash equilibria of stochastic games with perfect monitoring, geometric discounting, and public randomization. We develop novel algorithms for computing equilibrium payoffs, in which we combine policy iteration when incentive constraints are slack with value iteration when incentive constraints bind. We also provide software implementations of our algorithms. Preliminary simulations indicate that they are significantly more efficient than existing methods. The theoretical results that underlie the algorithms also imply bounds on the computational complexity of equilibrium payoffs when there are two players. When there are more than two players, we show by example that the number of extreme equilibrium payoffs may be countably infinite.

Suggested Citation

  • Dilip Abreu & Benjamin Brooks & Yuliy Sannikov, 2020. "Algorithms for Stochastic Games With Perfect Monitoring," Econometrica, Econometric Society, vol. 88(4), pages 1661-1695, July.
    • Handle: RePEc:wly:emetrp:v:88:y:2020:i:4:p:1661-1695
    DOI: 10.3982/ECTA14357
    as

    Download full text from publisher

    File URL: https://doi.org/10.3982/ECTA14357
    Download Restriction: no
    File URL: https://libkey.io/10.3982/ECTA14357?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
    ---><---

    References listed on IDEAS

    as
    1. Atkeson, Andrew, 1991. "International Lending with Moral Hazard and Risk of Repudiation," Econometrica, Econometric Society, vol. 59(4), pages 1069-1089, July.
    2. 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.
    3. 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.
    4. Lars Ljungqvist & Thomas J. Sargent, 2004. "Recursive Macroeconomic Theory, 2nd Edition," MIT Press Books, The MIT Press, edition 2, volume 1, number 026212274x, December.
    5. Philipp Renner & Simon Scheidegger, 2017. "Machine learning for dynamic incentive problems," Working Papers 203620397, Lancaster University Management School, Economics Department.
    6. Christopher Phelan & Ennio Stacchetti, 2001. "Sequential Equilibria in a Ramsey Tax Model," Econometrica, Econometric Society, vol. 69(6), pages 1491-1518, November.
    7. Ariel Pakes & Paul McGuire, 1994. "Computing Markov-Perfect Nash Equilibria: Numerical Implications of a Dynamic Differentiated Product Model," RAND Journal of Economics, The RAND Corporation, vol. 25(4), pages 555-589, Winter.
    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. 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. Abito, Jose Miguel & Chen, Cuicui, 2023. "A partial identification framework for dynamic games," International Journal of Industrial Organization, Elsevier, vol. 87(C).
    2. Rumen Kostadinov, 2023. "Worst-case Regret in Ambiguous Dynamic Games," Department of Economics Working Papers 2022-08, McMaster University.
    3. Galit Ashkenazi-Golan & Ilia Krasikov & Catherine Rainer & Eilon Solan, 2026. "The APS approach for undiscounted quitting games," International Journal of Game Theory, Springer;Game Theory Society, vol. 55(1), pages 1-36, June.

    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. Abreu, Dilip & Brooks, Benjamin & Sannikov, Yuliy, 2016. "A "Pencil-Sharpening" Algorithm for Two Player Stochastic Games with Perfect Monitoring," Research Papers 3428, Stanford University, Graduate School of Business.
    2. Kimmo Berg, 2016. "Elementary Subpaths in Discounted Stochastic Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 304-323, September.
    3. 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.
    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. 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.
    6. Brendon, Charles & Ellison, Martin, 2018. "Time-consistently undominated policies," LSE Research Online Documents on Economics 87176, London School of Economics and Political Science, LSE Library.
    7. Oscar Mauricio VALENCIA ARANA, 2006. "Imperfect Government Insurance and Treasury Securities Markets," Archivos de Economía 2814, Departamento Nacional de Planeación.
    8. 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.
    9. de Roos, Nicolas, 2004. "A model of collusion timing," International Journal of Industrial Organization, Elsevier, vol. 22(3), pages 351-387, March.
    10. Gorton, Gary B. & He, Ping & Huang, Lixin, 2014. "Agency-based asset pricing," Journal of Economic Theory, Elsevier, vol. 149(C), pages 311-349.
    11. Arellano, Cristina & Mendoza, Enrique G., 2002. "Credit Frictions and "Sudden Stop" in Small Open Economies: An Equilibrium Business Cycle Framework for Emerging Markets Crises," IDB Publications (Working Papers) 1440, Inter-American Development Bank.
    12. Chaim Fershtman & Ariel Pakes, 2000. "A Dynamic Oligopoly with Collusion and Price Wars," RAND Journal of Economics, The RAND Corporation, vol. 31(2), pages 207-236, Summer.
    13. Doraszelski, Ulrich & Escobar, Juan F., 2019. "Protocol invariance and the timing of decisions in dynamic games," Theoretical Economics, Econometric Society, vol. 14(2), May.
    14. Galit Ashkenazi-Golan & Ilia Krasikov & Catherine Rainer & Eilon Solan, 2026. "The APS approach for undiscounted quitting games," International Journal of Game Theory, Springer;Game Theory Society, vol. 55(1), pages 1-36, June.
    15. Kimmo Berg & Gijs Schoenmakers, 2017. "Construction of Subgame-Perfect Mixed-Strategy Equilibria in Repeated Games," Games, MDPI, vol. 8(4), pages 1-14, November.
    16. , & ,, 2015. "A folk theorem for stochastic games with infrequent state changes," Theoretical Economics, Econometric Society, vol. 10(1), January.
    17. Bielecki, Marcin, . "Długie oddziaływanie szoków finansowych z perspektywy wzrostu endogenicznego," Gospodarka Narodowa-The Polish Journal of Economics, Szkoła Główna Handlowa w Warszawie / SGH Warsaw School of Economics, vol. 2022(3).
    18. Grochulski, Borys & Zhang, Yuzhe, 2011. "Optimal risk sharing and borrowing constraints in a continuous-time model with limited commitment," Journal of Economic Theory, Elsevier, vol. 146(6), pages 2356-2388.
    19. Nicolas Vieille, 2010. "Recursive Methods in Discounted Stochastic Games: An Algorithm for - 1 and a Folk Theorem," Post-Print hal-00543616, HAL.
    20. Richard Lowery & Tim Landvoigt, 2016. "Financial Industry Dynamics," 2016 Meeting Papers 1248, Society for Economic Dynamics.

    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:wly:emetrp:v:88:y:2020:i:4:p:1661-1695. 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: Wiley Content Delivery (email available below). General contact details of provider: https://edirc.repec.org/data/essssea.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.