Source-linked AI summary
A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls
Fabian Frank, Jannik Peters
TL;DR
Approval voting lacks a clear way to choose sincere approval prefixes, motivating protocols that use information about other voters’ preferences. This paper uses plurality polls to define k-Plurality Approval and shows that its optimal choice achieves metric distortion 2 + sqrt(5).
Problem
Approval voting has no ground-truth approval ballot, and choosing a sincere preference prefix requires information about other voters’ preferences.
Method
The k-plurality approval protocol elicits each voter’s top choice, then has voters approve the smallest preference prefix containing top choices of at least a k fraction of voters.
Results
2 + sqrt(5) ≃ 4.236: for the optimal k, k-Plurality Approval achieves this metric distortion.
Takeaways & Limitations
The protocol achieves constant-factor metric distortion and can be computed using O(m) pairwise comparison queries per voter.
Takeaways & Limitations
The protocol is not strategyproof: voters may benefit from deviating during both plurality elicitation and approval phases.
Abstract
from arXiv · showhide
Approval voting is a simple and well-regarded voting rule: voters submit approval ballots (subsets of the candidates) and the candidate receiving the most approvals wins. One major limitation of approval voting is that it is not clear which candidates voters should approve if they have an underlying strict order over the candidates. In this paper, we initiate the study of approval voting under a simple kind of information: plurality polls. That is, we assume that for each candidate we know the share of voters who rank this candidate as their top choice. Using these plurality polls, we suggest a simple protocol parameterized by a fraction $k \in (0,1)$: every voter should approve the smallest prefix of their preference list containing the first choices of at least a fraction $k$ of the voters. We evaluate this protocol via the framework of metric distortion and show that for the optimal choice of $k$, this rule achieves a metric distortion of $2 + \sqrt{5} \simeq 4.236$. The proof techniques we use for this statement also show that the Bucklin voting rule has a metric distortion of at most $5$. Finally, we evaluate the robustness of our protocol to noise and show that the upper bounds obtained for our protocol are tight.
1 Introduction
The paper studies how plurality-poll information can guide approval ballots, addressing the lack of a ground-truth approval threshold. It proposes the k-plurality approval protocol and analyzes its metric distortion, robustness, query complexity, and related voting rules.
- Motivation: Approval voting lacks a ground-truth approval ballot, because any prefix of a voter’s preferences could be sincere.Strategies that ignore other voters’ preferences, such as approving a fixed top-ℓ set, can have unbounded metric distortion.
- Motivation: Voters therefore need information about other voters’ preferences, but suitable information and adaptation strategies remain unclear.Front-runner strategies require voters to identify leading candidates accurately and make assumptions about others’ preferences and strategic behavior.
- Protocol: Plurality polls reveal the distribution of voters’ top choices, enabling the k-plurality approval protocol.For k ∈ (0,1), each voter approves the smallest preference prefix containing top choices representing at least k · n voters.
- Results: 2 + √5 ≃ 4.236 is the protocol’s metric distortion for its optimal parameter choice, and the bounds are tight.The analysis also rules out a better distortion for anonymous approval-voting rules based on plurality polls.
- Results: 5 is the resulting metric-distortion bound for Bucklin’s rule, improving a previous bound of 11.The same analysis extends to the fallback bargaining family and shows that Bucklin’s first phase already achieves distortion at most 5.
- Robustness and implementation: The protocol remains close to its original guarantees when plurality polls are noisy, and it can be computed with O(m) pairwise comparisons per voter.It can also be implemented as a two-round querying protocol, while the paper leaves single-round constant distortion and strategic deviations as open questions.
- Framework and related work: Metric distortion evaluates the quantitative social-welfare loss of voting rules using only ordinal preferences and metric-consistent distances.Prior work established a deterministic lower bound of 3, while several rules attain constant-factor distortion.
2 Preliminaries and Notation
The preliminaries define preference profiles, plurality and approval scores, metric consistency, social cost, metric distortion, and social choice correspondences. They also introduce the notation used to describe candidates, voters, ranks, prefixes, and example ballots.
- Preference profiles: A preference profile consists of n voters with strict linear orders over a candidate set C = {c1, ..., cm}.top(i) denotes voter i’s most-preferred candidate, while rank(i,c) is c’s position in that voter’s order.
- Plurality notation: The plurality score plu(c) counts voters ranking candidate c first, and p denotes its normalized plurality score.These quantities summarize the top-choice distribution used by the protocol.
- Preference notation: A prefix of a voter’s preference contains candidates ranked above every candidate excluded from the set.The notation supports describing approval ballots formed from initial segments of rankings.
- Approval voting: An approval ballot is a subset Ai of candidates, and approval winners maximize the number of voters approving them.For candidate c, Ac is the set of approving voters and |Ac| is its approval score.
- Metric model: Voters and candidates occupy a common pseudo-metric space satisfying zero self-distance, symmetry, and the triangle inequality.The metric may assign zero distance to distinct points because it is a pseudo-metric.
- Metric consistency: A metric is consistent with a preference profile when every voter weakly prefers candidates ranked higher by having no greater distance to them.D(≻) denotes the set of pseudo-metrics consistent with the profile.
- Social cost and distortion: A candidate’s social cost is the sum of its distances from all voters, and metric distortion compares the selected outcome with the socially optimal candidate.The metric-distortion definition takes a supremum over preference profiles, voters, candidates, and consistent pseudo-metrics.
- Social choice correspondences: A social choice correspondence maps every preference profile to a non-empty subset of candidates.Approval voting is represented as a correspondence when multiple candidates tie for the highest approval score.
3 Distortion Bounds for k-Plurality Approval
The section defines the k-plurality approval protocol and establishes constant metric-distortion guarantees, matching lower bounds, and related results for fallback bargaining rules.
- Protocol: The k-plurality approval protocol uses two rounds: voters report top choices, then approve the smallest preference prefix containing top choices of at least k·n voters.The resulting approval profile determines the winner.
- Protocol complexity: O(m) pairwise comparisons per voter suffice to compute the protocol, rather than the Θ(m log m) comparisons needed by rules requiring complete preference sorting.Finding each voter’s most-preferred candidate requires at most m−1 comparisons.
- Upper-bound proof: The proof uses fractional assignments whose existence implies a social-cost comparison between the selected candidate and an alternative.Lemma 7 gives sc(a) ≤ (3 + 2t) sc(b) under its stated assignment conditions.
- Related rules: Bucklin’s rule and the majoritarian compromise achieve metric distortion at most 5, while the fallback bargaining rule inherits the k-plurality approval guarantees.The majoritarian compromise selects candidates reaching a weak-majority top-rank threshold at the smallest such r.
- Lower bounds: The k-plurality approval upper bounds are tight: constructed instances attain the stated lower bounds, and no anonymous sincere approval protocol using plurality polls can do better than 2 + √5.Analogous lower-bound constructions also apply to q-approval fallback bargaining.
4 Robustness to Noise
The paper models noisy plurality polls through prediction error and sampling, showing that k-Plurality Approval retains continuous distortion guarantees under bounded noise. Sampling-based polls also yield probabilistic and randomized-rule guarantees, though the resulting bound can be loose.
- Deterministic noisy polls: Poll noise is modeled by comparing a prediction distribution q with the normalized plurality vector p using maximum prefix-mass error Δ(q,p).The distance maximizes the discrepancy over voters’ upper contour sets and candidates.
- Deterministic noisy polls: Theorem 7 guarantees a distortion upper bound for any prediction poll whose error satisfies Δ(q,p) ≤ ε, provided k < 1 − ε.The resulting bound varies continuously with ε, and increasing ε lowers the optimal k-value.
- Deterministic noisy polls: The robustness proof changes only the bound component that relies on exact plurality scores; other structural properties require only that poll entries sum to one.This explains why the error term affects only one of the two functions in the distortion bound.
- Sampling-based polls: Sampling r voters uniformly produces an empirical poll Q(r), for which concentration inequalities provide a sample-size guarantee for distortion close to the deterministic noisy-poll bound.Theorem 8 gives a sufficient lower bound on r depending on ε, δ, n, and m.
- Sampling-based polls: The sampling procedure can also be viewed as a randomized voting rule that returns a probability distribution over candidates rather than a single candidate.A fixed tie-breaking rule is used to select an approval winner for each sampled poll.
5 Conclusion and Open Questions
The paper concludes that k-Plurality Approval is a simple plurality-poll-based protocol with constant metric distortion and extensions to other voting rules. It also identifies query complexity, dynamics, and strategic behavior as open questions.
- Conclusion: The paper introduces k-Plurality Approval, a protocol for eliciting approval ballots from plurality polls.The protocol’s winner can be found using O(m) pairwise comparison queries per voter and implemented in two rounds.
- Conclusion: The analysis also derives a metric-distortion result for Bucklin’s rule and for voting rules in the fallback bargaining family.These results arise from techniques developed for the approval protocol.
- Open questions: Open questions concern single-round O(m)-query protocols, dynamics under repeated polling, convergence, and the impact of strategic deviations.The protocol is not strategyproof because deviations may be beneficial during both plurality elicitation and approval.