Electing a committee with dominance constraints

Annals of Operations Research. 2022. Vol. 318. No. 2. P. 985–1000.

Ianovski E.

We consider the problem of electing a committee of k candidates, subject to constraints as to which committees are admissible for constitutional, conventional, or practical reasons. In our framework, the candidates are given labels as an abstraction of a politician’s religion, a film’s genre, a song’s language, or other attribute, and the election outcome is constrained by interval constraints (constraints of the form “Between 3 and 5 candidates with label X”) and dominance constraints (“At least as many candidates with label X as with label Y”). The goal is to select a committee that is as good as possible among those that satisfy the constraints. The difficulty is that in the standard social choice framework we do not have a quantifiable notion of “goodness”, only a voting rule that tells us which committee is the best. In this paper we argue how the logic underlying separable and best-k rules can be extended into an ordering of committees from best to worst, and study the question of how to select the best valid committee with respect to this order. The problem is NP-hard, but we show the existence of a polynomial time solution in the case of tree-like constraints, and a fixed-parameter tractable algorithm for the general case.

Keywords: social choice, voting, Computational Social Choice