Infinite games with finite knowledge gaps

DOI10.1016/J.IC.2016.10.009zbMATH Open1371.91020arXiv1411.5820OpenAlexW1890835473WikidataQ110742642 ScholiaQ110742642MaRDI QIDQ528188FDOQ528188

Authors: Dietmar Berwanger, Anup Basil Mathew 

Publication date: 12 May 2017

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Information tracking in games on graphs
• A communication based model for games of imperfect information
• Title not available (Why is that?)
• Church synthesis problem for noisy input

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)