2017/04/04 by Alexander Weinert, Weinert, Alexander
Computer Science · #Computer Science and Game Theory (cs.GT) #D.2.4 #FOS: Computer and information sciences #Formal Methods in Verification #Software Reliability and Analysis Research #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.1704.00904
openalex publication_date 2017/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 that they 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 and of quantitative Muller games to vertex-ranked games, thus showing EXPTIME-completeness of solving the former two kinds of games. In addition, 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.