Earlier Version

Bounded rationality in concurrent parity games

K. Chatterjee, Bounded Rationality in Concurrent Parity Games, IST Austria, 2011.

Download
OA 500.40 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
Abstract
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.
Publishing Year
Date Published
2011-07-11
Page
53
ISSN
IST-REx-ID

Cite this

Chatterjee K. Bounded Rationality in Concurrent Parity Games. IST Austria; 2011. doi:10.15479/AT:IST-2011-0008
Chatterjee, K. (2011). Bounded rationality in concurrent parity games. IST Austria. https://doi.org/10.15479/AT:IST-2011-0008
Chatterjee, Krishnendu. Bounded Rationality in Concurrent Parity Games. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0008.
K. Chatterjee, Bounded rationality in concurrent parity games. IST Austria, 2011.
Chatterjee K. 2011. Bounded rationality in concurrent parity games, IST Austria, 53p.
Chatterjee, Krishnendu. Bounded Rationality in Concurrent Parity Games. IST Austria, 2011, doi:10.15479/AT:IST-2011-0008.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:54:22Z


Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar