TY - JOUR
T1 - An interior-point differentiable path-following method to compute stationary equilibria in stochastic games
AU - Dang, Chuangyin
AU - Herings, P.J.J.
AU - Li, Peixuan
N1 - Funding Information:
Funding: This work was partially supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region Government [GRF: CityU 11304620].
Publisher Copyright:
© 2021 INFORMS.
PY - 2022/5
Y1 - 2022/5
N2 - 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 pathfollowing 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.
AB - 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 pathfollowing 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.
KW - BARGAINING MODEL
KW - DECOMPOSITION
KW - FRAMEWORK
KW - HOMOTOPY
KW - MARKOV EQUILIBRIA
KW - MIXED COMPLEMENTARITY-PROBLEMS
KW - PERFECT EQUILIBRIA
KW - POTENTIAL REDUCTION ALGORITHM
KW - interior-point method
KW - path-following algorithm
KW - stationary strategies
KW - stochastic games
KW - subgame perfect equilibria
UR - https://doi.org/10.1287/ijoc.2021.1139
U2 - 10.1287/ijoc.2021.1139
DO - 10.1287/ijoc.2021.1139
M3 - Article
SN - 1091-9856
VL - 34
SP - 1403
EP - 1418
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 3
ER -