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

memory boundspartial-observation gamespositive and almost-sure winningreachability and Büchi objectivesstochastic gamesstrategy 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

• 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
• 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?)
• 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 analysis of partially-observable Markov decision processes
• Qualitative Concurrent Stochastic Games with Imperfect Information
• 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 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 Effect of Tossing Coins in Omega-Automata
• 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)

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

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)