Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems

Abstract

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 (a strongly subexponential algorithm has only been known for binary SSGs). 

Using known reductions between various games, we achieve the first trongly subexponential solutions for Discounted and Mean Payoff Games. We also give alternative simple proofs for the best known upper bounds for Parity Games and binary SSGs.

To the best of our knowledge, the LP-type framework has been used so far only in order to yield linear or close to linear time algorithms for various problems in computational geometry and location theory. Our approach demonstrates the applicability of the LP-type framework in other fields, and for achieving subexponential algorithms.

This work has been published in Algorithmica, volume 49 (September 2007), pages 37-50