Answer: Polynomial-time solvable, in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
Theorem 14 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSolving PROGRAM is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given supported complete agent types \(t\) with binary-rational masses \(\mu_t\), each carrying a fixed inventory of item types \(a\) with sizes \(s_{ta}\) and values \(v_{ta}\), and partitioned into two owner classes \(G_1,G_2\), choose selected masses \(x_{ta}\in[0,\mu_t]\). With \(\mu(G_i)=\sum_{t\in G_i}\mu_t>0\), maximize \(\sum_{t,a}v_{ta}x_{ta}\), subject to \(\sum_{t,a}s_{ta}x_{ta}\le b\) and \(\frac{\sum_{t\in G_1,a}v_{ta}x_{ta}}{\mu(G_1)}=\frac{\sum_{t\in G_2,a}v_{ta}x_{ta}}{\mu(G_2)}\), where \(b\) is per-capita capacity and \(x_{ta}\) is the mass of type-\(t\) agents receiving item \(a\).
A society is given by its support: a list of \(\tau\) complete agent types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type \(t\) specifies an owner class and an explicitly listed finite inventory \(A_t\); each inventory entry represents one item per agent, and distinct entries may have identical attributes. Put \(m=\sum_t|A_t|\). Inventories may be empty.
The two owner classes \(G_1,G_2\) partition the support and satisfy \(M_i=\sum_{t\in G_i}\mu_t>0\). Capacity \(b>0\), sizes \(0<s_{ta}\le b\), values \(v_{ta}>0\), and threshold \(q\ge0\) are binary rationals; \(L\) is the total input bit length.
Choose real selected masses \(0\le x_{ta}\le\mu_t\) for \(a\in A_t\). An agent may have several inventory items selected; capacity is imposed on aggregate mass, with no additional constraint on individual bundles.
Define \(V_i(x)=\sum_{t\in G_i}\sum_{a\in A_t}v_{ta}x_{ta}\). Feasibility requires \(\sum_t\sum_{a\in A_t}s_{ta}x_{ta}\le b\) and \(V_1(x)/M_1=V_2(x)/M_2\). The objective is to maximize \(V_1(x)+V_2(x)\).
Is deciding whether the maximum is at least \(q\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For two discrete owners, maximizing expected total selected value over distributions on capacity-feasible item subsets, subject to equal expected owner utilities, is NP-hard. [Source](https://arxiv.org/html/1510.07358).
No prior result addressing exactly the supported-mass formulation above was identified in the literature search.
The decision problem is solvable in polynomial time in \(m,\tau,L\). In fact, an exact algorithm uses two fractional-knapsack computations. The proof below applies to the stated formulation, with aggregate capacity and independently selectable inventory entries.
Let \(E_i=\{(t,a):t\in G_i,\ a\in A_t\}\). Inventory entries remain distinct even when their attributes coincide.
The feasible region is a closed subset of the bounded box defined by \(0\le x_{ta}\le\mu_t\). It is nonempty because \(x=0\) is feasible. Consequently, the continuous objective attains its maximum.
Since the classes partition the support, \(M_1+M_2=1\). For any feasible allocation, write its common normalized utility as \(U\). Then
\(V_i(x)=M_iU,\qquad V_1(x)+V_2(x)=(M_1+M_2)U=U.\)
If \(q=0\), the answer is immediately yes. Suppose henceforth that \(q>0\).
Claim. The maximum is at least \(q\) if and only if there exists an allocation satisfying the item bounds, aggregate capacity, and
\(V_1(x)=M_1q,\qquad V_2(x)=M_2q.\)
Proof. If a feasible allocation has total value \(U\ge q\), replace every selected mass by \(x'_{ta}=(q/U)x_{ta}\). The scaling factor lies in \((0,1]\), so the bounds and capacity remain satisfied. Linearity gives \(V_i(x')=M_iq\).
Conversely, the displayed class values imply equal normalized utilities and total value \((M_1+M_2)q=q\). Thus such an allocation answers the decision question affirmatively. This proves the claim.
For each entry \(e=(t,a)\), define
\(y_e=v_{ta}x_{ta},\qquad u_e=v_{ta}\mu_t,\qquad r_e=s_{ta}/v_{ta}.\)
Here \(y_e\) is selected value, \(u_e\) is its upper bound, and \(r_e\) is capacity consumed per unit of value. Because \(v_{ta}>0\), the transformation is invertible, with \(x_{ta}=y_e/v_{ta}\). The bounds and capacity contribution become
\(0\le y_e\le u_e,\qquad s_{ta}x_{ta}=r_ey_e.\)
For class \(i\), let \(B_i=\sum_{e\in E_i}u_e\). For \(R\in[0,B_i]\), define its minimum required capacity by
\(C_i(R)=\min\left\{\sum_{e\in E_i}r_ey_e:\ 0\le y_e\le u_e,\ \sum_{e\in E_i}y_e=R\right\}.\)
We now derive this minimum explicitly.
If \(R=0\), take every \(y_e=0\), giving \(C_i(0)=0\). If \(R>B_i\), the required value is impossible. This also handles an empty class inventory: then \(B_i=0\).
For \(0<R\le B_i\), order the \(n_i=|E_i|\) entries so that
\(r_1\le r_2\le\cdots\le r_{n_i},\)
breaking ties arbitrarily. Let \(P_0=0\) and \(P_j=\sum_{\ell=1}^{j}u_\ell\). Choose the smallest index \(k\) with \(P_k\ge R\). Define
\(y_j^*=u_j\ \text{for }j<k,\qquad y_k^*=R-P_{k-1},\qquad y_j^*=0\ \text{for }j>k.\)
Minimality of \(k\) gives \(P_{k-1}<R\le P_k\), so this allocation satisfies every bound and has total value exactly \(R\).
Lemma. This allocation minimizes capacity, and hence
\(C_i(R)=\sum_{j<k}r_ju_j+r_k(R-P_{k-1}).\)
Proof. Let \(y\) be any allocation satisfying the bounds and \(\sum_jy_j=R\), and put \(\lambda=r_k\). Then
\(\sum_jr_jy_j=\lambda R+\sum_j(r_j-\lambda)y_j.\)
For \(j<k\), the coefficient \(r_j-\lambda\) is nonpositive. Therefore \(y_j\le u_j\) implies
\((r_j-\lambda)y_j\ge(r_j-\lambda)u_j.\)
For \(j>k\), the coefficient is nonnegative, so \(y_j\ge0\) implies \((r_j-\lambda)y_j\ge0\). The coefficient for \(j=k\) is zero. Consequently,
\(\sum_jr_jy_j\ge\lambda R+\sum_{j<k}(r_j-\lambda)u_j=\sum_{j<k}r_ju_j+r_k(R-P_{k-1}).\)
The constructed allocation \(y^*\) attains this lower bound, proving the lemma.
Set \(R_i=M_iq\). The answer is yes precisely when
\(R_1\le B_1,\qquad R_2\le B_2,\qquad C_1(R_1)+C_2(R_2)\le b.\)
Necessity. By Section 1, an affirmative answer yields an allocation with class values \(R_1,R_2\). The item bounds imply \(R_i\le B_i\). By the definition and proved formula for \(C_i\), each class consumes at least \(C_i(R_i)\) capacity. Thus their sum cannot exceed \(b\).
Sufficiency. If the three inequalities hold, construct the minimizing allocation from Section 2 separately for each class. Together, these allocations respect all item bounds, attain the required class values, and consume capacity \(C_1(R_1)+C_2(R_2)\le b\). Converting back to \(x_{ta}=y_{ta}/v_{ta}\) gives a feasible allocation of total value \(q\).
Thus the algorithm is:
The algorithm processes the explicitly listed \(\tau\) types and \(m\) inventory entries. Sorting uses \(O(m\log(m+1))\) comparisons; the remaining computations use \(O(m+\tau)\) rational arithmetic operations.
All comparisons and computations can be exact. For example, comparing two ratios uses
\(s_ev_f\le s_fv_e,\)
because the values are positive.
There is also no numerical precision issue at the threshold. Each \(u_e\) and \(r_e\) is formed from a constant number of input rationals. The class masses, value bounds, and prefixes are sums of at most \(m+\tau\) such quantities. A sum of rational numbers can be represented using the product of their denominators as a common denominator; its bit length is bounded by the sum of the summands’ denominator bit lengths, with a polynomial bound for the numerator as well.
The formula for \(C_i(R_i)\) uses only these sums and a constant number of further arithmetic operations. Hence all intermediate rational numbers have bit length polynomial in \(m,\tau,L\). Standard exact integer arithmetic therefore implements the entire algorithm in polynomial time.
The cited paper requires a random selected subset to satisfy capacity in every realization. Its probability variables range over capacity-feasible subsets; the paper proves hardness for that program. [Feigenbaum and Johnson, Section 4 and Theorem 14](https://arxiv.org/html/1510.07358).
The present formulation instead specifies independent selected-mass bounds and a single aggregate capacity inequality. These are exactly the constraints used above. In particular, there is no requirement that the selected masses arise as marginals of a distribution over capacity-feasible discrete subsets. The discrete hardness result therefore does not contradict the polynomial-time algorithm proved here.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The decision problem is solvable in polynomial time in \(m,\tau,L\). The argument is rigorous, handles the permitted degeneracies, and establishes polynomial bit complexity. No major or minor mathematical issues were found.
The attainment argument is valid. There are finitely many variables, each constrained to a closed bounded interval. The capacity inequality and fairness equality define closed sets, and the zero allocation satisfies both. Thus the feasible region is nonempty and compact, and the linear objective attains its maximum. These are precisely the hypotheses needed for the extreme-value theorem.
Because the owner classes partition the support and the masses sum to one, \(M_1+M_2=1\). Both class masses are strictly positive, so the common normalized utility \(U\) is well-defined. The identities
\[
V_i(x)=M_iU,\qquad V_1(x)+V_2(x)=U
\]
are correct.
The case \(q=0\) is correctly accepted using the zero allocation.
For \(q>0\), a feasible allocation of total value \(U\ge q\) has \(U>0\), making the scaling factor \(q/U\) defined and contained in \((0,1]\). Scaling preserves all bounds, aggregate capacity, and fairness, and produces class values \(M_iq\). Conversely, those exact class values give fairness and total value \(q\).
Assessment: The claimed equivalence is proved in both directions.
For every inventory entry, \(v_{ta}>0\) justifies the invertible substitution
\[
y_e=v_{ta}x_{ta}.
\]
The transformed upper bound \(u_e=v_{ta}\mu_t\) and capacity coefficient \(r_e=s_{ta}/v_{ta}\) are correct. In particular, \(u_e>0\) and \(r_e>0\).
The maximum available class value is correctly identified as \(B_i=\sum_{e\in E_i}u_e\). A target exceeding \(B_i\) is impossible. An empty class inventory gives \(B_i=0\), so positive targets are correctly rejected.
For \(0<R\le B_i\), the index \(k\) exists. Its minimality gives \(P_{k-1}<R\le P_k\), ensuring that the proposed fractional entry satisfies
\[
0<R-P_{k-1}\le u_k.
\]
The allocation therefore respects every bound and has exactly the required total value.
The optimality proof checks out term by term:
Ties in the ratios cause no difficulty because the corresponding coefficients can be zero. The boundary \(R=B_i\) is also covered.
Assessment: The minimum-capacity formula is fully proved; no external fractional-knapsack theorem is assumed.
Necessity follows correctly from the exact-target reduction: each class must supply its required value, and each class’s capacity consumption is at least its computed minimum.
Sufficiency is also valid. The two class allocations involve disjoint inventory entries, and the formulation imposes no additional constraint coupling entries within a type. Consequently, the allocations can be combined, their capacity consumptions added, and the substitution inverted.
The criterion involving \(C_i(R_i)\) is understood after verifying \(R_i\le B_i\); the algorithm explicitly performs those checks before evaluating either minimum. There is no undefined evaluation for an impossible target.
Assessment: The decision criterion and algorithm match exactly the supported-mass formulation.
The operation counts are appropriate: two sorts require \(O(m\log(m+1))\) comparisons, and the remaining computations require \(O(m+\tau)\) rational arithmetic operations.
The ratio comparison
\[
s_ev_f\le s_fv_e
\]
is equivalent to the required ordering because both values are positive.
The bit-length argument is sufficient. Products and quotients of a constant number of input rationals have polynomial representation length. Sums and prefixes contain only polynomially many such terms; the stated common-denominator representation bounds denominator growth, and numerator growth is likewise polynomial.
The capacity formula has the same controlled structure. Exact rational arithmetic can therefore decide the final comparison with \(b\), including equality, in polynomial time. The argument establishes bit complexity rather than merely counting arithmetic operations.
Assessment: The polynomial-time claim is justified.
The citation is accurate. Section 4 defines the discrete program using probability variables over capacity-feasible subsets, requires equal expected owner values, and maximizes expected total value. Theorem 14 states its NP-hardness. [Feigenbaum and Johnson, *Selfish Knapsack*](https://arxiv.org/html/1510.07358)
The prover correctly identifies the relevant difference: the present task imposes one aggregate capacity inequality on selected masses and does not require a distribution supported on capacity-feasible discrete subsets. The cited hardness theorem is not applied to the present formulation, and the polynomial-time argument does not depend on it.
Assessment: The explanatory comparison is correct.
None. All substantive claims needed to settle the assigned decision problem are established.
⟨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.