Abstract
In the framework of metric voting, voters and candidates are embedded in a shared metric space where a voter's cost for a candidate is defined by the distance between them. Social choice mechanisms aim to select a candidate that minimizes the total social cost (the sum of distances) using only ordinal preference information. While some deterministic rules achieve constant distortion, they often require voters to communicate full rankings of all $n$ candidates. This paper investigates the fundamental trade-offs between communication complexity, distortion, and the use of randomness. We establish that any deterministic mechanism restricted to $k$ ranking positions must suffer a distortion of at least $(2n-k)/k$, and we provide a matching upper bound of $O(n/k)$. Furthermore, we demonstrate that randomization can significantly overcome these limitations; we present a randomized mechanism that achieves an expected distortion of $3 - 2/n$ using only the voters' top choices, effectively closing a long-standing gap in the literature.
Introduction
Social choice theory frequently deals with the challenge of making optimal collective decisions based on limited information. In the "metric voting" model, we assume that preferences are derived from an underlying metric space. The goal is to minimize "distortion"—the worst-case ratio between the social cost of the candidate selected by a mechanism and the social cost of the true optimal candidate (the one minimizing the sum of distances to all voters).
While complex rules like the Copeland rule are known to guarantee a distortion of at most 5, they impose a heavy communication burden by requiring voters to submit complete rankings. Conversely, simple rules like Plurality or $k$-approval require very little communication but suffer from distortion that grows unboundedly with the number of candidates $n$. This research explores whether it is possible to achieve low distortion with limited communication, and how the introduction of randomness alters this trade-off.
The Cost of Determinism
The paper first addresses deterministic mechanisms where communication is restricted. Two types of constraints are analyzed: position-bounded communication (where voters provide candidates at $k$ specific ranking positions) and bit-bounded communication (where voters provide $b$ bits of information).
Lower and Upper Bounds
Through adversarial metric constructions, the author proves that any one-round deterministic mechanism using only $k$ positions must have a distortion of at least $\frac{2n-k}{k}$. For more general $b$-bit communication, the lower bound is $\Omega(n/b)$. These results indicate that for deterministic rules, distortion must grow linearly with the number of candidates if communication is limited.
To provide a matching upper bound, the paper introduces a new deterministic mechanism, $\mathcal{M}$. This rule constructs a "comparison graph" where directed edges represent the preferences of a specific fraction of the electorate. By identifying a subset of "popular" candidates and selecting a winner based on their out-degree within this graph, the mechanism achieves a distortion of $O(n/k)$. This confirms that the $n/k$ relationship is fundamental to deterministic metric voting.
Randomization as a Solution
A major contribution of this work is the demonstration that randomization can bypass the linear distortion barriers faced by deterministic rules. Previously, it was known that "Random Dictatorship" (picking a random voter's top choice) achieves an expected distortion of less than 3. However, a gap remained between this and the theoretical lower bound of $3 - 2/n$ for mechanisms using only top-choice information.
The author closes this gap by proposing a hybrid randomized rule. This mechanism flips a coin between Random Dictatorship and a "Proportional to Squares" strategy. This simple rule requires only the voters' first-place preferences yet achieves the optimal expected distortion of $3 - 2/n$. This result suggests that if a society can tolerate randomness, the communication-distortion trade-off becomes almost negligible, as near-optimal results are possible with minimal voter input.
Key Insights
- The Determinism Bottleneck: Determinism is the primary driver of high distortion in communication-constrained environments. Without randomness, distortion is forced to scale with the number of candidates.
- Information Quality: The paper identifies a $\Theta(\log n)$ gap between bit-bounded and position-bounded communication, suggesting that the specific structure of information (which positions are revealed) is as critical as the total volume of data.
- The Power of Top Choices: In the randomized setting, the first-place vote carries enough information to achieve the best possible distortion for any ordinal rule, regardless of how much more information is provided.
Conclusion and Future Work
This research provides a comprehensive map of the trade-offs between communication and distortion in metric voting. While deterministic rules are strictly limited by the amount of information they receive, randomized rules can achieve constant distortion with minimal communication.
Future research may explore multi-round (interactive) communication, which might allow deterministic rules to achieve lower distortion with fewer total bits. Additionally, the technical gap between $b$-bit and $k$-position lower bounds remains an open question for further refinement of the theory.
Summary updated