Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.11625 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912645114757120 |
|---|---|
| author | Springham, Drew Elkind, Edith de Keijzer, Bart Polukarov, Maria |
| author_facet | Springham, Drew Elkind, Edith de Keijzer, Bart Polukarov, Maria |
| contents | In multiwinner approval elections with many candidates, voters may struggle to determine their preferences over the entire slate of candidates. It is therefore of interest to explore which (if any) fairness guarantees can be provided under reduced communication. In this paper, we consider voters with one-dimensional preferences: voters and candidates are associated with points in $\mathbb R$, and each voter's approval set forms an interval of $\mathbb R$. We put forward a probabilistic preference model, where the voter set consists of $σ$ different groups; each group is associated with a distribution over an interval of $\mathbb R$, so that each voter draws the endpoints of her approval interval from the distribution associated with her group. We present an algorithm for computing committees that provide Proportional Justified Representation + (PJR+), which proceeds by querying voters' preferences, and show that, in expectation, it makes $\mathcal{O}(\log( σ\cdot k))$ queries per voter, where $k$ is the desired committee size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11625 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multiwinner Voting with Interval Preferences under Incomplete Information Springham, Drew Elkind, Edith de Keijzer, Bart Polukarov, Maria Computer Science and Game Theory In multiwinner approval elections with many candidates, voters may struggle to determine their preferences over the entire slate of candidates. It is therefore of interest to explore which (if any) fairness guarantees can be provided under reduced communication. In this paper, we consider voters with one-dimensional preferences: voters and candidates are associated with points in $\mathbb R$, and each voter's approval set forms an interval of $\mathbb R$. We put forward a probabilistic preference model, where the voter set consists of $σ$ different groups; each group is associated with a distribution over an interval of $\mathbb R$, so that each voter draws the endpoints of her approval interval from the distribution associated with her group. We present an algorithm for computing committees that provide Proportional Justified Representation + (PJR+), which proceeds by querying voters' preferences, and show that, in expectation, it makes $\mathcal{O}(\log( σ\cdot k))$ queries per voter, where $k$ is the desired committee size. |
| title | Multiwinner Voting with Interval Preferences under Incomplete Information |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.11625 |