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. |