Partial-Observation Stochastic Games

DOI10.1145/2579821zbMath1291.91021OpenAlexW2048183302MaRDI QIDQ5169972

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

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

Related Items

Runtime monitors for Markov decision processes, Quantitative verification and strategy synthesis for stochastic games, Verification and Control of Partially Observable Probabilistic Real-Time Systems, Randomness for free, Collaborative models for autonomous systems controller synthesis, Verification and control of partially observable probabilistic systems, Unnamed Item, A Note on Game Theory and Verification, Deciding Maxmin Reachability in Half-Blind Stochastic Games, Finite transducers and rational transductions, Qualitative analysis of concurrent mean-payoff games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of two-player games of incomplete information
• Probabilistic automata
• The complexity of stochastic games
• The covering and boundedness problems for vector addition systems
• The maxmin value of stochastic games with imperfect monitoring
• A multiparameter analysis of the boundedness problem for vector addition systems
• Discrete-time control for rectangular hybrid automata
• A survey of partial-observation stochastic parity games
• Concurrent reachability games
• The Value of Repeated Games with an Informed Controller
• Model checking concurrent programs with nondeterminism and randomization
• Recurrence and Transience for Probabilistic Automata.
• What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives.
• Decidable Problems for Probabilistic Automata on Infinite Words
• Deciding the Value 1 Problem for Probabilistic Leaktight Automata
• Abstraction Refinement for Games with Incomplete Information.
• Forward Analysis for WSTS, Part II: Complete WSTS
• The Effect of Tossing Coins in Omega-Automata
• On the expressiveness and complexity of randomization in finite state monitors
• Alternating-time temporal logic
• Antichain Algorithms for Finite Automata
• Randomness for Free
• Qualitative Analysis of Partially-Observable Markov Decision Processes
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• Qualitative Concurrent Stochastic Games with Imperfect Information
• Supervisory Control of a Class of Discrete Event Processes
• The Complexity of Markov Decision Processes
• Qualitative Determinacy and Decidability of Stochastic Games with Signals
• The Complexity of Partial-Observation Parity Games
• 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
• On Decision Problems for Probabilistic Büchi Automata
• Probabilistic automata
• Stochastic Games
• Power of Randomization in Automata on Infinite Strings
• Hybrid Systems: Computation and Control
• Recursive Concurrent Stochastic Games
• A first course on zero-sum repeated games