License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.108
URN: urn:nbn:de:0030-drops-28571
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2857/
Brázdil, Tomás ;
Brozek, Václav ;
Etessami, Kousha
One-Counter Stochastic Games
Abstract
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 the transition graph of classic one-counter automata. We study primarily the termination objective, where the goal of one player is 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 that are closely related to some well-studied objectives for stochastic games with rewards. Examples of problems we address include: does player 1 have a
strategy to ensure that the counter eventually hits 0, i.e., terminates, almost surely, regardless of what player 2 does? Or that the $liminf$ (or $limsup$) counter value equals $infty$ with a desired
probability? Or that the long run average reward is $>0$ with desired probability? We show that the qualitative termination problem
for OC-SSGs is in $NP$ intersect $coNP$, and is in P-time for 1-player OC-SSGs, or equivalently for one-counter Markov Decision Processes (OC-MDPs). Moreover, we show that quantitative limit problems for OC-SSGs are in $NP$ intersect $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.
BibTeX - Entry
@InProceedings{brzdil_et_al:LIPIcs:2010:2857,
author = {Tom{\'a}s Br{\'a}zdil and V{\'a}clav Brozek and Kousha Etessami},
title = {{One-Counter Stochastic Games}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {108--119},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-23-1},
ISSN = {1868-8969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2857},
URN = {urn:nbn:de:0030-drops-28571},
doi = {10.4230/LIPIcs.FSTTCS.2010.108},
annote = {Keywords: one-counter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward}
}
|
Keywords: |
|
one-counter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
14.12.2010 |
