Abstract: 
We study twoplayer concurrent games on finitestate graphs played for an infinite number of rounds, where 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. The objectives are ω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, respectively. In general the almostsure and limitsure winning strategies require both infinitememory as well as infiniteprecision (to describe probabilities). While the qualitative analysis problem for concurrent parity games with infinitememory, infiniteprecision randomized strategies was studied before, 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 infiniteprecision; 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 powerful as infiniteprecision finitememory strategies. We show that the winning sets can be computed in (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. Our symbolic algorithms are based on a characterization of the winning sets as μcalculus formulas, however, our μcalculus formulas are crucially different from the ones for concurrent parity games (without bounded rationality); and our memoryless witness strategy constructions are significantly different from the infinitememory witness strategy constructions for concurrent parity games.
