Randomized and deterministic algorithms for 2-player turn-based stochastic and non-stochastic games, part I

We describe the fastest known randomized algorithm for solving 2-player 0-sum turn-based stochastic games. The running time of the algorithm is sub-exponential, i. e. , roughly of the form 2^{O(n^{1/2})}, where n is the number of states of the games. The algorithm is based on randomized pivoting rules for the simplex algorithm developed by Kalai (1992) and Matousek, Sharir and Welzl (1992). Various versions of such algorithms were developed by Ludwig (1995), Bj\”{o}rklund and Vorobyov (2005), Halman (2007), with slight improvements by Hansen and Zwick (2015).

Authors

• Uri Zwick

Keywords

No keywords are indexed for this paper.