Marcin Jurdzi{\'n}ski
``Deciding the Winner in Parity Games is in UP and co-UP''

Abstract:

We observe that the problem of deciding the winner in mean payoff
games is in UP and co-UP.   
We also show a simple reduction from parity games to mean payoff
games. 
From this it follows that deciding the winner in parity games and 
the modal mu-calculus model checking are in UP and co-UP.