Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness

Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness

Yongjie Yang, Jianxin Wang

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 576-582. https://doi.org/10.24963/ijcai.2018/80

Multiwinner voting aims to select a subset of candidates (the winners) from admissible sets, according to the votes cast by voters. A special class of multiwinner rules—the k-committee selection rules where the number of winners is predefined—have gained considerable attention recently. In this setting, the admissible sets are all subsets of candidates of size exactly k. In this paper, we study admissible sets with combinatorial restrictions. In particular, in our setting, we are given a graph G whose vertex set is the candidate set. Admissible sets are the subsets of candidates whose induced subgraphs belong to some special class G of graphs. We consider different graph classes G and investigate the complexity of multiwinner determination problem for prevalent voting rules in this setting. In addition, we investigate the strategyproofness of many rules for different classes of admissible sets.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice