Abstract
Election rules are formal processes that aggregate voters' preferences to select a single winner. Most studied rules require voters to rank all candidates, which is impractical when the candidate pool is large. This paper investigates how well certain rules, specifically positional scoring rules like Borda and the Minimax rule, can be approximated using partial preferences. We compare two elicitation procedures: a randomized approach (ranking a random subset of $\ell$ candidates) and a deterministic approach (the $\ell$-truncated ballot). Theoretical bounds and computer simulations reveal that the randomized approach generally performs better, especially for structured preferences. While the Borda rule is easily approximated even with $\ell = 2$, the Minimax rule requires larger subsets for comparable guarantees.
Introduction
In social choice theory, the standard assumption is that voters can provide a complete linear ordering of all candidates. However, as the number of candidates $m$ increases, the cognitive burden on voters becomes prohibitive. Practical voting systems often resort to partial elicitation, such as asking for a "top-3" or "top-5" list. This paper addresses the fundamental question: how much accuracy is lost when we limit the information each voter provides, and what is the best way to collect this limited information?
Methodology: Preference Elicitation
The study evaluates two primary methods for collecting rankings of $\ell$ candidates from each voter:
- Randomized Approach: Each voter ranks a subset of $\ell$ candidates chosen uniformly at random.
- Deterministic Approach ($\ell$-truncated ballot): Each voter ranks their top $\ell$ most preferred candidates.
To approximate positional scoring rules under the randomized approach, the authors introduce a new class of scoring rules, denoted as $Sep_\ell$. These rules use specific weight vectors ($\alpha$-vectors) to estimate the true scores.
The figure above illustrates how the scoring weights $\lambda(p)$ are distributed across positions $p$ for various subset sizes. As $\ell$ increases, the approximation becomes more nuanced, allowing for a closer fit to the target voting rule.
Preference Models and Simulation Setup
To test these methods, the authors used four synthetic preference models:
- Impartial Culture (IC): Uniformly random rankings.
- One-dimensional Euclidean Model (1D): Candidates and voters are points on a line; preferences are based on distance.
- Mixture of Mallows’ Models (MMM): Rankings clustered around central "consensus" orderings.
- Single Peaked Impartial Culture (SPIC): Rankings consistent with a common axis.
Simulations involved $m=50$ candidates and up to $n=1000$ voters, measuring the approximation ratio—the ratio of the true winner's score to the score of the winner selected by the approximation method.
Results and Discussion
The findings highlight a significant advantage for randomization in most structured environments.
The Power of Randomization
For models like the 1D Euclidean or Mallows models, the randomized approach significantly outperforms the deterministic one. By sampling random subsets, the system captures information about the relative standing of mid-tier and bottom-tier candidates. In contrast, the top-$\ell$ deterministic method completely ignores these candidates, leading to a permanent loss of information that cannot be recovered even with more voters.
Robustness of Borda vs. Minimax
The Borda rule proves remarkably robust. With the randomized approach and $\ell=2$ (comparing just two random candidates), the approximation ratio exceeds 0.9 with only 200 voters. In contrast, the Minimax rule is "brittle." Because it depends on pairwise defeats across the entire candidate set, it requires larger subsets ($\ell \approx 8$) and more voters to achieve stable results.
When Determinism Wins
The only scenario where the deterministic top-$\ell$ approach is superior is the Impartial Culture (IC) model. In this "maximum noise" environment, there is no underlying structure to exploit, and the top-tier rankings provide the only reliable signal for identifying a winner.
Conclusion
This research demonstrates that for most realistic preference distributions, asking voters to rank a small, random subset of candidates is a highly effective strategy for approximating complex voting rules. While Borda is easily approximated with minimal information, Condorcet-consistent rules like Minimax demand more comprehensive partial rankings. Future work may extend these findings to multi-winner rules and consider the impact of strategic voting behavior.
Summary updated