Answer: \(\text{NP-hard}\), even with \(\tau=1\); the rational-threshold decision version is \(\text{NP-complete}\).
Observation 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSWM-PB is NP-hard. A proof is in Appendix §A.1 and is via a reduction from the maximum set coverage problem. This result is unsurprising since many models with project interactions in PB and MW elections face this issue [30,31,41,28,29]. FC-SWM-PB is also NP-hard since it is at least as hard as SWM-PB. For real-world voting problems, we often deal with scenarios where some problem parameters are small.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given projects \(P\) with costs \(c_j\), PBPI groups and interaction-valid votes, budget \(B\), and a rational distribution \(\mu\) over complete vote types \(\theta=(f,s,\eta)\), output an integral bundle \(Q\subseteq P\) with \(\sum_{j\in Q}c_j\le B\) maximizing \(U_\mu(Q)=\sum_\theta\mu_\theta u_\theta(Q)\).
Let \(P\) contain \(m\ge 1\) projects with positive integer costs \(c_j\), and let \(B\) be a positive integer budget. A supplied partition \(z_1,\ldots,z_r\) consists of nonempty groups, each marked contradictory or non-contradictory.
A complete vote type \(\theta=(f,s,\eta)\) specifies, for each group, \(f_g\in\mathbb Z_{\ge0}\), \(s_g\subseteq z_g\), and \(\eta_g\in\{0,1\}\), with \(\sum_g f_g\le B\). In contradictory groups require \(|s_g|\le1\) and \(\eta_g=0\); empty approval sets are allowed. No constraint \(f_g\le\sum_{j\in s_g}c_j\) is imposed.
A society is given by its support: the list of the \(\tau\) distinct complete vote types with positive mass, each mass \(\mu_\theta\) a binary rational, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
For an integral bundle \(Q\subseteq P\), define \(a_{\theta g}(Q)=\sum_{j\in Q\cap s_g}c_j\) and \(u_\theta(Q)=\sum_{g=1}^r\bigl[(1-\eta_g)+\eta_g\mathbf1\{s_g\subseteq Q\}\bigr]\min\{f_g,a_{\theta g}(Q)\}\).
Feasible bundles satisfy \(\sum_{j\in Q}c_j\le B\) and \(|Q\cap z_g|\le1\) for every contradictory group. There are no additional funding constraints. The optimization problem outputs any feasible bundle maximizing \(U_\mu(Q)=\sum_\theta\mu_\theta u_\theta(Q)\); ties may be resolved arbitrarily.
Let \(L\) be the total binary input length. State running times in \(m,\tau,L\) and any additional parameters used.
Is this integral-bundle welfare maximization problem for a society given by rational masses solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicitly listed voters, welfare maximization is NP-hard even with unit costs, one non-contradictory group, and only substitution votes ([Goyal–Sarmasarkar–Goel](https://arxiv.org/pdf/2305.11296v2)).
For weighted distinct votes with unit project costs, an FPT algorithm parameterized by the number of distinct votes is known; this covers a restricted mass setting, rather than unrestricted costs and support size ([Goyal–Sarmasarkar–Goel](https://arxiv.org/pdf/2305.11296v2)).
The optimization problem is NP-hard, even with support size \(\tau=1\), mass \(1\), one non-contradictory group, and only a substitution vote. Its rational-threshold decision version is NP-complete.
Consequently, an exact algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). Arbitrary tie-breaking does not affect this conclusion.
We reduce from the standard NP-complete SUBSET SUM problem: given positive integers \(a_1,\ldots,a_m\) and a positive integer target \(T\), all encoded in binary, determine whether some subset has sum exactly \(T\).
Construct the welfare instance as follows:
Every input requirement holds. Project costs and budget are positive integers; the group is nonempty; the fund allocation satisfies \(f_1=B\); and the unique positive rational mass sums to \(1\).
For any feasible bundle \(Q\), the budget constraint gives \(\sum_{j\in Q}a_j\le T\). Substituting the constructed vote into the utility definition therefore yields
\[ U_\mu(Q)=u_\theta(Q) =\min\left\{T,\sum_{j\in Q}a_j\right\} =\sum_{j\in Q}a_j. \]
Thus
\[ \max_{Q\text{ feasible}}U_\mu(Q)=T \quad\Longleftrightarrow\quad \exists Q\subseteq P:\ \sum_{j\in Q}a_j=T. \]
The forward implication holds because a feasible maximizing bundle with welfare \(T\) has total cost exactly \(T\). For the reverse implication, a subset summing to \(T\) is feasible and attains welfare \(T\), while every feasible bundle has welfare at most \(T\).
Hence, given any welfare-maximizing output bundle, computing its total cost and comparing it with \(T\) decides SUBSET SUM.
If the source input has binary length \(H\), the construction has \(\tau=1\) and length \(L=O(H+m\log(m+1))\), allowing explicit project identifiers. It can be written in time \(O(H+m\log(m+1))\). The final cost comparison takes \(O(mL)\) bit operations. A polynomial-time optimizer would therefore give a polynomial-time algorithm for SUBSET SUM. This proves NP-hardness.
The supplied unit-cost hardness result applies to explicitly listed voters with one non-contradictory group and substitution votes; see [Goyal–Sarmasarkar–Goel, Observation 5 and Appendix A.1](https://arxiv.org/pdf/2305.11296v2).
Here is the precise transfer to rational support. Suppose such an instance lists \(n\) voters. For each distinct complete vote type \(\theta\), let \(n_\theta\) be its multiplicity and assign mass
\[ \mu_\theta=\frac{n_\theta}{n}. \]
These masses are positive, sum to \(1\), and have binary numerator and denominator encodings of length \(O(\log(n+1))\). The resulting support has \(\tau\le n\).
For every feasible bundle,
\[ U_\mu(Q) =\sum_\theta\frac{n_\theta}{n}u_\theta(Q) =\frac1n\sum_{i=1}^{n}u_i(Q). \]
Multiplication by the positive constant \(1/n\) preserves all welfare comparisons and ties. The optimizing bundles are therefore exactly the same.
For source length \(H\) and maximum complete-vote encoding length \(h\), sorting vote encodings and counting multiplicities takes \(O(H+n\log(n+1)h)\) bit operations. The output length is \(O(H+n\log(n+1))\), hence polynomial in the explicitly listed input length.
Thus the support formulation remains NP-hard even with unit costs when \(\tau\) is unrestricted. Meanwhile, Section 1 shows why the supplied FPT result for unit costs cannot extend to arbitrary binary costs with parameter \(\tau\) alone: an algorithm taking \(F(\tau)\operatorname{poly}(m,L)\) time would solve the constructed \(\tau=1\) instances in polynomial time.
Define the decision version by adding a binary rational threshold \(K\): does some feasible bundle satisfy \(U_\mu(Q)\ge K\)? Let \(L'\) be the input length including this threshold.
A certificate is the \(m\)-bit incidence vector of \(Q\). Feasibility is checked by summing costs and checking each contradictory group. Utilities are computed directly from the supplied approval sets and allocations.
For exact rational arithmetic, write \(\mu_\theta=p_\theta/d_\theta\) and set
\[ D=\prod_\theta d_\theta, \qquad w_\theta=p_\theta(D/d_\theta). \]
The integers \(D\) and \(w_\theta\) have \(O(L)\) bits. Also, \(u_\theta(Q)\) is a nonnegative integer satisfying
\[ u_\theta(Q)\le\sum_g f_g\le B. \]
Since \(\sum_\theta w_\theta=D\), the integer numerator
\[ W(Q)=\sum_\theta w_\theta u_\theta(Q) \]
satisfies \(0\le W(Q)\le BD\), and therefore has \(O(L)\) bits. Welfare equals \(W(Q)/D\); comparison with \(K\) uses exact cross multiplication.
Using schoolbook arithmetic, a conservative verification bound is \(O(m\tau(L')^2)\) bit operations. The decision problem is consequently in \(\mathrm{NP}\), and Section 1 proves it NP-hard already for threshold \(K=B\). It is therefore NP-complete.
For completeness, exhaustive enumeration gives an exact optimizer in \(O(2^m m\tau L^2)\) bit operations.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The single-vote reduction establishes NP-hardness for binary costs, independently of the cited unit-cost result. The rational-threshold decision version is also correctly shown to be NP-complete. I found no major or minor mathematical issues.
The source problem is stated precisely: SUBSET SUM with positive binary integers and a positive target. This is a standard NP-complete formulation. Taking instances with at least one item satisfies the task’s requirement \(m\ge1\).
Every constructed input meets the target’s requirements:
Items with \(a_j>T\) create no difficulty: their projects simply cannot occur in feasible bundles. The construction does not depend on any additional funding constraint.
For every feasible bundle \(Q\), its total cost is at most \(T\). Consequently, the displayed calculation
\[
U_\mu(Q)=\min\left\{T,\sum_{j\in Q}a_j\right\}=\sum_{j\in Q}a_j
\]
is correct.
Both directions of the claimed equivalence hold:
A maximizing bundle exists because the feasible family is finite and contains the empty bundle. Thus extracting any maximizing bundle and comparing its cost with \(T\) decides SUBSET SUM. Arbitrary tie-breaking does not change that test.
The construction size and time bounds are polynomial in the source encoding length. The stated final comparison bound \(O(mL)\) is conservative and sufficient. This establishes the requested NP-hardness, even with \(\tau=1\). It does not assert strong NP-hardness, which this reduction alone would not establish.
The cited restrictions are accurate: Appendix A.1 uses unit costs, one non-contradictory group, substitution votes, and allocation \(1\) per voter. These are compatible with the target model. See [Observation 5 and Appendix A.1](https://arxiv.org/pdf/2305.11296v2).
Grouping identical complete votes and assigning masses \(n_\theta/n\) preserves welfare up to the positive factor \(1/n\). The displayed identity therefore preserves every comparison and tie.
The masses have polynomial encoding length, and the sorting, counting, and output-size bounds are valid conservative bounds. This establishes the additional unit-cost hardness claim for unrestricted support size.
The parameterized consequence is also correct: an exact algorithm with running time \(F(\tau)\operatorname{poly}(m,L)\) for arbitrary binary costs would run in polynomial time on the constructed instances with \(\tau=1\), implying \(\mathrm{P}=\mathrm{NP}\).
The incidence vector is a polynomial-size certificate. Budget feasibility, contradictory-group restrictions, approval intersections, and complementarity indicators are all directly checkable from the supplied input.
The common-denominator construction is valid:
Exact threshold comparison by cross multiplication is polynomial in \(L'\). The conservative verification bound \(O(m\tau(L')^2)\) accommodates the direct scans and schoolbook arithmetic. Membership in NP follows.
Setting \(K=B=T\) in the reduction establishes decision NP-hardness, so NP-completeness follows. The exhaustive-enumeration bound \(O(2^m m\tau L^2)\) is also valid.
No additional clarification or repair is needed.
⟨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.