Solving Random Parity Games in Polynomial Time

Richard Combes, Mikael Touati

We consider the problem of solving random parity games. We prove that parity games exibit a phase transition threshold above $d_P$, so that when the degree of the graph that define…