License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.11
URN: urn:nbn:de:0030-drops-61618
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6161/
Go to the corresponding LIPIcs Volume Portal

Bruyere, Veronique ; Hautem, Quentin ; Raskin, Jean-Francois

On the Complexity of Heterogeneous Multidimensional Games

pdf-format:
LIPIcs-CONCUR-2016-11.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bruyere_et_al:LIPIcs:2016:6161,
  author =	{Veronique Bruyere and Quentin Hautem and Jean-Francois Raskin},
  title =	{{On the Complexity of Heterogeneous Multidimensional Games}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6161},
  URN =		{urn:nbn:de:0030-drops-61618},
  doi =		{10.4230/LIPIcs.CONCUR.2016.11},
  annote =	{Keywords: wo-player zero-sum games played on graphs, quantitative objectives, multidimensional heterogeneous objectives}
}

Keywords: wo-player zero-sum games played on graphs, quantitative objectives, multidimensional heterogeneous objectives
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI