Group:Student Seminar
Title: Some New Results to the Simple Stochastic Games
Speaker: Decheng Dai Tsinghua university
Time: 2010-05-27 16:00-2010-05-27 17:00
Venue: FIT1-222


We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in \tileO(sqrt{ |V_R|! } ) time, where |V_R| is the number of RANDOM vertices and \tileO ignores polynomial terms. This algorithm is the fastest known algorithm when |V_R| = ω(log n) and |VR| = o( sqrt{min |Vmin|, |Vmax|}) and it works for general (non-stopping) simple stochastic games.

Short Bio: