Metric Distortion with Elicited Pairwise Comparisons

Soroush Ebadian, Daniel Halpern, Evi Micha, Youyong Kong

Abstract

In collective decision-making, obtaining full preference rankings from all participants is often impractical. This paper investigates preference elicitation through limited pairwise comparison queries under the metric distortion framework. We analyze how different levels of adaptivity—both between agents and within a single agent's query sequence—impact the worst-case social cost. Our findings establish a fundamental $m/t$ distortion barrier and provide near-optimal algorithms for various adaptivity constraints, demonstrating that high efficiency can be achieved even with minimal interaction rounds.

Introduction

Aggregating individual preferences to reach a social consensus is a cornerstone of digital democracy and Reinforcement Learning from Human Feedback (RLHF). However, asking every user to rank $m$ candidates is cognitively demanding. Instead, systems often use "this or that" queries. The challenge lies in selecting these queries to minimize distortion: the ratio between the social cost of the chosen outcome and the true optimal outcome in an underlying metric space.

Dimensions of Adaptivity

The efficiency of preference elicitation depends heavily on how queries are structured. The authors categorize strategies based on two types of adaptivity:

  1. Inter-agent adaptivity: Whether queries for one user can depend on previous users' responses.
  2. Intra-agent adaptivity: Whether a user's subsequent questions can depend on their own previous answers.
Figure 1: Visualization of candidate and voter partitioning used in the recursive query strategy.

To handle these constraints, the paper introduces algorithms like the "Single-Pass Plurality Veto," which partitions candidates and voters into groups to systematically narrow down the winner (see Figure 1). This approach allows for near-optimal results without requiring multiple rounds of interaction with the same population.

The Distortion Landscape

The core contribution of this work is a comprehensive mapping of distortion bounds across different adaptivity regimes. The researchers prove that the power of adaptivity is significant: being able to adapt queries based on a user's previous answers can slash distortion from $m^2/t$ down to $m/t$.

Figure 3: Summary of upper and lower distortion bounds based on inter-agent and intra-agent adaptivity.

As shown in Figure 3, fully adaptive strategies achieve a distortion of $\Theta(m/t)$, where $m$ is the number of candidates and $t$ is the number of queries per agent. Removing adaptivity leads to significant performance degradation. For instance, a fully non-adaptive approach results in a distortion of $\Theta(m^2/t)$.

Key Insights

  • The $m/t$ Barrier: The paper establishes a fundamental lower bound: no matter how clever the algorithm, if you only ask $t$ queries per person, you will always face a distortion of at least $\Omega(m/t)$.
  • Single-Pass Efficiency: Surprisingly, "single-pass" algorithms (where each user is queried only once) can match the performance of multi-round systems, provided they utilize intra-agent adaptivity.
  • Adaptivity Gaps: There is a massive performance gap between fixed query sets and those that evolve based on user feedback, particularly when inter-agent adaptivity is restricted.

Conclusion

This research provides a theoretical foundation for designing efficient elicitation protocols in systems like Polis or RLHF. While the $m/t$ bound is a fundamental limit, the discovery that single-pass adaptivity is sufficient for near-optimality offers a practical path forward for real-world social choice applications where minimizing user friction is paramount.

Summary updated

BibTeX
@inproceedings{ebadian2024metric,
  author = {Soroush Ebadian and Daniel Halpern and Evi Micha and Youyong Kong},
  title = {{Metric Distortion with Elicited Pairwise Comparisons}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=gmlVrofTmP},
}
Figure