Computation of Approximately Stable Committees in Approval-based Elections

Abstract

Approval-based committee selection is a model of significant interest in social choice theory. In this model, we have a set of voters $\mathcal{V}$, a set of candidates $\mathcal{C}$, and each voter has a set $A_v\subset \mathcal{C}$ of approved candidates. For any committee size $K$, the goal is to choose $K$ candidates to represent the voters' preferences. We study a criterion known as \emph{approximate stability}, where a committee is $\hat{I}»$-approximately-stable if there is no other committee $T$ preferred by at least $\frac{\hat{I}»|T|}{k}|\mathcal{V}|$ voters. We prove that a $3.65$-approximately stable committee always exists and can be computed algorithmically in this setting. Our approach is based on finding a Lindahl equilibrium and sampling from a strongly Rayleigh distribution associated with it.

18 pages, 2 figures