Infinite Games

Doctoral Privatissimum

Many of todays problems in computer science are no longer concerned with programs that transform data and then terminate, but with non-terminating systems which have to interact with a possibly antagonistic environment. Over the course of the last fifty years it turned out to be very fruitful to model and analyze such systems in a game-theoretic framework, which captures the antagonistic and strategic nature of the interaction between the system and its environment.

In this doctoral privatissimum we study graph-based two-player games of infinite duration, which model this interaction. We focus on current research topics like computing optimal strategies (e.g., ones that answer requests as soon as possible or minimize energy-consumption), computing small strategies, and also tradeoffs between these quality measures. Furthermore, we consider a variation of the basic setting in which we allow asynchronous strategies that allow one player to obtain a lookahead on her opponent’s moves, so-called delay games.

The goal of this privatissimum is to learn about the state-of-the-art in infinite games with quantitative winning conditions to be able to discuss questions like “do I need more memory to play optimally?”, “can I play better if I get a lookahead on my opponent’s moves?”, and “can I save memory if I get a lookahead on my opponent’s moves?”.