Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Publication date | 16/01/2023 |
---|---|
Host publication | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 |
Publisher | Curran Associates, Inc. |
Pages | 4590-4605 |
Number of pages | 16 |
ISBN (electronic) | 9781611977554 |
<mark>Original language</mark> | English |
Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Volume | 2023-January |
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 and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, 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. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time (Equation presented). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.