Evaluating Approval-Based Multiwinner Voting in Terms of Robustness to Noise
Evaluating Approval-Based Multiwinner Voting in Terms of Robustness to Noise
Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas, George A. Krimpas
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 74-80.
https://doi.org/10.24963/ijcai.2020/11
Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting can indeed be robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting