文章基本信息

标题：On the Complexity of Heterogeneous Multidimensional Games
本地全文：下载
作者：Veronique Bruyere ; Quentin Hautem ; Jean-Francois Raskin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：59
页码：11:1-11:15
DOI：10.4230/LIPIcs.CONCUR.2016.11
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study two-player zero-sum turn-based games played on multidimensional weighted graphs with heterogeneous quantitative objectives. Our objectives are defined starting from the measures Inf, Sup, LimInf, and LimSup of the weights seen along the play, as well as on the window mean-payoff (WMP) measure recently introduced in [Krishnendu,Doyen,Randour,Raskin, Inf. Comput., 2015]. Whereas multidimensional games with Boolean combinations of classical mean-payoff objectives are undecidable [Velner, FOSSACS, 2015], we show that CNF/DNF Boolean combinations for heterogeneous measures taken among {WMP, Inf, Sup, LimInf, LimSup} lead to EXPTIME-completeness with exponential memory strategies for both players. We also identify several interesting fragments with better complexities and memory requirements, and show that some of them are solvable in PTIME.
关键词：wo-player zero-sum games played on graphs; quantitative objectives; multidimensional heterogeneous objectives