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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Quantitative Reductions and Vertex-Ranked Infinite Games


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    2020-06-12



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Optimizing Murty's Ranked Assignment Method

    Miller, M.L. | Online Contents | 1997


    Optimizing Murty's ranked assignment method

    Miller, M.L. / Stone, H.S. / Cox, I.J. | IEEE | 1997


    Pareto Optimality in Infinite Horizon Cooperative Difference Games

    Lin, Yaning / Zhang, Weihai | Springer Verlag | 2022


    Itineraries evaluated and ranked using fuzzy logic

    Wang, Lizhi / Lehoux, Vassilissa / Espinouse, Marie-Laure et al. | Taylor & Francis Verlag | 2022