Multiwinner Voting with Interval Preferences under Incomplete Information

Drew Springham, Edith Elkind, Bart De Keijzer, Maria Polukarov
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6512-6536, 2026.

Abstract

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 k)$ queries per voter, where $k$ is the desired committee size.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-springham26a, title = {Multiwinner Voting with Interval Preferences under Incomplete Information}, author = {Springham, Drew and Elkind, Edith and De Keijzer, Bart and Polukarov, Maria}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6512--6536}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/springham26a/springham26a.pdf}, url = {https://proceedings.mlr.press/v337/springham26a.html}, abstract = {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 k)$ queries per voter, where $k$ is the desired committee size.} }
Endnote
%0 Conference Paper %T Multiwinner Voting with Interval Preferences under Incomplete Information %A Drew Springham %A Edith Elkind %A Bart De Keijzer %A Maria Polukarov %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-springham26a %I PMLR %P 6512--6536 %U https://proceedings.mlr.press/v337/springham26a.html %V 337 %X 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 k)$ queries per voter, where $k$ is the desired committee size.
APA
Springham, D., Elkind, E., De Keijzer, B. & Polukarov, M.. (2026). Multiwinner Voting with Interval Preferences under Incomplete Information. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6512-6536 Available from https://proceedings.mlr.press/v337/springham26a.html.

Related Material