A reduction from parity games to simple stochastic games

MaRDI QIDQ4964720zbMATH OpenFDO

Authors Krishnendu Chatterjee, Nathanaël Fijalkow

Publication date 3 March 2021

Full work available at URL https://arxiv.org/abs/1106.1232, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GANDALF2011.6

zbMATH Keywords

parity objectivesreachability objectivesstochastic games

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Recommendations

• Reduction of stochastic parity to stochastic mean-payoff games
• Computer Science Logic
• New algorithms for solving simple stochastic games
• The complexity of solving stochastic games on graphs
• Parity game reductions

Cited in

(13)

• Parity game reductions
• Comparison of algorithms for simple stochastic games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Parity to safety in polynomial time for pushdown and collapsible pushdown systems
• Comparison of algorithms for simple stochastic games
• Model-Free Reinforcement Learning for Stochastic Parity Games
• Solving simple stochastic games with few random nodes faster using Bland's rule
• scientific article; zbMATH DE number 5171562 (Why is no real title available?)
• Optimistic and topological value iteration for simple stochastic games
• Correlated equilibria and fairness in concurrent stochastic games
• Deterministic sub-exponential algorithm for discounted-sum games with unary weights
• ARRIVAL: recursive framework \& _1-contraction
• Reduction of stochastic parity to stochastic mean-payoff games

This page was built for publication: A reduction from parity games to simple stochastic games

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