An Arbitrary Starting Tracing Procedure for Computing Subgame Perfect Equilibria

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations


Original languageEnglish
Pages (from-to)667-687
Number of pages21
Journal / PublicationJournal of Optimization Theory and Applications
Issue number2
Online published26 Jun 2020
Publication statusPublished - Aug 2020


The computation of subgame perfect equilibrium in stationary strategies is an important but challenging problem in applications of stochastic games. In 2004, Herings and Peeters developed a homotopy method called stochastic linear tracing procedure to solve this problem. However, the starting point of their method requires to be explicitly calculated. To remedy this issue, we formulate an arbitrary starting linear tracing procedure in this paper. By introducing a homotopy variable ranging from two to zero, an artificial penalty game is developed, whose solutions construct a differentiable path after a well-chosen transformation of variables. The starting point of the path can be arbitrarily chosen, so that there is no need to employ additional algorithms to obtain it. Following the path, one can readily attain the "starting point" of the stochastic tracing procedure coined by Herings and Peeters. Then, as the homotopy variable changes from one to zero, the path essentially resumes to the stochastic tracing procedure. We prove that our method globally converges to a subgame perfect equilibrium in stationary strategies for the stochastic game of interest. Numerical results further illustrate the effectiveness and efficiency of our method.

Research Area(s)

  • Noncooperative stochastic games, Subgame perfect equilibrium, Linear tracing procedure, Arbitrary starting