Chamberlin-Courant Winner Determination Decision Problem

Definition

Chamberlin-Courant Winner Determination Decision 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$, a committee size $k$, and an integer score threshold $s$, the Chamberlin-Courant winner determination decision problem asks whether some size-$k$ committee reaches the threshold under the Chamberlin-Courant approval voting rule.

For a committee $W\subseteq C$, its score is

\operatorname{score}_{\mathrm{CC}}(W)

:=
\left|\left{v_i\in V\mid A_i\cap W\neq\emptyset\right}\right|.

$$\ast \ast Question:\ast \ast does$$

\exists W\subseteq C:
\qquad |W|=k
\quad\land\quad
\operatorname{score}_{\mathrm{CC}}(W)\geq s

$$hold?$$

Certificate

A size-$k$ committee $W$ is a certificate. Scan each approval set and test whether $A_i\cap W$ is empty; this computes the score and checks the threshold in polynomial time.

Complexity

The problem belongs to NP. It is NP-hard by the reduction from Independent Set, and is therefore NP-complete.

The associated search problem asks for an optimal committee rather than merely asking whether a given score threshold is attainable.