Infinite games with finite knowledge gaps

DOI10.1016/J.IC.2016.10.009MaRDI QIDQ528188zbMATHOpenAlexWikidataFDO

Authors Dietmar Berwanger, Anup Basil Mathew

Publication date 12 May 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.5820

zbMATH Keywords

games on graphscoordinationimperfect informationinfinite gamesdistributed synthesis

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: Infinite games where several players seek to coordinate under imperfect information are deemed to be undecidable, unless the information is hierarchically ordered among the players. We identify a class of games for which joint winning strategies can be constructed effectively without restricting the direction of information flow. Instead, our condition requires that the players attain common knowledge about the actual state of the game over and over again along every play. We show that it is decidable whether a given game satisfies the condition, and prove tight complexity bounds for the strategy synthesis problem under $omega$-regular winning conditions given by parity automata.

Recommendations

• Infinite games on finite sets
• Infinite asymptotic games
• Infinite games with uncertain moves
• Infinite games played on finite graphs
• Equilibria in infinite games of incomplete information
• Infinite-state games with finitary conditions
• Solving Infinite Games in the Baire Space
• Hypothetical knowledge and games with perfect information

Cites work

• scientific article; zbMATH DE number 3876591 (Why is no real title available?)
• scientific article; zbMATH DE number 4154410 (Why is no real title available?)
• scientific article; zbMATH DE number 1234441 (Why is no real title available?)
• scientific article; zbMATH DE number 1048047 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1500666 (Why is no real title available?)
• scientific article; zbMATH DE number 1754607 (Why is no real title available?)
• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• A course in game theory.
• A perfect-information construction for coordination in games
• Agreeing to disagree
• Alternating-time temporal logic
• Automata, logics, and infinite games. A guide to current research
• Consensus game acceptors
• Context-sensitive string languages and recognizable picture languages
• Coordination logic
• Distributed synthesis for acyclic architectures
• Distributed synthesis for well-connected architectures
• Game Quantification on Automatic Structures and Hierarchical Model Checking Games
• Games with recurring certainty
• Hierarchical information patterns and distributed strategy synthesis
• Infinite coordination games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Information tracking in games on graphs
• Knowledge and common knowledge in a distributed environment
• Lower bounds for multiplayer noncooperative games of incomplete information
• Nondeterministic controllers of nondeterministic processes
• On the (High) Undecidability of Distributed Synthesis Problems
• On the synthesis of strategies in infinite games
• Reasoning about infinite computations
• Recognizable picture languages and domino tiling
• Some Results on Tape-Bounded Turing Machines
• Space-bounded reducibility among combinatorial problems
• The Complexity of Decentralized Control of Markov Decision Processes
• The complexity of reasoning about knowledge and time. I: Lower bounds
• The complexity of two-player games of incomplete information

Cited in

(12)

• Infinite games with uncertain moves
• Games with recurring certainty
• Lossy channel games under incomplete information
• Characterizing the decidability of finite state automata team games with communication
• Hierarchical information and the synthesis of distributed strategies
• Information tracking in games on graphs
• Consensus game acceptors
• scientific article; zbMATH DE number 2038773 (Why is no real title available?)
• Hierarchical information patterns and distributed strategy synthesis
• Church synthesis problem for noisy input
• Consensus game acceptors and iterated transductions
• A communication based model for games of imperfect information

This page was built for publication: Infinite games with finite knowledge gaps

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