Abstract: We consider elections where both voters and candidates can be associated with points in a metric space and voters prefer candidates that are closer to those that are farther away. It is often assumed that the optimal candidate is the one that minimizes the total distance to the voters. Yet, the voting rules often do not have access to the metric space $M$ and only see preference rankings induced by $M$. Consequently, they often are incapable of selecting the optimal candidate. The distortion of a voting rule measures the worst-case loss of the quality being the result of having access only to preference rankings. We extend the idea of distortion to approval-based preferences. First, we compute the distortion of Approval Voting. Second, we introduce the concept of acceptability-based distortion—the main idea behind is that the optimal candidate is the one that is acceptable to most voters. We determine acceptability-distortion for a number of rules, including Plurality, Borda, $k$-Approval, Veto, the Copeland's rule, Ranked Pairs, the Schulze's method, and STV.
The Information Gap in Social Choice
In social choice theory, a common assumption is the existence of a "ground truth" metric space where voters and candidates are represented as points. In this model, voter preference is inversely proportional to the distance to a candidate. Ideally, a voting rule should select the candidate that minimizes the total distance to all voters.
However, real-world voting rules rarely have access to this underlying metric data. Instead, they operate on simplified ballots: either a ranking (e.g., A > B > C) or an approval set (e.g., {A, B}). Distortion is the mathematical measure of the worst-case quality loss resulting from this information gap. This paper by Grzegorz Pierczyński and Piotr Skowron expands this framework to approval-based systems and introduces a new metric: acceptability-based distortion (ab-distortion).
Measuring Acceptability
The authors propose that instead of just minimizing distance, we should consider how many voters find a candidate "acceptable." In their model, voters are centers of "acceptability balls"; a candidate is acceptable if they fall within this radius. Ab-distortion measures the normalized difference between the number of voters who find the optimal candidate acceptable versus those who find the elected winner acceptable.
The Performance of Approval Voting
Approval Voting (AV) is highly sensitive to the "approval radius" chosen by voters. The research identifies a specific "sweet spot" for AV performance. When the optimal candidate is approved by roughly 25% to 50% of the population, the distortion is minimized to a value of 3. Outside of this range—if voters approve too many or too few candidates—the distortion increases significantly.
Comparing Ranking Rules
The paper provides a rigorous comparison of traditional ranking-based rules under both distance-based and acceptability-based metrics.
Key Findings:
- Condorcet Rules: Rules focusing on head-to-head matchups, specifically Ranked Pairs and the Schulze method, were found to be optimal for acceptability-based distortion among ranking rules.
- The Failure of STV: Despite its popularity and low distance-based distortion, the Single Transferable Vote (STV) performs poorly in terms of acceptability. In worst-case scenarios, it can elect a candidate that almost no one finds acceptable.
- Copeland’s Paradox: While the Copeland rule is generally strong, it fails the acceptability test completely, with a worst-case ab-distortion of 1—the highest possible value.
- Standard Rules: Traditional rules like Plurality and Borda exhibit high distortion ($2m - 1$) as the number of candidates ($m$) increases.
Conclusion and Future Directions
The study highlights that the choice of voting rule should depend on the desired goal: minimizing distance or maximizing acceptability. While Ranked Pairs and Schulze appear robust for acceptability, questions remain regarding the performance of general positional scoring rules and how strategic voter behavior (adjusting approval radii) might impact these theoretical bounds.
Summary updated