Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth.
AU - Chatterjee, Krishnendu
AU - Meggendorfer, Tobias
AU - Saona, Raimundo
AU - Svoboda, Jakub
PY - 2023/1/16
Y1 - 2023/1/16
N2 - 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.
AB - 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.
U2 - 10.1137/1.9781611977554.ch173
DO - 10.1137/1.9781611977554.ch173
M3 - Conference contribution/Paper
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 4590
EP - 4605
BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PB - Curran Associates, Inc.
ER -