Learning a Ground Truth Ranking Using Noisy Approval Votes

Learning a Ground Truth Ranking Using Noisy Approval Votes

Ioannis Caragiannis, Evi Micha

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 149-155. https://doi.org/10.24963/ijcai.2017/22

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.
Keywords:
Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems
Agent-based and Multi-agent Systems: Social Choice Theory