Abstract
Efficient Vote Elicitation under Candidate Uncertainty / 309 Joel Oren, Yuval Filmus, Craig Boutilier 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.
