Description
A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as parity objectives, and mean-payoff (or long-run average) objectives. These games lie in NP and coNP. We present a polynomial time Turing reduction of stochastic parity games to stochastic mean-payoff games.