Abstract: 
We consider 2player 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 inde pendently 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 almostsure and limitsure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respec tively. In general the almostsure and limitsure winning strategies require both infinitememory as well as infiniteprecision (to describe probabilities). We study the boundedrationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to boundedresource strategies. In terms of precision, strategies can be deterministic, uniform, finiteprecision or infinite precision; and in terms of memory, strategies can be memoryless, finitememory or infinitememory. 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 finiteprecision infinitememory strategies, and infiniteprecision memoryless strategies are as power ful as infiniteprecision finitememory 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 turnbased 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 turnbased games.
