Department of Computer Science | Institute of Theoretical Computer Science

We show that the problem of finding optimal strategies for
both players in a simple stochastic game reduces to the generalized
linear complementarity problem (\GLCP) with a $\P$-matrix, a well-studied
problem whose hardness would imply $\NP=\coNP$. This makes the rich
\GLCP\ theory and numerous existing algorithms available for simple
stochastic games. As a special case, we get a reduction from binary
simple stochastic games to the $\P$-matrix linear complementarity
problem (\LCP).