Answer: Assuming \(\mathrm{P}\ne\mathrm{NP}\), no polynomial-time \(f(m,\tau)\)-approximation exists for any finite, polynomial-time computable factor \(f\), even when \(\tau=2\) and \(\mu_1=\mu_2=1/2\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet f(m) be a polynomial time computable function. Even for two agents, there is no polynomial time f(m)-approximation algorithm for the UWO-WP problem, assuming P ̸= NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) projects with per-member costs \(c_j\), and \(\tau\) supported types with binary-rational masses \(\mu_t\), budgets \(b_t\), and additive values \(v_{tj}\), find a set \(W\subseteq M\) maximizing \(\sum_{t}\mu_t\sum_{j\in W}v_{tj}-\sum_{j\in W}c_j\), subject to \(\sum_{j\in W}c_j\leq\sum_t\mu_t\min\!\left(b_t,\sum_{j\in W}v_{tj}\right)\).
A society is given by its support: the list of the \(\tau\) 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.
There are \(m\ge1\) indivisible projects \(M=\{1,\ldots,m\}\). Per-member project costs \(c_j\), individual budgets \(b_t\), and additive values \(v_{tj}\) are nonnegative binary rationals; zero budgets are allowed. Assume \(\sum_t\mu_t v_{tj}\ge c_j\) for every project.
Write \(V_t(W)=\sum_{j\in W}v_{tj}\) and \(C(W)=\sum_{j\in W}c_j\). A bundle \(W\subseteq M\) is feasible exactly when \(C(W)\le\sum_t\mu_t\min\{b_t,V_t(W)\}\); the empty bundle is allowed.
This constraint expresses funding through nonnegative contributions bounded by each member's budget and value, so every member has nonnegative quasi-linear utility. Welfare is \(\mathrm{SW}(W)=\sum_t\mu_t V_t(W)-C(W)\); let \(\mathrm{OPT}\) be its maximum over feasible bundles.
An \(f(m,\tau)\)-approximation returns a feasible bundle with \(f(m,\tau)\mathrm{SW}(W)\ge\mathrm{OPT}\), where \(f\ge1\) is finite and polynomial-time computable. State running times in \(m,\tau,L\), where \(L\) is the total binary input length.
Does this problem admit a polynomial-time \(f(m,\tau)\)-approximation for some such \(f\), or is every such guarantee impossible assuming \(\mathrm{P}\ne\mathrm{NP}\), even when \(\tau=2\)?
For discrete agents with additive values, no polynomial-time \(f(m)\)-approximation exists for any polynomial-time computable finite factor, even with two agents, assuming \(\mathrm{P}\ne\mathrm{NP}\). [Source](https://link.springer.com/article/10.1007/s10458-025-09715-7)
No result specifically treating this normalized mass formulation was located in the literature search.
Assuming \(\mathrm{P}\ne\mathrm{NP}\), no polynomial-time approximation with any finite, polynomial-time computable factor \(f(m,\tau)\) exists, even when \(\tau=2\) and both masses equal \(1/2\).
We prove this directly, including all normalization and encoding checks.
Suppose an algorithm \(\mathcal A\) returns a feasible bundle satisfying \(f(m,\tau)\mathrm{SW}(\mathcal A(I))\ge\mathrm{OPT}(I)\), in time polynomial in \(m,\tau,L\).
Reduce from the standard NP-complete positive-integer SUBSET SUM problem: given \(a_1,\ldots,a_n\) and a positive target \(T\), decide whether some \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{j\in S}a_j=T\). Write \(A=\sum_{j=1}^n a_j\). Inputs with \(T>A\) can be rejected immediately, so assume \(1\le T\le A\).
Compute an integer \(K\ge f(n+1,2)\), and set \(H=KA+T+1\). Polynomial-time computability of \(f\) permits such an upper bound with polynomial binary length: round an exact numerical output upward, or round an additive-error-\(1\) approximation upward and add \(1\).
Construct \(m=n+1\) projects and exactly two types, with \(\mu_1=\mu_2=1/2\). Set their budgets to \(b_1=4T\) and \(b_2=0\).
The first \(n\) projects are ordinary projects. For each \(j\le n\), set \(c_j=a_j\), \(v_{1j}=4a_j\), and \(v_{2j}=0\).
Let \(p=n+1\) be the special project, with \(c_p=T\), \(v_{1p}=0\), and \(v_{2p}=2H\).
All costs, budgets, and values are nonnegative integers; the masses are positive binary rationals summing to \(1\). The two types are distinct. The required projectwise inequality holds:
Thus the constructed instance satisfies every stated hypothesis.
Fix an ordinary-project subset \(S\), and write \(x=\sum_{j\in S}a_j\). Consider \(W=S\cup\{p\}\).
Its cost is \(C(W)=x+T\). Its maximum funding is
\(\sum_t\mu_t\min\{b_t,V_t(W)\}=\frac12\min\{4T,4x\}+\frac12\min\{0,2H\}=\min\{2T,2x\}\).
Consequently, \(W\) is feasible exactly when \(x+T\le\min\{2T,2x\}\). This is equivalent to the conjunction \(x+T\le2T\) and \(x+T\le2x\), which respectively give \(x\le T\) and \(x\ge T\).
Therefore,
\(S\cup\{p\}\text{ is feasible}\Longleftrightarrow\sum_{j\in S}a_j=T\).
In particular, a feasible bundle containing \(p\) exists exactly when the SUBSET SUM instance is a yes-instance.
For any bundle \(S\) containing only ordinary projects, its welfare is
\(\mathrm{SW}(S)=2x-x=x\le A\).
If \(S\cup\{p\}\) is feasible, the previous section gives \(x=T\). Its welfare is then
\(\mathrm{SW}(S\cup\{p\})=2x+H-(x+T)=H\).
These calculations imply:
On a yes-instance, the approximation guarantee forces
\(\mathrm{SW}(\mathcal A(I))\ge H/f(n+1,2)\ge H/K>A\),
where the strict inequality follows from \(H=KA+T+1>KA\). Since every bundle omitting \(p\) has welfare at most \(A\), the algorithm must return a bundle containing \(p\).
On a no-instance, feasibility forces its output to omit \(p\).
Thus running \(\mathcal A\) and accepting exactly when its output contains \(p\) decides SUBSET SUM.
Let \(\ell\) be the total binary length of the SUBSET SUM input. Let \(q(n+1)\) be a polynomial bound on the computation time and output length needed for the integer upper bound \(K\).
Binary summation and multiplication show that \(H\) has \(O(\ell+q(n+1))\) bits. The constructed instance has \(m=n+1\), \(\tau=2\), and total input length \(L=O(\ell+q(n+1))\). Its construction takes polynomial time in \(n,\ell\).
If the approximation algorithm runs in time \(R(m,\tau,L)=\operatorname{poly}(m,\tau,L)\), the resulting SUBSET SUM decision algorithm runs in
\(\operatorname{poly}(n,\ell)+R(n+1,2,O(\ell+q(n+1)))\),
which is polynomial in the source input length. This contradicts \(\mathrm{P}\ne\mathrm{NP}\).
Normalization also gives an exact transfer from the cited discrete model. For two discrete agents with budgets \(B_i\), values \(u_{ij}\), and costs \(C_j\), take masses \(\mu_i=1/2\), budgets \(b_i=2B_i\), values \(v_{ij}=2u_{ij}\), and costs \(c_j=C_j\). Then, for every bundle \(W\),
\(\sum_i\mu_i\min\{b_i,V_i(W)\}=\sum_i\min\{B_i,U_i(W)\}\)
and
\(\sum_i\mu_iV_i(W)-C(W)=\sum_iU_i(W)-C(W)\).
Hence feasibility and welfare are preserved exactly, with only a constant increase in each numerical encoding length. This explains why the normalized support formulation inherits the discrete inapproximability result; the direct proof above establishes it independently. [Source, Theorem 4](https://link.springer.com/article/10.1007/s10458-025-09715-7)
⟨structured verdict parsed — rendered above⟩
The direct reduction is correct and establishes the requested inapproximability, including for support size \(\tau=2\) with equal masses. There is one minor qualification needed in the supplementary discussion of transferring arbitrary discrete instances: two discrete agents need not correspond to two distinct supported types. This does not affect the direct proof.
The prover fixes an arbitrary proposed approximation algorithm and its finite, polynomial-time computable factor \(f(m,\tau)\). The construction may depend on that factor: the argument seeks a contradiction separately for each proposed algorithm and guarantee.
Evaluating the factor at \((n+1,2)\) is appropriate because these are exactly the constructed instance’s project count and support size. No assumption that \(f\) is polynomially bounded in numerical value is made or needed.
The stated procedures for obtaining an integer \(K\ge f(n+1,2)\) are valid under the usual numerical interpretation of polynomial-time computability. An exact encoded output can be rounded upward. If an approximation has absolute error at most \(1\), rounding upward and adding \(1\) also supplies an upper bound. Polynomial running time bounds the output’s binary length. Since \(f\ge1\), the resulting \(K\) can be positive, as required by the later division.
Positive-integer SUBSET SUM with a positive target is the standard NP-complete decision problem stated in the proof. Rejecting instances with \(T>A\) is valid because all input integers are positive. The remaining range \(1\le T\le A\) supplies all the inequalities subsequently used.
The constructed instance meets the task’s requirements:
Thus this is a valid instance with support size exactly two, rather than merely two labels for possibly identical types.
For an arbitrary ordinary subset \(S\), the notation \(x=\sum_{j\in S}a_j\) is unambiguous. For \(W=S\cup\{p\}\), the cost and funding calculations are correct:
\[ C(W)=x+T,\qquad \sum_t\mu_t\min\{b_t,V_t(W)\}=\min\{2T,2x\}. \]
The zero-budget type contributes zero despite its large valuation.
The equivalence
\[ x+T\le\min\{2T,2x\} \quad\Longleftrightarrow\quad x\le T\ \text{and}\ x\ge T \]
is exact. Consequently, a feasible bundle containing \(p\) exists precisely when the source instance has a subset summing to \(T\).
This also handles the empty ordinary subset: since \(T>0\), the special project alone is infeasible.
For every ordinary-only bundle, feasible or otherwise, the welfare calculation gives
\[ \mathrm{SW}(S)=x\le A. \]
For every feasible bundle containing \(p\), feasibility forces \(x=T\), and the calculation gives
\[ \mathrm{SW}(S\cup\{p\})=H. \]
Since \(K\ge1\) and \(T>0\), the definition \(H=KA+T+1\) implies \(H>A\). Therefore the claimed yes-instance optimum \(\mathrm{OPT}=H\) follows.
The critical approximation inequalities have the correct direction:
\[ \mathrm{SW}(\mathcal A(I)) \ge\frac{H}{f(n+1,2)} \ge\frac{H}{K} >A. \]
Hence a yes-instance forces the algorithm to include \(p\). On a no-instance, the algorithm’s required feasibility forces it to omit \(p\). Inspecting that project’s presence therefore decides SUBSET SUM exactly. No welfare comparison or numerical evaluation of the algorithm’s achieved ratio is needed.
The bound on \(H\)’s binary length is valid: multiplication adds operand bit lengths up to a constant, and addition changes the bound only by a constant.
The ordinary-project entries require only constant-factor duplication and scaling of the source integers. The special valuation is the only entry containing \(H\). Thus the stated bound
\[ L=O(\ell+q(n+1)) \]
is consistent with the ordinary binary list encoding.
The factor computation, construction, approximation call, and output inspection all take polynomial time in the source input length. Although \(K\) can have a very large numerical value, its polynomial binary length suffices. The contradiction with \(\mathrm{P}\ne\mathrm{NP}\) follows.
The displayed scaling identities for funding and welfare are algebraically correct. The cited [Theorem 4](https://link.springer.com/article/10.1007/s10458-025-09715-7) indeed states inapproximability for polynomial-time computable factors with two agents in the additive setting.
Minor issue — support representation. The transfer paragraph starts with arbitrary two-agent discrete data. Such agents can have identical budgets and valuation vectors, in which case scaling does not produce two distinct types. Listing them separately would not match the task’s definition of support size.
Minimum clarification: qualify this paragraph’s two-type interpretation by requiring distinct scaled types, or explain how coincident types are represented in the support. The direct reduction already verifies distinctness, so this issue does not weaken its conclusion.
⟨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.