Preference learning along multiple criteria: A game-theoretic perspective

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

Introduction

When designing AI systems that align with human values, we often ask humans to choose between two options—such as two different routes for a self-driving car—and aggregate those choices into a single ranking. A common gold standard in game theory for this aggregation is the von Neumann winner: a strategy (or a randomized mix of strategies) guaranteed to beat or tie any other single option on average.

However, this paper identifies a critical flaw in relying solely on the von Neumann winner: it assumes linearity. It assumes that if a user prefers option A over B, a randomized 50/50 mix of A and B can never be strictly better than both. In the real world, human decision-making is multi-criteria and highly non-linear. Option A might be incredibly fast but terrifyingly aggressive, while option B might be safe but agonizingly slow. A randomized mix might provide a "best of both worlds" balance that users actually prefer over either extreme. To address this, the authors introduce the Blackwell winner, a novel game-theoretic framework for learning human preferences across multiple conflicting criteria.

The Problem: The Limits of Linearity

The core challenge lies in defining and computing a "winner" when preferences are multi-criteria and the way humans aggregate those criteria is unknown. Traditional models force a single "expected utility" assumption, which often fails to capture human nuance.

Comparison of two driving policies and their preference matrices across conflicting criteria.

Consider a scenario where an autonomous vehicle must choose between two driving policies. As illustrated above, Policy A might be heavily preferred for comfort, while Policy B is preferred for speed. When forced to give an "overall" preference, a standard linear model might simply average these out, missing the fact that a user might actually prefer a dynamic combination of both behaviors depending on the context. By allowing for non-linear aggregation, a model can discover that a mix of behaviors is superior to any single "pure" behavior.

Methods: Introducing the Blackwell Winner

To solve this, the researchers draw inspiration from Blackwell’s approachability, a concept from game theory designed for games with vector-valued payoffs (where outcomes are scored across multiple criteria rather than a single scalar number).

  1. The Target Set: Instead of looking for a single winning score, the framework defines a target set ($S$) of acceptable score vectors (e.g., "at least 40% safe AND 30% fast"). This target set acts as a flexible prior, allowing designers to specify non-negotiable baselines (like safety) without needing to know the exact mathematical weight a human places on safety versus speed.
  2. The Blackwell Winner: The Blackwell winner is defined as the distribution over options that minimizes the worst-case distance to this target set.
  3. Convex Optimization: A major theoretical contribution of the paper is proving that finding this winner is not just a conceptual exercise. It can be formulated as a convex optimization problem. Because the objective function is both convex and Lipschitz continuous, it can be solved efficiently using standard first-order algorithmic tools like gradient descent.
  4. Statistical Learning: The authors propose a "plug-in" estimator to learn these preferences from noisy, real-world data (like survey responses). They prove that the sample complexity scales predictably with the number of objects ($d$) and criteria ($k$), achieving minimax optimality at $O(d^2k)$.

Experimental Validation: Autonomous Driving

The authors validated their framework using a custom-built autonomous driving user study. They recruited 50 subjects for an initial preference-gathering phase, followed by 41 subjects for evaluation. Users compared five different driving policies in a simulated environment (featuring empty roads, obstacle courses, and traffic) based on five subjective criteria: Aggressiveness, Predictability, Speed, Conservativeness, and Collision Risk.

Key Results

  • Superior Performance: The Blackwell winner (a randomized policy) significantly outperformed the standard von Neumann winner. Specifically, 66% of users preferred the Blackwell winner over the deterministic policy that was the "overall" favorite ($p < 0.03$).
  • True Generalization: The framework is a strict generalization of existing theory. If you reduce the problem to a single criterion, the Blackwell winner mathematically collapses back into the classic von Neumann winner.

Limitations and Future Work

While the framework is powerful, it requires the designer to manually choose the target set $S$. Automating the choice of a "good" target set remains an open and important question. Additionally, this study focused on passive learning from a fixed set of comparisons. Future work could explore active learning, where the AI strategically chooses which pairs to show a human to learn the Blackwell winner even faster. Finally, while the $O(d^2k)$ scaling is standard for pairwise comparisons, it may become a bottleneck for systems with thousands of items, suggesting a need for future structural assumptions, such as low-rank matrices, to scale to massive recommendation engines.

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