Quantitative reductions and vertex-ranked infinite games

Abstract 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 qualitative ones and that they additionally retain the optimality of solutions. Moreover, we introduce vertex-ranked games as general-purpose targets 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 vertex-ranking. 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 using them to compute fault-resilient strategies for safety specifications. This lays the foundation for a general study of fault-resilient strategies for more complex winning conditions.