ML Anthology

The Complexity of Election Problems with Group-Separable Preferences

Piotr Faliszewski, Alexander Karpov, Svetlana Obraztsova
IJCAI 2020 pp. 203-209
doi:10.24963/IJCAI.2020/29 /ijcai/2020/faliszewski2020ijcai-complexity/

Abstract

We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height.

PDF IJCAI Semantic Scholar

Cite

Text

Faliszewski et al. "The Complexity of Election Problems with Group-Separable Preferences." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/29

Markdown

[Faliszewski et al. "The Complexity of Election Problems with Group-Separable Preferences." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/faliszewski2020ijcai-complexity/) doi:10.24963/IJCAI.2020/29

BibTeX

@inproceedings{faliszewski2020ijcai-complexity,
  title     = {{The Complexity of Election Problems with Group-Separable Preferences}},
  author    = {Faliszewski, Piotr and Karpov, Alexander and Obraztsova, Svetlana},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {203-209},
  doi       = {10.24963/IJCAI.2020/29},
  url       = {https://mlanthology.org/ijcai/2020/faliszewski2020ijcai-complexity/}
}