Bounded rationality in concurrent parity games
IST Austria Technical Report
Chatterjee, Krishnendu
ddc:000
We consider 2-player 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 the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms,that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.
IST Austria
2011
info:eu-repo/semantics/technical_report
doc-type:other
text
https://research-explorer.app.ist.ac.at/record/5380
https://research-explorer.app.ist.ac.at/download/5380/5544
Chatterjee K. <i>Bounded Rationality in Concurrent Parity Games</i>. IST Austria; 2011. doi:<a href="https://doi.org/10.15479/AT:IST-2011-0008">10.15479/AT:IST-2011-0008</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.15479/AT:IST-2011-0008
info:eu-repo/semantics/altIdentifier/issn/2664-1690
info:eu-repo/semantics/openAccess