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. Elsevier. DOI: 10.1016/j.ic.2020.104596 ISSN 0890-5401 (In Press)

[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
Status:In Press
Keywords: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:17 Jun 2020 11:10
Last Modified:02 Sep 2020 11:35

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.