Abstract
We study the additive distortion of social choice functions in the implicit utilitarian model, and argue that it is a more appropriate metric than multiplicative distortion when an alternative that confers significant social welfare may exist (i.e., when the stakes are high). We define a randomized analog of positional scoring rules, and present a rule which is asymptotically optimal within this class as the number of alternatives increases. We then show that the instance-optimal social choice function can be efficiently computed. Next, we take a beyond-worst-case view, bounding the additive distortion of prominent voting rules as a function of the best welfare attainable in an instance. Lastly, we evaluate the additive distortion of a range of rules on real-world election data.
Introduction
In social choice theory, the implicit utilitarian model is a common framework for evaluating voting rules. In this model, voters possess internal "cardinal" utilities for various alternatives, but they only report their preferences as "ordinal" rankings. The goal is to select a winner that maximizes social welfare—the sum of all voters' utilities—using only these rankings.
Traditionally, the performance of a voting rule is measured by its multiplicative distortion, which is the ratio of the maximum possible welfare to the welfare achieved by the rule. However, this metric can be misleading in "high-stakes" elections. Multiplicative distortion is often dominated by low-stakes cases where no alternative is particularly good, leading to overly pessimistic bounds. This paper argues for the use of additive distortion (also known as regret), which measures the absolute difference between the maximum possible welfare and the achieved welfare. This shift is particularly relevant when a single candidate could provide massive utility to the population, making the absolute loss of welfare more critical than the ratio.
Methodology
The researchers explore several approaches to minimize additive distortion:
Randomized Scoring Rules (RSRs) and the BoB Rule
Randomized Scoring Rules are probabilistic versions of classic rules like the Borda count. Instead of a single winner, an RSR assigns a probability of winning to each candidate proportional to their aggregate score. The authors derive the Best-or-Bust (BoB) rule, an RSR with a specific scoring vector of $(25/33, 7/33, 1/33, 0, \dots, 0)$. This rule is designed to minimize the "best-or-bust" bound, an upper bound on additive distortion assuming zero utility is gained if the absolute best candidate is not selected.
Instance-Optimal Social Choice
Beyond general rules, the authors provide the AddOpt algorithm. This algorithm efficiently computes the exact probability distribution over candidates that minimizes additive distortion for a specific set of votes (an instance). This allows for the most robust decision-making possible given the available ordinal information.
Empirical Evaluation
To test these theoretical constructs, the authors evaluated several voting rules using real-world election data from the PrefLib library, including datasets from Vermont public office elections, the Glasgow City Council, the Debian project, and the American Psychological Association (APA).
As shown in the figure above, the Add OPT rule consistently achieves the lowest additive distortion across all datasets, confirming its effectiveness as an instance-optimal approach. Interestingly, while the BoB rule is theoretically superior in the worst case, Randomized Dictatorship (selecting a random voter and choosing their top choice) often performs better on these real-world datasets. This suggests that the specific preference structures found in human elections rarely mirror the theoretical worst-case scenarios.
Key Results and Insights
- Theoretical Bounds: The BoB rule achieves an additive distortion of at most $\approx 0.407n$ for any number of alternatives $m \geq 3$. Conversely, the authors prove a lower bound of $\approx 0.277n$ for any randomized social choice function.
- The Power of Randomization: There is a significant performance gap between deterministic and randomized rules. The best deterministic rule (Plurality) has an additive distortion of $n/2$, whereas randomized rules can significantly reduce this regret.
- Top-Heavy Importance: The scoring vector of the BoB rule suggests that to minimize regret, one primarily needs to consider the top three choices of voters. The "tail" of the ranking provides diminishing returns for welfare guarantees.
- Promise Distortion: Under the "promise" that a high-quality candidate exists (providing at least $75\%$ of the maximum possible welfare), simple rules like Plurality and the Harmonic rule can achieve zero additive distortion.
Conclusion
This work highlights that additive distortion is a robust metric for high-stakes social choice, as it does not require the restrictive "unit-sum" utility assumption. While a gap remains between the theoretical lower and upper bounds for randomized rules, the introduction of the BoB rule and the AddOpt algorithm provides practical tools for minimizing regret in real-world voting systems. Future research may extend these findings to metric distortion settings, where voter preferences are modeled as distances in a geometric space.
Summary updated