ETD

• algorithms for mean-payoff
• algorithms for parity
• computational complexity
• graph games
• mean-payoff games
• parity games

The thesis deals with aspects of the algorithmic complexity of some infinite games, called graph games.
In particular we focus on parity games and mean-payoff games, two important graph games which play an important role in the solution of several interesting computational problems as, for instance, combinatorial linear programming and LP-type problems, scheduling with and/or constraints, formal verification of temporal logics and constraint satisfaction problems.

We begin by proving classical results about a strong form of determinancy for parity and mean-payoff games.
We then introduce the notion of game reduction and we prove various reductions between games, as well as their complexity status in $\text{NP} \cap \text{coNP}$.
We survey the state of the art of upper bounds on the problem of solving parity games and mean-payoff games efficiently, focusing in particular on the recent advances in the solution of parity games and highlighting their similarities.
Finally we give the definition of a new graph game, of intermediate complexity between parity games and mean-payoff games, and prove that it shares important properties with the other graph games.