IDEAS home Printed from https://ideas.repec.org/p/cmu/gsiawp/-962041374.html
   My bibliography  Save this paper

Computing Equilibria of Dynamic Games

Author

Listed:
  • Kenneth Judd
  • Sevin Yeltekin

Abstract

We develop a numerical method for computing all pure strategy subgame-perfect equilibrium values of dynamic strategic games with discrete states and actions. We define a monotone mapping that eliminates dominated strategies, and when applied iteratively, delivers an accurate approximation to the true equilibrium payoffs of the underlying game. Our algorithm has three parts. The first provides an outer approximation to equilibrium values, constructed so that any value outside of this approximation is not an equilibrium value. The second provides an inner approximation; any value contained within this approximation is an equilibrium value. Together, the two approximations deliver a practical check of approximation accuracy. The third part of our algorithm delivers sample equilibrium paths. To illustrate our method, we apply it to a dynamic oligopoly competition with endogenous production capacity.
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • Kenneth Judd & Sevin Yeltekin, "undated". "Computing Equilibria of Dynamic Games," GSIA Working Papers 2011-E20, Carnegie Mellon University, Tepper School of Business.
  • Handle: RePEc:cmu:gsiawp:-962041374
    as

    Download full text from publisher

    File URL: https://student-3k.tepper.cmu.edu/gsiadoc/WP/2011-E20.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Carl Davidson & Raymond Deneckere, 1986. "Long-Run Competition in Capacity, Short-Run Competition in Price, and the Cournot Model," RAND Journal of Economics, The RAND Corporation, vol. 17(3), pages 404-415, Autumn.
    2. A. Michael Spence, 1979. "Investment Strategy and Growth in a New Market," Bell Journal of Economics, The RAND Corporation, vol. 10(1), pages 1-19, Spring.
    3. Sleet, Christopher & Yeltekin, Sevin, 2007. "Recursive monetary policy games with incomplete information," Journal of Economic Dynamics and Control, Elsevier, vol. 31(5), pages 1557-1583, May.
    4. Jean-Pierre Benoit & Vijay Krishna, 1987. "Dynamic Duopoly: Prices and Quantities," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 54(1), pages 23-35.
    5. Davidson, Carl & Deneckere, Raymond J, 1990. "Excess Capacity and Collusion," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 31(3), pages 521-541, August.
    6. Fudenberg, Drew & Tirole, Jean, 1983. "Capital as a commitment: Strategic investment to deter mobility," Journal of Economic Theory, Elsevier, vol. 31(2), pages 227-250, December.
    7. 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..
    8. Kenneth L. Judd & Sevin Yeltekin & James Conklin, 2003. "Computing Supergame Equilibria," Econometrica, Econometric Society, vol. 71(4), pages 1239-1254, July.
    9. Fudenberg, Drew & Maskin, Eric, 1991. "On the dispensability of public randomization in discounted repeated games," Journal of Economic Theory, Elsevier, vol. 53(2), pages 428-438, April.
    10. Benoit, Jean-Pierre & Krishna, Vijay, 1991. "Entry deterrence and dynamic competition : The role of capacity reconsidered," International Journal of Industrial Organization, Elsevier, vol. 9(4), pages 477-495, December.
    11. Sorin, Sylvain, 1992. "Repeated games with complete information," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 1, chapter 4, pages 71-107, Elsevier.
    12. Sleet, Christopher & Yeltekin, Sevin, 2006. "Optimal taxation with endogenously incomplete debt markets," Journal of Economic Theory, Elsevier, vol. 127(1), pages 36-73, March.
    13. 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.
    14. David Besanko & Ulrich Doraszelski & Lauren Xiaoyuan Lu & Mark Satterthwaite, 2010. "Lumpy Capacity Investment and Disinvestment Dynamics," Operations Research, INFORMS, vol. 58(4-part-2), pages 1178-1193, August.
    15. James Conklin, 1996. "Computing Value Correspondences for Repeated Games with State Variables," Working Papers 9622, Banco de España.
    16. David M. Kreps & Jose A. Scheinkman, 1983. "Quantity Precommitment and Bertrand Competition Yield Cournot Outcomes," Bell Journal of Economics, The RAND Corporation, vol. 14(2), pages 326-337, Autumn.
    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. Santiago R. Balseiro & Huseyin Gurkan & Peng Sun, 2019. "Multiagent Mechanism Design Without Money," Operations Research, INFORMS, vol. 67(5), pages 1417-1436, September.
    3. Schosser, Josef, 2019. "Consistency between principal and agent with differing time horizons: Computing incentives under risk," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1113-1123.

    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. Sorgard, Lars, 1997. "Judo economics reconsidered: Capacity limitation, entry and collusion," International Journal of Industrial Organization, Elsevier, vol. 15(3), pages 349-368, May.
    2. Kimmo Berg & Gijs Schoenmakers, 2017. "Construction of Subgame-Perfect Mixed-Strategy Equilibria in Repeated Games," Games, MDPI, vol. 8(4), pages 1-14, November.
    3. 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.
    4. Kimmo Berg & Mitri Kitti, 2014. "Equilibrium Paths in Discounted Supergames," Discussion Papers 96, Aboa Centre for Economics.
    5. Knittel, Christopher R. & Lepore, Jason J., 2010. "Tacit collusion in the presence of cyclical demand and endogenous capacity levels," International Journal of Industrial Organization, Elsevier, vol. 28(2), pages 131-144, March.
    6. Bergman, Mats A., 1998. "Endogenous Timing of Investments Yields Modified Stackelberg Outcomes," SSE/EFI Working Paper Series in Economics and Finance 272, Stockholm School of Economics.
    7. Kimmo Berg & Markus Kärki, 2018. "Critical Discount Factor Values in Discounted Supergames," Games, MDPI, vol. 9(3), pages 1-17, July.
    8. Knittel, Christopher R. & Lepore, Jason J., 2010. "Tacit collusion in the presence of cyclical demand and endogenous capacity levels," International Journal of Industrial Organization, Elsevier, vol. 28(2), pages 131-144, March.
    9. Emmanuel Dechenaux & Dan Kovenock, 2011. "Endogenous rationing, price dispersion and collusion in capacity constrained supergames," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 47(1), pages 29-74, May.
    10. de Roos, Nicolas, 2006. "Examining models of collusion: The market for lysine," International Journal of Industrial Organization, Elsevier, vol. 24(6), pages 1083-1107, November.
    11. R. Cellini & L. Lambertini, 2000. "Non-Linear Market Demand and Capital Accumulation in A Differential Oligopoly Game," Working Papers 372, Dipartimento Scienze Economiche, Universita' di Bologna.
    12. Ashkenazi-Golan, Galit & Lehrer, Ehud, 2019. "What you get is what you see: Cooperation in repeated games with observable payoffs," Journal of Economic Theory, Elsevier, vol. 181(C), pages 197-237.
    13. de Frutos, María-Ángeles & Fabra, Natalia, 2011. "Endogenous capacities and price competition: The role of demand uncertainty," International Journal of Industrial Organization, Elsevier, vol. 29(4), pages 399-411, July.
    14. Steen, Frode & Sorgard, Lars, 1999. "Semicollusion in the Norwegian cement market," European Economic Review, Elsevier, vol. 43(9), pages 1775-1796, October.
    15. Salonen, Hannu & Vartiainen, Hannu, 2008. "Valuating payoff streams under unequal discount factors," Economics Letters, Elsevier, vol. 99(3), pages 595-598, June.
    16. Spagnolo, Giancarlo, 2005. "Managerial incentives and collusive behavior," European Economic Review, Elsevier, vol. 49(6), pages 1501-1523, August.
    17. Du, Chuang, 2012. "Solving payoff sets of perfect public equilibria: an example," MPRA Paper 38622, University Library of Munich, Germany.
    18. Vettas, Nikolaos & Biglaiser, Gary, 2004. "Dynamic Price Competition with Capacity Constraints and Strategic Buyers," CEPR Discussion Papers 4315, C.E.P.R. Discussion Papers.
    19. Hörner, Johannes & Takahashi, Satoru, 2016. "How fast do equilibrium payoff sets converge in repeated games?," Journal of Economic Theory, Elsevier, vol. 165(C), pages 332-359.
    20. George J. Mailath & : Wojciech Olszewski, 2008. "Folk Theorems with Bounded Recall under (Almost) Perfect Monitoring, Second Version," PIER Working Paper Archive 08-027, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 28 Jul 2008.

    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:cmu:gsiawp:-962041374. 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: Steve Spear (email available below). General contact details of provider: https://www.cmu.edu/tepper .

    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.