The Complexity of Quantitative Concurrent Parity Games

We consider two-player innite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and indepen-dently, and stochastic, in that the moves determine a probability distribution for the successor state. The value of a game is the maximal probability with which a player can guarantee the satisfaction of her objective. We show that the values of concurrent games with!-regular objectives expressed as parity conditions can be decided in NP \ coNP. This result substantially im-proves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special case of turn-based stochastic reachability games, for which NP \ coNP is the best known bound. While the previous, more restricted NP \ coNP re-sults for graph games relied on the existence of partic-ularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strate-gies may not exist, and "-optimal strategies (which achieve the value of the game within a parameter "> 0) require in general both randomization and innite mem-ory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main re-sult, yields two results that are interesting on their own. First, we show that there exist "-optimal strategies that in the limit coincide with memoryless strategies; this parallels the celebrated result of Mertens-Neyman for concurrent games with limit-average objectives. Sec-ond, we complete the characterization of the memory re-quirements for "-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suce for "-optimality for coBuchi conditions