@inbook{doi:10.1137/1.9781611977554.ch173,
    Abstract = {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 O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.},
    Author = {Chatterjee, Krishnendu and Meggendorfer, Tobias and Saona, Raimundo and Svoboda, Jakub},
    BookTitle = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
    EPrint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch173},
    File = {Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth - 1.9781611977554.ch173 - a.pdf},
    Pages = {4590-4605},
    Title = {Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth},
    URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch173},
    bdsk-url-1 = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch173},
    bdsk-url-2 = {https://doi.org/10.1137/1.9781611977554.ch173},
    date-added = {2023-03-11 23:11:12 +0100},
    date-modified = {2023-03-11 23:11:12 +0100},
    doi = {10.1137/1.9781611977554.ch173}
}

@inbook{doi:10.1137/1.9781611977554.ch173, Abstract = {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 O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.}, Author = {Chatterjee, Krishnendu and Meggendorfer, Tobias and Saona, Raimundo and Svoboda, Jakub}, BookTitle = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, EPrint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch173}, File = {Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth - 1.9781611977554.ch173 - a.pdf}, Pages = {4590-4605}, Title = {Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth}, URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch173}, bdsk-url-1 = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch173}, bdsk-url-2 = {https://doi.org/10.1137/1.9781611977554.ch173}, date-added = {2023-03-11 23:11:12 +0100}, date-modified = {2023-03-11 23:11:12 +0100}, doi = {10.1137/1.9781611977554.ch173} }