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

Abstract

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.

Appendix

Theorem 6

The ABCC rule AV is a maximum likelihood estimator for the noise model ${\mathcal {M}}_p$.

Proof

Let $\varPi =(S_i)_{i\in [n]}$ be a profile with n approval votes. We need to show that the profile $\varPi$ has maximum probability to have been produced by the noise model ${\mathcal {M}}_p$ with a set of k alternatives of maximum AV score from the votes of $\varPi$ as the ground truth committee.

Indeed, the probability that $\varPi$ has been produced by the noise model ${\mathcal {M}}_p$ with ground truth committee U is

$$\begin{aligned} \prod _{i\in [n]}{{\,\mathrm{Pr}\,}}_{{\mathcal {M}}_p}[S_i|U]&= \prod _{i\in [n]}{p^m\cdot \left( \frac{1-p}{p}\right) ^{d_\varDelta (S_i,U)}}=p^{mn}\cdot \left( \frac{1-p}{p}\right) ^{\sum _{i\in [n]}{d_\varDelta (S_i,U)}}. \end{aligned}$$

Since $p>1/2$, the above expression is maximized by minimizing the quantity $\sum _{i\in [n]}{d_\varDelta (S_i,U)}$. Now, we can express this quantity in terms of the number of agents n, the committtee size k, the total size of approval votes in profile $\varPi$, and the AV score of committee U from the votes of $\varPi$, using the following derivation:

$$\begin{aligned} \sum _{i\in [n]}{d_\varDelta (U,S_i)}&= \sum _{i\in [n]}{\left( |U{\setminus} S_i|+|S_i{\setminus} U|\right) }= \sum _{i\in [n]}\left( |U|+|S_i|-|U\cap S_i|\right) \\&= nk+\sum _{i\in [n]}{|S_i|}-\sum _{i\in [n]}{{{\,\mathrm{sc}\,}}_{{{\,\mathrm{AV}\,}}}(U,S_i)}= nk+\sum _{i\in [n]}{|S_i|}-{{\,\mathrm{sc}\,}}_{{{\,\mathrm{AV}\,}}}(U,\varPi ). \end{aligned}$$

Hence, the probability that the profile $\varPi$ is generated by a noise model ${\mathcal {M}}_p$ is maximized for the ground truth committee U of maximum score ${{\,\mathrm{sc}\,}}_{{{\,\mathrm{AV}\,}}}(U,\varPi )$. $\square$