Comparing Election Methods Where Each Voter Ranks Only Few Candidates

Matthias Bentert, Piotr Skowron

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:

  1. Randomized Approach: Each voter ranks a subset of $\ell$ candidates chosen uniformly at random.
  2. 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.

Scoring functions $\lambda(p)$ for different subset sizes $\ell=2, 4, 8$

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.
Visualization of candidate positions in a 1D Euclidean model

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

Abstract

Election rules are formal processes that aggregate voters preferences, typically to select a single candidate, called the winner. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized-we ask each voter to rank a random subset of $\ell$ candidates, and (ii) deterministic-we ask each voter to provide a ranking of her $\ell$ most preferred candidates (the $\ell$-truncated ballot). We establish theoretical bounds on the approximation ratios and we complement our theoretical analysis with computer simulations. We find that mostly (apart from the cases when the preferences have no or very little structure) it is better to use the randomized approach. While we obtain fairly good approximation guarantees for the Borda rule already for $\ell = 2$, for approximating the Minimax rule one needs to ask each voter to compare a larger set of candidates in order to obtain good guarantees.
BibTeX
@inproceedings{bentert2020comparing,
  author = {Matthias Bentert and Piotr Skowron},
  title = {{Comparing Election Methods Where Each Voter Ranks Only Few Candidates}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5598},
}
Figure