elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Parity games with weights

Schewe, Sven and Weinert, Alexander and Zimmermann, Martin (2019) Parity games with weights. Logical Methods in Computer Science, 15 (3), 20:1-20:50. Technische Universität Braunschweig. DOI: 10.23638/LMCS-15(3:20)2019 ISSN 1860-5974

[img] PDF - Postprint version (accepted manuscript)
616kB

Official URL: https://lmcs.episciences.org/5705

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 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 and 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.

Item URL in elib:https://elib.dlr.de/131260/
Document Type:Article
Title:Parity games with weights
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Schewe, Svensven.schewe (at) liverpool.ac.ukhttps://orcid.org/0000-0002-9093-9518
Weinert, Alexanderalexander.weinert (at) dlr.dehttps://orcid.org/0000-0001-8143-246X
Zimmermann, Martinmartin.zimmermann (at) liverpool.ac.ukhttps://orcid.org/0000-0002-8038-2453
Date:13 August 2019
Journal or Publication Title:Logical Methods in Computer Science
Refereed publication:Yes
Open Access:Yes
Gold Open Access:Yes
In SCOPUS:Yes
In ISI Web of Science:Yes
Volume:15
DOI :10.23638/LMCS-15(3:20)2019
Page Range:20:1-20:50
Publisher:Technische Universität Braunschweig
ISSN:1860-5974
Status:Published
Keywords:Informatik, Spieltheorie, Quantitative Spiele
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Vorhaben SISTEC
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology
Institut of Simulation and Software Technology > Distributed Systems and Component Software
Deposited By: Weinert, Alexander
Deposited On:28 Nov 2019 12:10
Last Modified:28 Nov 2019 12:10

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.