Title: Games with Costs and Delays,
Abstract: 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.