Games with Costs and Delays

Zimmermann, Martin ORCID: 0000-0002-8038-2453
(2017) Games with Costs and Delays. In: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017-6-20 - 2017-6-23.

[img] Text
costanddelay.pdf - Author Accepted Manuscript

Download (685kB) | Preview


We demonstrate the usefulness of adding delay to infinite games with quantitative winning conditions. In a delay game, one of the players may delay her moves to obtain a lookahead on her opponent's moves. We show that determining the winner of delay games with winning conditions given by parity automata with costs is EXPTIME-complete and that exponential bounded lookahead is both sufficient and in general necessary. Thus, although the parity condition with costs is a quantitative extension of the parity condition, our results show that adding costs does not increase the complexity of delay games with parity conditions. Furthermore, we study a new phenomenon that appears in quantitative delay games: lookahead can be traded for the quality of winning strategies and vice versa. We determine the extent of this tradeoff. In particular, even the smallest lookahead allows to improve the quality of an optimal strategy from the worst possible value to almost the smallest possible one. Thus, the benefit of introducing lookahead is twofold: not only does it allow the delaying player to win games she would lose without, but lookahead also allows her to improve the quality of her winning strategies in games she wins even without lookahead.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: cs.GT, cs.GT, cs.FL
Depositing User: Symplectic Admin
Date Deposited: 15 Jul 2019 13:11
Last Modified: 19 Jan 2023 00:37
DOI: 10.1109/lics.2017.8005125
Related URLs: