Klein, Felix and Zimmermann, Martin 
ORCID: 0000-0002-8038-2453
(2015)
What are Strategies in Delay Games? Borel Determinacy for Games with
Lookahead.
.
|
Text
boreldet.pdf - Published version Download (490kB) | Preview |
Abstract
We investigate determinacy of delay games with Borel winning conditions, infinite-duration two-player games in which one player may delay her moves to obtain a lookahead on her opponent's moves. First, we prove determinacy of such games with respect to a fixed evolution of the lookahead. However, strategies in such games may depend on information about the evolution. Thus, we introduce different notions of universal strategies for both players, which are evolution-independent, and determine the exact amount of information a universal strategy needs about the history of a play and the evolution of the lookahead to be winning. In particular, we show that delay games with Borel winning conditions are determined with respect to universal strategies. Finally, we consider decidability problems, e.g., "Does a player have a universal winning strategy for delay games with a given winning condition?", for omega-regular and omega-context-free winning conditions.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | cs.LO, cs.LO, cs.GT |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Jul 2019 12:59 |
| Last Modified: | 19 Jan 2023 00:37 |
| DOI: | 10.4230/LIPIcs.CSL.2015.519 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3049682 |
Dimensions
Dimensions
