Strategy Machines for Mean Payoff Parity Games and Mean Penalty Parity Games |

Speaker	Marcus Gelderie
Title	Strategy Machines for Mean Payoff Parity Games and Mean Penalty Parity Games
When	05.06.2013, 10:00
Where	Room 5052
Abstract	We study the computational complexity of optimal strategies in mean payoff parity games and mean penalty parity games. To this end we use strategy machines (a Turing machine based representation of a strategy) to implement optimal strategies in both classes of games. Despite the fact that optimal strategies require infinite memory in both classes of games, the memory requirement grows only logarithmically in the number of rounds played so far. We show that in both cases optimal polynomially sized implementations exist which compute the next move in time logarithmic in the number of vertices and the number of rounds played.This implies that optimal strategies are computationally manageable for a long prefix of an infinite play. Perhaps more significantly, it also implies that ε-optimal strategies re computationally very efficient.

Strategy Machines for Mean Payoff Parity Games and Mean Penalty Parity Games