Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.00130 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 $λ$-approximately-stable if there is no other committee $T$ preferred by at least $\frac{λ|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.