Near-Tight Algorithms for
the Chamberlin-Courant and Thiele Voting Rules^††thanks: A conference version of this work appears in IJCAI 2022 [48].

We study computational aspects of the Chamberlin-Courant voting rule (CC) [13] with general misrepresentation function and the Thiele rules [49] in which we choose a committee of size $k$ such that the total utility of the voters is maximized. In the case of CC, the utility of a voter from a committee is determined by the most preferred committee member. In the case of a $w$-Thiele rule, parameterized by a non-increasing sequence $w=(w_{1},w_{2},\dots)$, the utility of a voter is equal to $w_{1}+w_{2}+\dots+w_{x}$, where $x$ is the number of committee members approved by the voter.

CC and Thiele rules are basic multiwinner voting rules studied in social choice theory and, in particular, in the computational social choice community [26, 11]. They were discussed broadly for their applications, not only in parliamentary elections but also in many scenarios when a group of agents has to pick some number of items for joint use [47].

Unfortunately, computing an optimal committee under CC is already $\mathsf{NP}$-hard for the case of approval ballots, i.e., when each voter gives a subset of approved candidates [43]. This special case is called Approval Chamberlin-Courant (Approval-CC) and it was considered by Procaccia et al. [43] as a minimization problem. Its maximization version is equivalent to the well-known Max $k$-Coverage problem for which many hardness results have been shown [46]. In particular, Max $k$-Coverage is $\mathsf{NP}$-hard¹¹1$\mathsf{NP}$-hardness of Max $k$-Coverage directly implies $\mathsf{NP}$-hardness of Approval-CC. This consequence was mentioned (without a proof) in the conference paper of Procaccia et al. [42]. to approximate within $(1-1/e+\varepsilon)$ factor for any $\varepsilon>0$ [27]. Moreover, this hardness of approximation holds even in FPT-time with respect to solution size $k$ assuming a gap version of the Exponential Time Hypothesis [36].

Notice that Approval-CC is equivalent to the $(1,0,\dots)$-Thiele rule, so all these hardness results for Approval-CC hold for this basic Thiele rule as well. One may consider other $w$-Thiele rules with specific $w$, e.g., $w$-Thiele rule with $w_{i}=1/i$ which is equivalent to the well-known Proportional Approval Voting [35] and $w_{i}=1/i^{2}$ which is related to Penrose apportionment method [11]. Notice that $(1,1,\dots)$-Thiele is equivalent to Multiwinner Approval Voting [4], which is solvable in polynomial-time. All the other ones²²2 We assume $w_{1}=1$ without loss of generality. are $\mathsf{NP}$-hard [47, Theorem 5].

Analogously to Max $k$-Coverage, hardness of approximation results hold for the natural class of $w$ sequences such that partial sums of $w$ grows in a sublinear way, where a hardness constant depends strictly on $w$ [20, 5, 6]. It follows that for such Thiele rules one should not expect a PTAS nor even an FPT-approximation scheme.

Because of the hardness of CC and Thiele rules, both rules were studied in restricted domains, i.e., on preference profiles with certain structures, e.g., single-peaked (SP) and single-crossing (SC). For a survey on structured preferences, see [24]. Such restricted domains are motivated by real-world elections. For instance, SP preference profiles appear when, intuitively, the candidates can be placed on an one-dimensional axis, and the farther away a candidate is from a voter’s favorite candidate the more the voter dislikes the candidate. Examples of such SP-axis are different policies in an ideological spectrum: the Left vs the Right, more liberal vs more conservative etc.

Fortunately, CC and Thiele rules on SP domain (CC-SP and Thiele-SP respectively) are known to be polynomial-time solvable [7, 39]. However, the dynamic programming algorithm for CC-SP proposed by Betzler et al. [7] is not optimal in terms of running time. We fill this gap by showing an almost optimal algorithm and we study polynomial-time solvability for nearly single-peaked preference profiles for CC and Thiele rules.

First we introduce some notations and define the computational problems formally. The $\tilde{\mathcal{O}}$ notation suppresses factors subpolynomial in the input size, i.e., factors $(nm)^{o(1)}$. The $\mathcal{O}^{*}$ notation suppresses factors polynomial in the input size, i.e., factors $(nm)^{\mathcal{O}(1)}$.

In this section we present our algorithm for CC-SP that is almost optimal under the assumption that an SP-axis is given in the input or at least one vote is a linear order. In the latter case we can find an SP-axis in $\mathcal{O}(nm)$ time, otherwise, if all votes are weak orders we do this in $\mathcal{O}(nm^{2})$ time [28]. This is a bottle-neck for our algorithm. In such a case, we obtain the same $\mathcal{O}(nm^{2})$ running time as the original dynamic programming approach of Betzler et al. [7].

We first label the candidates so that $c_{1}\prec c_{2}\prec\cdots\prec c_{m}$ with respect to the SP-axis. For simplicity of our analysis, we add an artificial candidate $c_{0}\prec c_{1}$ so that $r(v,c_{0})=U$ for any $v\in V$, where $U$ is the maximum value of misrepresentation. Similarly, we add another artificial candidate $c_{m+1}\succ c_{m}$ so that $r(v,c_{m+1})=U$ for any $v\in V$. After the additions, the profile is still single-peaked and the solution to the SP-CC instance does not change.

We first reduce CC-SP to the well-studied Minimum Weight $t$-Link Path problem which is defined as follows.

We create a graph on vertex set $\{0,\ldots,m+1\}$. For every $i,j$ where $0\leq i<j\leq m+1$, we add an edge from $i$ to $j$ with weight $w(i,j)=r(\{c_{i},c_{j}\}))-r(\{c_{i}\})$. We let the source vertex be vertex $0$ and let the target vertex be vertex $m+1$. We set $t=k+1$. To show the correctness of this reduction, we use the following claim which is a key consequence of SP.

The following lemma shows the correctness of our reduction from CC-SP to Minimum Weight $t$-Linked Path.

By Lemma 4, it suffices to compute the minimum weight $t$-link path of the auxiliary graph. To do so efficiently, we use the fact that the edge weights have a certain structure.

By Lemma 5, we can use the $m^{1+o(1)}$ time algorithm for the Minimum Weight $t$-Link Path instance (we use the algorithm by Schieber [45] for the case where $k=\Omega(\log m)$ and use the algorithm by Aggarwal and Park [1] for the case where $k=\mathcal{O}(\log(m))$). Note that by a brute-force algorithm, we can compute each edge weight in $\mathcal{O}(n)$ time, so the overall running time becomes $nm^{1+o(1)}$. The subpolynomial factor in this running time is $2^{\mathcal{O}(\sqrt{\log(k)\log\log(m)})}$ when $k=\Omega(\log(m))$, which can be quite large. The following lemma gives a way to compute the edge weights faster, and consequently improves the subpolynomial factor.

In the real-RAM model of computation we consider in this paper, we can use any standard sorting algorithm to sort $n$ integers in $\mathcal{O}(n\log(n))$ time, so the pre-processing time of Lemma 6 becomes $\mathcal{O}(nm\log(n))$. In the word-RAM model of computation, faster algorithms for sorting integers are known. For instance, it is known that $\operatorname*{Int\-Sort}(n,nm)=\mathcal{O}(n\sqrt{\log\log(n)})$ [30]. Also, in a common case where $m=\operatorname*{poly}(n)$, $\operatorname*{Int\-Sort}(n,nm)=\mathcal{O}(n)$ by radix sort. One may use such faster integer sorting algorithms to obtain faster running time for the overall algorithm in the word-RAM model of computation, when all misrepresentations are given as integers (e.g. when we use Borda misrepresentation function).

Combining Lemma 6 with previous ideas we obtain the following theorem.

Betzler et al. [7] showed that Approval-CC is ${\mathsf{W}}[2]$-hard w.r.t. $k$. Their reduction is from the Hitting Set problem (HS), in which we are given a family $\mathcal{F}=\{F_{1},\dots F_{n}\}$ of sets over a universe $U=\{u_{1},\dots,u_{m}\}$ and a positive integer $k$, and the task is to decide whether there exists a size-$k$ subset $U^{\prime}\subseteq U$ such that $U^{\prime}\cap F_{i}\neq\emptyset$ for every $F_{i}\in\mathcal{F}$.

Actually, the reduction presented by Betzler et al. [7] also works for the Monroe rule. This makes the reduction more complex than it is needed for Approval-CC. A simple reduction from HS to Approval-CC has a strict correspondence between a universe and candidates, and between a family of sets and voters. A voter approves a candidate if the corresponding set to the voter contains the corresponding element to the candidate. The misrepresentation bound is equal to $0$ as this will require to cover (hit) all the voters (sets). Because of this correspondence, Approval-CC with $R=0$ is equivalent to HS.

It was observed recently [29] that, assuming Set Cover Conjecture (SCC) there is no $\mathcal{O}^{*}((2-\varepsilon)^{n})$-time algorithm for Approval-CC or Borda-CC, for every $\varepsilon>0$. This observation follows directly from the reductions presented by Betzler et al. [7] and SCC-hardness of HS [17, Conjecture 14.36]. On the other hand, for general misrepresentation function, Betzler et al. [7] showed an $\mathcal{O}^{*}(n^{n})$-time algorithm. An interesting open question is to close this gap for general misrepresentation functions. Note that for the case of Borda-CC, Gupta et al. [29] showed an $\mathcal{O}^{*}(2^{n})$-time algorithm.

Below, we observe the SETH-hardness of CC, due to the SETH-hardness of HS [16] and the reduction of Betzler et al. [7].

It means that the $\mathcal{O}^{*}(2^{m})$-time brute-force algorithm, which checks all size-$k$ subsets of candidates, is essentially optimal for CC in terms of parameter $m$. On the other hand, for CC-SP we showed an almost optimal algorithm (Theorem 8). Hence, it is natural to study computational complexity of CC on preferences that are close to SP in terms of the candidate-deletion operation.

We assume that a candidate-deletion set is given as this makes the problem formulation as general as possible. Otherwise, finding the minimum size candidate-deletion set would be a bottleneck for our algorithm as, in general, the problem is ${\mathsf{NP}}$-hard. The hardness follows from the observation that the problem with approval ballots is equivalent to the problem of deleting a minimum number of columns to transform a given binary matrix into a matrix with the consecutive ones property (Min-COS-C). For an overview on the computational complexity of Min-COS-C see, e.g., [18]. An interesting hardness result for Min-COS-C described therein is that an $\alpha$-approximation algorithm for Min-COS-C derives an $\alpha/2$-approximate solution to the Vertex Cover problem. As a consequence, it is ${\mathsf{NP}}$-hard to approximate the smallest candidate-deletion set within a factor of $2.72$ [33] and it is Unique Games Conjecture-hard to approximate within a factor of $4-\epsilon$, for every $\epsilon>0$ [34]. The hardness holds already for approval preferences, where each voter approves at most $2$ candidates. On the other hand, we can compute the minimum size candidate-deletion set in polynomial-time if all votes are linear orders [44, 25]. This holds, e.g., when the misrepresentation function is derived from a committee scoring rule [22] where a classic example is Borda scoring rule used in Borda-CC.

In the following theorem we show that CC is FPT w.r.t. the size of a given candidate-deletion set⁷⁷7This result was presented before by Misra et al. [37], however our construction is well-suited for generalization to Thiele rules presented in Section 5, so we provide a proof for completeness. (denoted by $D$) and the obtained algorithm is essentially optimal assuming SETH. The main idea of the algorithm is to: 1) guess pre-elected winners among $D$; 2) delete $D$ from the instance together with appropriate modification of the instance with respect to the pre-elected winners; 3) as the modified instance appears to be a CC-SP instance, we use our algorithm from Theorem 8.