Computational Aspects of Multi-Winner Approval Voting (d4-conf-aaai-2014-0025)

Given candidates \(C\), committee size \(k\), rational finite-support masses \(\mu_A\) over approval types \(A\subseteq C\), and threshold \(q\), decide whether there exists an integral committee \(W\subseteq C\) with \(\lvert W\rvert=k\) and \(\sum_A\mu_A H_{\lvert W\cap A\rvert}\ge q\), where \(H_r=\sum_{j=1}^{r}1/j\); equivalently, compute a maximizing \(W\).

Definitions. An instance consists of a candidate set \(C\), a committee size \(k\), a finite list of approval types \(A\subseteq C\) with rational masses \(\mu_A\ge 0\) satisfying \(\sum_A\mu_A=1\), and a rational threshold \(q\). Let \(H_0=0\) and \(H_r=\sum_{j=1}^{r}1/j\). A committee \(W\subseteq C\) of size \(k\) has score \(S(W)=\sum_A\mu_AH_{\lvert W\cap A\rvert}\).

Target. Is deciding whether some \(W\subseteq C\) with \(\lvert W\rvert=k\) satisfies \(S(W)\ge q\) solvable in polynomial time, or is it NP-hard?

Nearest known results. For unweighted finite approval profiles, winner determination under proportional approval voting is NP-complete, even when every voter approves exactly two candidates.

Result

The decision problem is NP-complete, and hence NP-hard. Hardness holds even when every positive-mass approval type contains exactly two candidates.

NP-hardness

We use the NP-completeness result supplied in the question for the unweighted PAV threshold problem.

An unweighted instance consists of a candidate set \(C\), a committee size \(k\), explicitly listed voters with approval sets \(A_1,\ldots,A_n\), and a threshold \(T\). Its question is whether some committee \(W\) of size \(k\) satisfies
\[ \sum_{i=1}^{n}H_{|W\cap A_i|}\ge T. \]
We may assume \(n\ge 1\): instances with no voters have constant score zero and can be decided directly.

For each distinct approval set \(A\) occurring in the profile, let
\[ c_A=\bigl|\{i:A_i=A\}\bigr|. \]
Construct a target instance with the same \(C\) and \(k\), and set
\[ \mu_A=\frac{c_A}{n}, \qquad q=\frac{T}{n}. \]
These masses are nonnegative rationals, and
\[ \sum_A\mu_A=\frac{\sum_Ac_A}{n}=1. \]
Thus the constructed instance satisfies the required normalization.

For every committee \(W\) of size \(k\),
\[ S(W) =\sum_A\frac{c_A}{n}H_{|W\cap A|} =\frac1n\sum_{i=1}^{n}H_{|W\cap A_i|}. \]
Since \(n>0\), it follows that
\[ S(W)\ge q \quad\Longleftrightarrow\quad \sum_{i=1}^{n}H_{|W\cap A_i|}\ge T. \]
Consequently, the original instance is a yes-instance exactly when the constructed instance is a yes-instance.

The construction takes polynomial time: identical approval sets can be grouped in polynomial time, each count \(c_A\) is at most \(n\), and dividing the input threshold by \(n\) adds at most \(O(\log n)\) bits to its representation. If every original voter approves exactly two candidates, every resulting approval type also contains exactly two candidates. The supplied hardness result therefore applies.

Membership in NP

A certificate is a committee \(W\). We first check that \(W\subseteq C\) and \(|W|=k\). It remains to show that its score can be compared with \(q\) exactly in polynomial time.

Let \(m=|C|\), and write the listed masses and threshold as
\[ \mu_{A_i}=\frac{a_i}{b_i}\quad(1\le i\le t), \qquad q=\frac{u}{v}, \]
with positive integer denominators. Define
\[ D=m!\,v\prod_{i=1}^{t}b_i. \]
Every denominator \(j\) occurring in any \(H_r\), where \(r\le m\), divides \(m!\). Therefore
\[ D S(W) = \sum_{i=1}^{t} a_i\sum_{j=1}^{|W\cap A_i|} \frac{D}{b_i j}, \qquad Dq=\frac{Du}{v} \]
are integers, with every displayed division exact.

The bit length of \(D\) is at most
\[ O\!\left(m\log(m+1)+\log v+\sum_{i=1}^{t}\log b_i\right), \]
which is polynomial in the explicit input length. There are at most \(tm\) summands, and their numerators also have polynomial bit length. Standard integer arithmetic therefore computes and compares these integers in polynomial time. Because \(D>0\), this comparison decides whether \(S(W)\ge q\).

Thus the problem belongs to NP. Combined with the reduction above, this proves NP-completeness.

⟨structured verdict parsed — rendered above⟩

The prover resolves the target correctly. The reduction establishes NP-hardness, including the restriction to approval types of size two, and the certificate verification establishes membership in NP. No substantive or expositional repairs are needed.

• Use of the supplied hardness result. The prover explicitly states the unweighted threshold problem used as the source. This is the decision version of the PAV winner-determination result supplied in the task. Its candidates, committee size, approval sets, and harmonic score agree with the target definitions. No additional theorem hypotheses are introduced.

Restricting to profiles with \(n\ge 1\) is harmless: profiles without voters have identically zero score, and their feasibility and threshold conditions can be decided directly.

• Validity of the constructed instance. Grouping voters with identical approval sets gives positive integer counts \(c_A\) satisfying \(\sum_A c_A=n\). Therefore the proposed masses \(\mu_A=c_A/n\) are rational, nonnegative, and sum to one. The threshold \(q=T/n\) is rational. Retaining \(C\) and \(k\) preserves the feasible committees.

• Correctness of the reduction. For every feasible committee \(W\), grouping equal approval sets yields exactly

\[ S(W)=\frac{1}{n}\sum_{i=1}^{n}H_{\lvert W\cap A_i\rvert}. \]
Since \(n>0\), comparison against \(q=T/n\) preserves the threshold inequality in both directions. Thus the reduction preserves both yes-instances and no-instances.

• Polynomial size and running time. Under the explicit input representation used in the task and proof, grouping approval sets takes polynomial time. There are at most \(n\) resulting types, and each count and mass denominator requires \(O(\log(n+1))\) bits. Dividing the source threshold by \(n\) increases its representation length by at most that amount. The construction is consequently a polynomial-time reduction.

Grouping does not change any approval set, so the restriction that each voter approves exactly two candidates transfers to every resulting positive-mass type.

• Certificate verification and exact arithmetic. A committee has polynomial representation length, and checking containment and cardinality takes polynomial time. After those checks, every intersection size is at most \(m=\lvert C\rvert\).

The proposed positive integer
\[ D=m!\,v\prod_{i=1}^{t}b_i \]
clears every relevant denominator: for each summand, \(j\) divides \(m!\), and \(b_i\) is a factor of the denominator product. Thus \(D/(b_i j)\) is an integer. The displayed formulas for \(DS(W)\) and \(Dq\) are correct.

The bit-length bound is polynomial in the explicit input length. Including the input numerators and adding at most \(tm\) terms still gives integers of polynomial bit length. Exact computation and comparison therefore take polynomial time.

• Edge cases and conclusion. Zero masses contribute zero. Empty intersections use the empty sum, matching \(H_0=0\). If \(m=0\), the definition \(0!=1\) keeps the denominator construction valid. Infeasible committee sizes fail the certificate check. Negative thresholds cause no difficulty because the comparison uses signed integers and a positive multiplier.

Both NP-hardness and NP membership are established, so the claimed NP-completeness follows.

⟨structured verdict parsed — rendered above⟩