Preference Elicitation as Average-Case Sorting

Dominik Peters, Ariel D. ProcacciaAAAI 2021 · DOI

Abstract

Preference elicitation—the process of determining a user's ranking of alternatives—is a fundamental challenge in voting systems and recommendation engines. While standard sorting algorithms require $\Theta(m \log m)$ pairwise comparisons in the worst case, real-world scenarios often provide probabilistic priors about user preferences. This paper introduces distribution-aware sorting algorithms that leverage these priors to reduce query complexity. By utilizing models like Mallows and Plackett–Luce, the proposed methods achieve $O(m)$ expected query complexity, matching information-theoretic lower bounds and significantly outperforming uninformed baselines on real-world datasets.

Introduction

In many applications, we need to elicit a complete ranking of $m$ alternatives from a user. The most reliable method is through pairwise comparison queries (e.g., "Do you prefer A or B?"). From a computer science perspective, this is a sorting problem. However, the classic $\Theta(m \log m)$ lower bound assumes no prior knowledge. In practice, we often have access to historical data or predictive models that provide a distribution over possible rankings. This research explores whether such distributions can be used to minimize the number of questions asked.

Distribution-Aware Sorting

The core contribution is the Distribution-Aware Insertion Sort. Unlike standard insertion sort, which uses binary search to find the correct position for a new item, this algorithm uses a "biased" binary search.

  1. Biased Binary Search: Given a prior distribution $D$, the algorithm calculates the probability of an item belonging in each possible position within the already-sorted list. It then performs a binary search biased toward the high-probability regions.
  2. Entropy Bounds: The authors prove that for a ranking drawn from $D$, the expected number of queries is bounded by $H(D) + 2(m-1)$, where $H(D)$ is the Shannon entropy of the distribution.
  3. Model Integration: The approach is tailored for common preference models like the Mallows model, where insertion probabilities have a closed-form solution, and the Plackett–Luce model, which leverages Luce’s choice axiom for conditional probability calculations.

Key Insights: Scaling and Robustness

A critical insight is that for many common preference models, the entropy scales linearly with the number of alternatives ($O(m)$). This allows for a transition from logarithmic-factor overhead to linear scaling.

Figure 2: Number of queries as a function of the dispersion parameter $\phi$ for different numbers of alternatives $m$.

As shown in Figure 2, the number of queries increases as the dispersion parameter $\phi$ approaches 1 (representing the uniform "Impartial Culture" distribution). However, for structured preferences ($\phi < 1$), the scaling remains efficient. Furthermore, even in diverse populations modeled as mixtures of $k$ distributions, the query complexity only increases by a factor of $\log k$, demonstrating the robustness of the approach.

Experimental Results

The algorithms were evaluated on real-world datasets from PrefLib (e.g., election data, sports rankings) and the Jester joke dataset.

Figure 3: Relative number of queries required by Mallows and Plackett–Luce models compared to the uninformed Impartial Culture baseline (100%) across various real-world datasets.

As illustrated in Figure 3, the distribution-aware approach consistently reduces the elicitation effort. On average, the method saved 10.1% of queries compared to standard sorting. In specific datasets like Burlington ‘09, the savings exceeded 25%. These results confirm that even imperfect priors derived from real-world data can significantly streamline the elicitation process.

Discussion and Future Work

The proposed framework has significant implications for "virtual democracy," where AI agents represent human voters. By allowing humans to efficiently verify or correct AI-predicted rankings, the system maintains democratic legitimacy with minimal user burden.

However, challenges remain. The computational cost of calculating exact probabilities for some models can be high. Additionally, there is a potential for "anchoring bias," where users might uncritically accept a model's suggestions to save effort. Future research will focus on optimizing computational performance and conducting human-subject studies to evaluate the psychological impact of biased elicitation interfaces.

Summary updated

BibTeX
@inproceedings{peters2021preference,
  author = {Dominik Peters and Ariel D. Procaccia},
  title = {{Preference Elicitation as Average-Case Sorting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16709},
}
Figure