Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe first step of DA-Pareto, computing B∗, amounts to answering an NP-hard question, even for PB scenarios. Further- more, the second step of DA-Pareto, its for-loop, involves an expo- nential enumeration. DA-Greedy runs in polynomial time. Our result on the axiomatic properties of the greedy rule follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given projects \(P\), rational per-capita costs \(c_j>0\), a public budget \(L\), and a binary-encoded rational distribution \(\mu\) over complete voter types \(t=(s_t,d_t,u_t)\), with weight \(w_t=s_t-d_t\), compute the DA-Pareto outcome and a feasible funding witness. First choose \(B^*\in\arg\max\{S_\mu(B):\sum_{j\in B}c_j\le L\}\), where \(S_\mu(B)=\sum_t\mu_t w_t\sum_{j\in B}u_t(p_j)\). Then choose a support-maximizing bundle among \(B^*\) and bundles \(B\) that weakly improve every positive-mass type’s utility over \(B^*\), strictly improve at least one type, and can be funded within \(L\) plus donations from strictly benefiting types. Aggregate donations \(x_{t,j}\) must satisfy \(x_{t,j}=0\) when \(u_t(p_j)=0\), \(\sum_{j\in B}x_{t,j}\le\mu_t d_t\), and \(\sum_{j\in B}x_{t,j}>0\) only for types strictly benefiting over \(B^*\); public funding and donations together must cover each selected project’s cost. Return the selected bundle and its funding witness.
Let \(P=\{p_1,\ldots,p_m\}\), with \(m\ge1\), have indivisible projects of rational per-capita costs \(c_j>0\), and let \(\ell\ge0\) be the rational public budget.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. All numerical inputs are binary rationals; let \(L\) be their total encoding length.
Each complete type is \(t=(s_t,d_t,u_t)\), where \(s_t>0\), \(0\le d_t<s_t\), \(w_t=s_t-d_t\), and \(u_t(p_j)\ge0\) with \(\sum_j u_t(p_j)=1\). Define \(u_t(B)=\sum_{p_j\in B}u_t(p_j)\) and \(S_\mu(B)=\sum_t\mu_t w_tu_t(B)\); donations do not directly reduce utility.
First choose \(B^*\in\arg\max\{S_\mu(B):B\subseteq P,\ \sum_{p_j\in B}c_j\le\ell\}\).
A funding witness for \(B\) consists of nonnegative rational public payments \(\beta_j\) and aggregate donations \(x_{t,j}\), all zero outside \(B\), satisfying \(\sum_j\beta_j\le\ell\), \(\sum_jx_{t,j}\le\mu_td_t\), and \(\beta_j+\sum_tx_{t,j}=c_j\) for every \(p_j\in B\).
Require \(x_{t,j}=0\) whenever \(u_t(p_j)=0\) or \(u_t(B)\le u_t(B^*)\).
Let \(\mathcal T\) contain \(B^*\) and every bundle admitting such a witness with \(u_t(B)\ge u_t(B^*)\) for all support types and strict inequality for at least one. A DA-Pareto outcome maximizes \(S_\mu\) over \(\mathcal T\). Either maximization may choose any maximizer.
Is computing a DA-Pareto outcome together with a feasible funding witness polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For finite electorates, computing the initial public-budget optimum is NP-hard even when all voting weights are equal; DA-Greedy is polynomial-time computable. [Verified source](https://www.iog.io/api/research/pdf/ZHUBN4XC).
No result settling this exact distribution-over-types formulation was located in the literature search.
Theorem. Computing a DA-Pareto outcome together with a funding witness is \(\mathrm{NP}\)-hard, even when \(\tau=1\), the public budget and donation limit are strictly positive, and the sole type assigns positive utility to every project. The reduction is independent of both maximizations’ tie choices.
Zero donations already yield a knapsack special case. The proof below goes further: on every yes-instance, every final outcome strictly improves on the initial optimum and necessarily uses donations.
Construction. Reduce from SUBSET SUM: given positive binary-encoded integers \(a_1,\ldots,a_n\) and \(T\ge1\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=T\). This problem is \(\mathrm{NP}\)-complete; it is the exact-sum problem called KNAPSACK in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let \(A=\sum_{i=1}^n a_i\), and choose the smallest power of two \(M>A\). Create projects \(p_1,\ldots,p_n,q\), with
\( c_i=a_i,\qquad c_q=T+1,\qquad \ell=T-\frac12. \)
Use one type, of mass \(\mu=1\), with
\( s=\frac32,\qquad d=\frac12,\qquad w=s-d=1, \)
and utilities
\( u(p_i)=\frac{a_i}{M},\qquad u(q)=\frac{M-A}{M}. \)
Every utility is strictly positive, and their sum is \(1\). All numbers are dyadic rationals, so the construction also satisfies the narrower interpretation of “binary rational.” Their encoding lengths are polynomial in the SUBSET SUM input length: \(\log M=O(\log A)\), and \(\log A\le\log n+\max_i\log a_i+O(1)\).
Since \(\mu=w=1\), the objective is \(S_\mu(B)=u(B)\).
Properties of the initial and final bundles. Fix any permitted initial maximizer \(B^*\).
First, \(q\notin B^*\), because \(c_q>\ell\). The remaining project costs are integers, so public-budget feasibility implies
\( \sum_{p_i\in B^*}a_i\le T-1, \qquad u(B^*)\le\frac{T-1}{M}. \)
Second, every bundle admitting a funding witness satisfies
\( \sum_{p_j\in B}c_j =\sum_j\beta_j+\sum_jx_{1,j} \le\ell+\mu d =T. \)
The baseline bundle \(B^*\) also has a witness: pay its entire cost publicly and set all donations to zero. Thus every bundle in \(\mathcal T\) has total cost at most \(T\). In particular, none contains \(q\), whose cost is \(T+1\). Consequently, every \(B\in\mathcal T\) satisfies
\( S_\mu(B)=u(B)=\frac1M\sum_{p_i\in B}a_i\le\frac{T}{M}. \)
Yes-instances. Suppose \(\sum_{i\in I}a_i=T\), and let \(B_I=\{p_i:i\in I\}\). Then
\( u(B_I)=\frac{T}{M}>\frac{T-1}{M}\ge u(B^*). \)
Hence the sole type strictly benefits and is eligible to donate to every selected project.
Because \(T>0\), the set \(I\) is nonempty. Choose \(i_0\in I\), and define a witness by
\( x_{1,i_0}=\frac12,\qquad \beta_{i_0}=a_{i_0}-\frac12, \qquad \beta_i=a_i\ \text{for }i\in I\setminus\{i_0\}, \)
with all other payments and donations zero. These amounts are nonnegative because \(a_{i_0}\ge1\). They exactly fund each selected project, use donations totaling \(d=\frac12\), and use public payments totaling
\( \sum_j\beta_j=T-\frac12=\ell. \)
The donation restrictions hold because \(u(p_{i_0})>0\) and \(u(B_I)>u(B^*)\). Therefore \(B_I\in\mathcal T\).
The preceding upper bound now implies that every DA-Pareto outcome \(B\) has objective \(T/M\), hence \(\sum_{p_i\in B}a_i=T\). Moreover, any witness for such an outcome must donate at least \(T-\ell=\frac12\); donations are necessary.
No-instances and decoding. If the SUBSET SUM instance has no solution, every bundle in \(\mathcal T\) excludes \(q\) and has integer total cost at most \(T\), but cannot have cost exactly \(T\). Thus every DA-Pareto outcome has objective strictly less than \(T/M\).
Given any valid output bundle \(B\), we therefore recover the SUBSET SUM answer by testing whether
\( \sum_{p_i\in B}a_i=T. \)
This test takes polynomial time. It works for every initial maximizer and every final maximizer, and does not require examining the returned witness.
Therefore, a polynomial-time algorithm in \(m,\tau,L\) for the requested computation would solve SUBSET SUM in polynomial time. The requested problem is \(\mathrm{NP}\)-hard; a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the requested problem: computing a DA-Pareto outcome together with a funding witness is \(\mathrm{NP}\)-hard, even with one support type, strictly positive public budget and donation limit, and positive utility for every project. The reduction works for every allowed choice of initial and final maximizers.
No major or minor mathematical issues were found.
The prover states the source problem precisely: positive binary-encoded integers \(a_1,\ldots,a_n\), a positive integer target \(T\), and the question whether a subset sums exactly to \(T\). This is the standard \(\mathrm{NP}\)-complete SUBSET SUM problem. The linked [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf) is the cited source for the exact-sum problem under the name KNAPSACK.
The argument gives a polynomial-time construction and a polynomial-time decoder using one valid output of the requested computation. This suffices for the claimed computational hardness; it does not require establishing membership in a complexity class.
Because \(M>A\), every original project has positive utility \(a_i/M\), and the additional project has positive utility \((M-A)/M\). Their utilities sum exactly to \(1\).
The sole mass is \(1\), so it is positive and satisfies the normalization requirement. The parameters satisfy \(s=3/2>0\), \(0<d=1/2<s\), and \(w=1\). Every cost is positive. Since \(T\ge1\), the public budget \(\ell=T-1/2\) is strictly positive.
All constructed numbers are dyadic rationals, including the utilities because \(M\) is a power of two. Thus the construction satisfies either ordinary binary encoding of rationals or the narrower dyadic interpretation.
The stated bound on \(\log A\) is valid, and the smallest power of two exceeding \(A\) has polynomial bit length. There are \(n+1\) projects and one type. Each constructed numerator and denominator has polynomial bit length, so the total output encoding length is polynomial in the source input length.
Computing \(A\), \(M\), and the resulting rational entries requires only polynomial-time integer arithmetic. No numerical parameter is represented in unary or expanded according to its magnitude.
The inequality \(c_q=T+1>\ell\) excludes \(q\) from every initial feasible bundle.
All remaining costs are integers. Therefore a total cost at most \(T-1/2\) is necessarily at most \(T-1\). Since \(S_\mu=u\) and utilities on these projects are proportional to their costs, the bound
\[
u(B^*)\le (T-1)/M
\]
follows for every initial maximizer.
Paying each selected cost publicly and setting all donations to zero is a valid witness for \(B^*\). The donation restrictions are satisfied, including the restriction applying when \(u(B)=u(B^*)\).
Summing the project funding equalities and applying the public and donation limits gives total cost at most
\[
\ell+\mu d=T.
\]
This applies to every bundle admitting a witness. The separate baseline-witness observation correctly extends the bound to all members of \(\mathcal T\).
Consequently, no member of \(\mathcal T\) contains \(q\). For every remaining candidate, its objective equals its integer total cost divided by \(M\), and hence is at most \(T/M\).
A subset summing to \(T\) has utility \(T/M\), strictly exceeding the established bound for \(u(B^*)\). With one type, this establishes the entire Pareto condition and the type’s donation eligibility.
The subset is nonempty because \(T>0\). The designated project has cost at least \(1\), so its public payment \(a_{i_0}-1/2\) is nonnegative. The specified witness exactly funds every selected project, uses donation \(1/2=\mu d\), and uses public payment \(T-1/2=\ell\). All entries outside the bundle are zero.
The only positive donation goes to a project with positive utility, and the donor strictly improves. Thus every witness constraint is verified.
On a yes-instance, a candidate attains the universal upper bound \(T/M\). Every final maximizer must therefore attain that value and encode a subset summing to \(T\). Any witness for such a bundle must use at least \(T-\ell=1/2\) in donations.
On a no-instance, every candidate excludes \(q\) and has integer cost at most \(T\), but no candidate can have cost exactly \(T\). Its objective is therefore strictly below \(T/M\).
Testing the returned bundle’s original-project cost against \(T\) correctly decides SUBSET SUM in polynomial time. The argument never requires a particular tie choice or inspection of the returned witness.
None is required. The reduction establishes the stated hardness and the stronger donation and tie-independence claims. It does not claim strong \(\mathrm{NP}\)-hardness or \(\mathrm{NP}\)-completeness.
⟨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.