IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i3p1403-1418.html
   My bibliography  Save this article

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

Author

Listed:
  • Chuangyin Dang

    (Department of Systems Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong)

  • P. Jean-Jacques Herings

    (Department of Economics, Maastricht University, 6200 MD Maastricht, Netherlands)

  • Peixuan Li

    (Department of Systems Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong)

Abstract

The subgame perfect equilibrium in stationary strategies (SSPE) is the most important solution concept in applications of stochastic games, making it imperative to develop efficient methods to compute an SSPE. For this purpose, this paper develops an interior-point differentiable path-following method (IPM), which establishes a connection between an artificial logarithmic barrier game and the stochastic game of interest by adding a homotopy variable. IPM brings several advantages over the existing methods for stochastic games. On the one hand, IPM provides a bridge between differentiable path-following methods and interior-point methods and remedies several issues of an existing homotopy method called the stochastic linear tracing procedure (SLTP). First, the starting stationary strategy profile can be arbitrarily chosen. Second, IPM does not need switching between different systems of equations. Third, the use of a perturbation term makes IPM applicable to all stochastic games rather than generic games only. Moreover, a well-chosen transformation of variables reduces the number of equations and variables by roughly one half. Numerical results show that the proposed method is more than three times as efficient as SLTP. On the other hand, the stochastic game can be reformulated as a mixed complementarity problem and solved by the PATH solver. We employ the proposed IPM and the PATH solver to compute SSPEs. Numerical results evince that for some stochastic games the PATH solver may fail to find an SSPE, whereas IPM is successful in doing so for all stochastic games, which confirms the reliability and stability of the proposed method. Summary of Contribution: This paper incorporates the interior-point methods into a differentiable path-following method for computing stationary equilibria for stochastic games. This novel method brings excellent computational advantages and remedies several issues with the existing methods for stochastic games. We prove the global convergence of the proposed method and employ this method to solve numerous randomly generated stochastic games with different scales. Numerical results further confirm the high efficiency, stability, and universality of this method for stochastic games.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1403-1418
    DOI: 10.1287/ijoc.2021.1139
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1139
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2021.1139?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. 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, December.
    2. 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.
    3. 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.
    4. Elzen, A. van den & Laan, G. van der & Talman, A.J.J., 1989. "An adjustment process for an exchange economy with linear production technologies," Serie Research Memoranda 0082, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    5. Banks, Jeffrey S. & Duggan, John, 2006. "A General Bargaining Model of Legislative Policy-making," Quarterly Journal of Political Science, now publishers, vol. 1(1), pages 49-85, January.
    6. Egging, Ruud, 2013. "Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model," European Journal of Operational Research, Elsevier, vol. 226(2), pages 341-353.
    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. Britz, Volker, 2018. "Rent-seeking and surplus destruction in unanimity bargaining," Games and Economic Behavior, Elsevier, vol. 109(C), pages 1-20.
    11. 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..
    12. 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.
    13. 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.
    14. Frederic Murphy & Axel Pierru & Yves Smeers, 2016. "A Tutorial on Building Policy Models as Mixed-Complementarity Problems," Interfaces, INFORMS, vol. 46(6), pages 465-481, December.
    15. 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.
    16. Todd S. Munson & Francisco Facchinei & Michael C. Ferris & Andreas Fischer & Christian Kanzow, 2001. "The Semismooth Algorithm for Large Scale Complementarity Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 294-311, November.
    17. 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.
    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.
    20. Tava Lennon Olsen & Rodney P. Parker, 2014. "On Markov Equilibria in Dynamic Inventory Competition," Operations Research, INFORMS, vol. 62(2), pages 332-344, April.
    21. Eibelshäuser, Steffen & Poensgen, David, 2019. "Markov Quantal Response Equilibrium and a Homotopy Method for Computing and Selecting Markov Perfect Equilibria of Dynamic Stochastic Games," VfS Annual Conference 2019 (Leipzig): 30 Years after the Fall of the Berlin Wall - Democracy and Market Economy 203603, Verein für Socialpolitik / German Economic Association.
    22. Govindan, Srihari & Wilson, Robert, 2009. "Global Newton Method for stochastic games," Journal of Economic Theory, Elsevier, vol. 144(1), pages 414-421, January.
    23. Eilon Solan, 1998. "Discounted Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 1010-1021, November.
    24. Ioannis Karatzas & Martin Shubik & William D. Sudderth, 1994. "Construction of Stationary Markov Equilibria in a Strategic Market Game," Mathematics of Operations Research, INFORMS, vol. 19(4), pages 975-1006, November.
    25. Uday V. Shanbhag & Gerd Infanger & Peter W. Glynn, 2011. "A Complementarity Framework for Forward Contracting Under Uncertainty," Operations Research, INFORMS, vol. 59(4), pages 810-834, August.
    26. 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.
    27. Wei He & Yeneng Sun, 2013. "Stationary Markov Perfect Equilibria in Discounted Stochastic Games," Papers 1311.1562, arXiv.org, revised Jan 2017.
    28. A. S. Nowak & T. E. S. Raghavan, 1992. "Existence of Stationary Correlated Equilibria with Symmetric Information for Discounted Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 17(3), pages 519-526, August.
    29. Angel E. R. Gutierrez & Sandro R. Mazorche & José Herskovits & Grigori Chapiro, 2017. "An Interior Point Algorithm for Mixed Complementarity Nonlinear Problems," Journal of Optimization Theory and Applications, Springer, vol. 175(2), pages 432-449, November.
    30. Antoon van den Elzen & Gerard van der Laan & Dolf Talman, 1994. "An Adjustment Process for an Economy with Linear Production Technologies," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 341-351, May.
    31. R. Saigal, 1983. "A Homotopy for Solving Large, Sparse and Structured Fixed Point Problems," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 557-578, November.
    32. Kuo-Ling Huang & Sanjay Mehrotra, 2017. "Solution of Monotone Complementarity and General Convex Programming Problems Using a Modified Potential Reduction Interior Point Method," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 36-53, February.
    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. Steffen Eibelshäuser & Victor Klockmann & David Poensgen & Alicia von Schenk, 2023. "The Logarithmic Stochastic Tracing Procedure: A Homotopy Method to Compute Stationary Equilibria of Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1511-1526, November.

    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. 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).
    2. Li, Peixuan & Dang, Chuangyin & Herings, P.J.J., 2023. "Computing Perfect Stationary Equilibria in Stochastic Games," Other publications TiSEM 5b68f5d7-3209-4a1b-924c-6, Tilburg University, School of Economics and Management.
    3. 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).
    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. 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.
    7. Jean-Jacques Herings, P., 2002. "Universally converging adjustment processes--a unifying approach," Journal of Mathematical Economics, Elsevier, vol. 38(3), pages 341-370, November.
    8. P. Jean-Jacques Herings & Harold Houba, 2010. "The Condorcet Paradox Revisited," Tinbergen Institute Discussion Papers 10-026/1, Tinbergen Institute.
    9. Duggan, John, 2017. "Existence of stationary bargaining equilibria," Games and Economic Behavior, Elsevier, vol. 102(C), pages 111-126.
    10. 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.
    11. P. Jean-Jacques Herings & Harold Houba, 2022. "Costless delay in negotiations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 74(1), pages 69-93, July.
    12. Boone, C.A.J.J. & Roijakkers, A.H.W.M. & van Olffen, W., 2002. "Locus of control and study program choice: evidence of personality sorting in educational choice," Research Memorandum 006, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    13. 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.
    14. Jing Fu & Frank Page & Jean-Pierre Zigrand, 2023. "Correction to: Layered Networks, Equilibrium Dynamics, and Stable Coalitions," Dynamic Games and Applications, Springer, vol. 13(2), pages 669-704, June.
    15. Duggan, John & Kalandrakis, Tasos, 2012. "Dynamic legislative policy making," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1653-1688.
    16. 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.
    17. 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.
    18. Steffen Eibelshäuser & Victor Klockmann & David Poensgen & Alicia von Schenk, 2023. "The Logarithmic Stochastic Tracing Procedure: A Homotopy Method to Compute Stationary Equilibria of Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1511-1526, November.
    19. 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.
    20. Zhan, Yang & Dang, Chuangyin, 2021. "Determination of general equilibrium with incomplete markets and default penalties," Journal of Mathematical Economics, Elsevier, vol. 92(C), pages 49-59.

    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:inm:orijoc:v:34:y:2022:i:3:p:1403-1418. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.