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!
|
| _version_ | 1866913969392844800 |
|---|---|
| author | Gao, Drew Sun, Yihang Vondrák, Jan |
| author_facet | Gao, Drew Sun, Yihang Vondrák, Jan |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00130 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computation of Approximately Stable Committees in Approval-based Elections Gao, Drew Sun, Yihang Vondrák, Jan Computer Science and Game Theory Discrete Mathematics 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. |
| title | Computation of Approximately Stable Committees in Approval-based Elections |
| topic | Computer Science and Game Theory Discrete Mathematics |
| url | https://arxiv.org/abs/2508.00130 |