Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games

DOI10.1007/978-3-319-06089-7_6MaRDI QIDQ5410636zbMATH OpenOpenAlexFDO

Authors David Auger, Pierre Coucheney, Yann Strozecki

Publication date 16 April 2014

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

Full work available at URL https://arxiv.org/abs/1402.0471

zbMATH Keywords

algorithmic game theoryFPT algorithmsstochastic games

Mathematics Subject Classification ID

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

Abstract: The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the few problems in $NPcapcoNP$ which are not known to be in $P$. However, there are some cases where these games can be easily solved, as for instance when the underlying graph is acyclic. In this work, we try to extend this tractability to several classes of games that can be thought as "almost" acyclic. We give some fixed-parameter tractable or polynomial algorithms in terms of different parameters such as the number of cycles or the size of the minimal feedback vertex set.

Recommendations

• Simplifying Optimal Strategies in Stochastic Games
• Simplifying optimal strategies in \(\limsup\) and \(\liminf\) stochastic games
• Optimal strategies in a class of zero-sum ergodic stochastic games
• Optimal strategies in infinite-state stochastic reachability games
• Characterization and simplification of optimal strategies in positive stochastic games
• scientific article; zbMATH DE number 4106653
• Determining the optimal strategies for zero-sum average stochastic positional games
• scientific article; zbMATH DE number 549853

Cited in

(8)

• Optimal comparison strategies in Ulam's searching game with two errors
• A note on the complexity of determining optimal strategies in games with common payoffs
• A non-iterative algorithm for generalized pig games
• Simplifying Optimal Strategies in Stochastic Games
• Solving simple stochastic games with few random nodes faster using Bland's rule
• OPTIMAL STRATEGY IN “GUESS WHO?”: BEYOND BINARY SEARCH
• Optimistic and topological value iteration for simple stochastic games
• ARRIVAL: recursive framework \& _1-contraction

This page was built for publication: Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games

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