Well-Structured Committees

Well-Structured Committees

Sushmita Gupta, Pallavi Jain, Saket Saurabh

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

In the standard model of committee selection, we are given a set of ordinal votes over a set of candidates and a desired committee size, and the task is to select a committee that relates to the given votes. Motivated by possible interactions and dependencies between candidates, we study a generalization of committee selection in which the candidates are connected via a network and the task is to select a committee that relates to the given votes while also satisfy certain properties with respect to this candidate network. To accommodate certain correspondences to the voter preferences, we consider three standard voting rules (in particular, $k$-Borda, Chamberlin-Courant, and Gehrlein stability); to model different aspects of interactions and dependencies between candidates, we consider two graph properties (in particular, Independent Set and Connectivity). We study the parameterized complexity of the corresponding combinatorial problems and discuss certain implications of our algorithmic results.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice