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.


    Access

    Download


    Export, share and cite



    Title :

    Quantitative Reductions and Vertex-Ranked Infinite Games


    Contributors:

    Published in:

    Publication date :

    2020-06-12



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    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