Robustness Among Multiwinner Voting Rules (d4-conf-sagt-2017-0004)

Given candidates \(C\), committee size \(k\), distinguished candidate \(c^\star\), and a rational distribution \(\mu\) over complete rankings \(t\in S_m\), define \(\operatorname{CC}_\mu(S)=\sum_t\mu_t\bigl(m-\min_{c\in S}\operatorname{pos}_t(c)\bigr)\). Decide whether \(c^\star\in S\) for some \(S\subseteq C\) with \(|S|=k\) maximizing this score, and return such a witnessing committee when one exists.

Let \(C\) contain \(m\) candidates, let \(1\leq k\leq m\), and let \(c^\star\in C\). The input distribution \(\mu\) is an explicit list of rankings with nonzero binary-encoded rational masses summing to \(1\). For each size-\(k\) committee \(S\), define \(\operatorname{CC}_\mu(S)=\sum_t\mu_t\bigl(m-\min_{c\in S}\operatorname{pos}_t(c)\bigr)\), where the top position is \(1\).

Is deciding whether \(c^\star\) belongs to some committee maximizing \(\operatorname{CC}_\mu\) NP-hard or in P? When one exists, can such a committee be returned?

For finite lists of equally weighted voters, deciding whether a candidate belongs to some optimal Borda–Chamberlin–Courant committee is \(\Theta_2^p\)-complete.

Conclusion

The decision problem is NP-hard, even when all listed rankings have equal mass. This follows directly from the supplied completeness result by a polynomial-time, score-preserving reduction.

An optimal committee containing \(c^\star\), if one exists, can be returned by an exact algorithm. Both the decision problem and this search task admit polynomial-time algorithms with an NP oracle. Consequently, an ordinary polynomial-time algorithm that always returns such a committee or correctly reports that none exists would imply \(\mathrm{P}=\mathrm{NP}\).

1. Reduction from equally weighted voters

Consider an instance of the equally weighted problem from the premise. Let its explicitly listed voters have rankings \(r_1,\ldots,r_n\), with \(n\geq 1\). Keep the candidate set \(C\), committee size \(k\), and distinguished candidate \(c^\star\). Assign each listed ranking mass \(1/n\).

Each mass is a positive rational requiring \(O(\log n)\) bits. Thus the resulting distribution has polynomial encoding length and can be constructed in polynomial time. If the distribution representation requires distinct rankings, merge repeated rankings and give each ranking occurring \(a\) times mass \(a/n\); this also takes polynomial time.

For every size-\(k\) committee \(S\), its score in the constructed instance is
\[ \operatorname{CC}_{\mu}(S) = \frac{1}{n}\sum_{i=1}^{n} \left(m-\min_{c\in S}\operatorname{pos}_{r_i}(c)\right). \]
Therefore its score is exactly the original total Borda–Chamberlin–Courant score multiplied by the positive constant \(1/n\). All score comparisons, including ties, are preserved. In particular,
\[ c^\star\text{ belongs to some original optimal committee} \quad\Longleftrightarrow\quad c^\star\text{ belongs to some optimal committee under }\mu. \]

By the supplied \(\Theta_2^p\)-completeness premise, this establishes \(\Theta_2^p\)-hardness, and hence NP-hardness, for the rational-mass problem under the same polynomial-time reduction convention.

2. Exact integer scores of polynomial bit length

Write the explicitly listed masses as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive binary-encoded integers. Define
\[ D=\prod_t b_t, \qquad w_t=a_t(D/b_t). \]
These are positive integers, and the assumption \(\sum_t\mu_t=1\) gives \(\sum_t w_t=D\).

Define the integer score
\[ F(S)=\sum_t w_t \left(m-\min_{c\in S}\operatorname{pos}_t(c)\right) =D\,\operatorname{CC}_{\mu}(S). \]
Thus \(F\) has exactly the same maximizing committees as \(\operatorname{CC}_{\mu}\). Moreover,
\[ 0\leq F(S)\leq (m-1)D. \]

The bit length of \(D\) is at most \(1+\sum_t\log_2 b_t\), so it is polynomial in the input length. All weights and scores likewise have polynomial bit length, and \(F(S)\) can be computed exactly in polynomial time from a proposed committee.

3. Finding the optimum and returning a committee

For disjoint candidate sets \(A,B\subseteq C\) and an integer threshold \(q\), consider the following feasibility question:

Does there exist a committee \(S\subseteq C\) with \(|S|=k\), \(A\subseteq S\), \(S\cap B=\varnothing\), and \(F(S)\geq q\)?

This question belongs to NP: a committee \(S\) is a polynomial-length certificate, and every stated condition can be checked in polynomial time using the preceding integer-score representation.

First, use this NP oracle with \(A=B=\varnothing\). Binary search over the integer interval from \(0\) to \((m-1)D\) determines
\[ M=\max_{|S|=k}F(S). \]
The number of queries is \(O(\log((m-1)D+2))\), which is polynomial in the input length.

Next, query feasibility with \(A=\{c^\star\}\), \(B=\varnothing\), and \(q=M\). The answer is yes exactly when an optimal committee containing \(c^\star\) exists.

If the answer is yes, construct one as follows. Initially set \(A=\{c^\star\}\) and \(B=\varnothing\). Process each remaining candidate \(c\):

• Query feasibility with required set \(A\cup\{c\}\), forbidden set \(B\), and threshold \(M\).
• If feasible, add \(c\) to \(A\).
• Otherwise, add \(c\) to \(B\).

The invariant is that some optimal committee contains every candidate in \(A\) and excludes every candidate in \(B\). It holds initially by the successful distinguished-candidate query. A yes answer preserves it directly. After a no answer, every previously feasible committee excludes \(c\), so adding \(c\) to \(B\) also preserves it.

At termination, \(A\cup B=C\). Any committee witnessing the invariant must therefore equal \(A\). Consequently, \(A\) has size \(k\), contains \(c^\star\), and has optimal score \(M\).

This proves a \(\mathrm{P}^{\mathrm{NP}}\) upper bound for decision and an \(\mathrm{FP}^{\mathrm{NP}}\) upper bound for returning a committee or reporting nonexistence. Without an oracle, exhaustive enumeration of all size-\(k\) committees also gives an unconditional exact algorithm.

The NP-hardness conclusion settles the requested classification; no matching completeness classification for arbitrary rational masses is asserted.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves both requested questions. It establishes NP-hardness for the explicitly represented distribution problem and gives an exact procedure for returning an optimal committee containing \(c^\star\), or reporting that none exists. No mathematical gaps were found.

• Application of the supplied hardness premise.

The source problem is precisely the equally weighted Borda–Chamberlin–Courant membership problem supplied in USER_TASK. The reduction retains the candidate set, committee size, distinguished candidate, and rankings. Its hypotheses therefore match the supplied result.

The inference from \(\Theta_2^p\)-hardness to NP-hardness is valid under the stated common reduction convention, since \(\mathrm{NP}\subseteq\Theta_2^p\). No additional voting-theoretic theorem is required.

• Encoding and construction of the distribution.

Assigning each of the \(n\) explicitly listed voters mass \(1/n\) produces positive rational masses summing to \(1\). Each mass has binary encoding length \(O(\log n)\), so the construction has polynomial size and running time.

The optional treatment of repeated rankings is also correct: replacing \(a\) identical rankings by one ranking of mass \(a/n\) preserves all committee scores. Such aggregation is polynomial-time computable. Aggregated masses need not be equal, but this does not affect the reduction to the general rational-mass problem. The equal-mass restriction claimed in the conclusion is valid for the list representation allowing repeated rankings used in the primary construction.

• Preservation of the decision answer.

For every feasible committee, the constructed score is exactly its original total score divided by \(n\). Because \(n\geq1\), this scaling is positive and preserves every comparison and tie.

Consequently, the entire set of maximizing committees is preserved. In particular, membership of \(c^\star\) in some maximizing committee is preserved in both directions. This proves the claimed hardness.

• Exact integer arithmetic and bit complexity.

The denominator product \(D=\prod_t b_t\) is a positive integer divisible by every \(b_t\). Thus every \(w_t=a_t(D/b_t)\) is a positive integer, and normalization gives \(\sum_t w_t=D\).

The identity \(F(S)=D\,\operatorname{CC}_\mu(S)\) is correct. Since \(S\) is nonempty and ranking positions lie between \(1\) and \(m\), each satisfaction term lies between \(0\) and \(m-1\). Hence the stated bound \(0\leq F(S)\leq(m-1)D\) holds.

The bit-length bound for \(D\) is correct. Products, exact divisions, and score evaluations involve polynomially many integers of polynomial bit length, so their claimed polynomial running times are justified. An exponentially large numerical value of \(D\) does not invalidate this argument.

• NP feasibility oracle and optimization.

A committee is a polynomial-length certificate. Its cardinality, required and forbidden candidates, and threshold score can all be checked in polynomial time. Thus the proposed feasibility language belongs to NP.

With no required or forbidden candidates, threshold feasibility is monotone. At least one size-\(k\) committee exists because \(1\leq k\leq m\). Binary search therefore finds the maximum integer score within the stated polynomial number of queries.

The subsequent query requiring \(c^\star\) at threshold \(M\) characterizes the desired membership exactly: no committee can score above the global optimum \(M\).

• Committee reconstruction.

The initial successful query supplies the claimed invariant. A successful inclusion query preserves it. If inclusion fails, no committee witnessing the current invariant can contain the candidate under consideration; forbidding that candidate therefore also preserves the invariant.

Each candidate is assigned to exactly one of the required or forbidden sets. At termination these sets partition \(C\), so any remaining witness must equal \(A\). Its cardinality, optimality, and inclusion of \(c^\star\) follow directly.

This reasoning also covers \(k=1\), \(k=m\), and \(m=1\). In particular, a zero upper score bound presents no difficulty.

• Scope of the conclusion.

The decision and search upper bounds are correctly stated as \(\mathrm{P}^{\mathrm{NP}}\) and \(\mathrm{FP}^{\mathrm{NP}}\), respectively. Exhaustive enumeration provides an unconditional exact algorithm. The prover does not incorrectly claim an ordinary polynomial-time search algorithm.

An ordinary polynomial-time algorithm returning a valid committee or correctly reporting nonexistence would decide the NP-hard membership problem, yielding the stated consequence \(\mathrm{P}=\mathrm{NP}\).

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩