Computing Voting Rules with Elicited Incomplete Votes
<|reference_start|>Computing Voting Rules with Elicited Incomplete Votes: 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.<|reference_end|>
@article{halpern2024computing,
    title={Computing Voting Rules with Elicited Incomplete Votes},
    author={Daniel Halpern, Safwan Hossain, Jamie Tucker-Foltz},
    journal={arXiv preprint arXiv:2402.11104},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11104},
    primaryClass={cs.GT cs.AI}
}