An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections

Michal Tomasz Godziszewski, Pawel Batko, Piotr Skowron, Piotr Faliszewski

AAAI 2021 pp. 5448-5455

doi:10.1609/AAAI.V35I6.16686 /aaai/2021/godziszewski2021aaai-analysis/

Abstract

We study approval-based committee elections for the case where the voters' preferences come from a 2D-Euclidean model. We consider two main issues: First, we ask for the complexity of computing election results. Second, we evaluate election outcomes experimentally, following the visualization technique of Elkind et al., (AAAI-2017). Regarding the first issue, we find that many NP-hard rules remain intractable for 2D-Euclidean elections. For the second one, we observe that the behavior and nature of many rules strongly depends on the exact protocol for choosing the approved candidates.

PDF AAAI Semantic Scholar

Cite

Text

Godziszewski et al. "An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I6.16686

Markdown

[Godziszewski et al. "An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/godziszewski2021aaai-analysis/) doi:10.1609/AAAI.V35I6.16686

BibTeX

@inproceedings{godziszewski2021aaai-analysis,
  title     = {{An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections}},
  author    = {Godziszewski, Michal Tomasz and Batko, Pawel and Skowron, Piotr and Faliszewski, Piotr},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {5448-5455},
  doi       = {10.1609/AAAI.V35I6.16686},
  url       = {https://mlanthology.org/aaai/2021/godziszewski2021aaai-analysis/}
}