Proportional Winner Determination Search Problem

Definition

Proportional 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 PAV score:

$$W^{\ast }\in \underset{\begin{array}{c}W\subseteq C;|W|=k\end{array}}{\mathrm{argmax}}\sum _{i=1}^n{H}_{|A_i\cap W|},H_t:=\sum _{j=1}^t\frac{1}{j},H_0:=0.$$

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$, count the selected approved candidates for each voter:

$$t_i:=|A_i\cap W|,{\mathrm{score}}_{\mathrm{PAV}}(W)=\sum _{i=1}^n{H}_{t_i}.$$

The score of one committee is therefore computable in polynomial time. The hard part is selecting the committee whose score is largest.

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, apart from the polynomial-bit arithmetic needed for the harmonic values. This is polynomial for fixed $k$, but not when $k$ varies with the input.