文章基本信息

标题：Games with Delays - A Frankenstein Approach
本地全文：下载
作者：Dietmar Berwanger ; Marie van den Bogaard
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：45
页码：307-319
DOI：10.4230/LIPIcs.FSTTCS.2015.307
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We investigate infinite games on finite graphs where the information flow is perturbed by non- deterministic signalling delays. It is known that such perturbations make synthesis problems virtually unsolvable, in the general case. On the classical model where signals are attached to states, tractable cases are rare and difficult to identify. In this paper, we propose a model where signals are detached from control states, and we identify a subclass on which equilibrium outcomes can be preserved, even if signals are delivered with a delay that is finitely bounded. To offset the perturbation, our solution procedure combines responses from a collection of virtual plays following an equilibrium strategy in the instant- signalling game to synthesise, in a Dr. Frankenstein manner, an equivalent equilibrium strategy for the delayed-signalling game.
关键词：infinite games on graphs; imperfect information; delayed monitoring; distributed synthesis