The Logarithmic Stochastic Tracing Procedure: A Homotopy Method to Compute Stationary Equilibria of Stochastic Games

Steffen Eibelshäuser (), Victor Klockmann (), David Poensgen () and Alicia von Schenk ()
Additional contact information
Steffen Eibelshäuser: Goethe University Frankfurt, 60629 Frankfurt am Main, Germany
Victor Klockmann: University of Würzburg, 97070 Würzburg, Germany
David Poensgen: Goethe University Frankfurt, 60629 Frankfurt am Main, Germany
Alicia von Schenk: University of Würzburg, 97070 Würzburg, Germany

INFORMS Journal on Computing, 2023, vol. 35, issue 6, 1511-1526

Abstract: We introduce the logarithmic stochastic tracing procedure, a homotopy method to compute stationary equilibria for finite and discounted stochastic games. We build on the linear stochastic tracing procedure but introduce logarithmic penalty terms as a regularization device, which brings two major improvements. First, the scope of the method is extended: it now has a convergence guarantee for all games of this class rather than just generic ones. Second, by ensuring a smooth and interior solution path, computational performance is increased significantly. A ready-to-use implementation is publicly available. As demonstrated here, its speed compares quite favorably to other available algorithms, and it allows us to solve games of considerable size in reasonable times. Because the method involves the gradual transformation of a prior into equilibrium strategies, it is possible to search the prior space and uncover potentially multiple equilibria and their respective basins of attraction. This also connects the method to established theory of equilibrium selection.

Keywords: stochastic game; tracing; homotopy method; equilibrium computation; equilibrium selection (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0360 (application/pdf)

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:inm:orijoc:v:35:y:2023:i:6:p:1511-1526

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().