Sven Schewe ; Alexander Weinert ; Martin Zimmermann - Parity Games with Weights

lmcs:5071 - Logical Methods in Computer Science, August 23, 2019, Volume 15, Issue 3 -
Parity Games with Weights

Authors: Sven Schewe ; Alexander Weinert ; Martin Zimmermann

    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 labeled with a nonnegative 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$ coNP, the signature complexity for games of this type. We also show that the protagonist has finite-state winning strategies, and provide tight pseudo-polynomial bounds for the memory he needs to win the game. Naturally, the antagonist may need infinite memory to win. Moreover, we present tight bounds on the quality of winning strategies for the protagonist. Furthermore, we investigate the problem of determining, for a given threshold $b$, whether the protagonist has a strategy of quality at most $b$ and show this problem to be EXPTIME-complete. The protagonist inherits the necessity of exponential memory for implementing such strategies from the special case of finitary parity games.

    Volume: Volume 15, Issue 3
    Published on: August 23, 2019
    Accepted on: August 23, 2019
    Submitted on: January 10, 2019
    Keywords: Computer Science - Computer Science and Game Theory,Computer Science - Logic in Computer Science
    Fundings :
      Source : OpenAIRE Graph
    • Energy Efficient Control; Funder: UK Research and Innovation; Code: EP/M027287/1

    Linked data

    Source : ScholeXplorer IsPartOf DOI 10.4230/lipics.csl.2018
    • 10.4230/lipics.csl.2018
    LIPIcs, Volume 119, CSL'18, Complete Volume
    Ghica, Dan ; Jung, Achim ;

    2 Documents citing this article


    Consultation statistics

    This page has been seen 589 times.
    This article's PDF has been downloaded 210 times.