Recursive Concurrent Stochastic Games

DOI10.1007/11787006_28MaRDI QIDQ5901225zbMATH OpenOpenAlexFDO

Authors Kousha Etessami, Mihalis Yannakakis

Publication date 11 September 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.3581

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Stochastic games, stochastic differential games (91A15)

Abstract: We study Recursive Concurrent Stochastic Games (RCSGs), extending our recent analysis of recursive simple stochastic games to a concurrent setting where the two players choose moves simultaneously and independently at each state. For multi-exit games, our earlier work already showed undecidability for basic questions like termination, thus we focus on the important case of single-exit RCSGs (1-RCSGs). We first characterize the value of a 1-RCSG termination game as the least fixed point solution of a system of nonlinear minimax functional equations, and use it to show PSPACE decidability for the quantitative termination problem. We then give a strategy improvement technique, which we use to show that player 1 (maximizer) has epsilon-optimal randomized Stackless & Memoryless (r-SM) strategies for all epsilon > 0, while player 2 (minimizer) has optimal r-SM strategies. Thus, such games are r-SM-determined. These results mirror and generalize in a strong sense the randomized memoryless determinacy results for finite stochastic games, and extend the classic Hoffman-Karp strategy improvement approach from the finite to an infinite state setting. The proofs in our infinite-state setting are very different however, relying on subtle analytic properties of certain power series that arise from studying 1-RCSGs. We show that our upper bounds, even for qualitative (probability 1) termination, can not be improved, even to NP, without a major breakthrough, by giving two reductions: first a P-time reduction from the long-standing square-root sum problem to the quantitative termination decision problem for finite concurrent stochastic games, and then a P-time reduction from the latter problem to the qualitative termination problem for 1-RCSGs.

Recommendations

• Recursive Concurrent Stochastic Games
• Recursive Markov decision processes and recursive stochastic games
• Recursive stochastic games with positive rewards
• Quantitative stochastic parity games
• Automata, Languages and Programming

Cited in

(20)

• Qualitative reachability in stochastic BPA games
• A survey of stochastic -regular games
• scientific article; zbMATH DE number 7561608 (Why is no real title available?)
• Sequential stochastic core of a cooperative stochastic programming game
• Recursive stochastic games with positive rewards
• Equilibria, fixed points, and complexity classes
• Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games
• A formula for the value of a stochastic game
• Graph Games and Reactive Synthesis
• Automata, Languages and Programming
• Multi-player equilibria verification for concurrent stochastic games
• Recursive Concurrent Stochastic Games
• scientific article; zbMATH DE number 7204389 (Why is no real title available?)
• Concurrent reachability games
• Strategy improvement for concurrent reachability and turn-based stochastic safety games
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• Expected termination time in BPA games
• New algorithms for solving zero-sum stochastic games
• Partial-observation stochastic games, how to win when belief fails
• The recursive core for non-superadditive games

This page was built for publication: Recursive Concurrent Stochastic Games

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