The Complexity of Proportionality Degree in Committee Elections
Abstract
Over the last few years, researchers have put significant effort into understanding of the notion of proportional representation in committee election. In particular, recently they have proposed the notion of proportionality degree. We study the complexity of computing committees with a given proportionality degree and of testing if a given committee provides a particular one. This way, we complement recent studies that mostly focused on the notion of (extended) justified representation. We also study the problems of testing if a cohesive group of a given size exists and of counting such groups.
Cite
Text
Janeczko and Faliszewski. "The Complexity of Proportionality Degree in Committee Elections." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I5.20442Markdown
[Janeczko and Faliszewski. "The Complexity of Proportionality Degree in Committee Elections." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/janeczko2022aaai-complexity/) doi:10.1609/AAAI.V36I5.20442BibTeX
@inproceedings{janeczko2022aaai-complexity,
title = {{The Complexity of Proportionality Degree in Committee Elections}},
author = {Janeczko, Lukasz and Faliszewski, Piotr},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2022},
pages = {5092-5099},
doi = {10.1609/AAAI.V36I5.20442},
url = {https://mlanthology.org/aaai/2022/janeczko2022aaai-complexity/}
}