Abstract
In many social choice applications, information about individuals' preferences can only be elicited using a limited number of pairwise comparisons. In these cases, the task is twofold: we must first choose the queries, and then second, we must aggregate the responses to choose an outcome. We study the problem of designing algorithms for this setting. To compare the effectiveness of different outcomes, we use the metric distortion framework. In addition, we consider various constraints on the query algorithms, namely, placing restrictions on how the choice of the next query may depend on previous answers. Our main contributions are nearly optimal algorithms for all settings considered.
Introduction
Aggregating individual preferences to find a collective "best" outcome is a fundamental challenge in fields ranging from Reinforcement Learning from Human Feedback (RLHF) to digital democracy platforms like Polis. In practice, obtaining a full ranking of all options from every participant is often infeasible. Instead, preferences are elicited through a limited number of pairwise comparisons—simple "this or that" questions.
This paper addresses two core problems in this context: query selection (determining which pairs of candidates users should compare) and aggregation (developing rules to select a winner based on partial responses). To evaluate these algorithms, the authors employ the metric distortion framework. This model assumes that voters and candidates are positioned in a hidden metric space where the "cost" of a candidate is the sum of its distances to all voters. The goal is to minimize distortion: the ratio between the cost of the chosen candidate and the cost of the socially optimal candidate.
Methods and Adaptivity Constraints
The study focuses on $t$-query algorithms, where each of the $n$ agents is asked at most $t$ pairwise comparisons. The researchers categorize these algorithms based on their degree of adaptivity:
- Inter-agent adaptivity: Whether queries for one user can depend on the responses of others.
- Intra-agent adaptivity: Whether subsequent queries for a single user can depend on their own previous answers.
- Number of passes: Whether the system can revisit a user (multi-pass) or must finalize queries in a single interaction (single-pass).
As a theoretical work, the paper relies on mathematical proofs and lower-bound constructions (worst-case scenarios) within the metric distortion framework. A key contribution is the development of a Single-Pass Adaptive algorithm (Algorithm 2). This algorithm utilizes a modified "Plurality Veto" rule, where one subset of voters nominates candidates and another subset "vetoes" their least-preferred options among those nominated.
Key Results
The research establishes fundamental limits and nearly optimal bounds for distortion across the various adaptivity settings. The following table summarizes the trade-offs between query limits ($t$) and decision quality (distortion) relative to the number of candidates ($m$).
Major Insights
- The $m/t$ Fundamental Limit: For $m$ candidates and $t$ queries per person, a distortion of at least $\Omega(m/t)$ is unavoidable, regardless of the query strategy.
- Efficiency of Single-Pass Interaction: Surprisingly, multi-round interactions are not required to reach optimal bounds. A single-pass algorithm can achieve the $O(m/t)$ target, matching the theoretical lower bound up to a small constant factor. Specifically, Algorithm 2 achieves a distortion of $6(\frac{m-1}{t}) + 1$.
- The Cost of Non-Adaptivity: Removing the ability to adapt queries based on a user's previous answers (intra-agent non-adaptivity) can significantly degrade performance, particularly in non-inter-agent adaptive settings where distortion jumps to $\Theta(m^2/t)$.
- Parallelism and Fairness: The analysis of inter-agent non-adaptive algorithms provides insights for systems where users must be queried simultaneously or where avoiding bias from earlier responses is a priority.
Discussion and Future Work
While this work provides nearly optimal algorithms for most settings, some logarithmic gaps remain in the inter-agent non-adaptive scenarios. Furthermore, the current bounds are dependent on the number of candidates ($m$). In domains with an effectively infinite number of options, such as open-ended comment sections or LLM fine-tuning, future research could explore "feature-based" metric spaces to remove this dependence. Additionally, exploring randomized query strategies may offer further improvements or simpler algorithmic implementations.
Summary updated