Games with a weak adversary
Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121.
Download (ext.)
https://arxiv.org/abs/1404.5453
[Preprint]
Conference Paper
| Published
| English
Author
Chatterjee, KrishnenduISTA ;
Doyen, Laurent
Department
Grant
Series Title
LNCS
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 in general, 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. From our results we derive new complexity results for partial-observation stochastic games.
Publishing Year
Date Published
2014-01-01
Proceedings Title
Lecture Notes in Computer Science
Publisher
Springer
Acknowledgement
This research was partly supported by European project Cassting (FP7-601148).
Technical Report under https://research-explorer.app.ist.ac.at/record/5418
Volume
8573
Issue
Part 2
Page
110 - 121
Conference
ICALP: Automata, Languages and Programming
Conference Location
Copenhagen, Denmark
Conference Date
2014-07-08 – 2014-07-11
IST-REx-ID
Cite this
Chatterjee K, Doyen L. Games with a weak adversary. In: Lecture Notes in Computer Science. Vol 8573. Springer; 2014:110-121. doi:10.1007/978-3-662-43951-7_10
Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. In Lecture Notes in Computer Science (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer. https://doi.org/10.1007/978-3-662-43951-7_10
Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” In Lecture Notes in Computer Science, 8573:110–21. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_10.
K. Chatterjee and L. Doyen, “Games with a weak adversary,” in Lecture Notes in Computer Science, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 110–121.
Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121.
Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” Lecture Notes in Computer Science, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21, doi:10.1007/978-3-662-43951-7_10.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1404.5453