Computing Voting Rules with Elicited Incomplete Votes
This addresses the challenge of eliciting complete preferences in large-scale elections, offering theoretical insights for voting system design, though it is incremental as it builds on prior work on specific instances.
The paper tackles the problem of computing voting rules when voters only provide incomplete preferences over a subset of candidates, fully characterizing which positional scoring rules can be computed with such limited information and showing impossibility results for rules like plurality and single transferable vote. It provides parameterized upper and lower bounds on the query complexity for computable rules, with exact results for deterministic algorithms but leaving randomized algorithms as an open problem.
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 \leq 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.