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

DOI10.1145/2579821zbMATH Open1291.91021OpenAlexW2048183302MaRDI QIDQ5169972FDOQ5169972

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

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

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)

Cites Work

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

Cited In (26)

• 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
• A Note on Game Theory and Verification
• Verification and control of partially observable probabilistic systems
• 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
• The complexity of partial-observation stochastic parity games with finite-memory strategies
• Insuring against loss of evidence in game-theoretic probability
• 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
• Algorithms for Omega-Regular Games with Imperfect Information
• Solving partial-information stochastic parity games

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)