The Complexity of Solving Stochastic Games on Graphs

DOI10.1007/978-3-642-10631-6_13zbMath1272.91025OpenAlexW1502195915MaRDI QIDQ3652196

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

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

The Complexity of Synthesis from Probabilistic Components, Tropically convex constraint satisfaction, A potential reduction algorithm for two-person zero-sum mean payoff stochastic games, Quantitative verification and strategy synthesis for stochastic games, Constant Rank Two-Player Games are PPAD-hard, On canonical forms for zero-sum stochastic mean payoff games, Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information, Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, Value iteration for simple stochastic games: stopping criterion and learning algorithm, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, A convex programming-based algorithm for mean payoff stochastic games with perfect information, On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games, Optimistic and topological value iteration for simple stochastic games, Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games, Constraint Satisfaction Problems over Numeric Domains, On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness, Stochastic Games, Tropical spectrahedra, Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes, Automatizability and Simple Stochastic Games, Approximation schemes for stochastic mean payoff games with perfect information and few random positions, Strategy recovery for stochastic mean payoff games, Unnamed Item, Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs, Model-Free Reinforcement Learning for Stochastic Parity Games, The operator approach to entropy games