Evaluating approval-based multiwinner voting in terms of robustness to noise

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.

Automated summary

Approval-based multiwinner voting rules have gained much attention in the Computational Social Choice literature. To assess their effectiveness, new noise models specifically tailored for approval votes and committees are proposed. Our findings indicate that these voting rules can be robust to reasonable noise, and a hierarchy of rules in terms of their robustness to noise is presented.