Rahul Savani
University of Warwick
Abstract:
The talk will describe the closely related mean-payoff and parity games, which are both two-player zero-sum games played on graphs. They have applications in theoretical computer science, for example, in logic and verification. The existence of polynomial time algorithms for the solution of these games is a major open problem. The talk will describe strategy improvement algorithms for the games; for mean-payoff games the algorithm is an extension of policy iteration for Markov decision processes with average rewards, and for parity games, the discrete strategy improvement algorithm of Voege and Jurdzinksi (2000). For these algorithms, each improvement step takes time polynomial in the size of the game. So far, no examples are known that require more than a linear number of strategy improvement steps. Finally, extensions to stochastic mean-payoff and parity games will be discussed.