One-Counter Stochastic Games

D 2010

One-Counter Stochastic Games

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

Basic information

Original name

One-Counter Stochastic Games

Authors

BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), Václav BROŽEK (203 Czech Republic, guarantor, belonging to the institution) and Kousha ETESSAMI (840 United States of America)

Edition

Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), p. 108-119, 12 pp. 2010

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Proceedings paper

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

is not subject to a state or trade secret

References:

URL URL

RIV identification code

RIV/00216224:14330/10:00044742

Organization unit

Faculty of Informatics

ISBN

978-3-939897-23-1

ISSN

UT WoS

000310361000009

Keywords in English

one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward

Abstract

V originále

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.

Links

GAP202/10/1469, research and development project

Name: Formální metody pro analýzu a verifikaci komplexních systémů

Investor: Czech Science Foundation

MSM0021622419, plan (intention)

Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems

1M0545, research and development project

Name: Institut Teoretické Informatiky

Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science

Cite

BRÁZDIL, Tomáš, Václav BROŽEK and Kousha ETESSAMI. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2010, p. 108-119. ISBN 978-3-939897-23-1.

@inproceedings{897695,
   author = {Brázdil, Tomáš and Brožek, Václav and Etessami, Kousha},
   address = {Dagstuhl, Germany},
   booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
   keywords = {one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-939897-23-1},
   pages = {108-119},
   publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
   title = {One-Counter Stochastic Games},
   url = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.108},
   year = {2010}
}

TY  - CONF
ID  - 897695
AU  - Brázdil, Tomáš - Brožek, Václav - Etessami, Kousha
PY  - 2010
TI  - One-Counter Stochastic Games
PB  - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY  - Dagstuhl, Germany
SN  - 9783939897231
KW  - one-counter automata
KW  - simple stochastic games
KW  - Markov decision process
KW  - termination
KW  - long run average reward
UR  - http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.108
N2  - 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.
ER  -

BRÁZDIL, Tomáš, Václav BROŽEK and Kousha ETESSAMI. One-Counter Stochastic Games. In \textit{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2010, p.~108-119. ISBN~978-3-939897-23-1.

Přehled o publikaci