A subexponential randomized algorithm for the simple stochastic game problem

DOI10.1006/INCO.1995.1035MaRDI QIDQ1891171zbMATH OpenOpenAlexFDO

Authors Walter Ludwig

Publication date 28 May 1995

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1995.1035

zbMATH Keywords

randomized algorithmstochastic gamesubexponential time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Stochastic games, stochastic differential games (91A15)

Recommendations

• Another sub-exponential algorithm for the simple stochastic game
• New results on simple stochastic games
• scientific article; zbMATH DE number 549853
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• A randomized subexponential algorithm for parity games

Cited in

(42)

• Verifying minimum stable circuit values
• A short certificate of the number of universal optimal strategies for stopping simple stochastic games
• The complexity of mean payoff games on graphs
• On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles.
• A sublinear-time randomized approximation algorithm for matrix games
• Comparison of algorithms for simple stochastic games
• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• A randomized subexponential algorithm for parity games
• Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
• Automatizability and simple stochastic games
• From Parity and Payoff Games to Linear Programming
• Quantitative verification and strategy synthesis for stochastic games
• Solving parity games in big steps
• A Band and Bound Technique for Simple Random Algorithms
• Symmetric strategy improvement
• Solving Simple Stochastic Games
• New results on simple stochastic games
• A survey of stochastic -regular games
• Solving parity games by a reduction to SAT
• The complexity of all-switches strategy improvement
• Comparison of algorithms for simple stochastic games
• Solving simple stochastic games with few random nodes faster using Bland's rule
• A faster deterministic exponential time algorithm for energy games and mean payoff games
• scientific article; zbMATH DE number 7110187 (Why is no real title available?)
• Exact algorithms for solving stochastic games
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Solving Parity Games in Big Steps
• The complexity of mean payoff games
• On the complexity of computational problems associated with simple stochastic games
• On strategy improvement algorithms for simple stochastic games
• Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness
• Another sub-exponential algorithm for the simple stochastic game
• Modal and temporal logics for processes
• Priority promotion with Parysian flair
• An objective improvement approach to solving discounted payoff games
• An objective improvement approach to solving discounted payoff games
• Deterministic sub-exponential algorithm for discounted-sum games with unary weights
• ARRIVAL: recursive framework \& _1-contraction
• On the undecidability of probabilistic planning and related stochastic optimization problems
• Combinatorial structure and randomized subexponential algorithms for infinite games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Unique sink orientations of grids

This page was built for publication: A subexponential randomized algorithm for the simple stochastic game problem

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