Partial-observation stochastic games, how to win when belief fails

DOI10.1145/2579821MaRDI QIDQ5169972zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Laurent Doyen

Publication date 17 July 2014

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2579821

zbMATH Keywords

stochastic gamesmemory boundspartial-observation gamespositive and almost-sure winningreachability and Büchi objectivesstrategy complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Recommendations

• Partial-observation stochastic games: how to win when belief fails
• A survey of partial-observation stochastic parity games
• Partial-observation stochastic reachability and parity games
• The complexity of partial-observation stochastic parity games with finite-memory strategies
• Solving partial-information stochastic parity games

Cites work

• scientific article; zbMATH DE number 4124989 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1444727 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• A first course on zero-sum repeated games
• A multiparameter analysis of the boundedness problem for vector addition systems
• A survey of partial-observation stochastic parity games
• Abstraction refinement for games with incomplete information
• Algorithms for Omega-Regular Games with Imperfect Information
• Alternating-time temporal logic
• Antichain algorithms for finite automata
• Concurrent reachability games
• Decidable problems for probabilistic automata on infinite words
• Deciding the value 1 problem for probabilistic leaktight automata
• Discrete-time control for rectangular hybrid automata
• Forward analysis for WSTS. II: Complete WSTS
• Hybrid Systems: Computation and Control
• Model checking concurrent programs with nondeterminism and randomization
• On Decision Problems for Probabilistic Büchi Automata
• On the expressiveness and complexity of randomization in finite state monitors
• On the power of imperfect information
• Power of Randomization in Automata on Infinite Strings
• Probabilistic automata
• Probabilistic automata
• Probabilistic automata on finite words: decidable and undecidable problems
• Qualitative Concurrent Stochastic Games with Imperfect Information
• Qualitative analysis of partially-observable Markov decision processes
• Qualitative determinacy and decidability of stochastic games with signals
• Randomness for free
• Recurrence and transience for probabilistic automata
• Recursive Concurrent Stochastic Games
• Repeated games with incomplete information. With the collaboration of Richard E. Stearns
• Solving partial-information stochastic parity games
• Stochastic Games
• Supervisory Control of a Class of Discrete Event Processes
• The Complexity of Markov Decision Processes
• The Effect of Tossing Coins in Omega-Automata
• The complexity of partial-observation parity games
• The complexity of partial-observation stochastic parity games with finite-memory strategies
• The complexity of stochastic games
• The complexity of two-player games of incomplete information
• The covering and boundedness problems for vector addition systems
• The maxmin value of stochastic games with imperfect monitoring
• The value of repeated games with an informed controller
• What is decidable about partially observable Markov decision processes with omega-regular objectives

Cited in

(26)

• Algorithms for Omega-Regular Games with Imperfect Information
• Solving partial-information stochastic parity games
• Runtime monitors for Markov decision processes
• Stochastic parity games on lossy channel systems
• The frontier of decidability in partially observable recursive games
• Verification and control of partially observable probabilistic real-time systems
• Partial-observation stochastic reachability and parity games
• Verification and control of partially observable probabilistic systems
• A Note on Game Theory and Verification
• How do we remember the past in randomised strategies?
• Randomness for free
• Deciding maxmin reachability in half-blind stochastic games
• Finite transducers and rational transductions
• Insuring against loss of evidence in game-theoretic probability
• The complexity of partial-observation stochastic parity games with finite-memory strategies
• Quantitative verification and strategy synthesis for stochastic games
• HSVI can solve zero-sum partially observable stochastic games
• Randomness for free
• Dicing on the Streett
• Stochastic equilibria under imprecise deviations in terminal-reward concurrent games
• Qualitative determinacy and decidability of stochastic games with signals
• Partial-observation stochastic games: how to win when belief fails
• Algorithms for Omega-Regular Games with Imperfect Information
• Qualitative analysis of concurrent mean-payoff games
• Collaborative models for autonomous systems controller synthesis
• Qualitative Concurrent Stochastic Games with Imperfect Information

This page was built for publication: Partial-observation stochastic games, how to win when belief fails

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