Simple Stochastic Games with Few Random Vertices Are Easy to Solve

DOI10.1007/978-3-540-78499-9_2MaRDI QIDQ5458347zbMATH OpenOpenAlexFDO

Authors 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) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Recommendations

• Solving Simple Stochastic Games
• New results on simple stochastic games
• Solving Simple Stochastic Games with Few Random Vertices
• Another sub-exponential algorithm for the simple stochastic game
• scientific article; zbMATH DE number 549853

Cites work

• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A subexponential randomized algorithm for the simple stochastic game problem
• Exact solution of linear equations using p-adic expansions
• New algorithms for solving simple stochastic games
• 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
• The complexity of stochastic games

Cited in

(17)

• On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
• General cops and robbers games with randomness
• A non-iterative algorithm for generalized pig games
• scientific article; zbMATH DE number 7559118 (Why is no real title available?)
• Comparison of algorithms for simple stochastic games
• Solving simple stochastic games with few coin toss positions
• Comparison of algorithms for simple stochastic games
• A generic strategy improvement method for simple stochastic games
• New results on simple stochastic games
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• Solving Simple Stochastic Games with Few Random Vertices
• Solving Simple Stochastic Games
• Random bimatrix games are asymptotically easy to solve (a simple proof)
• Strategy improvement for concurrent reachability and turn-based stochastic safety games
• Another sub-exponential algorithm for the simple stochastic game
• A subexponential randomized algorithm for the simple stochastic game problem
• Automatizability and simple stochastic games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458347)