Strongly subexponential algorithms for Simple Stochastic Games,

Parity Games, Mean Payoff Games and Discounted Payoff Games

Nir Halman

We show that a Simple Stochastic Game (SSG) can be formulated as an

LP-type problem. Using this formulation, and the known algorithm of

Sharir and Welzl for LP-type problems, we obtain the first strongly

subexponential solution for SSGs.

Using known reductions between various games, we achieve the first

strongly subexponential solutions for Discounted Payoff Games and Mean

Payoff Games. We also give alternative simple proofs for the best known

upper bounds for Parity Games and binary SSGs.