Abstract
We consider a voting scenario where agents have
opinions that are estimates of an underlying common ground truth ranking of the available alternatives, and each agent is asked to approve a set with
her most preferred alternatives. We assume that estimates are implicitly formed using the well-known
Mallows model for generating random rankings.
We show that k-approval voting — where all agents
are asked to approve the same number k of alternatives and the outcome is obtained by sorting the alternatives in terms of their number of approvals —
has exponential sample complexity for all values of
k. This negative result suggests that an exponential
(in terms of the number of alternatives m) number
of agents is always necessary in order to recover
the ground truth ranking with high probability. In
contrast, by just asking each agent to approve a random number of alternatives, the sample complexity
improves dramatically: it now depends only polynomially on m. Our results may have implications
on the effectiveness of crowdsourcing applications
that ask workers to provide their input by approving
sets of available alternatives