{"ID":2888533,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.00130","arxiv_id":"2508.00130","title":"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 $λ$-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.","short_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$ candida...","url_abs":"https://arxiv.org/abs/2508.00130","url_pdf":"https://arxiv.org/pdf/2508.00130v1","authors":"[\"Drew Gao\",\"Yihang Sun\",\"Jan Vondrák\"]","published":"2025-07-31T19:36:37Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DM\"]","methods":"[]","has_code":false}