Abstract
Elections and opinion polls often have many candidates, with the aim to either rank the candidates or identify a small set of winners according to voters' preferences. In practice, voters do not provide a full ranking; instead, each voter provides their favorite K candidates, potentially in ranked order. The election organizer must choose K and an aggregation rule. We provide a theoretical framework to make these choices. Each K-Approval or K-partial ranking mechanism (with a corresponding positional scoring rule) induces a learning rate for the speed at which the election correctly recovers the asymptotic outcome. Given the voter choice distribution, the election planner can thus identify the rate optimal mechanism. Earlier work in this area provides coarse order-of-magnitude guaranties which are not sufficient to make such choices. Our framework further resolves questions of when randomizing between multiple mechanisms may improve learning, for arbitrary voter noise models. Finally, we use data from 5 large participatory budgeting elections that we organized across several US cities, along with other ranking data, to demonstrate the utility of our methods. In particular, we find that historically such elections have set K too low and that picking the right mechanism can be the difference between identifying the ultimate winner with only a 80% probability or a 99.9% probability after 400 voters.
Introduction
In many real-world scenarios—such as Participatory Budgeting (PB) in cities or niche opinion polls—there are often dozens of candidates but a relatively small pool of voters. The primary goal is typically to identify a single winner or a small set of winners. However, a fundamental challenge arises in information elicitation. Asking a voter to rank 70 candidates leads to cognitive overload and noisy data, while asking for only a single favorite ($K=1$) discards valuable information about secondary preferences that could be crucial for distinguishing between top contenders.
This research addresses a critical design question: How many candidates ($K$) should voters select, and which aggregation rule identifies the "true" winners most efficiently?
Theoretical Framework: Learning Rates
The authors develop a framework based on Large Deviation Analysis to define a "learning rate" ($r$). This rate characterizes how quickly the probability of an election error (selecting the wrong winner) decays as the number of voters ($N$) increases, following the behavior $e^{-rN}$.
By analyzing positional scoring rules (like $K$-Approval), the framework identifies the "rate-optimal" $K$ for any given voter preference distribution. This approach assumes "design invariance," meaning that with infinite voters, different reasonable rules would converge to the same outcome, allowing the comparison to focus strictly on the speed of learning.
Empirical Scaling and Results
The theory was validated using data from five large-scale PB elections in US cities (Boston, Durham, and Rochester) and 28 datasets from the PrefLib repository.
A key empirical finding is that the optimal $K$ scales linearly with both the number of candidates and the number of desired winners. Historically, organizers have set $K$ much lower than is statistically optimal. For instance, in a Boston PB election, switching from 1-Approval to 2- or 3-Approval improved the probability of identifying the correct winner from 80% to 99.9% after just 400 votes.
Key Insights
- The "Top Half" Heuristic: In high-noise environments, the most efficient strategy is often to ask voters for their favorite half of the candidates, even when seeking a single winner.
- Randomization: Surprisingly, randomizing the ballot (e.g., asking some voters for their top 3 and others for their top 4) can improve learning rates by balancing the strengths of different $K$ values in separating candidate pairs.
- W-Approval Mismatch: If the goal is to select $W$ winners, asking for exactly $W$ candidates ($W$-Approval) is frequently not the fastest way to find them, especially as noise increases.
Limitations and Future Work
While statistically efficient, asking for more candidates increases the "cognitive cost" for voters. Future research must balance learning rates against voter effort. Additionally, the current model assumes truthful reporting; strategic voting behaviors are not yet accounted for. Finally, in polarized settings where different rules might lead to different winners, the optimization becomes a more complex value-based decision.
Summary updated