Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting

Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting

Yongjie Yang

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 637-643. https://doi.org/10.24963/ijcai.2019/90

We study the complexity of several manipulation and control problems for six prevalent approval based multiwinner voting rules. We show that these rules generally resist the proposed strategic types. In addition, we also give fixed-parameter tractability results for these problems with respect to several natural parameters and derive polynomial-time algorithms for certain special cases.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory