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.2018.36
URN: urn:nbn:de:0030-drops-97037
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9703/
Schewe, Sven ;
Weinert, Alexander ;
Zimmermann, Martin
Parity Games with Weights
Abstract
Quantitative extensions of parity games have recently attracted significant interest. These extensions include parity games with energy and payoff conditions as well as finitary parity games and their generalization to parity games with costs. Finitary parity games enjoy a special status among these extensions, as they offer a native combination of the qualitative and quantitative aspects in infinite games: the quantitative aspect of finitary parity games is a quality measure for the qualitative aspect, as it measures the limit superior of the time it takes to answer an odd color by a larger even one. Finitary parity games have been extended to parity games with costs, where each transition is labelled with a non-negative weight that reflects the costs incurred by taking it. We lift this restriction and consider parity games with costs with arbitrary integer weights. We show that solving such games is in NP cap co-NP, the signature complexity for games of this type. We also show that the protagonist has finite-state winning strategies, and provide tight exponential bounds for the memory he needs to win the game. Naturally, the antagonist may need infinite memory to win. Finally, we present tight bounds on the quality of winning strategies for the protagonist.
BibTeX - Entry
@InProceedings{schewe_et_al:LIPIcs:2018:9703,
author = {Sven Schewe and Alexander Weinert and Martin Zimmermann},
title = {{Parity Games with Weights}},
booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
pages = {36:1--36:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-088-0},
ISSN = {1868-8969},
year = {2018},
volume = {119},
editor = {Dan Ghica and Achim Jung},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9703},
URN = {urn:nbn:de:0030-drops-97037},
doi = {10.4230/LIPIcs.CSL.2018.36},
annote = {Keywords: Infinite Games, Quantitative Games, Parity Games}
}
|
Keywords: |
|
Infinite Games, Quantitative Games, Parity Games |
|
Collection: |
|
27th EACSL Annual Conference on Computer Science Logic (CSL 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
29.08.2018 |
