Evaluating approval-based multiwinner voting in terms of robustness to noise
This work addresses the robustness of voting rules for computational social choice, but it is incremental as it builds on existing literature with new noise models.
The paper tackled the problem of evaluating approval-based multiwinner voting rules by proposing new noise models tailored for approval votes and committees, and found that such voting is always robust to reasonable noise, with a hierarchy of rules based on their robustness levels.
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 is always robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.