Strongly subexponential algorithms for Simple Stochastic Games,
Parity Games, Mean Payoff Games and Discounted Payoff Games
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.