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.CSL.2016.31
URN: urn:nbn:de:0030-drops-65714
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6571/
Go to the corresponding LIPIcs Volume Portal

Weinert, Alexander ; Zimmermann, Martin

Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs

pdf-format:
LIPIcs-CSL-2016-31.pdf (0.5 MB)

Abstract

The winning condition of a parity game with costs requires an arbitrary, but fixed bound on the distance between occurrences of odd colors and the next occurrence of a larger even one. Such games quantitatively extend parity games while retaining most of their attractive properties, i.e, determining the winner is in NP and co-NP and one player has positional winning strategies.

We show that the characteristics of parity games with costs are vastly different when asking for strategies realizing the minimal such bound: the solution problem becomes PSPACE-complete and exponential memory is both necessary in general and always sufficient. Thus, playing parity games with costs optimally is harder than just winning them. Moreover, we show that the tradeoff between the memory size and the realized bound is gradual in general.

BibTeX - Entry

@InProceedings{weinert_et_al:LIPIcs:2016:6571,
  author =	{Alexander Weinert and Martin Zimmermann},
  title =	{{Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Jean-Marc Talbot and Laurent Regnier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6571},
  URN =		{urn:nbn:de:0030-drops-65714},
  doi =		{10.4230/LIPIcs.CSL.2016.31},
  annote =	{Keywords: Parity Games with Costs, Optimal Strategies, Memory Requirements, Tradeoffs}
}

Keywords: Parity Games with Costs, Optimal Strategies, Memory Requirements, Tradeoffs
Collection: 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Issue Date: 2016
Date of publication: 29.08.2016

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