Brázdil, Tomás ;
Brozek, Václav ;
Etessami, Kousha
OneCounter Stochastic Games
Abstract
We study the computational complexity of basic decision problems for onecounter simple stochastic games (OCSSGs), under various objectives. OCSSGs are 2player turnbased stochastic games played on the transition graph of classic onecounter 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 wellstudied 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 OCSSGs is in $NP$ intersect $coNP$, and is in Ptime for 1player OCSSGs, or equivalently for onecounter Markov Decision Processes (OCMDPs). Moreover, we show that quantitative limit problems for OCSSGs are in $NP$ intersect $coNP$, and are in Ptime for 1player OCMDPs. Both qualitative limit problems and qualitative termination problems for OCSSGs are already at least as hard as Condon's quantitative decision problem for finitestate 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 = {{OneCounter Stochastic Games}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {108119},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897231},
ISSN = {18688969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2857},
URN = {urn:nbn:de:0030drops28571},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.108},
annote = {Keywords: onecounter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward}
}
2010
Keywords: 

onecounter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 