Simple Stochastic Games with Few Random Vertices Are Easy to Solve

DOI10.1007/978-3-540-78499-9_2zbMath1138.91337OpenAlexW1543883954MaRDI QIDQ5458347

Hugo Gimbert, Florian Horn

Publication date: 11 April 2008

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78499-9_2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15)

Related Items

General cops and robbers games with randomness, Strategy improvement for concurrent reachability and turn-based stochastic safety games, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, Unnamed Item, On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness, Automatizability and Simple Stochastic Games, Approximation schemes for stochastic mean payoff games with perfect information and few random positions, Unnamed Item, A non-iterative algorithm for generalized pig games, Comparison of algorithms for simple stochastic games

Cites Work

• A polynomial-time algorithm, based on Newton's method, for linear programming
• Exact solution of linear equations using p-adic expansions
• The complexity of stochastic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Solving Simple Stochastic Games with Few Random Vertices
• Stochastic Games
• Unnamed Item
• Unnamed Item
• Unnamed Item