Comparing Election Methods Where Each Voter Ranks Only Few Candidates

Matthias Bentert, Piotr Skowron

Introduction

In many real-world voting scenarios, such as selecting a movie from a vast library or a political candidate from a large primary field, asking voters to provide a complete ranking of all $m$ candidates is often a "cognitive nightmare." Cognitive research suggests that humans can effectively rank only about 5 to 9 items at once. This creates a significant information gap: if we only collect partial preferences, how much does the quality of the final decision suffer?

This paper investigates two primary elicitation strategies to address this gap:

  1. Randomized: Each voter ranks a small, randomly selected subset of $\ell$ candidates.
  2. Deterministic ($\ell$-truncated): Each voter ranks only their top $\ell$ favorite candidates.

The goal is to determine how well these partial snapshots can approximate the results of full-preference rules like the Borda count (a positional scoring rule) and the Minimax rule (based on pairwise defeats).

Methodology

The researchers employed a combination of theoretical proofs and computer simulations. They proposed a randomized approximation algorithm ($\alpha$-PSF-ALG) that asks voters to rank random subsets and applies a specific weighting vector to estimate true scores. For deterministic approximation, they adapted a "minimax regret" framework for truncated ballots, picking a winner that minimizes potential error based on the "worst possible" and "best possible" scores a candidate could achieve in any consistent full ranking.

To evaluate these methods, three standard synthetic models were used to simulate voter behavior: the Impartial Culture (IC) model for unstructured noise, the One-dimensional Euclidean Model (1D) for spatial preferences, and the Mixture of Mallows’ Models (MMM) for consensus-based structures.

Key Insights

A central finding is the "power of random sampling." Top-$\ell$ truncation creates a massive blind spot; a candidate who is everyone's $(\ell+1)$-th choice—potentially the best compromise—would never appear on a top-$\ell$ ballot. In contrast, random subsets act as an unbiased probe into the entire preference spectrum.

The study reveals that the Borda count is relatively "easy" to approximate. Asking voters to compare just two random candidates ($\ell=2$) is sufficient to converge on the true winner as the voter population grows. Conversely, the Minimax rule is "harder" to approximate because it depends on specific pairwise comparisons that are easily missed in small samples, thus requiring more information per voter.

Results

Theoretical analysis shows that for the Borda rule with $\ell$-truncated ballots, the approximation ratio is approximately $\ell/m$. This linear relationship is clearly visible in experimental results.

Approximation ratio for the Borda rule as a function of the fraction of top positions $\ell/m$.

In contrast, the Minimax rule exhibits a much lower approximation ratio for the same fraction of information, highlighting the increased difficulty in estimating its winners from partial data.

Approximation ratio for the Minimax rule, demonstrating the increased difficulty of approximation compared to scoring rules.

Simulations with 50 candidates ($m=50$) showed that ranking just 8 random candidates ($\ell=8$) yielded nearly perfect approximations for most models once the voter count reached a few hundred. This suggests that massive voter turnouts are not required to overcome the noise introduced by random sampling.

Conclusion and Future Work

While the randomized approach shows great promise, particularly in structured societies (1D or Mallows models), several areas remain for future exploration. The current study assumes honest voting; strategic behavior in the context of random subset ranking is a critical next step. Additionally, extending this analysis to more complex rules like Kemeny-Young or STV (Single Transferable Vote) would broaden the practical applicability of these findings. Future research could also explore alternative metrics of "closeness" beyond simple score approximation.

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