文章基本信息

标题：A Perfect-Information Construction for Coordination in Games
本地全文：下载
作者：Dietmar Berwanger ; Lukasz Kaiser ; Bernd Puchala 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：13
页码：387-398
DOI：10.4230/LIPIcs.FSTTCS.2011.387
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Distributed Synthesis; Games on Graphs; Imperfect Information; Epistemic Models