Answer: \(\mathrm{NP}\)-complete, with hardness already holding for nonnegative integer utilities and \(\tau=2\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateEven when there are two agents with additive utility functions, it is NP-hard to decide whether there is an agreeable set of size exactly $\frac{m}{2}$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) indivisible items, two additive utility types \(v_1,v_2\), and rational masses \(\mu_1=\mu_2=1/2\), decide whether there exists \(A\subseteq S\) with \(|A|=m/2\) such that \(v_j(A)\ge v_j(S\setminus A)\) for each \(j\in\{1,2\}\).
Let \(S\) contain \(m\geq 2\) indivisible items, where \(m\) is even. There are two additive utility types with nonnegative binary-rational item values \(v_j(x)\), without utility normalization.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau=2\) and \(\mu_1=\mu_2=1/2\); \(\tau\) denotes support size, not the number of possible types.
A single subset \(A\subseteq S\) is agreeable if \(v_j(A)\geq v_j(S\setminus A)\) for every \(j\in\{1,2\}\); indifference is allowed. Require \(|A|=m/2\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether such an agreeable subset exists solvable in polynomial time, or is it NP-hard?
For two discrete agents with nonnegative additive utilities, this exact-half decision problem is weakly NP-hard. For a fixed number of agents and integer utilities, minimum-size agreeability admits a pseudo-polynomial-time algorithm.
The decision problem is \(\mathrm{NP}\)-complete, with hardness already holding for nonnegative integer utilities, support size \(\tau=2\), and masses \(\mu_1=\mu_2=1/2\). Thus a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The hardness is witnessed by a reduction from the weakly \(\mathrm{NP}\)-complete Partition problem. The integer-utility restriction also admits a pseudo-polynomial algorithm, as shown below.
A certificate specifies a subset \(A\subseteq S\) by its \(m\) membership bits. Verify that \(|A|=m/2\) and, for every supported type, that
\(2v_j(A)\geq v_j(S).\)
These are exactly the required agreeability inequalities, because additivity gives \(v_j(S\setminus A)=v_j(S)-v_j(A)\).
For exact rational arithmetic, write each value as \(p_{jx}/q_{jx}\), with \(q_{jx}>0\), and multiply all utilities of type \(j\) by \(D_j=\prod_{x\in S}q_{jx}\). This positive scaling preserves every comparison. The resulting integer values and their sums have \(O(L)\) bits: the bit lengths of all input numerators and denominators together are bounded by \(L\).
Using elementary integer arithmetic, denominator clearing and certificate verification take \(O(m\tau L^2)\) bit operations. Hence the problem belongs to \(\mathrm{NP}\).
We reduce from Partition: given positive binary-encoded integers \(a_1,\ldots,a_n\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies
\(\sum_{i\in I}a_i=\frac12\sum_{i=1}^{n}a_i.\)
The classical \(\mathrm{NP}\)-completeness of this problem is established, for example, in these [Cornell lecture notes](https://www.cs.cornell.edu/courses/cs6820/2022fa/Handouts/NPC4.pdf).
Put \(T=\sum_{i=1}^{n}a_i\) and \(C=\max_i a_i\). Construct \(m=2n\) distinct items: original items \(x_1,\ldots,x_n\) and padding items \(d_1,\ldots,d_n\). Define the two additive utility types by the following item values:
| Item | Type \(1\) | Type \(2\) |
|---|---:|---:|
| \(x_i\) | \(a_i\) | \(C-a_i\) |
| \(d_i\) | \(0\) | \(C\) |
Give each type mass \(1/2\).
All values are nonnegative integers. The two types are distinct because \(C>0\) and their values on every padding item differ. Thus the support has exactly two types. Moreover,
\(v_1(x)+v_2(x)=C\quad\text{for every }x\in S,\)
and therefore
\(v_1(S)=T,\qquad v_2(S)=2nC-T.\)
Consider any subset \(A\) satisfying the required cardinality \(|A|=n=m/2\). Write \(s=v_1(A)\). The constant itemwise sum gives
\(v_2(A)=nC-s.\)
Consequently, agreeability for type \(1\) is equivalent to
\(2s\geq T,\)
while agreeability for type \(2\) is equivalent to
\(2(nC-s)\geq 2nC-T,\)
which simplifies to \(2s\leq T\). Hence
\(A\text{ is agreeable for both types}\quad\Longleftrightarrow\quad s=T/2.\)
We now verify both directions of the reduction.
If \(T\) is odd, the forced equality is impossible for integer utilities, correctly preserving a negative instance.
The construction has \(2n\) items, and every value is at most \(C\). Its output length is \(O(n\log(C+1))\), polynomial in the source encoding length. Computing the values requires only comparisons and subtractions of binary integers. This proves polynomial-time many-one hardness.
Together with membership in \(\mathrm{NP}\), the reduction proves \(\mathrm{NP}\)-completeness.
For completeness, suppose the utilities are integers. Label the items \(x_1,\ldots,x_m\), and put \(h=m/2\) and \(W_j=v_j(S)\).
Define \(F_i(k,s)\) as the maximum type-\(2\) utility of a \(k\)-item subset of \(\{x_1,\ldots,x_i\}\) whose type-\(1\) utility is exactly \(s\). Use \(-\infty\) when no such subset exists. Initialize \(F_0(0,0)=0\), with all other entries infeasible.
The recurrence is
\(F_i(k,s)=\max\{F_{i-1}(k,s),\,F_{i-1}(k-1,s-v_1(x_i))+v_2(x_i)\},\)
omitting infeasible or out-of-range terms. It is correct because every feasible subset either excludes \(x_i\) or includes it; removing an included item gives precisely the second predecessor state. Induction on \(i\) therefore proves the stated meaning of every entry.
An agreeable exact-half subset exists precisely when some integer \(s\geq\lceil W_1/2\rceil\) satisfies
\(F_m(h,s)\geq\lceil W_2/2\rceil.\)
There are \(O(m^2(W_1+1))\) entries, each requiring \(O(L)\) bit operations. For \(\tau=2\), this gives time \(O(m^2(W_1+1)L)\). Interchanging the two types replaces \(W_1\) by \(\min\{W_1,W_2\}\).
For rational utilities, denominator clearing takes \(O(m\tau L^2)\) time, after which the same algorithm applies to the scaled integer totals. Those totals can be exponential in \(L\), so this is not a polynomial-time bound in the binary input length.
Finally, the positive masses do not change feasibility: the definition requires both supported types to agree with the same subset.
⟨structured verdict parsed — rendered above⟩
The output correctly resolves the task: the exact-half agreeability decision problem is \(\mathrm{NP}\)-complete, including when utilities are nonnegative integers, the support contains exactly two distinct types, and both masses are \(1/2\). No major or minor mathematical issues were found.
The certificate uses \(m\) membership bits. Checking cardinality and the inequalities \(2v_j(A)\geq v_j(S)\) verifies exactly the stated requirements, including indifference. Additivity justifies the equivalence with \(v_j(A)\geq v_j(S\setminus A)\).
Denominator clearing is valid: \(D_j=\prod_{x\in S}q_{jx}\) is positive and divisible by every denominator for type \(j\). Each scaled value and each total has \(O(L)\) bits. Elementary multiplication and exact division therefore support the stated bound \(O(m\tau L^2)\) bit operations.
The prover precisely states the binary-encoded positive-integer Partition problem used in the reduction. Its cited [Cornell lecture notes](https://www.cs.cornell.edu/courses/cs6820/2022fa/Handouts/NPC4.pdf) define Partition and establish its hardness. The source problem matches the required equal-sum subset formulation.
The construction produces \(m=2n\) distinct items, so the item count is even and the required subset size is \(n\). Since \(C=\max_i a_i>0\), every utility is a nonnegative integer. On each padding item, the two types have different values, \(0\) and \(C\), so they are distinct types. Assigning each mass \(1/2\) yields exactly the required support and masses. No normalization is imposed or used.
The itemwise identity \(v_1(x)+v_2(x)=C\) holds for both original and padding items. Consequently,
\[
v_1(S)=T,\qquad v_2(S)=2nC-T.
\]
For every subset of the required size, writing \(s=v_1(A)\) gives \(v_2(A)=nC-s\). The two agreeability inequalities then become \(2s\geq T\) and \(2s\leq T\). Thus the claimed equivalence with \(s=T/2\) is exact. The cardinality restriction is used explicitly and correctly.
A Partition solution selects at most \(n\) original items, so the available \(n\) padding items suffice to reach cardinality \(n\). Conversely, an agreeable subset supplies a Partition solution through its selected original items because padding contributes zero to type \(1\). Odd \(T\) correctly forces infeasibility. Equalities are accepted, as required by the task.
There are \(2n\) items and all values lie between \(0\) and \(C\). The stated output-length bound \(O(n\log(C+1))\) is polynomial in the source input length. Computing the maximum and the differences requires polynomial-time binary arithmetic. The construction therefore establishes polynomial-time many-one hardness; combined with membership, it establishes \(\mathrm{NP}\)-completeness.
The state definition, initialization, and recurrence are consistent. For fixed cardinality and exact type-\(1\) utility, retaining the maximum type-\(2\) utility suffices for the final threshold test. The include/exclude recurrence covers every feasible subset, and the infeasible-state convention handles boundary cases, including zero utilities and zero totals.
With \(0\leq k\leq h\) and \(0\leq s\leq W_1\), the stated number of entries is \(O(m^2(W_1+1))\). Stored utilities have \(O(L)\) bits, supporting the time bound \(O(m^2(W_1+1)L)\) for \(\tau=2\). Swapping types permits the smaller total as the indexed utility. The rational extension correctly adds denominator-clearing time and does not claim a polynomial bound in \(L\).
The proof establishes the requested hardness classification and a valid supplementary pseudo-polynomial algorithm. No additional clarification or repair is needed. The schema’s “continuous” status field is interpreted as the complexity classification of the supplied decision problem.
⟨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.