×

Solving simple stochastic games. (English) Zbl 1142.91332

Beckmann, Arnold (ed.) et al., Logic and theory of algorithms. 4th conference on computability in Europe, CiE 2008, Athens, Greece, June 15–20, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69405-2/pbk). Lecture Notes in Computer Science 5028, 206-209 (2008).
Summary: We present a new algorithm for solving Simple Stochastic Games (SSGs), which is fixed parameter tractable when parametrized with the number of random vertices. This algorithm is based on an exhaustive search of a special kind of positional optimal strategies, the \(f\)-strategies. The running time is \(\mathcal {O}(|V_{\text R}|!\cdot(\log (|V|)|E| + |p|))\), where \(|V|,\;|V_{\text{R}}|,\;|E|\) and \(|p|\) are respectively the number of vertices, random vertices and edges, and the maximum bit-length of a transition probability. Our algorithm improves existing algorithms for solving SSGs in three aspects. First, our algorithm performs well on SSGs with few random vertices, second it does not rely on linear or quadratic programming, third it applies to all SSGs, not only stopping SSGs.
For the entire collection see [Zbl 1137.68002].

MSC:

91A15 Stochastic games, stochastic differential games
91A05 2-person games
91-08 Computational methods for problems pertaining to game theory, economics, and finance
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Condon, A., The complexity of stochastic games, Information and Computation, 96, 203-224 (1992) · Zbl 0756.90103 · doi:10.1016/0890-5401(92)90048-K
[2] Condon, A.: On algorithms for simple stochastic games. In: Advances in computational complexity theory. DIMACS series in discrete mathematics and theoretical computer science, vol. 13, pp. 51-73 (1993) · Zbl 0808.90141
[3] Derman, C., Finite State Markov Decision Processes (1972), London: Academic Press, London
[4] Dixon, J. D., Exact solution of linear equations using p-adic expansions, Numerische Mathematik, 40, 137-141 (1982) · Zbl 0492.65016 · doi:10.1007/BF01459082
[5] Gimbert, H., Horn, F.: Solving simple stochastic games with few random vertices (2007), http://hal.archives-ouvertes.fr/hal-00195914/fr/ · Zbl 1163.91318
[6] Halman, N., Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, 49, 37-50 (2007) · Zbl 1131.91012 · doi:10.1007/s00453-007-0175-3
[7] Kachiyan, L. G., A polynomial time algorithm for linear programming, Soviet Math. Dokl., 20, 191-194 (1979) · Zbl 0409.90079
[8] Ludwig, W., A subexponential randomized algorithm for the simple stochastic game problem, Information and Computation, 117, 151-155 (1995) · Zbl 0827.90141 · doi:10.1006/inco.1995.1035
[9] Renegar, J., A polynomial-time algorithm, based on newton’s method, for linear programming, Mathematical Programming, 40, 59-93 (1988) · Zbl 0654.90050 · doi:10.1007/BF01580724
[10] Shapley, L. S., Stochastic games, Proceedings of the National Academy of Science USA, 39, 1095-1100 (1953) · Zbl 0051.35805 · doi:10.1073/pnas.39.10.1095
[11] Somla, R., New algorithms for solving simple stochastic games, Electr. Notes Theor. Comput. Sci., 119, 1, 51-65 (2005) · Zbl 1272.91028 · doi:10.1016/j.entcs.2004.07.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.