IDEAS home Printed from https://ideas.repec.org/p/unm/umagsb/2020001.html
   My bibliography  Save this paper

An Interior-Point Path-Following Method to Compute Stationary Equilibria in Stochastic Games

Author

Listed:
  • Dang, Chuangyin
  • Herings, P. Jean-Jacques

    (RS: GSBE Theme Data-Driven Decision-Making, RS: GSBE Theme Conflict & Cooperation, Microeconomics & Public Economics)

  • Li, Peixuan

Abstract

Subgame perfect equilibrium in stationary strategies (SSPE) is the most important solution concept used in applications of stochastic games, which makes it imperative to develop efficient numerical methods to compute an SSPE. For this purpose, this paper develops an interior-point path-following method (IPM), which remedies a number of issues with the existing method called stochastic linear tracing procedure (SLTP). The homotopy system of IPM is derived from the optimality conditions of an artificial barrier game, whose objective function is a combination of the original payoff function and a logarithmic term. Unlike SLTP, the starting stationary strategy profile can be arbitrarily chosen and IPM does not need switching between different systems of equations. The use of a perturbation term makes IPM applicable to all stochastic games, whereas SLTP only works for a generic stochastic game. A transformation of variables reduces the number of equations and variables of by roughly one half. Numerical results show that our method is more than three times as efficient as SLTP.

Suggested Citation

  • Dang, Chuangyin & Herings, P. Jean-Jacques & Li, Peixuan, 2020. "An Interior-Point Path-Following Method to Compute Stationary Equilibria in Stochastic Games," Research Memorandum 001, Maastricht University, Graduate School of Business and Economics (GSBE).
    • Handle: RePEc:unm:umagsb:2020001
    DOI: 10.26481/umagsb.2020001
    as

    Download full text from publisher

    File URL: https://cris.maastrichtuniversity.nl/ws/files/39595761/RM20001.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.26481/umagsb.2020001?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. Chen, Wei-Ting & Huang, Kuancheng & Ardiansyah, Muhammad Nashir, 2018. "A mathematical programming model for aircraft leasing decisions," Journal of Air Transport Management, Elsevier, vol. 69(C), pages 15-25.
    2. John C. Harsanyi & Reinhard Selten, 1988. "A General Theory of Equilibrium Selection in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582384, April.
    3. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    4. Herings, P. Jean-Jacques & Peeters, Ronald J. A. P., 2004. "Stationary equilibria in stochastic games: structure, selection, and computation," Journal of Economic Theory, Elsevier, vol. 118(1), pages 32-60, September.
    5. P. Herings & Karl Schmedders, 2006. "Computing equilibria in finance economies with incomplete markets and transaction costs," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 27(3), pages 493-512, April.
    6. Kalyan Chatterjee & Bhaskar Dutia & Debraj Ray & Kunal Sengupta, 2013. "A Noncooperative Theory of Coalitional Bargaining," World Scientific Book Chapters, in: Bargaining in the Shadow of the Market Selected Papers on Bilateral and Multilateral Bargaining, chapter 5, pages 97-111, World Scientific Publishing Co. Pte. Ltd..
    7. Pakes, Ariel & McGuire, Paul, 2001. "Stochastic Algorithms, Symmetric Markov Perfect Equilibrium, and the 'Curse' of Dimensionality," Econometrica, Econometric Society, vol. 69(5), pages 1261-1281, September.
    8. He, Wei & Sun, Yeneng, 2017. "Stationary Markov perfect equilibria in discounted stochastic games," Journal of Economic Theory, Elsevier, vol. 169(C), pages 35-61.
    9. Yang Zhan & Chuangyin Dang, 2018. "A smooth path-following algorithm for market equilibrium under a class of piecewise-smooth concave utilities," Computational Optimization and Applications, Springer, vol. 71(2), pages 381-402, November.
    10. Chuangyin Dang & Yinyu Ye & Zhisu Zhu, 2011. "An interior-point path-following algorithm for computing a Leontief economy equilibrium," Computational Optimization and Applications, Springer, vol. 50(2), pages 223-236, October.
    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. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
    13. Banks, Jeffrey s. & Duggan, John, 2000. "A Bargaining Model of Collective Choice," American Political Science Review, Cambridge University Press, vol. 94(1), pages 73-88, March.
    14. McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142, Elsevier.
    15. Nowak, Andrzej S. & Szajowski, Krzysztof, 1998. "Nonzero-sum Stochastic Games," MPRA Paper 19995, University Library of Munich, Germany, revised 1999.
    16. Wei He & Yeneng Sun, 2013. "Stationary Markov Perfect Equilibria in Discounted Stochastic Games," Papers 1311.1562, arXiv.org, revised Jan 2017.
    17. Maskin, Eric & Tirole, Jean, 2001. "Markov Perfect Equilibrium: I. Observable Actions," Journal of Economic Theory, Elsevier, vol. 100(2), pages 191-219, October.
    18. P. Jean-Jacques Herings & Ronald J.A.P. Peeters, 2001. "symposium articles: A differentiable homotopy to compute Nash equilibria of n -person games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(1), pages 159-185.
    19. Eaves, B. Curtis & Schmedders, Karl, 1999. "General equilibrium models and homotopy methods," Journal of Economic Dynamics and Control, Elsevier, vol. 23(9-10), pages 1249-1279, September.
    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. Chuangyin Dang & P. Jean-Jacques Herings & Peixuan Li, 2022. "An Interior-Point Differentiable Path-Following Method to Compute Stationary Equilibria in Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1403-1418, May.
    2. Peixuan Li & Chuangyin Dang & P. Jean-Jacques Herings, 2024. "Computing perfect stationary equilibria in stochastic games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 78(2), pages 347-387, September.
    3. Cao, Yiyin & Dang, Chuangyin & Xiao, Zhongdong, 2022. "A differentiable path-following method to compute subgame perfect equilibria in stationary strategies in robust stochastic games and its applications," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1032-1050.
    4. Yang Zhan & Chuangyin Dang, 2021. "Computing equilibria for markets with constant returns production technologies," Annals of Operations Research, Springer, vol. 301(1), pages 269-284, June.
    5. Yang Zhan & Peixuan Li & Chuangyin Dang, 2020. "A differentiable path-following algorithm for computing perfect stationary points," Computational Optimization and Applications, Springer, vol. 76(2), pages 571-588, June.
    6. Ron N. Borkovsky & Ulrich Doraszelski & Yaroslav Kryukov, 2010. "A User's Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," Operations Research, INFORMS, vol. 58(4-part-2), pages 1116-1132, August.
    7. P. Jean-Jacques Herings & Harold Houba, 2010. "The Condorcet Paradox Revisited," Tinbergen Institute Discussion Papers 10-026/1, Tinbergen Institute.
    8. Peixuan Li & Chuangyin Dang, 2020. "An Arbitrary Starting Tracing Procedure for Computing Subgame Perfect Equilibria," Journal of Optimization Theory and Applications, Springer, vol. 186(2), pages 667-687, August.
    9. Doraszelski, Ulrich & Satterthwaite, Mark, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," CEPR Discussion Papers 6212, C.E.P.R. Discussion Papers.
    10. Ulrich Doraszelski & Mark Satterthwaite, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," Levine's Bibliography 321307000000000912, UCLA Department of Economics.
    11. Herings, P. Jean-Jacques & Peeters, Ronald J. A. P., 2004. "Stationary equilibria in stochastic games: structure, selection, and computation," Journal of Economic Theory, Elsevier, vol. 118(1), pages 32-60, September.
    12. Jenkins, Mark & Liu, Paul & Matzkin, Rosa L. & McFadden, Daniel L., 2021. "The browser war — Analysis of Markov Perfect Equilibrium in markets with dynamic demand effects," Journal of Econometrics, Elsevier, vol. 222(1), pages 244-260.
    13. Herings, P. Jean-Jacques & Zhan, Yang, 2021. "The computation of pairwise stable networks," Research Memorandum 004, Maastricht University, Graduate School of Business and Economics (GSBE).
    14. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    15. Cao, Yiyin & Dang, Chuangyin, 2022. "A variant of Harsanyi's tracing procedures to select a perfect equilibrium in normal form games," Games and Economic Behavior, Elsevier, vol. 134(C), pages 127-150.
    16. Light, Bar & Weintraub, Gabriel, 2018. "Mean Field Equilibrium: Uniqueness, Existence, and Comparative Statics," Research Papers 3731, Stanford University, Graduate School of Business.
    17. Jayakumar Subramanian & Amit Sinha & Aditya Mahajan, 2023. "Robustness and Sample Complexity of Model-Based MARL for General-Sum Markov Games," Dynamic Games and Applications, Springer, vol. 13(1), pages 56-88, March.
    18. Doraszelski, Ulrich & Kryukov, Yaroslav & Borkovsky, Ron N., 2008. "A User's Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," CEPR Discussion Papers 6733, C.E.P.R. Discussion Papers.
    19. Yiyin Cao & Chuangyin Dang & Yabin Sun, 2022. "Complementarity Enhanced Nash’s Mappings and Differentiable Homotopy Methods to Select Perfect Equilibria," Journal of Optimization Theory and Applications, Springer, vol. 192(2), pages 533-563, February.
    20. Dang, Chuangyin & Meng, Xiaoxuan & Talman, Dolf, 2015. "An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope," Other publications TiSEM 07b7a0e7-f814-4ec2-a3a7-e, Tilburg University, School of Economics and Management.

    More about this item

    JEL classification:

    • C62 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium
    • 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:unm:umagsb:2020001. 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: Andrea Willems or Leonne Portz (email available below). General contact details of provider: https://edirc.repec.org/data/meteonl.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.