–
May 11, 2017
A simple stochastic game is a 2 players zero-sum game played on a
graph. The game consists in moving a pebble on the graph. Players
control the direction taken by the pebble on disjoint sets of
vertices, and the direction of the other vertices is randomly
determined. The goal of the player called MAX (resp. MIN) is to
make the pebble reach a sink with the highest (resp. lowest)
possible value.
Computing the optimal strategies of this game is one of the few
problems in NP and coNP which is not known to be in P. This
problem is also interesting for worst case stochastic
optimization, since Markov decision process with an adversary can
be reduced to it. However, there are instances for which the game
can be solved in polynomial time. This is the case if the graph
is acyclic. In this talk, I will show that several classes of
graph closed to acyclic graphs are tractable. I will also present
algorithmic questions related to similar reachability problem on
rotor graph, which is also known to be in NP and coNP but not in P.
