Earlier Version

Robustness of structurally equivalent concurrent parity games

K. Chatterjee, Robustness of Structurally Equivalent Concurrent Parity Games, IST Austria, 2011.

Download
OA IST-2011-0006_IST-2011-0006.pdf 336.00 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
Abstract
We consider two-player stochastic games played on a finite state space for an infinite num- ber 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 ω-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 games with 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 func- tion 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).
Publishing Year
Date Published
2011-06-27
Page
18
ISSN
IST-REx-ID

Cite this

Chatterjee K. Robustness of Structurally Equivalent Concurrent Parity Games. IST Austria; 2011. doi:10.15479/AT:IST-2011-0006
Chatterjee, K. (2011). Robustness of structurally equivalent concurrent parity games. IST Austria. https://doi.org/10.15479/AT:IST-2011-0006
Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent Parity Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0006.
K. Chatterjee, Robustness of structurally equivalent concurrent parity games. IST Austria, 2011.
Chatterjee K. 2011. Robustness of structurally equivalent concurrent parity games, IST Austria, 18p.
Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent Parity Games. IST Austria, 2011, doi:10.15479/AT:IST-2011-0006.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
1322b652d6ab07eb5248298a3f91c1cf


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar