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

• 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
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• 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

(19)

• Random bimatrix games are asymptotically easy to solve (a simple proof)
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• A subexponential randomized algorithm for the simple stochastic game problem
• Comparison of algorithms for simple stochastic games
• A non-iterative algorithm for generalized pig games
• On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
• Solving simple stochastic games with few coin toss positions
• Automatizability and simple stochastic games
• Solving Simple Stochastic Games
• Strategy improvement for concurrent reachability and turn-based stochastic safety games
• Solving Simple Stochastic Games with Few Random Vertices
• New results on simple stochastic games
• Comparison of algorithms for simple stochastic games
• Solving simple stochastic games with few random nodes faster using Bland's rule
• A generic strategy improvement method for simple stochastic games
• Another sub-exponential algorithm for the simple stochastic game
• Simple stochastic stopping games: a generator and benchmark library
• Universal complexity bounds based on value iteration for stochastic mean payoff games and entropy games
• General cops and robbers games with randomness

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)