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:
- Randomized: Each voter ranks a small, randomly selected subset of $\ell$ candidates.
- 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.
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.
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