Answer: \(\mathrm{coNP}\)-complete for verification of a supplied bundle; \(\mathrm{NP}\)-hard for computing a co-winning bundle
Theorem 10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each R ∈{Rmax min , R+ min, Rmax Σ } and their sequential and Pareto variants, R-WINNER is coNP-hard even for projects with unit costs, without diversity con- straints or donations, and for dichotomous preferences. Finally, winner determination is polynomial-time solvable for all greedy rules and their sequential variants, but this does not extend to the Pareto variants.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given indivisible projects \(C\), costs \(c_j\), budget \(B\), and a finite voter-type set \(\Theta\) with rational masses \(\mu_\theta\) summing to \(1\), where each type has an approval vector \(a_\theta\in\{0,1\}^{m}\), a feasible bundle \(A\subseteq C\) satisfies \(\sum_{j\in A}c_j\le B\). Decide whether \(A\) is co-winning under \(R_{\Sigma}^{\max}\), i.e. whether \(W_\mu(A)\ge W_\mu(A')\) for every feasible bundle \(A'\), where \(W_\mu(A)=\sum_{\theta\in\Theta}\mu_\theta\max_{j\in A}a_\theta(j)\) and \(W_\mu(\varnothing)=0\).
Given projects \(C=[m]\), integer costs \(c_j\), budget \(B\), and voter types \(\Theta\) with rational masses \(\mu_\theta\ge 0\) summing to \(1\), each type \(\theta\) has approvals \(a_\theta\in\{0,1\}^m\). A bundle \(A\subseteq C\) is feasible if \(\sum_{j\in A}c_j\le B\).
Define \(W_\mu(A)=\sum_{\theta\in\Theta}\mu_\theta\max_{j\in A}a_\theta(j)\), with \(W_\mu(\varnothing)=0\). A bundle is co-winning if its welfare is at least that of every feasible bundle.
Is this co-winning problem solvable in polynomial time, or is it NP-hard?
For a discrete electorate, the corresponding \(R^{\max}_{\Sigma}\)-WINNER problem is coNP-hard even with unit-cost projects, no diversity constraints or donations, and dichotomous preferences.
The definition gives rise to two standard problems:
These have different complexity classifications. Verification is \(\mathrm{coNP}\)-complete, while computing a co-winning bundle is \(\mathrm{NP}\)-hard.
Consider a discrete electorate \(V\) of \(n\geq 1\) voters. Each voter \(i\in V\) has an approval vector \(a_i\in\{0,1\}^m\).
For every approval vector \(\alpha\in\{0,1\}^m\) occurring among the voters, define
\[ V_\alpha=\{i\in V:a_i=\alpha\}, \qquad \mu_\alpha=\frac{|V_\alpha|}{n}. \]
Use one voter type for each nonempty \(V_\alpha\), with approval vector \(\alpha\). These masses are nonnegative rational numbers and satisfy
\[ \sum_\alpha\mu_\alpha = \frac{1}{n}\sum_\alpha |V_\alpha| = 1. \]
For every nonempty bundle \(A\),
\[ W_\mu(A) = \sum_\alpha \frac{|V_\alpha|}{n} \max_{j\in A}\alpha(j) = \frac{1}{n}\sum_{i\in V}\max_{j\in A}a_i(j). \]
The equality also holds for \(A=\varnothing\), since both welfare functions are defined to be \(0\). Thus the rational-mass welfare is exactly the discrete welfare multiplied by the positive constant \(1/n\). Consequently, for any two bundles \(A,A'\),
\[ W_\mu(A)\geq W_\mu(A') \quad\Longleftrightarrow\quad \sum_{i\in V}\max_{j\in A}a_i(j) \geq \sum_{i\in V}\max_{j\in A'}a_i(j). \]
The feasible bundles are unchanged because the projects, costs, and budget are copied verbatim. Hence a bundle is co-winning in the discrete instance if and only if it is co-winning in the rational-mass instance.
The transformation is polynomial-time: the multiplicity of each approval vector can be computed by grouping the explicitly listed voters, and every mass has denominator \(n\), requiring only \(O(\log n)\) bits. Unit costs are preserved.
Define the verification language to contain pairs \((I,A)\) such that \(A\) is feasible in \(I\) and
\[ W_\mu(A)\geq W_\mu(A') \]
for every feasible bundle \(A'\).
A no-certificate for a feasible bundle \(A\) is a bundle \(A'\) satisfying
\[ \sum_{j\in A'}c_j\leq B \qquad\text{and}\qquad W_\mu(A')>W_\mu(A). \]
The certificate contains at most \(m\) project indices. Feasibility and both welfare values can be computed in polynomial time. Exact comparison of the rational welfare values also takes polynomial time because the total bit length of all numerators and denominators produced by rational addition is polynomial in the input length.
If \(A\) itself is infeasible, this can be recognized directly in polynomial time. Therefore the complement of the verification language belongs to \(\mathrm{NP}\), proving that verification belongs to \(\mathrm{coNP}\).
By the supplied premise, discrete \(R^{\max}_{\Sigma}\)-WINNER verification is \(\mathrm{coNP}\)-hard even for unit-cost projects, dichotomous preferences, and no additional constraints.
The normalization construction above is a polynomial-time many-one reduction from that problem to rational-mass co-winner verification. It preserves every welfare comparison and every feasible bundle. Therefore rational-mass co-winner verification is \(\mathrm{coNP}\)-hard under the same restrictions.
Combining membership and hardness, rational-mass co-winner verification is \(\mathrm{coNP}\)-complete.
This follows directly from \(\textsc{Set Cover}\).
Let a \(\textsc{Set Cover}\) instance consist of a nonempty universe \(U\), subsets \(S_1,\dots,S_m\subseteq U\), and an integer \(k\). Construct one project \(j\) for each set \(S_j\), give every project cost \(c_j=1\), and set \(B=k\).
For each element \(u\in U\), introduce a voter type of mass \(1/|U|\) with
\[ a_u(j)=1 \quad\Longleftrightarrow\quad u\in S_j. \]
If distinct elements have identical approval vectors, they may equivalently be grouped into one type whose mass is their multiplicity divided by \(|U|\).
For every feasible bundle \(A\),
\[ W_\mu(A) = \frac{\left|\bigcup_{j\in A}S_j\right|}{|U|}. \]
Thus the optimum welfare equals \(1\) if and only if there are at most \(k\) sets covering all of \(U\).
Suppose there were a polynomial-time algorithm returning a co-winning bundle \(A^\star\). We could run it on the constructed instance and check whether \(W_\mu(A^\star)=1\). This would decide \(\textsc{Set Cover}\) in polynomial time. Hence computing a co-winning bundle is \(\mathrm{NP}\)-hard, even with unit costs and uniform masses before identical types are aggregated.
Equivalently, the threshold problem asking whether some feasible \(A\) satisfies \(W_\mu(A)\geq q\) is \(\mathrm{NP}\)-complete; hardness already holds for \(q=1\).
Rational voter masses do not remove the discrete combinatorial hardness:
Strictly speaking, a \(\mathrm{coNP}\)-complete verification language should not simply be called \(\mathrm{NP}\)-hard under polynomial-time many-one reductions: such an additional classification would imply \(\mathrm{NP}=\mathrm{coNP}\). Under the constructive interpretation of “find a co-winning bundle,” however, \(\mathrm{NP}\)-hardness holds directly.
⟨structured verdict parsed — rendered above⟩
The prover correctly distinguishes two natural formulations that the task leaves ambiguous:
The normalization from a discrete electorate to rational voter masses is correct and preserves all welfare comparisons. Assuming the supplied discrete \(R^{\max}_{\Sigma}\)-WINNER hardness premise refers to verification of a supplied bundle, the coNP-completeness argument is valid.
The Set Cover reduction also correctly establishes that computing an optimal, hence co-winning, bundle is NP-hard. There are only minor formalization issues concerning the meaning of NP-hardness for a function problem and the precise domain of the Set Cover parameter.
The distinction between verification and computation is legitimate and useful. The original question does not explicitly say whether a candidate bundle is part of the input, so reporting both classifications appropriately addresses the ambiguity.
The classifications are not contradictory: coNP-completeness concerns a decision language, while the stated NP-hardness concerns producing an optimal bundle.
The construction assigning mass
\[ \mu_\alpha=\frac{|V_\alpha|}{n} \]
to every occurring approval vector is correct. The masses are rational, nonnegative, and sum to \(1\).
For every bundle \(A\), including \(A=\varnothing\), the equality
\[ W_\mu(A)=\frac{1}{n}\sum_{i\in V}\max_{j\in A}a_i(j) \]
is correct. Multiplication by the positive constant \(1/n\) preserves every welfare comparison. Copying projects, costs, and budget preserves feasibility exactly.
The claimed polynomial running time and encoding size are also correct: there are at most \(n\) distinct approval vectors, and each mass has polynomial bit length.
For a feasible candidate \(A\), a strictly better feasible bundle \(A'\) is a valid NP certificate that \(A\) is not co-winning.
Checking feasibility, evaluating welfare, and comparing rational values can all be done in polynomial time. Although the explanation about rational addition is brief, its substance is correct: the accumulated numerator and denominator have bit length bounded polynomially by the total input encoding length.
The treatment of an infeasible candidate \(A\) is also correct. Since the verification language explicitly requires \(A\) to be feasible, infeasibility can be recognized deterministically in polynomial time as membership in the complement.
Under the supplied premise, the normalization is a valid polynomial-time many-one reduction. It maps the candidate bundle unchanged and preserves its co-winning status in both directions. Therefore the claimed coNP-hardness, including preservation of unit costs and dichotomous preferences, follows.
The only dependency requiring clarification is that the supplied discrete \(R^{\max}_{\Sigma}\)-WINNER result must indeed be the candidate-bundle verification problem. The prover calls it “verification,” while the task only names the corresponding WINNER problem. This appears intended, but should be stated explicitly.
For a bundle \(A\), the formula
\[ W_\mu(A)=\frac{\left|\bigcup_{j\in A}S_j\right|}{|U|} \]
is correct. With unit costs and budget \(k\), feasible bundles correspond to selections of at most \(k\) sets. Consequently, optimal welfare is \(1\) exactly when the Set Cover instance is positive.
If an algorithm outputs any co-winning bundle, evaluating whether its welfare is \(1\) decides Set Cover. This establishes NP-hardness of the search task under a polynomial-time oracle or search reduction.
The use of “NP-hard” for a function problem is slightly informal unless the reduction notion is specified. Likewise, “equivalently” is too strong when relating the search problem to the threshold decision problem: the reduction proves both claims, but they are not literally the same computational problem.
The construction tacitly uses the standard Set Cover convention that \(k\) is nonnegative. This should be made explicit because negative \(k\) would leave no feasible bundle under the given feasibility definition.
None of these issues undermines the central reductions or classifications.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.