Preference learning along multiple criteria: A game-theoretic perspective

Kush Bhatia, Ashwin Pananjady, Peter L. Bartlett, Anca D. Dragan, Martin J. Wainwright

Abstract

Traditional ranking methods often aggregate multi-dimensional preferences into a single score, potentially losing critical structural information. This paper introduces the Blackwell winner, a game-theoretic solution concept for multi-criteria preference learning. By generalizing the von Neumann winner through Blackwell’s approachability theory, the framework allows for non-linear aggregation across conflicting criteria. We demonstrate that the Blackwell winner can be computed via convex optimization and achieves near-optimal minimax sample complexity. A user study on autonomous driving confirms that the Blackwell winner aligns more closely with human preferences than traditional single-criterion models.

Introduction: Beyond Single-Score Preferences

Choosing between options in complex domains—such as autonomous driving or information retrieval—rarely involves a single dimension of quality. A passenger might value both speed and comfort, yet these goals often conflict. Standard preference learning models typically seek a von Neumann winner: a randomized strategy that beats any other option on average based on a single "overall" preference matrix.

However, the von Neumann winner assumes linearity: if policy A is preferred to B, a mixture of A and B should scale accordingly. In reality, users often prefer a balanced "compromise" (e.g., Policy R) over extremes. This occurs because preferences are inherently multi-criteria. Aggregating these into one score too early obscures the trade-offs necessary to find optimal balances.

Comparison of driving policies A and B alongside preference matrices for overall, comfort, and speed criteria.

The Blackwell Winner Framework

To address these limitations, we propose decomposing preferences into $k$ distinct criteria. The Blackwell winner is defined by two components:

  1. Target Sets ($S$): Designers define a set of acceptable performance vectors across all criteria (e.g., minimum satisfaction levels for both safety and speed).
  2. Minimax Game: The Blackwell winner is the distribution over objects that minimizes the worst-case distance to this target set when compared against any other possible distribution.

Technical Contributions

  • Optimization: We prove that the Blackwell winner is the solution to a convex optimization problem, enabling efficient computation using gradient-based or gradient-free algorithms.
  • Sample Complexity: Using a "plug-in" estimator based on empirical win rates, we show that the learning process achieves a near-optimal minimax sample complexity of $O(d^2k/\epsilon^2)$, where $d$ is the number of objects and $k$ is the number of criteria. This indicates that the complexity scales linearly, not exponentially, with the number of criteria.

Experimental Results and User Study

The framework was validated through a user study involving 50 participants evaluating autonomous driving policies. Users compared five base policies across criteria such as aggressiveness, predictability, and collision risk.

Key findings include:

  • Superior Alignment: The Blackwell winner was preferred over the standard von Neumann winner by 66% of users.
  • Effective Trade-offs: While the von Neumann winner often over-indexed on a single dominant criterion, the Blackwell winner successfully identified policies that were "acceptably good" across all subjective metrics.
  • Predictability of Simple Criteria: Preferences along specific criteria (e.g., "which car is faster?") were found to be more linear and predictable than "overall" preferences, justifying the multi-criteria decomposition.

Conclusion and Future Directions

The Blackwell winner provides a robust framework for navigating the trade-offs inherent in multi-criteria decision-making. By moving away from early aggregation, it captures the nuances of human preference more effectively than traditional game-theoretic winners. Future work will explore automated discovery of optimal target sets and the application of active learning to further reduce sample requirements.

Summary updated

Abstract

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.
BibTeX
@inproceedings{bhatia2020preference,
  author = {Kush Bhatia and Ashwin Pananjady and Peter L. Bartlett and Anca D. Dragan and Martin J. Wainwright},
  title = {{Preference learning along multiple criteria: A game-theoretic perspective}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=uEUVKsJjkBq},
}
Figure