Workspaces ---- 337staff act actionwebs actionwebslocal agv apesless apon automotive bcvtb bhc bipeds capecode certafcs cg chess chessadmin chesslocal chessworkshop clotho cosmoi cps cpslab croquet cyphysim dataflow ddosos denso densoeal densosas design dgc3 dgc3exec directors drosonetsim dsc eecs124 eecs149 eecs149lab eecs20 escher gm gsoc handsimdroid hcddes hcssas hilv hybrid hyper iab ieee1588 instructors mast metropolis modelica naomi nes nsferc pa presenters pret pss ptalon ptango ptconf ptdb ptemaf ptesdf ptexternal pthomas ptides ptidesarch ptolemy ptopenmodelica ptpresenters pturing reactable reap researchers scos softdevel softwalls spfsos superb tbd thales triq vw

The Complexity of Quantitative Concurrent Parity Games
Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger

Citation
Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger. "The Complexity of Quantitative Concurrent Parity Games". SODA, 2006.

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 decided in NP and 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 and coNP is the best known bound. While the previous, more restricted NP and 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 e-optimal strategies (which achieve the value of the game within a parameter e > 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 e-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 e-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for e-optimality for coBüchi conditions.

• soda06.ps · application/postscript · 283 kbytes
 Citation formats
• HTML
Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger. <a
href="http://chess.eecs.berkeley.edu/pubs/79.html"
>The Complexity of Quantitative Concurrent Parity
Games</a>, SODA, 2006.
• Plain text
Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger.
"The Complexity of Quantitative Concurrent Parity
Games". SODA, 2006.
• BibTeX
@inproceedings{ChatterjeeAlfaroHenzinger06_ComplexityOfQuantitativeConcurrentParityGames,
author = {Krishnendu Chatterjee and Luca de Alfaro and Tom
Henzinger},
title = {The Complexity of Quantitative Concurrent Parity
Games},
booktitle = {SODA},
year = {2006},
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 decided in NP and 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 and coNP is the
best known bound. While the previous, more
restricted NP and 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 e-optimal strategies
(which achieve the value of the game within a
parameter e > 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 e-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 e-optimal strategies for
concurrent games with parity conditions, by
showing that memoryless strategies suffice for
e-optimality for coBÃ¼chi conditions. },
URL = {http://chess.eecs.berkeley.edu/pubs/79.html}
}


Posted by Krishnendu Chatterjee, PhD on 9 May 2006.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.