Quantitative Reductions and Infinite Vertex-Ranked Games
Alexander Weinert
We introduce quantitative reductions, a novel technique for solving quantitative games that does not rely on a reduction to qualitative games. We demonstrate that such reductions exhibit the same desirable properties as qualitative ones. In addition, they retain the optimality of solutions. As a general-purpose target for quantitative reductions, we introduce vertex-ranked games, in which the value of a play is determined only by a qualitative winning condition and a ranking of the vertices. Moreover, we demonstrate how to solve such games optimally.
Finally, we provide quantitative reductions to vertex-ranked games for both quantitative request-response and Muller games. Thereby, we show Exptime-completeness of solving the former games, while obtaining a new proof for the membership of solving the latter games in Exptime.