Chamberlin-Courant Approval Voting Rule (COMSOC)

Definition

Chamberlin-Courant Approval Voting Rule (COMSOC)

The Chamberlin-Courant approval voting rule selects a committee $C^{\ast }\subseteq C$ maximising the total voter satisfaction by representing each voter through their most-preferred committee member, i.e.,

$$\mathrm{CC}(A_1,\dots ,A_n;k):=\underset{\begin{array}{c}{C}^{\ast }\subseteq C,\\ |C^{\ast }|=k\end{array}}{\mathrm{argmax}}\left|\{v_i\in V\mid A_i\cap C^{\ast }\ne \varnothing \}\right|.$$

Complexity

The Chamberlin-Courant approval voting rule is NP-complete.

Justified Representation

Justified Representation by Chamberlin-Courant Approval Voting Rule

The Chamberlin-Courant approval voting rule yields a justified representation.

Justified Representation by Chamberlin-Courant Approval Voting Rule

Let $C^{\ast }$ be a committee selected by the Chamberlin-Courant approval voting rule. Suppose, for contradiction, that $C^{\ast }$ does not satisfy justified representation.

Then there exists a cohesive voter group $V^{\prime }\subseteq V$ that is not represented by $C^{\ast }$. Since $V^{\prime }$ is cohesive, by definition,

$$|V^{\prime }|\ge \frac{|V|}{k}=\frac{n}{k}\text{and}\bigcap _{v_i\in V^{\prime }}{A}_i\ne \varnothing .$$

Since $V^{\prime }$ is not represented,

$$C^{\ast }\cap \bigcup _{v_i\in V^{\prime }}{A}_i=\varnothing .$$

Hence none of the $|V^{\prime }|$ voters is represented by $C^{\ast }$. Therefore at most

$$n-|V^{\prime }|$$

voters outside $V^{\prime }$ are represented.

Assign every represented voter to one committee member in $C^{\ast }$ that they approve. Since $|C^{\ast }|=k$, these at most $n-|V^{\prime }|$ represented voters are distributed among $k$ committee members. By the generalised pigeonhole principle, some $c\in C^{\ast }$ is assigned at most

$$\frac{n-|V^{\prime }|}{k}$$

voters.

Because $|V^{\prime }|\ge n/k$,

$$\frac{n-|V^{\prime }|}{k}\le \frac{n}{k}-\frac{|V^{\prime }|}{k}\le |V^{\prime }|-\frac{|V^{\prime }|}{k}<|V^{\prime }|.$$

Thus there is a committee member $c$ whose removal can make fewer than $|V^{\prime }|$ voters unrepresented.

Since

$$\bigcap _{v_i\in V^{\prime }}{A}_i\ne \varnothing ,$$

choose some candidate

$$c^{\prime }\in \bigcap _{v_i\in V^{\prime }}{A}_i.$$

Moreover, $c^{\prime }\notin C^{\ast }$, since otherwise every voter in $V^{\prime }$ would already be represented.

Consider the committee

$$C^{\prime }=(C^{\ast }\setminus \{c\})\cup \{c^{\prime }\}.$$

Removing $c$ makes at most $\frac{n-|V^{\prime }|}{k}$ previously represented voters unrepresented, while adding $c^{\prime }$ represents all $|V^{\prime }|$ voters, because every voter in $V^{\prime }$ approves $c^{\prime }$.

Since

$$|V^{\prime }|>\frac{n-|V^{\prime }|}{k},$$

the committee $C^{\prime }$ represents strictly more voters than $C^{\ast }$.

This contradicts the assumption that $C^{\ast }$ maximises the Chamberlin-Courant score. Therefore every Chamberlin-Courant winning committee satisfies justified representation