One-Counter Stochastic Games

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš BROŽEK Václav ETESSAMI Kousha

Year of publication 2010
Type Article in Proceedings
Conference IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
MU Faculty or unit

Faculty of Informatics

Citation
Web
Field Informatics
Keywords one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward
Description We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on transition graphs of classic one-counter automata. We study primarily the termination objective, where one player has to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives. We show that the qualitative termination problem for OC-SSGs is both in NP and coNP, and in P-time for 1-player OC-SSGs. Moreover, we show that quantitative limit problems for OC-SSGs are both in NP and coNP, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.