Simple Stochastic Games with Few Random Vertices Are Easy to Solve

DOI10.1007/978-3-540-78499-9_2zbMATH Open1138.91337OpenAlexW1543883954MaRDI QIDQ5458347FDOQ5458347

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

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

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)

Cites Work

• The complexity of stochastic games
• Stochastic Games
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Exact solution of linear equations using p-adic expansions
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• New algorithms for solving simple stochastic games
• Solving Simple Stochastic Games with Few Random Vertices

Cited In (17)

• General cops and robbers games with randomness
• A non-iterative algorithm for generalized pig games
• Title not available (Why is that?)
• Comparison of algorithms for simple stochastic games
• Comparison of algorithms for simple stochastic games
• Solving simple stochastic games with few coin toss positions
• 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
• On discounted approximations of undiscounted stochastic games and Markov decision processes with limited 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)