Proportional Winner Determination Decision Problem

Definition

Proportional 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 a rational score threshold $s$, the proportional winner determination decision problem asks whether some size-$k$ committee reaches the threshold under Proportional Approval Voting (PAV).

Let

$$H_t:=\sum _{j=1}^t\frac{1}{j},H_0:=0$$

be the $t$th harmonic number. For a committee $W\subseteq C$, its PAV score is

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

Question: does

$$\exists W\subseteq C:|W|=k\wedge {\mathrm{score}}_{\mathrm{PAV}}(W)\ge s$$

hold?

Certificate

A size-$k$ committee $W$ is a certificate. Compute $t_i=|A_i\cap W|$ for every voter and add $H_{t_i}$. The resulting rational score can be compared with the binary-encoded threshold in polynomial time. For example, all denominators can be bounded by a common denominator built from $1,\dots ,k$, whose binary length is polynomial in $k$.

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.