2026-07-20T17:19:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3335 2024-03-06T10:34:07Z ddc:004 open_access

A Perfect-Information Construction for Coordination in Games Berwanger, Dietmar Kaiser, Lukasz Puchala, Bernd Distributed Synthesis Games on Graphs Imperfect Information Epistemic Models We present a general construction for eliminating imperfect information from games with several players who coordinate against nature, and to transform them into two-player games with perfect information while preserving winning strategy profiles. The construction yields an infinite game tree with epistemic models associated to nodes. To obtain a more succinct representation, we define an abstraction based on homomorphic equivalence, which we prove to be sound for games with observable winning conditions. The abstraction generates finite game graphs in several relevant cases, and leads to a new semi-decision procedure for multi-player games with imperfect information. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dietmar Berwanger and Lukasz Kaiser and Bernd Puchala 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.387 urn:nbn:de:0030-drops-33354 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.387 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode