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. |
Event calendar
- Subscribe to the ics feed.
Upcoming Events
- No Events