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 (10)

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

This page was built for publication: Simple Stochastic Games with Few Random Vertices Are Easy to Solve