Robustness of structurally equivalent concurrent parity games

DOI10.1007/978-3-642-28729-9_18MaRDI QIDQ2892776zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee

Publication date 22 June 2012

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

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

Mathematics Subject Classification ID

2-person games (91A05) Stochastic games, stochastic differential games (91A15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).

Recommendations

• Qualitative concurrent parity games
• Quantitative stochastic parity games
• Qualitative concurrent parity games: bounded rationality
• Qualitative Concurrent Stochastic Games with Imperfect Information
• Concurrent games with tail objectives

Cited in

(11)

• scientific article; zbMATH DE number 7561655 (Why is no real title available?)
• Timed Parity Games: Complexity and Robustness
• Safe learning for near-optimal scheduling
• The complexity of reachability in parametric Markov decision processes
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• On the Complexity of Reachability in Parametric Markov Decision Processes
• Learning-based mean-payoff optimization in an unknown MDP under omega-regular constraints
• Bidding mechanisms in graph games
• PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP
• Entropic risk for turn-based stochastic games
• PAC statistical model checking of mean payoff in discrete- and continuous-time MDP

This page was built for publication: Robustness of structurally equivalent concurrent parity games

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