Preference learning along multiple criteria: A game-theoretic perspective
This work addresses ranking problems in multi-criteria decision-making, such as autonomous driving, by providing a novel theoretical and practical extension, though it is incremental relative to existing game-theoretic methods.
The authors tackled the problem of ranking from ordinal data in multi-criteria settings by generalizing the von Neumann winner concept using Blackwell's approachability, resulting in a framework that allows non-linear preference aggregation and achieves near-optimal minimax sample complexity. In a user study on autonomous driving, the Blackwell winner outperformed the von Neumann winner for overall preferences.
The literature on ranking from ordinal data is vast, and there are several ways to aggregate overall preferences from pairwise comparisons between objects. In particular, it is well known that any Nash equilibrium of the zero sum game induced by the preference matrix defines a natural solution concept (winning distribution over objects) known as a von Neumann winner. Many real-world problems, however, are inevitably multi-criteria, with different pairwise preferences governing the different criteria. In this work, we generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability. Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization. From a theoretical standpoint, we show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem. Furthermore, given random samples of pairwise comparisons, we show that a simple plug-in estimator achieves near-optimal minimax sample complexity. Finally, we showcase the practical utility of our framework in a user study on autonomous driving, where we find that the Blackwell winner outperforms the von Neumann winner for the overall preferences.