The complexity of two-player games of incomplete information
Two-player games of incomplete information have certain portions of positions which are private to each player and cannot be viewed by the opponent. Asymptotically optimal decision algorithms for space bounded games are provided. Various games of incomplete information are presented which are shown to be universal in the sense that they are the hardest of all reasonable games of incomplete information. The problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly exponential time. Private alternating Turing machines are defined to be a new type of alternating Turing machines related to games of incomplete information. The space complexity S(n) of these machines is characterized in terms of the complexity of deterministic Turing machines, with time bounds doubly exponential in S(n). Blindfold games are restricted games in that the second player is not allowed to modify the common position. Asymptotically optimal decision algorithms for space bounded blindfold games are provided. Various blindfold games are also shown to have exponential space complete outcome problems and to be universal for reasonable blindfold games. Blind alternating Turing machines are defined to be private alternating Turing machines with restrictions similar to those in blindfold games. The space complexity of these machines is characterized in terms of the complexity of deterministic Turing machines with a single exponential increase in space bounds.
- A Combinatorial Problem Which Is Complete in Polynomial Space
- Alternation
- Decision algorithms for multiplayer noncooperative games of incomplete information
- GO Is Polynomial-Space Hard
- scientific article; zbMATH DE number 3723925 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- On the complexity of some two-person perfect-information games
- On the Computational Complexity of Algorithms
- Provably Difficult Combinatorial Games
- Relationships between nondeterministic and deterministic tape complexities
- Space-bounded reducibility among combinatorial problems
- The polynomial-time hierarchy
- Solitaire automata
- Multi-oracle interactive protocols with constant space verifiers
- Common knowledge and update in finite environments
- Decision algorithms for multiplayer noncooperative games of incomplete information
- Looking at mean payoff through foggy windows
- Compositional and symbolic synthesis of reactive controllers for multi-agent systems
- Latticed-LTL synthesis in the presence of noisy inputs
- Probabilistic game automata
- Polynomial games and determinacy
- Strategy construction for parity games with imperfect information
- Time-aware uniformization of winning strategies
- Knowledge-based strategies for multi-agent teams playing against nature
- Cooperating in video games? Impossible! Undecidability of team multiplayer games
- Indecision and delays are the parents of failure -- taming them algorithmically by synthesizing delay-resilient control
- POMDPs under probabilistic semantics
- Uniform strategies, rational relations and jumping automata
- Compositional construction of most general controllers
- Quantum alternation
- Mean-payoff games with partial observation
- What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
- Observation and distinction: representing information in infinite games
- GIB: Imperfect information in a computationally challenging game
- The complexity of synchronous notions of information flow security
- The complexity of coverage
- Lazy synthesis
- An alternating-time temporal logic with knowledge, perfect recall and past: axiomatisation and model-checking
- A compositional framework for controller synthesis
- Minimum Attention Controller Synthesis for Omega-Regular Objectives
- scientific article; zbMATH DE number 4176870 (Why is no real title available?)
- Strategy Construction for Parity Games with Imperfect Information
- The complexity of Scotland Yard
- Computing Weakest Strategies for Safety Games of Imperfect Information
- Classifying the computational complexity of problems
- Model-checking games for logics of imperfect information
- Connectivity games over dynamic networks
- Symbolic supervisory control of infinite transition systems under partial observation using abstract interpretation
- scientific article; zbMATH DE number 1559566 (Why is no real title available?)
- Games with Symmetric Incomplete Information and Asymmetric Computational Resources
- scientific article; zbMATH DE number 2086402 (Why is no real title available?)
- The complexity of debate checking
- scientific article; zbMATH DE number 7455737 (Why is no real title available?)
- Non-cooperative rational interactive proofs
- Partial-observation stochastic games, how to win when belief fails
- scientific article; zbMATH DE number 7104930 (Why is no real title available?)
- Game-based Synthesis of Distributed Controllers for Sampled Switched Systems
- Infinite games with finite knowledge gaps
- A general notion of uniform strategies
- On Decision Problems for Probabilistic Büchi Automata
- Lower bounds for multiplayer noncooperative games of incomplete information
- BOCoSy: Small but Powerful Symbolic Output-Feedback Control
- Information tracking in games on graphs
- Perspective games
- Robust almost-sure reachability in multi-environment MDPs
- Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games
- Synthesis with privacy against an observer
- Stochastic games with synchronizing objectives
- The complexity of pursuit on a graph
- Perspective games with notifications
- Regular games with imperfect information are not that regular
- A formal approach to attack graphs
- Synthesis with privacy against an observer
- Alternating-time temporal logic
- Stochastic games with synchronization objectives
- The complexity of asynchronous model based testing
- The non-cooperative rational synthesis problem for SPEs and -regular objectives
- Turing machines with access to history
- Computation of equilibria in noncooperative games
- Randomness for free
- Alternating-time stream logic for multi-agent systems
This page was built for publication: The complexity of two-player games of incomplete information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800838)
