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.