Robustness of structurally equivalent concurrent parity games

K. Chatterjee, in:, Springer, 2012, pp. 270–285.


Conference Paper | Published | English
Department
Series Title
LNCS
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).
Publishing Year
Date Published
2012-03-22
Volume
7213
Page
270 - 285
Conference
FoSSaCS: Foundations of Software Science and Computation Structures
Conference Location
Tallinn, Estonia
Conference Date
2012-03-24 – 2012-04-01
IST-REx-ID

Cite this

Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:10.1007/978-3-642-28729-9_18
Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia: Springer. https://doi.org/10.1007/978-3-642-28729-9_18
Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. https://doi.org/10.1007/978-3-642-28729-9_18.
K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.
Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213. 270–285.
Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent Parity Games. Vol. 7213, Springer, 2012, pp. 270–85, doi:10.1007/978-3-642-28729-9_18.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1107.2009

Search this title in

Google Scholar