One-counter stochastic games

DOI10.4230/LIPICS.FSTTCS.2010.108MaRDI QIDQ2908841zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Václav Brožek, Kousha Etessami

Publication date 29 August 2012

Full work available at URL https://arxiv.org/abs/1009.5636, http://subs.emis.de/LIPIcs/frontdoor_dc21.html

zbMATH Keywords

limitlong run average rewardMarkov decision processone-counter automatasimple stochastic gamestermination

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Stochastic games, stochastic differential games (91A15)

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 infinity 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 intersection 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 intersection 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.

Recommendations

• Approximating the termination value of one-counter MDPs and stochastic games
• Approximating the termination value of one-counter MDPs and stochastic games
• One-counter Markov decision processes
• Recursive stochastic games with positive rewards
• A Survey of Stochastic Games with Limsup and Liminf Objectives

Cited in

(21)

• The Viterbi algorithm for subsets of stochastic context-free languages
• One-pile Nim games with arbitrarily many random players
• Approximating the termination value of one-counter MDPs and stochastic games
• On decidability and complexity of low-dimensional robot games
• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Analyzing probabilistic pushdown automata
• Computing expected runtimes for constant probability programs
• Qualitative analysis of VASS-induced MDPs
• Runtime analysis of probabilistic programs with unbounded recursion
• Approximating the termination value of one-counter MDPs and stochastic games
• Minimizing expected termination time in one-counter Markov decision processes
• Recursive Stochastic Games with Positive Rewards
• scientific article; zbMATH DE number 2040951 (Why is no real title available?)
• One-counter Markov decision processes
• Probabilistic model checking for energy-utility analysis
• Efficient analysis of probabilistic programs with an unbounded counter
• 1½-Player Stochastic StopWatch Games
• Submixing and shift-invariant stochastic games
• Games with 1-backtracking
• Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs
• Runtime analysis of probabilistic programs with unbounded recursion

This page was built for publication: One-counter stochastic games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908841)