On the complexity of computational problems associated with simple stochastic games

DOI10.1007/3-540-61332-3_165MaRDI QIDQ6184676zbMATH OpenOpenAlexFDO

Authors Akio Yanbe, Kouichi Sakurai

Publication date 29 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61332-3_165

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15)

Recommendations

• The complexity of stochastic games
• On strategy improvement algorithms for simple stochastic games
• On strategy improvement algorithms for simple stochastic games
• scientific article; zbMATH DE number 549853
• The complexity of solving stochastic games on graphs

Cites work

• N by N Checkers is Exptime Complete
• A Combinatorial Problem Which Is Complete in Polynomial Space
• A Monte-Carlo Algorithm for Estimating the Permanent
• A note on the graph isomorphism counting problem
• A short certificate of the number of universal optimal strategies for stopping simple stochastic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Algorithms for discounted stochastic games
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Complete problems for deterministic polynomial time
• Computing a perfect strategy for nxn chess requires time exponential in n
• Discounted Markov games: Generalized policy iteration method
• Discounted Markov games; successive approximation and stopping times
• Every Prime Has a Succinct Certificate
• Games against nature
• GO Is Polynomial-Space Hard
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• Nonlinear programming and stationary strategies in stochastic games
• On Nonterminating Stochastic Games
• On the complexity of some two-person perfect-information games
• Positional strategies for mean payoff games
• Probabilistic game automata
• Stochastic Games
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Markov Decision Processes
• The complexity of short two-person games
• The complexity of stochastic games

This page was built for publication: On the complexity of computational problems associated with simple stochastic games

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