Marcin Jurdzinski
Warwick

Algorithms for solving infinite games on graphs

This talk is a selective survey of algorithms for solving a number of
infinite-path-following games on graphs, such as parity, mean-payoff,
and discounted games.  The games considered are zero-sum,
perfect-information, and non-stochastic.  Several state-of-the-art
algorithms for solving infinite games on graphs are presented, exhibing
disparate algorithmic techniques, such as divide-and-conquer, dynamic
programming/value iteration, local search/strategy improvement, and
mathematical programming, as well as hybrid approaches that dovetail
some of the former.  While the problems of solving infinite games on
graphs are in NP and co-NP, and also in PLS and PPAD, and hence unlikely
to be complete for any of the four complexity classes, no
polynomial-time algorithms are known for solving them.