d4-journals-jair-2025-0101 (d4-journals-jair-2025-0101)

Given a finite task set \(Q\), type masses \(\mu_t\) with \(\sum_t\mu_t=1\), per-unit resource vectors \(b_{tk}\), eligibility sets \(I_t\), per-capita task demands \(d_{qk}\), and rewards \(r_q\), choose \(y_q\in\{0,1\}\) and resource allocations \(x_{tqk}\ge 0\) to maximize \(\sum_{q\in Q}r_qy_q\), subject to \(x_{tqk}=0\) when \(q\notin I_t\), \(\sum_qx_{tqk}\le\mu_tb_{tk}\), \(\sum_tx_{tqk}=d_{qk}y_q\), and \(x_{tqk}\le\mu_t\min\{b_{tk},d_{qk}\}y_q\). Tasks remain indivisible; allocations may split type mass across tasks. Determine the complexity of deciding whether a feasible allocation has reward at least \(K\).

Let \(Q\) be a task set of size \(m\ge1\), with \(h\ge1\) resource coordinates. A society is given by its support: a list of \(\tau\ge1\) types with positive masses \(\mu_t\), each encoded as a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has per-unit resource holdings \(b_{tk}\ge0\) and an eligibility set \(I_t\subseteq Q\), with \(\bigcup_t I_t=Q\). Each task has per-capita demands \(d_{qk}\ge0\) and reward \(r_q\ge0\). These numbers and the threshold \(K\ge0\) are binary rationals; let \(L\) be the total input bit length.
Tasks are indivisible and may be completed at most once; resources are divisible, types may contribute to multiple tasks, and unused resources and idle mass are allowed. Choose \(y_q\in\{0,1\}\), with \(\sum_q y_q\ge1\), and real allocations \(x_{tqk}\ge0\) satisfying, for every applicable index,
\(x_{tqk}=0\) if \(q\notin I_t\), \(\sum_q x_{tqk}\le\mu_t b_{tk}\), \(\sum_t x_{tqk}=d_{qk}y_q\), and \(x_{tqk}\le\mu_t\min\{b_{tk},d_{qk}\}y_q\).
The decision problem asks whether such an allocation exists with \(\sum_q r_qy_q\ge K\). State running times in \(m,\tau,h,L\).

Is this continuous task-selection decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

The finite-agent version with integer resource contributions is \(\mathrm{NP}\)-complete, including the restriction to one resource coordinate and universal eligibility ([Zhang et al., 2025](https://doi.org/10.1613/jair.1.17138)).
No verified result for exactly the normalized mass-allocation problem above was identified.

Result

The decision problem is $\mathrm{NP}$-complete, already for one resource coordinate and universal eligibility. Hardness holds both for $\tau=1$ and for $\tau=2$ with distinct types and masses $\mu_1=\mu_2=1/2$.

The key structural fact is that the normalized caps force every feasible allocation to be proportional to the masses.

1. The continuous allocations are uniquely determined

Lemma. Every feasible solution satisfies
$$ x_{tqk}=\mu_t d_{qk}y_q $$
for every type, task, and resource coordinate.

Proof. The per-task cap gives
$$ 0\le x_{tqk} \le \mu_t\min\{b_{tk},d_{qk}\}y_q \le \mu_t d_{qk}y_q. $$
For fixed $q,k$, define the nonnegative deficits
$$ \delta_t=\mu_t d_{qk}y_q-x_{tqk}. $$
By mass normalization and the demand equality,
$$ \sum_t\delta_t =d_{qk}y_q\sum_t\mu_t-\sum_t x_{tqk} =d_{qk}y_q-d_{qk}y_q =0. $$
A finite sum of nonnegative numbers equals zero only when every summand equals zero. Thus $\delta_t=0$ for every $t$, proving the lemma. $\square$

Two consequences follow.

First, if a selected task $q$ has $d_{qk}>0$ for some $k$, then
$$ x_{tqk}=\mu_t d_{qk}>0 $$
for every type, because every $\mu_t$ is positive. Eligibility therefore requires $q\in I_t$ for every $t$. Tasks whose demands are all zero require no contributions and need not have universal eligibility.

Second, each type’s capacity constraint becomes
$$ \mu_t\sum_q d_{qk}y_q\le \mu_t b_{tk}. $$
Dividing by the positive mass gives
$$ \sum_q d_{qk}y_q\le b_{tk}. $$

2. Exact equivalence to task knapsack

Define
$$ B_k=\min_{1\le t\le\tau}b_{tk} $$
and let
$$ A= \left\{ q\in Q: \bigl(d_{qk}=0\text{ for every }k\bigr) \ \text{or}\ \bigl(q\in I_t\text{ for every }t\bigr) \right\}. $$

Proposition. The original instance is a yes-instance if and only if there exists a nonempty subset $S\subseteq A$ satisfying
$$ \sum_{q\in S}d_{qk}\le B_k \quad\text{for every }k, \qquad \sum_{q\in S}r_q\ge K. $$

Proof of necessity. Let $S=\{q:y_q=1\}$ for a feasible solution. Nonemptiness and the reward inequality are original constraints. The lemma and its eligibility consequence give $S\subseteq A$. Its capacity consequence gives
$$ \sum_{q\in S}d_{qk}\le b_{tk} $$
for every $t,k$, hence the bound by $B_k$.

Proof of sufficiency. Suppose such an $S$ exists. Set $y_q=1$ exactly on $S$ and define
$$ x_{tqk}=\mu_t d_{qk}y_q. $$
These allocations are nonnegative. They obey eligibility: every selected task with a positive demand belongs to every eligibility set, and every task with zero demands receives zero allocation.

Mass normalization gives the required demand equalities:
$$ \sum_t x_{tqk} =d_{qk}y_q\sum_t\mu_t =d_{qk}y_q. $$
The capacity inequalities hold because
$$ \sum_q x_{tqk} =\mu_t\sum_{q\in S}d_{qk} \le\mu_t B_k \le\mu_t b_{tk}. $$

It remains to verify the per-task caps. If $q\in S$, nonnegativity of demands gives
$$ d_{qk}\le\sum_{p\in S}d_{pk}\le B_k\le b_{tk}. $$
Consequently $\min\{b_{tk},d_{qk}\}=d_{qk}$, and the cap holds with equality. If $q\notin S$, both sides of the cap are zero. Thus all original constraints hold. $\square$

This is exactly a multidimensional binary knapsack decision problem on $A$, with the additional requirement that the selected subset be nonempty.

3. NP-hardness with one resource coordinate

We reduce from the classical NP-hard SUBSET SUM problem: given positive binary integers $a_1,\ldots,a_m$ and a positive target $B$, decide whether some subset sums exactly to $B$. This positive-integer formulation and its hardness are stated in the introduction of [Polak, Rohwedder, and Węgrzycki, *Knapsack and Subset Sum with Small Items*](https://arxiv.org/html/2105.04035).

Construct an instance with
$$ Q=\{1,\ldots,m\},\qquad h=1,\qquad \tau=2, $$
and set
$$ \mu_1=\mu_2=\frac12,\qquad b_{11}=B,\qquad b_{21}=B+1,\qquad I_1=I_2=Q. $$
For every task $q$, set
$$ d_{q1}=a_q,\qquad r_q=a_q, \qquad K=B. $$

This satisfies every input hypothesis. The two types are distinct, both masses are positive, and their sum is one. All numerical data are binary rationals. The construction has output bit length linear in the SUBSET SUM input bit length and takes linear time.

Here $A=Q$ and $B_1=B$. By the proposition, the constructed instance is feasible exactly when some nonempty $S\subseteq Q$ satisfies
$$ \sum_{q\in S}a_q\le B \quad\text{and}\quad \sum_{q\in S}a_q\ge B. $$
These inequalities are equivalent to
$$ \sum_{q\in S}a_q=B. $$
Since $B>0$, any subset attaining this equality is nonempty. Thus the reduction preserves yes- and no-instances.

Therefore the problem is NP-hard even with $h=1$, fixed support size $\tau=2$, fixed masses, and universal eligibility. The same reduction works with $\tau=1$, $\mu_1=1$, and $b_{11}=B$.

4. NP membership and running times

A certificate consists solely of the $m$ selection bits. The proposition lets a verifier check eligibility, nonemptiness, the $h$ demand inequalities, and the reward threshold using exact rational arithmetic. No real-valued allocation certificate is needed.

For explicit bit-complexity bounds, clear denominators using the product $D$ of all input rational denominators. Its bit length is $O(L)$, because the sum of their encoded lengths is at most $L$. Every scaled quantity and every subset sum has $O(L)$ bits: summation adds at most $O(\log m)$ bits, and $m\le L$ for an explicit task list.

Using ordinary integer arithmetic, a conservative bound for preprocessing and certificate verification is
$$ O(m\tau hL^2) $$
bit operations. This proves membership in $\mathrm{NP}$.

A deterministic exact algorithm preprocesses $A$ and the capacities, then enumerates all nonempty subsets of $A$. Its running time is bounded by
$$ O\!\left(\bigl(m\tau h+2^m mh\bigr)L^2\right), $$
with polynomial space.

Together with the reduction, NP membership proves $\mathrm{NP}$-completeness. In particular, a polynomial-time algorithm in $m,\tau,h,L$ exists if and only if $\mathrm{P}=\mathrm{NP}$.

⟨structured verdict parsed — rendered above⟩

The proof establishes $\mathrm{NP}$-completeness for the stated normalized mass-allocation problem. The allocation lemma, exact subset-selection equivalence, and hardness reduction are correct. There is one minor encoding qualification in the claim that the reduction takes linear time and produces linear output length.

1. Forced allocations

The lemma is valid for every $t,q,k$, including unselected tasks and zero-demand coordinates.

The original cap and nonnegativity imply
$$ 0\le x_{tqk}\le \mu_t d_{qk}y_q. $$
Thus every defined deficit $\delta_t$ is nonnegative. The calculation
$$ \sum_t\delta_t =d_{qk}y_q\sum_t\mu_t-\sum_t x_{tqk} =0 $$
uses exactly the stated mass normalization and demand equality. Since the support is finite, every deficit must vanish.

Consequently, the asserted identity
$$ x_{tqk}=\mu_t d_{qk}y_q $$
follows without any additional hypothesis. The lemma asserts uniqueness conditional on feasibility; it does not incorrectly assert that every selection is feasible.

Both stated consequences are correct:

• If a selected task has a positive demand in any coordinate, positivity of every $\mu_t$ forces a positive contribution from every type in that coordinate. The eligibility constraint then requires universal eligibility for that task.
• Substitution into each capacity constraint, followed by division by the positive mass, gives the stated bound on the total selected demand.

The exception for tasks with all demands zero is necessary and correctly included.

2. Exact subset-selection equivalence

The definitions of $B_k$ and $A$ are well-defined because $\tau\ge1$ and $h\ge1$.

Necessity is fully justified. The original selection constraint supplies nonemptiness. The lemma supplies membership in $A$, and the capacity inequalities hold for every type, hence also for their minimum $B_k$. The reward condition is retained unchanged.

Sufficiency is fully justified. For the allocations specified in the proof:

• Nonnegativity follows from the input assumptions.
• Selected tasks with any positive demand have universal eligibility by membership in $A$.
• Tasks with all demands zero receive zero allocation.
• Unselected tasks also receive zero allocation, so they satisfy eligibility regardless of their eligibility sets.
• The demand equalities follow from mass normalization.
• The displayed capacity calculation is correct.

The per-task cap check is particularly important and is correct. For any selected task and coordinate, nonnegativity gives
$$ d_{qk}\le\sum_{p\in S}d_{pk}\le B_k\le b_{tk}. $$
Therefore the minimum appearing in the original cap equals $d_{qk}$, and the proposed allocation satisfies that cap with equality. For unselected tasks, both sides are zero.

There is no missing individual-task feasibility condition: the displayed inequality establishes it from the aggregate demand bound.

3. Hardness reduction

The source problem is stated precisely enough for the reduction: positive binary integers, a positive target, and selection of each listed item at most once. The cited paper’s introduction defines SUBSET SUM on positive integers and states its weak $\mathrm{NP}$-hardness. Weak hardness suffices here because the target input uses binary numerical encoding. [Polak, Rohwedder, and Węgrzycki](https://arxiv.org/html/2105.04035)

The constructed instance satisfies the task’s hypotheses:

• It has one resource coordinate and two support types.
• Both masses are positive and sum to one.
• The types are distinct because their holdings differ.
• Universal eligibility covers every task.
• Holdings, demands, rewards, and threshold are nonnegative binary rationals.

The effective capacity is correctly computed as $B_1=B$. Applying the proved proposition yields precisely the two inequalities
$$ \sum_{q\in S}a_q\le B, \qquad \sum_{q\in S}a_q\ge B. $$
Their conjunction is equivalent to the source equality. Positivity of $B$ correctly handles the target’s nonempty-selection requirement.

The stated one-type specialization also satisfies all hypotheses and preserves the same equivalence. Thus both claimed support-size restrictions are established.

Minor issue — encoding of eligibility sets. The assertion that the construction has linear output length and takes linear time is representation-dependent. A bitmap representation of each universal eligibility set permits this claim. An explicit list of binary task indices can instead require $O(m\log m)$ bits for these sets, which need not be linear in the source input length.

This does not affect the polynomial reduction or the hardness conclusion.

Minimum clarification: specify the eligibility-set encoding supporting the linear claim, or replace “linear” by “polynomial” in that sentence.

4. Membership and running times

The certificate consisting of the $m$ selection bits is sufficient because the proposition is an equivalence. No allocation certificate or assumption about encoding arbitrary real numbers is needed.

The denominator-clearing argument is sound:

• The product of the input denominators has $O(L)$ bits.
• Scaling any input rational by that product produces an integer with $O(L)$ bits.
• Summing at most $m$ such quantities adds only $O(\log m)$ bits.
• The explicit input supplies $m\le L$, so these sums still have $O(L)$ bits.

The stated conservative verification bound
$$ O(m\tau hL^2) $$
is sufficient for preprocessing eligibility and capacities, clearing denominators, and checking the selected demand and reward sums using ordinary integer arithmetic.

The exhaustive-search bound
$$ O\!\left(\bigl(m\tau h+2^m mh\bigr)L^2\right) $$
also safely covers preprocessing and checking every candidate subset. Sequential enumeration requires only polynomial space.

These bounds address the requested parameters $m,\tau,h,L$.

5. Edge cases and conclusion

The argument correctly accommodates zero holdings, zero demands, zero rewards, $K=0$, and an empty admissible set $A$. In particular, the proposition retains the nonempty-selection condition even when the reward threshold is zero. Neither the hardness argument nor the membership argument relies on excluding these valid target inputs.

The final $\mathrm{NP}$-completeness conclusion follows. The statement relating polynomial-time solvability to $\mathrm{P}=\mathrm{NP}$ is also correct. No mathematical repair is required; only the reduction’s linear encoding claim needs qualification.

⟨structured verdict parsed — rendered above⟩