Efficient Vote Elicitation Under Candidate Uncertainty
Abstract
Top- k voting is an especially natural form of partial vote elicitation in which only length k prefixes of rankings are elicited. We analyze the ability of top- k vote elicitation to correctly determine true winners, with high probability, given probabilistic models of voter preferences and candidate availability. We provide bounds on the minimal value of k required to determine the correct winner under the plurality and Borda voting rules, considering both worst-case preference profiles and profiles drawn from the impartial culture and Mallows probabilistic models. We also derive conditions under which the special case of zero-elicitation (i.e., k = 0) produces the correct winner. We provide empirical results that confirm the value of top- k voting.
Cite
Text
Oren et al. "Efficient Vote Elicitation Under Candidate Uncertainty." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Oren et al. "Efficient Vote Elicitation Under Candidate Uncertainty." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/oren2013ijcai-efficient/)BibTeX
@inproceedings{oren2013ijcai-efficient,
title = {{Efficient Vote Elicitation Under Candidate Uncertainty}},
author = {Oren, Joel and Filmus, Yuval and Boutilier, Craig},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {309-316},
url = {https://mlanthology.org/ijcai/2013/oren2013ijcai-efficient/}
}