# Computing Voting Rules with Elicited Incomplete Votes

arXiv: https://arxiv.org/abs/2402.11104 · HTML: https://mlsanity.com/paper/2402.11104/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 27 references that are in the map.
- First posted on arXiv 16 Feb 2024.

## Builds on (most cited first, 3 of 3)

- [Representation with Incomplete Votes](https://mlsanity.com/paper/2211.15608/) (2022)
- [Sample Complexity for Winner Prediction in Elections](https://mlsanity.com/paper/1502.04354/) (2015)
- [Comparing Election Methods Where Each Voter Ranks Only Few Candidates](https://mlsanity.com/paper/1901.10848/) (2019)

## Built on by (most cited first, 5 of 5)

- [Full-Stack Alignment: Co-Aligning AI and Institutions with Thick Models of Value](https://mlsanity.com/paper/2512.03399/) (2025)
- [DeepVoting: Learning and Fine-Tuning Voting Rules with Canonical Embeddings](https://mlsanity.com/paper/2408.13630/) (2024)
- [Artificial Delegates Resolve Fairness Issues in Perpetual Voting with Partial Turnout](https://mlsanity.com/paper/2506.21186/) (2025)
- [Linear Social Choice with Few Queries: A Moment-Based Approach](https://mlsanity.com/paper/2603.19510/) (2026)
- [Computing Voting Rules with Improvement Feedback](https://mlsanity.com/paper/2502.12542/) (2025)

## Abstract (arXiv)

Motivated by the difficulty of specifying complete ordinal preferences over a large set of m candidates, we study voting rules that are computable by querying voters about t < m candidates. Generalizing prior works that focused on specific instances of this problem, our paper fully characterizes the set of positional scoring rules that can be computed for any 1 ≤ t < m, which, notably, does not include plurality. We then extend this to show a similar impossibility result for single transferable vote (elimination voting). These negative results are information-theoretic and agnostic to the number of queries. Finally, for scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries a deterministic or randomized algorithm must make to determine the score-maximizing candidate. While there is no gap between our bounds for deterministic algorithms, identifying the exact query complexity for randomized algorithms is a challenging open problem, of which we solve one special case.