2026-07-24T10:14:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6161 2024-03-06T10:38:28Z ddc:004 open_access

On the Complexity of Heterogeneous Multidimensional Games Bruyere, Veronique Hautem, Quentin Raskin, Jean-Francois wo-player zero-sum games played on graphs quantitative objectives multidimensional heterogeneous objectives 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Veronique Bruyere and Quentin Hautem and Jean-Francois Raskin 2016 Is Part Of LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2016.11 urn:nbn:de:0030-drops-61618 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.11 eng https://creativecommons.org/licenses/by/3.0/legalcode