Mascle, Corto, Shirmohammadi, Mahsa and Totzke, Patrick 
ORCID: 0000-0001-5274-8190
(2019)
Controlling a Random Population is EXPTIME-hard.
[Internet Publication]
|
Text
1909.06420v1.pdf - Published version Download (465kB) | Preview |
Abstract
Bertrand et al. [1] (LMCS 2019) describe two-player zero-sum games in which one player tries to achieve a reachability objective in $n$ games (on the same finite arena) simultaneously by broadcasting actions, and where the opponent has full control of resolving non-deterministic choices. They show EXPTIME completeness for the question if such games can be won for every number $n$ of games. We consider the almost-sure variant in which the opponent randomizes their actions, and where the player tries to achieve the reachability objective eventually with probability one. The lower bound construction in [1] does not directly carry over to this randomized setting. In this note we show EXPTIME hardness for the almost-sure problem by reduction from Countdown Games.
| Item Type: | Internet Publication |
|---|---|
| Uncontrolled Keywords: | cs.LO, cs.LO, cs.DC |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Jul 2020 10:01 |
| Last Modified: | 18 Jan 2023 23:46 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3093262 |
Share
Share
