Efficient Vote Elicitation under Candidate Uncertainty Joel Oren and Yuval Filmus and Craig Boutilier
Abstract
Top-k voting is an especially natural form of partial vot elicitation in which only length k prefixes of rankings a elicited. We analyze the ability of top-k vote elicitatio 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 bot 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 wi ner. We provide empirical results that confirm the value of top-k voting.