Chamberlin-Courant Winner Determination Search Problem

Definition

Chamberlin-Courant Winner Determination Search Problem

Given an approval election with candidate set $C$, voters $V=\{v_1,\dots ,v_n\}$, approval sets $A_1,\dots ,A_n\subseteq C$, and a committee size $k$, output a size-$k$ committee $W^{\ast }\subseteq C$ that maximises the Chamberlin-Courant score:

$$W^{\ast }\in \underset{\begin{array}{c}W\subseteq C;|W|=k\end{array}}{\mathrm{argmax}}\left|\left\{v_i\in V\mid A_i\cap W\ne \varnothing \right\}\right|.$$

If several committees attain the maximum, outputting any one of them is valid. Thus the output is one committee tied for the maximum score, not necessarily the complete set of tied committees.

Evaluating a Committee

For a proposed committee $W$, the score is the number of voters whose approval set intersects $W$:

$${\mathrm{score}}_{\mathrm{CC}}(W)=\sum _{i=1}^n[A_i\cap W\ne \varnothing ],$$

where $[P]=1$ when the predicate $P$ is true and $[P]=0$ otherwise. Hence evaluating one proposed committee is polynomial; the difficulty is finding a committee with maximum score.

Complexity

The search problem is NP-hard when $k$ is part of the input. A polynomial-time algorithm for it would also solve the decision problem: compute an optimal committee and compare its score with the requested threshold.

An exhaustive algorithm examines all $\left(\genfrac{}{}{0ex}{}{|C|}{k}\right)$ committees. With $m=|C|$ and $n=|V|$, scoring every committee by scanning all approval sets takes

$$O\left(\left(\genfrac{}{}{0ex}{}{m}{k}\right)nm\right)$$

time under an explicit representation of the approval sets. This is polynomial for fixed $k$, but not when $k$ varies with the input.