Proportional Approval Voting Rule (COMSOC)

Definition

Proportional Approval Voting Rule (COMSOC)

The proportional approval voting rule selects a committee $C^{\ast }\subseteq C$ maximising the total voter satisfiaction while giving diminishing returns for each additional approved committee member

$$\mathrm{CC}(A_1,\dots ,A_n;k):=\underset{\begin{array}{c}{C}^{\ast }\subseteq C,\\ |C^{\ast }|=k\end{array}}{\mathrm{argmax}}\sum _{v_i\in V}\sum _{j=1}^{|A_i\cap C^{\ast }|}\frac{1}{j}.$$

Complexity

The proportional approval voting rule is NP-complete.

Justified Representation

Justified Representation by Proportional Approval Voting Rule

The proportional approval voting rule yields a justified representation.

Justified Representation by Proportional Approval Voting Rule

Let $C^{\ast }$ be a committee selected by the proportional 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 }$. Hence,

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

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

$$A_i\cap C^{\ast }=\varnothing \text{for every }{v}_i\in V^{\prime }.$$

For every voter $v_i\notin V^{\prime }$, let

$$t_i=|A_i\cap C^{\ast }|$$

denote the number of approved committee members. If an elected candidate $c\in A_i\cap C^{\ast }$ is removed, the PAV contribution of $v_i$ decreases from

$$1+\frac{1}{2}+\cdots +\frac{1}{t_i}$$

to

$$1+\frac{1}{2}+\cdots +\frac{1}{t_i-1}.$$

Hence removing such a candidate decreases the score of $v_i$ by exactly

$$\frac{1}{t_i}.$$

For each $c\in C^{\ast }$, let $\Delta (c)$ denote the total PAV score lost by removing $c$:

$$\Delta (c):=\mathrm{PAV}(C^{\ast })-\mathrm{PAV}(C^{\ast }\setminus \{c\}).$$

Consider the sum of these losses over all $k$ committee members. A represented voter $v_i$ approves exactly $t_i$ members of $C^{\ast }$ and therefore contributes

$$t_i\cdot \frac{1}{t_i}=1$$

to

$$\sum _{c\in C^{\ast }}\Delta (c).$$

An unrepresented voter contributes $0$. Since none of the $|V^{\prime }|$ voters in $V^{\prime }$ is represented, at most $n-|V^{\prime }|$ voters contribute. Therefore

$$\sum _{c\in C^{\ast }}\Delta (c)\le n-|V^{\prime }|.$$

Since $|C^{\ast }|=k$, the generalised pigeonhole principle implies that some $c\in C^{\ast }$ satisfies

$$\Delta (c)\le \frac{n-|V^{\prime }|}{k}.$$

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

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

Hence,

$$\Delta (c)<|V^{\prime }|.$$

Since $V^{\prime }$ is cohesive,

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

so choose

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

Since $V^{\prime }$ is not represented by $C^{\ast }$, we have $c^{\prime }\notin C^{\ast }$.

Now consider the committee

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

Removing $c$ decreases the PAV score by $\Delta (c)$. Adding $c^{\prime }$ gives every voter in $V^{\prime }$ their first approved committee member, so each gains PAV score

$$1.$$

Therefore adding $c^{\prime }$ increases the PAV score by at least

$$|V^{\prime }|.$$

Since

$$|V^{\prime }|>\Delta (c),$$

we obtain

$$\mathrm{PAV}(C^{\prime })>\mathrm{PAV}(C^{\ast }),$$

contradicting the optimality of $C^{\ast }$.

Therefore every committee selected by proportional approval voting satisfies justified representation

Extended Justified Representation

Extended Justified Representation by Proportional Approval Voting Rule

The proportional approval voting rule yields a extended justified representation.