When far is better: The Chamberlin-Courant approach to obnoxious committee selection

Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance as ``far is better''. Formally stated, we initiate the study of ``obnoxious'' committee scoring rules when the voters' preferences are expressed via a metric space. To this end, we propose a model where large distances imply high satisfaction and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value 1 k, the committee size k, a voter derives satisfaction from only the -th favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of = 1, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a d-dimensional Euclidean space. We show that when is 1 and k, the problem is polynomial-time solvable in R² and general metric space, respectively. However, for = k-1, it is NP-hard even in R². Thus, we have ``double-dichotomy'' in R² with respect to the value of, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be ``tight'' for R² because the problem is NP-hard for general metric space, even for =1. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations.