Stochastic Games with Bounded Treewidth

Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP but the existence of polynomial-time algorithm is a major open question, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a gamewith n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O((tn^2 log D)^(t log n)). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth. The main result was published in SODA'23. Contributed talk given by Jakub Svoboda

Authors

• Jakub Svoboda Institute of Science and Technology Austria

Keywords

No keywords are indexed for this paper.