Answer: \(\mathrm{NP}\text{-complete}\), even with \(\tau=1\), \(q=1\), \(W=1\), and positive dyadic rational utilities equal to weights.
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateshows that finding the knapsack maximizing the approval score is NP-hard in the general case. Moreover, well- known pseudo-polynomial solution methods proposed for the stan- dard knapsack problem (based on dynamic programming) are not easily transposable to the approval winner determination problem, as shown in Example 2. Example 2. Consider a collective decision problem where 2 agents have to choose 2 representatives from a pool of 3 candidates, i.e.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given items \(P\), positive weights \(w_j\), capacity \(W\), a finite support \(T\) of types with rational masses \(\mu_t \ge 0\) summing to \(1\), and each type’s rational additive utilities \(u_j^t\) and approval threshold \(\delta_t\), does there exist \(X \subseteq P\) with \(\sum_{j \in X} w_j \le W\) such that \(\sum_{t \in T} \mu_t \mathbf{1}\{\sum_{j \in X} u_j^t \ge \delta_t\} \ge q\), for a given rational target share \(q\)?
Let \(P\) be a nonempty set of \(m\) indivisible items, with positive binary rational weights \(w_j\) and positive integer capacity \(W\).
A society is given by its support: the list \(T\) of its \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has signed binary rational additive utilities \(u_j^t\) and a signed binary rational approval threshold \(\delta_t\); it approves \(X\subseteq P\) exactly when \(\sum_{j\in X}u_j^t\ge\delta_t\). Utilities need not be normalized.
Given a binary rational target share \(q\in(0,1]\), decide whether some \(X\subseteq P\) satisfies \(\sum_{j\in X}w_j\le W\) and \(\sum_{t\in T}\mu_t\mathbf{1}\{\sum_{j\in X}u_j^t\ge\delta_t\}\ge q\). The empty subset is allowed; items cannot be selected fractionally.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicitly listed agents and a positive integer target number of approvals, discrete approval multi-agent knapsack is NP-complete (Benabbou and Perny, 2016).
With positive integer weights and fixed capacity, that discrete problem is solvable in polynomial time.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when \(\tau=1\), \(q=1\), \(W=1\), and every utility equals the corresponding positive dyadic rational weight.
Consequently, a polynomial-time algorithm in \(m,\tau,L\) exists if and only if \(\mathrm{P}=\mathrm{NP}\).
A certificate is a selection vector \(x\in\{0,1\}^m\). We verify feasibility, determine which supported types approve, and compare their total mass with \(q\).
These operations can be performed exactly in polynomial time. Write each input rational as \(p_r/d_r\), with positive denominator \(d_r\), and let \(D=\prod_r d_r\). The binary length of \(D\) is at most the sum of the denominator lengths, hence \(O(L)\). Multiplying every rational by \(D\) produces integers of \(O(L)\) bits. The resulting sums also have \(O(L)\) bits, since there are at most \(m\) or \(\tau\) summands and both parameters are bounded by the explicit input length.
Thus all comparisons reduce to exact integer arithmetic. Using elementary multiplication and division, certificate verification takes
\(O\bigl((m\tau+m+\tau)L^2\bigr)\)
bit operations. Signed utilities and thresholds cause no difficulty. We process only the \(\tau\) listed types; no expansion of rational masses into agents is required. Therefore the problem belongs to \(\mathrm{NP}\).
We reduce from SUBSET SUM: given binary-encoded positive integers \(a_1,\ldots,a_n\) and a positive integer \(B\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{j\in I}a_j=B\). This version is \(\mathrm{NP}\)-complete; the standard reduction produces positive integers and a positive target. [Cornell’s SUBSET SUM proof](https://courses.cs.cornell.edu/cs4820/2018fa/lectures/subset_sum.pdf)
Let \(A=\sum_{j=1}^n a_j\), and choose a power of two \(D=2^k>A+B\). Construct \(n+1\) items, indexed by \(0,1,\ldots,n\), with
\(w_j=u_j^t=a_j/D\quad(1\le j\le n),\qquad w_0=u_0^t=(D-B)/D.\)
There is one type \(t\), with \(\mu_t=1\). Set \(\delta_t=1\), \(q=1\), and \(W=1\).
The construction satisfies every hypothesis. All weights and utilities are positive dyadic rationals because \(D>B\). The support has size \(\tau=1\), its mass sums to one, and the capacity is a positive integer. Moreover, \(k=O(S)\), where \(S\) is the SUBSET SUM input length, so the construction has polynomial size and is computable in polynomial time.
Correctness. Because \(q=\mu_t=1\), a successful subset must be approved by \(t\). Utilities equal weights, so success is equivalent to
\(\sum_{j\in X}w_j\le1\quad\text{and}\quad\sum_{j\in X}w_j\ge1,\)
hence to \(\sum_{j\in X}w_j=1\).
Every subset omitting item \(0\) has total weight at most \(A/D<1\). Therefore every successful subset contains item \(0\). Writing \(I=X\setminus\{0\}\), its total weight equals one precisely when
\(\dfrac{D-B+\sum_{j\in I}a_j}{D}=1,\)
which is equivalent to \(\sum_{j\in I}a_j=B\).
Conversely, any SUBSET SUM solution \(I\) yields the successful subset \(I\cup\{0\}\). This proves both directions of the reduction. The empty subset has utility zero and is rejected in these instances.
The problem is therefore \(\mathrm{NP}\)-hard under the stated restrictions and, by membership in \(\mathrm{NP}\), \(\mathrm{NP}\)-complete.
The positive integer weight restriction is essential to the stated fixed-capacity result.
If every weight is a positive integer and capacity is a fixed constant \(c\), every feasible subset contains at most \(c\) items. Enumerating all subsets of size at most \(c\), including the empty subset, examines at most
\(\sum_{r=0}^{\min(m,c)}\binom mr\le(m+1)^c\)
candidates. Using the verifier above gives running time
\(O\bigl((m+1)^c(m\tau+m+\tau)L^2\bigr),\)
which is polynomial in \(m,\tau,L\) for fixed \(c\).
Positive rational weights provide no such cardinality bound. The reduction above proves hardness even for capacity \(1\). Clearing their denominators replaces that capacity by the integer \(D\), whose numerical value can be exponential in its binary encoding length; it does not produce a fixed-capacity integer instance.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned decision problem correctly: it proves \(\mathrm{NP}\)-completeness, including hardness with one supported type and capacity \(1\). I found no major or minor issues.
The certificate \(x\in\{0,1\}^m\) specifies an admissible indivisible selection and has polynomial length. It also represents the empty subset.
The common-denominator argument is valid. The product of the positive input denominators has \(O(L)\) bits. Scaling each rational by this product produces an integer of \(O(L)\) bits, including for signed numerators. Scaling the integer capacity likewise preserves this bound.
Summing at most \(m\) or \(\tau\) such integers introduces at most a logarithmic increase in bit length. Since both parameters are bounded by the explicit input length, the resulting sums still have \(O(L)\) bits.
The claimed verification bound
\[
O\bigl((m\tau+m+\tau)L^2\bigr)
\]
is a valid conservative bound using elementary integer arithmetic. It covers denominator construction, scaling, utility and weight sums, approval tests, and the final mass comparison. Processing the supported types directly correctly avoids any expansion into individual agents.
The prover states the required source theorem precisely: SUBSET SUM with binary-encoded positive integers and a positive integer target is \(\mathrm{NP}\)-complete.
The [cited Cornell notes](https://courses.cs.cornell.edu/cs4820/2018fa/lectures/subset_sum.pdf) establish SUBSET SUM completeness. Although their initial definition permits nonnegative integers, their hardness construction uses positive item values and a positive target on the nontrivial instances. The citation therefore supports the restricted source problem used here.
The construction respects every target restriction:
The assertion that the power of two can be chosen with \(k=O(S)\) is correct: the binary length of \(A+B\) is \(O(S)\). Consequently, all constructed numerators and denominators have polynomial length, and the entire construction is computable in polynomial time.
With one type of mass \(1\) and target share \(1\), success requires that type’s approval.
Because utilities equal weights and the approval threshold and capacity both equal \(1\), the two necessary inequalities are precisely
\[
\sum_{j\in X}w_j\le 1
\qquad\text{and}\qquad
\sum_{j\in X}w_j\ge 1.
\]
Their conjunction is equivalent to equality. Both inequalities are inclusive, as required by the task.
Every subset omitting item \(0\) has weight at most \(A/D<1\). Thus every successful subset must contain item \(0\).
For a subset containing item \(0\), the displayed calculation is correct:
\[
\frac{D-B+\sum_{j\in I}a_j}{D}=1
\quad\Longleftrightarrow\quad
\sum_{j\in I}a_j=B.
\]
The denominator is positive, so multiplication preserves equivalence.
Conversely, a source solution produces a subset whose weight and utility are exactly \(1\), satisfying both feasibility and approval. The reduction therefore preserves yes and no instances. It also handles \(B>A\): the same equivalence rules out a successful target subset.
The empty subset has utility \(0<1\), so allowing it introduces no unintended solution.
The explanation of the supplied tractability statement is correct. Positive integer weights and fixed positive capacity \(c\) limit every feasible subset to at most \(c\) items.
The candidate bound
\[
\sum_{r=0}^{\min(m,c)}\binom mr\le(m+1)^c
\]
is valid, including when \(c>m\). Multiplying it by the verifier’s running time yields the stated polynomial bound for fixed \(c\).
Rational weights do not impose that cardinality restriction. In the constructed instances, clearing the common denominator changes capacity \(1\) into capacity \(D\), which can have exponential numerical value despite polynomial binary length. Thus the hardness result does not conflict with fixed-capacity tractability for positive integer weights.
Membership and the polynomial reduction establish the claimed \(\mathrm{NP}\)-completeness. The stated equivalence between a polynomial-time algorithm and \(\mathrm{P}=\mathrm{NP}\) follows. No additional clarification or repair is required.
⟨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.