TL;DR
When an election has dozens of candidates but only a few hundred voters, the choice of voting mechanism (how many candidates a voter picks) is the difference between a coin flip and a near-certain outcome. This paper uses large deviation theory to prove that common "pick-one" ballots are often inefficient, suggesting that asking voters for their "top half" of candidates is a better way to find the true winner quickly.
What Problem Does This Paper Address?
In many real-world scenarios—like Participatory Budgeting (PB) in cities or niche opinion polls—there are many candidates (sometimes 70+) but a relatively small pool of voters. The goal is usually to identify a single winner or a small set of winners.
The challenge is information elicitation. If you ask a voter to rank all 70 candidates, they’ll experience "cognitive overload" and likely provide noisy data. If you only ask for their single favorite candidate ($K=1$), you lose valuable information about their second and third choices, which might be crucial for distinguishing between the top contenders.
The authors tackle a fundamental design question: How many candidates ($K$) should we ask voters to select, and how should we aggregate those votes to identify the "true" winners as fast as possible?
Methods
The researchers develop a theoretical framework based on Large Deviation Analysis.
- Learning Rates: They define a "learning rate" ($r$) that characterizes how fast the probability of an election error (picking the wrong winner) decays as the number of voters ($N$) increases. The error probability behaves like $e^{-rN}$.
- Positional Scoring Rules: They analyze mechanisms where candidates receive points based on their position in a voter's partial ranking (e.g., $K$-Approval, where the top $K$ candidates get 1 point each).
- Asymptotic Design Invariance: They focus on "well-behaved" voter distributions where different reasonable voting rules would eventually converge to the same winner if given infinite voters. This allows them to compare rules based purely on their speed of learning.
- Optimization: They provide a way to calculate the "rate-optimal" $K$ for a given distribution of voter preferences.
Datasets
The paper validates its theory using a mix of real-world and simulated data:
- Participatory Budgeting (PB) Data: Data from 5 large-scale PB elections organized by the authors in US cities (Boston, Durham, and Rochester). These are unique because they used $K$-Ranking, allowing the authors to simulate what would have happened under different $K$ values.
- PrefLib: 28 datasets from the PrefLib repository, covering diverse domains from sushi preferences to Glasgow City Council elections.
- Mallows Model: A standard statistical model for noisy rankings used for numerical simulations.
Key Insights and Ideas
- $K$ is usually too low: Historically, election organizers set $K$ (the number of candidates to pick) much lower than is optimal for learning.
- The "Top Half" Heuristic: In high-noise environments (which characterize most real-world voting), the optimal strategy is often to ask voters to identify their favorite half of the candidates, even if the goal is only to find a single winner.
- Randomization can help: While it seems counterintuitive, the authors show that randomizing the ballot (e.g., asking some voters for their top 3 and others for their top 4) can sometimes speed up learning. This happens because different $K$ values are better at "separating" different pairs of candidates; randomization balances these strengths.
- W-Approval isn't always best for W-Winners: If you want to pick 5 winners, asking voters for exactly 5 candidates (5-Approval) is often not the fastest way to find them.
Key Results
- Dramatic Accuracy Gains: In one Boston PB election, using 1-Approval (pick one) resulted in only an 80% chance of identifying the correct winner after 400 voters. Using 2-Approval or 3-Approval increased that probability to 99.9%.
- Empirical Scaling: By running regressions on real-world data, the authors found that the optimal $K$ scales linearly with both the number of candidates and the number of desired winners.
- Validation: The theoretical "learning rates" derived from large deviation bounds closely matched the actual empirical error rates observed in bootstrapped real-world data.
Limitations and Future Work
- Cognitive Load: The paper focuses on the statistical efficiency of elicitation. However, asking a voter to pick 10 candidates is harder than asking for 1. The authors acknowledge that future work should balance the statistical "learning rate" against the "cognitive cost" to the voter.
- Strategic Voting: The model assumes voters report their true preferences. It does not account for strategic behavior (e.g., a voter not picking their second favorite to help their first favorite win).
- Non-Invariant Settings: The theory relies on "design invariance" (different rules leading to the same winner). In highly polarized elections where different rules yield different winners, the optimization problem becomes much more complex and value-laden.
Summary updated