Tolerant Strategies in Infinite Games

Speaker  Christof Löding
Title Tolerant Strategies in Infinite Games
When 29.01.2009
Where Lecture Room Informatik 11
Abstract We consider two-player games of infinite duration played on finite graphs. As usual, the winning condition specifies the winning plays for the first player by means of the set of vertices that is visited infinitely often (e.g., Büchi, Muller, or parity conditions). Besides this standard winning condition, we consider a ‘tolerance’ condition for the first player. The goal is compute winning strategies for the first player that are not too restrictive, in the sense that the second player always has the possibility to move such that the resulting play satisfies the tolerance condition. We analyze the complexity for computing such strategies and the memory required for realizing them.
Slides download