Answer: \(\mathrm{NP}\)-complete, even for \(\tau=1\) with universal approval and positive integer costs and budgets.
Proposition 9 — class: hardness
Given projects \(C\), rational per-unit costs \(q_c\), and supported types \(\theta\) with rational masses \(\mu_\theta\), approval sets \(A_\theta\), and budgets \(b_\theta\), find a funded set \(S\subseteq C\) and contributions \(z_{\theta c}\geq 0\) maximizing \(\sum_\theta \mu_\theta\sum_{c\in S\cap A_\theta}q_c\), subject to \(z_{\theta c}=0\) for \(c\notin A_\theta\), \(\sum_c z_{\theta c}\leq b_\theta\), and \(\sum_\theta\mu_\theta z_{\theta c}=q_c\) for \(c\in S\) and \(0\) otherwise.
Let \(C\) be a set of \(m\geq 1\) indivisible projects with positive binary-rational costs \(q_c\).
A society is given by its support: the list of \(\tau\geq 1\) types with positive binary-rational masses \(\mu_\theta\), summing to \(1\). Each type has an approval set \(A_\theta\subseteq C\) and a positive binary-rational budget \(b_\theta\) per unit of mass. Here \(\tau\) is the support size, not the number of possible types.
An outcome consists of a funded set \(S\subseteq C\) and real contributions \(z_{\theta c}\geq 0\) per unit of type mass, satisfying \(z_{\theta c}=0\) whenever \(c\notin A_\theta\), \(\sum_{c\in C}z_{\theta c}\leq b_\theta\), and \(\sum_\theta\mu_\theta z_{\theta c}=q_c\) for \(c\in S\), with this sum equal to \(0\) otherwise.
Its utilitarian welfare is \(U(S)=\sum_\theta\mu_\theta\sum_{c\in S\cap A_\theta}q_c\). Projects must be fully funded or unfunded; contributions may be fractional.
Given also a nonnegative binary-rational threshold \(K\), decide whether a feasible outcome has \(U(S)\geq K\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite societies, computing a utilitarian-optimal implementable outcome is \(\mathrm{NP}\)-hard even with one agent. For a prescribed funded set, implementability can be checked in polynomial time.
The decision problem is \(\mathrm{NP}\)-complete, even when \(\tau=1\), the sole type approves every project, and all costs and budgets are positive integers. Thus a polynomial-time algorithm exists if and only if \(\mathrm{P}=\mathrm{NP}\).
We reduce from SUBSET SUM: given positive integers \(a_1,\ldots,a_m\) and a positive integer \(B\), all encoded in binary, decide whether some subset sums to \(B\). This is a standard \(\mathrm{NP}\)-complete problem, appearing as the exact-sum knapsack problem in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Construct an instance with projects \(C=\{c_1,\ldots,c_m\}\), costs \(q_{c_i}=a_i\), and one type satisfying
\(\mu_1=1,\qquad A_1=C,\qquad b_1=B.\)
Set \(K=B\). These data satisfy every required positivity and normalization condition. The construction copies the binary integers and has linear running time and output length in the source input length.
For any funded set \(S\), the funding equations force \(z_{1c}=q_c\) for \(c\in S\), and \(z_{1c}=0\) otherwise. Consequently,
\(S\text{ is feasible}\quad\Longleftrightarrow\quad\sum_{c\in S}q_c\le B.\)
For the reverse implication, the specified contributions themselves give a feasible outcome whenever this inequality holds. Since the type approves every project,
\(U(S)=\sum_{c\in S}q_c.\)
Therefore, feasibility together with \(U(S)\ge K=B\) is equivalent to
\(\sum_{c\in S}q_c=B.\)
The constructed instance is a yes-instance exactly when the original SUBSET SUM instance is a yes-instance. This proves \(\mathrm{NP}\)-hardness for support size one. Fractional contributions do not remove the discrete choice of which projects to fund.
A certificate consists solely of the funded set \(S\), encoded by \(m\) bits. We show that its feasibility and welfare can be checked in polynomial time; real contributions need not be supplied.
Define the total available budget of type \(\theta\) by \(B_\theta=\mu_\theta b_\theta\). Construct a directed network with source \(s\), one vertex for each type, one vertex for each project in \(S\), and sink \(t\). Its arcs and capacities are:
Let \(Q(S)=\sum_{c\in S}q_c\).
Feasibility equivalence. The set \(S\) is feasible if and only if the maximum flow value is \(Q(S)\).
Indeed, given feasible contributions, put \(x_{\theta c}=\mu_\theta z_{\theta c}\). The budget constraints give \(\sum_c x_{\theta c}\le B_\theta\), and full funding gives \(\sum_\theta x_{\theta c}=q_c\). Nonnegativity implies \(x_{\theta c}\le q_c\), so these amounts define a flow of value \(Q(S)\).
Conversely, a flow of value \(Q(S)\) saturates every project-to-sink arc, because their capacities sum to \(Q(S)\). Write \(x_{\theta c}\) for the flow on \(\theta\to c\), and set \(z_{\theta c}=x_{\theta c}/\mu_\theta\), with all other contributions zero. Division is valid because every mass is positive. Flow conservation gives full funding, and source-arc capacities give
\(\sum_c z_{\theta c}\le B_\theta/\mu_\theta=b_\theta.\)
Approval restrictions hold because the corresponding arcs exist only for approved projects. This proves the equivalence, including \(S=\varnothing\).
Welfare is computed exactly as
\(U(S)=\sum_{c\in S}q_c\sum_{\theta:\,c\in A_\theta}\mu_\theta,\)
and compared with \(K\).
The network has at most \(m+\tau+2\) vertices and \(m\tau+m+\tau\) arcs. Under the usual binary encoding of rationals, multiplying all input denominators produces a common scaling factor with \(O(L)\) bits. It clears the denominators of every capacity, including the products \(\mu_\theta b_\theta\). Scaled capacities and intermediate flow values have \(O(L)\) bits.
Using Edmonds–Karp and ordinary integer arithmetic gives the conservative verification bound
\(T_{\mathrm{verify}}=O\!\left((m+\tau+2)(m\tau+m+\tau)^2L^2\right).\)
Exact welfare computation and denominator preprocessing also fit within this bound. Hence the \(m\)-bit certificate has a polynomial-time verifier, proving membership in \(\mathrm{NP}\). Combined with the reduction, this establishes \(\mathrm{NP}\)-completeness.
For completeness, enumerating all funded sets gives a deterministic decision algorithm with running time
\(O\!\left(2^m(m+\tau+2)(m\tau+m+\tau)^2L^2\right).\)
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly: the decision problem is \(\mathrm{NP}\)-complete, already for one type. I found no major or minor mathematical issues.
The constructed instance satisfies the target’s requirements: positive costs and budget, one positive mass summing to one, universal approval, and a nonnegative threshold. Copying the numbers introduces no growth in their bit lengths. The claimed linear construction is valid with the usual indexed-project and approval-bit-vector encoding; polynomial construction suffices for the reduction.
\[
\sum_{c\in S}q_c\leq B.
\]
The prover explicitly supplies the converse through these same contributions. There are no additional approval constraints because every project is approved.
\[
U(S)=\sum_{c\in S}q_c.
\]
Combining feasibility with \(U(S)\geq B\) forces equality with \(B\). Conversely, any subset summing to \(B\) provides a feasible outcome meeting the threshold. Both directions of the reduction are established. Fractional contributions introduce no escape from this equality because the sole type’s contributions are fixed by full funding.
The empty funded set is covered correctly: its required flow value and welfare are both zero. In particular, the decision instance is accepted when \(K=0\).
The denominator-scaling claim is correct when “all input denominators” means all denominator occurrences in the input. In particular, the scaling product includes both the mass denominator and the budget denominator for each product \(\mu_\theta b_\theta\), even when those denominators have equal numerical values. The factor and scaled capacities have \(O(L)\) bits. Summing capacities and maintaining flows preserves that bit-length bound. The products in the welfare calculation likewise admit exact polynomial-time arithmetic.
Consequently, the certificate has a polynomial-time verifier, proving membership in \(\mathrm{NP}\). Together with the reduction, this establishes \(\mathrm{NP}\)-completeness. Enumerating the \(2^m\) certificates also gives the stated deterministic bound. The assertion about polynomial-time solvability being equivalent to \(\mathrm{P}=\mathrm{NP}\) follows.
Actionable feedback: No repair or additional lemma is needed. The output establishes the claimed classification for the specified support representation.
⟨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.