Computation of Approximately Stable Committees in Approval-based Elections

2025/07/31 by Gao, Drew, Yihang Sun, Jan Vondrák +2 · 1 citation
Economics, Econometrics and Finance · Physics and Astronomy · Social Sciences · #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #Electoral Systems and Political Participation #FOS: Computer and information sciences #Game Theory and Voting Systems #Opinion Dynamics and Social Influence

paper · pdf · doi:10.48550/arxiv.2508.00130

openalex publication_date 2025/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Approval-based committee selection is a model of significant interest in social choice theory. In this model, we have a set of voters V, a set of candidates C, and each voter has a set A_v ⊂ 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 approximate stability, where a committee is λ-approximately-stable if there is no other committee T preferred by at least (λ|T|)/(k) |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.

Citations

• Computing Lindahl Equilibrium for Public Goods with and without Funding Caps
• Six Candidates Suffice to Win a Voter Majority
• Approximate Core for Committee Selection via Multilinear Extension and Market Clearing
• Proportionality and the Limits of Welfarism
• Approximately Stable Committee Selection
• The Core of Approval-Based Committee Elections with Few Seats

Cited by

• Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium

Related

• Approximately Stable Committee Selection
• Approval-Based Committee Voting under Uncertainty
• Robust Committee Voting, or The Other Side of Representation
• The Core of Approval-Based Committee Elections with Few Seats
• Approval-Based Committee Voting under Incomplete Information