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.
The Blackwell Winner Framework
To address these limitations, we propose decomposing preferences into $k$ distinct criteria. The Blackwell winner is defined by two components:
- Target Sets ($S$): Designers define a set of acceptable performance vectors across all criteria (e.g., minimum satisfaction levels for both safety and speed).
- 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