Efficient Vote Elicitation under Candidate Uncertainty
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 309-315.
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.
@inproceedings{ijcai2013p54,
title = {Efficient Vote Elicitation under Candidate Uncertainty},
author = {Oren, Joel and Filmus, Yuval and Boutilier, Craig},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {309--315},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/54},
}
TY - CPAPER TI - Efficient Vote Elicitation under Candidate Uncertainty AU - Oren, Joel AU - Filmus, Yuval AU - Boutilier, Craig T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 309 EP - 315 UR - https://ijcai.org/proceedings/2013/54 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
