The Complexity of Election Problems with Group-Separable Preferences

The Complexity of Election Problems with Group-Separable Preferences

Piotr Faliszewski, Alexander Karpov, Svetlana Obraztsova

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 203-209. https://doi.org/10.24963/ijcai.2020/29

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.
Keywords:
Agent-based and Multi-agent Systems: Voting
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory