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

Quantitative Reductions and Vertex-Ranked Infinite Games

Weinert, Alexander (2020) Quantitative Reductions and Vertex-Ranked Infinite Games. Information and Computation, 278, p. 104596. Elsevier. doi: 10.1016/j.ic.2020.104596. ISSN 0890-5401.

[img] PDF - Postprint version (accepted manuscript)

Official URL: https://www.sciencedirect.com/science/article/abs/pii/S0890540120300845


We introduce quantitative reductions, a novel technique for structuring the space of quantitative games and solving them that does not rely on a reduction to qualitative games. We show that such reductions exhibit the same desirable properties as their qualitative counterparts and additionally retain the optimality of solutions. Moreover, we introduce vertex-ranked games as a general-purpose target for quantitative reductions and show how to solve them. In such games, the value of a play is determined only by a qualitative winning condition and a ranking of the vertices. We provide quantitative reductions of quantitative request-response games to vertex-ranked games, thus showing ExpTime-completeness of solving the former games. Moreover, we reduce quantitative Muller games to vertex-ranked games, yielding a new proof of ExpTime-membership of the problem of solving the former games. Furthermore, we exhibit the usefulness and flexibility of vertex-ranked games by showing how to use such games to compute fault-resilient strategies for safety specifications. This work lays the foundation for a general study of fault-resilient strategies for more complex winning conditions.

Item URL in elib:https://elib.dlr.de/134511/
Document Type:Article
Title:Quantitative Reductions and Vertex-Ranked Infinite Games
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Weinert, AlexanderAlexander.Weinert (at) dlr.dehttps://orcid.org/0000-0001-8143-246X
Date:12 June 2020
Journal or Publication Title:Information and Computation
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:Yes
DOI :10.1016/j.ic.2020.104596
Page Range:p. 104596
EditorsEmailEditor's ORCID iD
Orlandini, AndreaItalian National Research Council – CNR, Italy; andrea.orlandini@istc.cnr.itUNSPECIFIED
Zimmermann, Martinmartin.zimmermann@liverpool.ac.ukhttps://orcid.org/0000-0002-8038-2453
Keywords:Spieltheorie, Quantitative Spiele
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Vorhaben SISTEC (old)
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:17 Jun 2020 11:10
Last Modified:31 May 2021 09:51

Repository Staff Only: item control page

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