Krishnendu Chatterjee, Luca de Alfaro and Thomas A. Henzinger

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1354
November 2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1354.pdf

We consider two-player infinite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and independently, 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 omega-regular objectives expressed as parity conditions can be computed in NP cap coNP. This result substantially improves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special cases of turn-based deterministic parity games (Emerson-Jutla) and of turn-based stochastic reachability games (Condon), for both of which NP cap coNP is the best known bound.

While the previous, more restricted NP cap coNP results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and epsilon-optimal strategies (which achieve the value of the game within a parameter epsilon > 0) require in general both randomization and infinite memory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. First, we show that there exist epsilon-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. Second, we complete the characterization of the memory requirements for epsilon-optimal strategies for concurrent omega-regular games, by showing that memoryless strategies suffice for epsilon-optimality for coBuchi conditions.

BibTeX citation:

@techreport{Chatterjee:CSD-04-1354,
    Author = {Chatterjee, Krishnendu and de Alfaro, Luca and Henzinger, Thomas A.},
    Title = {The Complexity of Quantitative Concurrent Parity Games},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5722.html},
    Number = {UCB/CSD-04-1354},
    Abstract = {We consider two-player infinite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and independently, 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 omega-regular objectives expressed as parity conditions can be computed in NP <i>cap</i> coNP. This result substantially improves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special cases of turn-based deterministic parity games (Emerson-Jutla) and of turn-based stochastic reachability games (Condon), for both of which NP <i>cap</i> coNP is the best known bound. <p>While the previous, more restricted NP <i>cap</i> coNP results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and epsilon-optimal strategies (which achieve the value of the game within a parameter epsilon > 0) require in general both randomization and infinite memory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. First, we show that there exist epsilon-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. Second, we complete the characterization of the memory requirements for epsilon-optimal strategies for concurrent omega-regular games, by showing that memoryless strategies suffice for epsilon-optimality for coBuchi conditions.}
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu
%A de Alfaro, Luca
%A Henzinger, Thomas A.
%T The Complexity of Quantitative Concurrent Parity Games
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1354
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5722.html
%F Chatterjee:CSD-04-1354