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 (26)

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

This page was built for publication: The Complexity of Solving Stochastic Games on Graphs