The complexity of solving stochastic games on graphs
DOI10.1007/978-3-642-10631-6_13zbMATH Open1272.91025OpenAlexW1502195915MaRDI QIDQ3652196FDOQ3652196
Authors: Daniel Andersson, Peter Bro Miltersen 
Publication date: 17 December 2009
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_13
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) 2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)
Cited In (49)
- Model-Free Reinforcement Learning for Stochastic Parity Games
- Tropical spectrahedra
- Title not available (Why is that?)
- Stability in graphs and games
- Solvency Markov decision processes with interest
- On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games
- A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes
- Constant rank two-player games are PPAD-hard
- Stochastic games for distributed players on graphs.
- Optimistic and topological value iteration for simple stochastic games
- Exact algorithms for solving stochastic games
- Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
- A reduction from parity games to simple stochastic games
- Games, complexity classes, and approximation algorithms.
- The complexity of mean payoff games
- Approximation schemes for stochastic mean payoff games with perfect information and few random positions
- Stochastic limit-average games are in EXPTIME
- Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
- The Complexity of Synthesis from Probabilistic Components
- Tropically convex constraint satisfaction
- Towards solving 2-TBSG efficiently
- The complexity of stochastic Müller games
- The operator approach to entropy games
- Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information
- A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
- On the complexity of computational problems associated with simple stochastic games
- The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games
- On the Complexity of Non-reversible Betting Games on Many-Valued Events
- Constraint satisfaction problems over numeric domains
- Quantitative verification and strategy synthesis for stochastic games
- Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
- Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
- Strategy Improvement for Stochastic Rabin and Streett Games
- Games through Nested Fixpoints
- Title not available (Why is that?)
- Value iteration for simple stochastic games: stopping criterion and learning algorithm
- Title not available (Why is that?)
- Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs
- Stochastic games
- A convex programming-based algorithm for mean payoff stochastic games with perfect information
- On canonical forms for zero-sum stochastic mean payoff games
- Complexity of path discovery game problems
- A Survey of Stochastic Games with Limsup and Liminf Objectives
- Stochastic games on a graph
- The complexity of mean payoff games on graphs
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- Automatizability and simple stochastic games
- Strategy recovery for stochastic mean payoff games
- On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
This page was built for publication: The complexity of solving stochastic games on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652196)
