Earlier Version

Games with a weak adversary

K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.

Download
OA 328.25 KB

Technical Report | Published | English
Author
Department
Series Title
IST Austria Technical Report
Abstract
We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results.
Publishing Year
Date Published
2014-03-22
Page
18
ISSN
IST-REx-ID

Cite this

Chatterjee K, Doyen L. Games with a Weak Adversary. IST Austria; 2014. doi:10.15479/AT:IST-2014-176-v1-1
Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. IST Austria. https://doi.org/10.15479/AT:IST-2014-176-v1-1
Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-176-v1-1.
K. Chatterjee and L. Doyen, Games with a weak adversary. IST Austria, 2014.
Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.
Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary. IST Austria, 2014, doi:10.15479/AT:IST-2014-176-v1-1.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:53:07Z


Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar