IDEAS home Printed from https://ideas.repec.org/p/cwl/cwldpp/1742.html
   My bibliography  Save this paper

Recursive Methods in Discounted Stochastic Games: An Algorithm for delta Approaching 1 and a Folk Theorem

Author

Listed:

Abstract

We present an algorithm to compute the set of perfect public equilibrium payoffs as the discount factor tends to one for stochastic games with observable states and public (but not necessarily perfect) monitoring when the limiting set of (long-run players') equilibrium payoffs is independent of the state. This is the case, for instance, if the Markov chain induced by any Markov strategy profile is irreducible. We then provide conditions under which a folk theorem obtains: if in each state the joint distribution over the public signal and next period’s state satisfies some rank condition, every feasible payoff vector above the minmax payoff is sustained by a perfect public equilibrium with low discounting.

Suggested Citation

  • 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.
    • Handle: RePEc:cwl:cwldpp:1742
    as

    Download full text from publisher

    File URL: https://cowles.yale.edu/sites/default/files/files/pub/d17/d1742.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Mertens, J.-F. & Parthasarathy, T., 1987. "Equilibria for discounted stochastic games," LIDAM Discussion Papers CORE 1987050, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Phelan, Christopher, 2006. "Public trust and government betrayal," Journal of Economic Theory, Elsevier, vol. 130(1), pages 27-43, September.
    3. Drew Fudenberg & David Levine & Eric Maskin, 2008. "The Folk Theorem With Imperfect Public Information," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 12, pages 231-273, World Scientific Publishing Co. Pte. Ltd..
    4. Green, Edward J & Porter, Robert H, 1984. "Noncooperative Collusion under Imperfect Price Information," Econometrica, Econometric Society, vol. 52(1), pages 87-100, January.
    5. Mertens, J.-F. & Parthasarathy, T., 1991. "Nonzero-sum stochastic games," LIDAM Reprints CORE 912, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Roger Lagunoff & Akihiko Matsui, 1997. "Asynchronous Choice in Repeated Coordination Games," Econometrica, Econometric Society, vol. 65(6), pages 1467-1478, November.
    7. Drew Fudenberg & David K. Levine, 2008. "Efficiency and Observability with Long-Run and Short-Run Players," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 13, pages 275-307, World Scientific Publishing Co. Pte. Ltd..
    8. Drew Fudenberg & David M. Kreps & Eric S. Maskin, 1990. "Repeated Games with Long-run and Short-run Players," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 57(4), pages 555-573.
    9. Drew Fudenberg & Eric Maskin, 2008. "The Folk Theorem In Repeated Games With Discounting Or With Incomplete Information," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 11, pages 209-230, World Scientific Publishing Co. Pte. Ltd..
    10. Mertens, Jean-Francois, 2002. "Stochastic games," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 47, pages 1809-1832, Elsevier.
    11. 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.
    12. Kenneth L. Judd & Sevin Yeltekin & James Conklin, 2003. "Computing Supergame Equilibria," Econometrica, Econometric Society, vol. 71(4), pages 1239-1254, July.
    13. 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.
    14. Abraham Neyman, 2002. "Stochastic games: Existence of the MinMax," Discussion Paper Series dp295, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    15. Mailath, George J. & Samuelson, Larry, 2006. "Repeated Games and Reputations: Long-Run Relationships," OUP Catalogue, Oxford University Press, number 9780195300796.
    16. Yoon, Kiho, 2001. "A Folk Theorem for Asynchronously Repeated Games," Econometrica, Econometric Society, vol. 69(1), pages 191-200, January.
    17. Truman Bewley & Elon Kohlberg, 1976. "The Asymptotic Theory of Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 1(3), pages 197-208, August.
    18. Christopher Phelan & Ennio Stacchetti, 2001. "Sequential Equilibria in a Ramsey Tax Model," Econometrica, Econometric Society, vol. 69(6), pages 1491-1518, November.
    19. Rotemberg, Julio J & Saloner, Garth, 1986. "A Supergame-Theoretic Model of Price Wars during Booms," American Economic Review, American Economic Association, vol. 76(3), pages 390-407, June.
    20. A. J. Hoffman & R. M. Karp, 1966. "On Nonterminating Stochastic Games," Management Science, INFORMS, vol. 12(5), pages 359-370, January.
    21. Roy Radner & Roger Myerson & Eric Maskin, 1986. "An Example of a Repeated Partnership Game with Discounting and with Uniformly Inefficient Equilibria," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 53(1), pages 59-69.
    Full references (including those not matched with items on IDEAS)

    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. Nicolas Vieille, 2010. "Recursive Methods in Discounted Stochastic Games: An Algorithm for - 1 and a Folk Theorem," Post-Print hal-00543616, HAL.
    2. Escobar, Juan F. & Llanes, Gastón, 2018. "Cooperation dynamics in repeated games of adverse selection," Journal of Economic Theory, Elsevier, vol. 176(C), pages 408-443.
    3. Osório-Costa, António M., 2009. "Efficiency Gains in Repeated Games at Random Moments in Time," MPRA Paper 13105, University Library of Munich, Germany.
    4. Laclau, Marie & Tomala, Tristan, 2017. "Repeated games with public deterministic monitoring," Journal of Economic Theory, Elsevier, vol. 169(C), pages 400-424.
    5. Abito, Jose Miguel & Chen, Cuicui, 2023. "A partial identification framework for dynamic games," International Journal of Industrial Organization, Elsevier, vol. 87(C).
    6. Miyagawa, Eiichi & Miyahara, Yasuyuki & Sekiguchi, Tadashi, 2008. "The folk theorem for repeated games with observation costs," Journal of Economic Theory, Elsevier, vol. 139(1), pages 192-221, March.
    7. Marie Laclau & Tristan Tomala, 2016. "Repeated games with public information revisited," PSE Working Papers hal-01285326, HAL.
    8. Fudenberg, Drew & Yamamoto, Yuichi, 2011. "Learning from private information in noisy repeated games," Journal of Economic Theory, Elsevier, vol. 146(5), pages 1733-1769, September.
    9. Fudenberg, Drew & Olszewski, Wojciech, 2011. "Repeated games with asynchronous monitoring of an imperfect signal," Games and Economic Behavior, Elsevier, vol. 72(1), pages 86-99, May.
    10. Kimmo Berg, 2016. "Elementary Subpaths in Discounted Stochastic Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 304-323, September.
    11. Dou, Winston Wei & Ji, Yan & Wu, Wei, 2021. "Competition, profitability, and discount rates," Journal of Financial Economics, Elsevier, vol. 140(2), pages 582-620.
    12. Drew Fudenberg & David K. Levine, 2008. "An Approximate Folk Theorem with Imperfect Private Information," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 14, pages 309-330, World Scientific Publishing Co. Pte. Ltd..
    13. Nuh Aygün Dalkıran, 2016. "Order of limits in reputations," Theory and Decision, Springer, vol. 81(3), pages 393-411, September.
    14. Laclau, M., 2014. "Communication in repeated network games with imperfect monitoring," Games and Economic Behavior, Elsevier, vol. 87(C), pages 136-160.
    15. Sugaya, Takuo & Wolitzky, Alexander, 2017. "Bounding equilibrium payoffs in repeated games with private monitoring," Theoretical Economics, Econometric Society, vol. 12(2), May.
    16. Doraszelski, Ulrich & Escobar, Juan F., 2012. "Restricted feedback in long term relationships," Journal of Economic Theory, Elsevier, vol. 147(1), pages 142-161.
    17. Juan‐Pablo Montero & Juan Ignacio Guzman, 2010. "Output‐Expanding Collusion In The Presence Of A Competitive Fringe," Journal of Industrial Economics, Wiley Blackwell, vol. 58(1), pages 106-126, March.
    18. Drew Fudenberg & David K. Levine & Satoru Takahashi, 2008. "Perfect public equilibrium when players are patient," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 16, pages 345-367, World Scientific Publishing Co. Pte. Ltd..
    19. Kaplow, Louis & Shapiro, Carl, 2007. "Antitrust," Handbook of Law and Economics, in: A. Mitchell Polinsky & Steven Shavell (ed.), Handbook of Law and Economics, edition 1, volume 2, chapter 15, pages 1073-1225, Elsevier.
    20. Kimmo Berg & Gijs Schoenmakers, 2017. "Construction of Subgame-Perfect Mixed-Strategy Equilibria in Repeated Games," Games, MDPI, vol. 8(4), pages 1-14, November.

    More about this item

    Keywords

    Stochastic games;

    JEL classification:

    • 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

    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:cwl:cwldpp:1742. 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: Brittany Ladd (email available below). General contact details of provider: https://edirc.repec.org/data/cowleus.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.