An Arbitrary Starting Tracing Procedure for Computing Subgame Perfect Equilibria

Peixuan Li () and Chuangyin Dang ()
Additional contact information
Peixuan Li: City University of Hong Kong
Chuangyin Dang: City University of Hong Kong

Journal of Optimization Theory and Applications, 2020, vol. 186, issue 2, No 14, 667-687

Abstract: Abstract 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.

Keywords: Noncooperative stochastic games; Subgame perfect equilibrium; Linear tracing procedure; Arbitrary starting; 91A06; 91A10; 91A25 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-020-01703-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:186:y:2020:i:2:d:10.1007_s10957-020-01703-z

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-020-01703-z

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().