Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.06194 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909021811769344 |
|---|---|
| author | Becker, Patrick Greger, Matthias Peters, Dominik |
| author_facet | Becker, Patrick Greger, Matthias Peters, Dominik |
| contents | In an approval-based committee election, the task is to select a committee of up to $k$ candidates from a set of $m$ candidates based on the preferences of $n$ voters, each of whom approves a subset of the candidates. A central open question is whether there always exists a committee in the core, a stability notion capturing proportional representation. We prove core non-emptiness for all approval-based committee elections with at most five voters. The proof is based on affine monoid methods and shows that, for $n\le5$, every fractional committee admits a deterministic rounding to an integral committee that preserves each voter's utility up to floors. We extend our argument to the weighted voter setting, which implies core existence for instances with up to five distinct approval sets. In all these cases, a core committee can be computed in polynomial time. We show that our technique cannot be extended as-is: our rounding method breaks down for $n=6$, and for $n=3$ when applied to more general models with additive valuations or non-unit candidate costs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06194 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Core Existence in Approval-Based Committee Elections with up to Five Voter Types Becker, Patrick Greger, Matthias Peters, Dominik Computer Science and Game Theory In an approval-based committee election, the task is to select a committee of up to $k$ candidates from a set of $m$ candidates based on the preferences of $n$ voters, each of whom approves a subset of the candidates. A central open question is whether there always exists a committee in the core, a stability notion capturing proportional representation. We prove core non-emptiness for all approval-based committee elections with at most five voters. The proof is based on affine monoid methods and shows that, for $n\le5$, every fractional committee admits a deterministic rounding to an integral committee that preserves each voter's utility up to floors. We extend our argument to the weighted voter setting, which implies core existence for instances with up to five distinct approval sets. In all these cases, a core committee can be computed in polynomial time. We show that our technique cannot be extended as-is: our rounding method breaks down for $n=6$, and for $n=3$ when applied to more general models with additive valuations or non-unit candidate costs. |
| title | Core Existence in Approval-Based Committee Elections with up to Five Voter Types |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2605.06194 |