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 ω-regular objectives expressed as parity conditions can be decided in NP ∩ 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 case of turn-based stochastic reachability games, for which NP ∩ coNP is the best known bound.While the previous, more restricted NP ∩ 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 ε-optimal strategies (which achieve the value of the game within a parameter ε > 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 ε-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 ε-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for ε-optimality for coBüchi conditions.
Index Terms
- The complexity of quantitative concurrent parity games
Recommendations
Qualitative concurrent parity games
We consider two-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 ...
Quantitative stochastic parity games
SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithmsWe study perfect-information stochastic parity games. These are two-player nonterminating games which are played on a graph with turn-based probabilistic transitions. A play results in an infinite path and the conflicting goals of the two players are ω-...
Energy parity games
Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the ...
Comments