Strategy Improvement for Parity Games: A combinatorial perspective

Parity games are simple two-player, infinite-move games particularly useful in Computer Science for modelling non-terminating reactive systems and recursive processes.  A longstanding open problem related to these games is whether the winner of a parity game can be decided in polynomial time.  One of the most promising algorithms to date is a strategy improvement algorithm of Voege and Jurdzinski, however no good bounds are known on its running time.

In this talk I will discuss how the problem of finding a winner in a parity game can be reduced to the problem of locally finding a global sink on an acyclic unique sink oriented hypercube.  As a consequence, we can improve (albeit only marginally) the bounds of the strategy improvement algorithm.

This talk is similar to one I presented at the InfoSys seminar in the Computing Laboratory in October.