Answer: \(\mathrm{NP}\)-hard
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet µ be a satisfaction function that is strictly cost-responsive for instances with a single voter. Then, there is no polynomial-time algorithm that, given an ABB instance (A, P, c, b) as input, always computes an outcome satisfying µ-EJR, unless P = NP. Note that µ# does not satisfy strict cost-responsiveness. Indeed, outcomes satisfying µ#-EJR can be computed effi- ciently, e.g., by employing MES[µ#] (Peters, Pierczy´nski, 3Our result is less general in that it only considers the approval case and more general in that it does not assume additivity. and Skowron 2021; Los, Christoff, and Grossi 2022).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given projects with rational costs and budget, finitely many approval types with rational masses summing to one, and cost-based satisfaction, compute an integral feasible project set W satisfying mass-EJR: for every positive-mass coalition q and every commonly approved T with cost at most q's mass times the budget, some type in q must receive at least the satisfaction of T.
Definitions. An instance has a finite project set \(P\), binary-encoded rational costs \(c:P\to\mathbb{Q}_{>0}\), a binary-encoded rational budget \(b>0\), and a finite set \(\mathcal{T}\subseteq 2^P\) of approval types with binary-encoded rational masses \(\sigma_A\ge 0\) satisfying \(\sum_{A\in\mathcal{T}}\sigma_A=1\). Let \(c(S)=\sum_{p\in S}c(p)\). An outcome is an integral \(W\subseteq P\) with \(c(W)\le b\).
Call \(W\) mass-EJR if, for every \(T\subseteq P\) and every \(z\) with \(0\le z_A\le\sigma_A\), \(q(z)=\sum_A z_A>0\), \(z_A>0\Rightarrow T\subseteq A\), and \(c(T)\le q(z)b\), some \(A\) with \(z_A>0\) satisfies \(c(A\cap W)\ge c(T)\). The computational problem is to find a mass-EJR outcome.
Target. Is computing a mass-EJR outcome solvable in polynomial time, or is it NP-hard?
Nearest known results. For the finite-voter version with cost-based satisfaction, computing an EJR outcome is NP-hard unless \(\mathrm{P}=\mathrm{NP}\). No verified result was located for exactly the finite-type mass formulation above.
Computing a mass-EJR outcome is \( \mathrm{NP} \)-hard, even for instances having exactly one approval type of mass \(1\), where that type approves every project.
The reduction is from Subset Sum. Consequently, a polynomial-time algorithm for computing a mass-EJR outcome would imply \( \mathrm{P}=\mathrm{NP} \).
Fix an outcome \(W\). For every nonempty \(T\subseteq P\), define the mass of the approval types that approve \(T\) but would not be satisfied by \(W\) at level \(c(T)\) as
\[ \beta_W(T) = \sum_{\substack{A\in\mathcal T:\\ T\subseteq A,\; c(A\cap W)<c(T)}} \sigma_A. \]
The outcome \(W\) is mass-EJR if and only if, for every nonempty \(T\subseteq P\),
\[ c(T)>b\,\beta_W(T). \]
Suppose first that \(W\) is not mass-EJR. Then there are \(T\subseteq P\) and \(z\) satisfying all the conditions in the definition, while every type \(A\) with \(z_A>0\) has
\[ c(A\cap W)<c(T). \]
Because \(q(z)>0\) and all project costs are positive, \(T\) is nonempty. Every type in the support of \(z\) is therefore included in the sum defining \(\beta_W(T)\). Since \(z_A\le \sigma_A\),
\[ q(z)=\sum_A z_A\le \beta_W(T). \]
The cohesiveness condition gives
\[ c(T)\le q(z)b\le \beta_W(T)b. \]
Thus the displayed strict inequality fails.
Conversely, suppose that for some nonempty \(T\),
\[ c(T)\le b\,\beta_W(T). \]
Since \(c(T)>0\), this implies \(\beta_W(T)>0\). Define
\[ z_A= \begin{cases} \sigma_A,&\text{if }T\subseteq A\text{ and }c(A\cap W)<c(T),\\ 0,&\text{otherwise}. \end{cases} \]
Then \(0\le z_A\le\sigma_A\),
\[ q(z)=\beta_W(T)>0, \]
and every type with \(z_A>0\) approves all of \(T\). Moreover,
\[ c(T)\le q(z)b. \]
By construction, every type \(A\) with \(z_A>0\) satisfies
\[ c(A\cap W)<c(T). \]
Hence this \(T,z\) violates mass-EJR. This proves the equivalence. \( \square \)
Consider the restricted family of instances with
\[ \mathcal T=\{P\}, \qquad \sigma_P=1. \]
For every \(T\subseteq P\),
\[ c(P\cap W)=c(W). \]
In this one-type family, a feasible outcome \(W\) is mass-EJR if and only if
\[ c(W)=\max\{c(S):S\subseteq P,\ c(S)\le b\}. \]
Suppose \(W\) is mass-EJR. Let \(S\subseteq P\) satisfy \(c(S)\le b\). Choose \(T=S\) and \(z_P=1\). These choices satisfy
\[ q(z)=1,\qquad c(T)\le q(z)b=b. \]
Mass-EJR therefore requires
\[ c(P\cap W)=c(W)\ge c(S). \]
This holds for every budget-feasible \(S\), so \(W\) has maximum possible feasible cost.
Conversely, suppose \(W\) has maximum cost among all budget-feasible subsets. Consider any admissible \(T,z\). Since there is only one type, \(z_P>0\), \(q(z)=z_P\le1\), and
\[ c(T)\le q(z)b\le b. \]
Thus \(T\) is budget-feasible. Optimality of \(W\) gives
\[ c(P\cap W)=c(W)\ge c(T), \]
which is exactly the required witness condition. Hence \(W\) is mass-EJR. \( \square \)
Because \(P\) is finite, a maximum-cost budget-feasible subset always exists. Thus these restricted instances are guaranteed to admit mass-EJR outcomes.
Take an instance of Subset Sum consisting of positive integers
\[ a_1,\ldots,a_n \]
and a positive integer target \(B\). Construct the mass-EJR instance
\[ P=\{p_1,\ldots,p_n\},\qquad c(p_i)=a_i,\qquad b=B, \]
with the single approval type
\[ \mathcal T=\{P\},\qquad \sigma_P=1. \]
This construction is polynomial in the binary encoding of the Subset Sum instance.
Suppose an algorithm returns a mass-EJR outcome \(W\). By the proposition, \(W\) maximizes \(c(S)\) over all subsets satisfying \(c(S)\le B\). Therefore,
\[ c(W)=B \]
if and only if there is a subset of the integers whose sum is exactly \(B\):
Thus one call to a polynomial-time mass-EJR finder, followed by an exact rational comparison, would decide Subset Sum in polynomial time.
Computing a mass-EJR outcome is \( \mathrm{NP} \)-hard unless \( \mathrm{P}=\mathrm{NP} \). The hardness already holds with one approval type of mass \(1\) approving every project. It is therefore driven entirely by the integral project-selection problem, not by the representation of the population masses.
The reduction is from the weakly \( \mathrm{NP} \)-complete Subset Sum problem, so it proves \( \mathrm{NP} \)-hardness but does not by itself establish strong \( \mathrm{NP} \)-hardness.
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces Subset Sum to computing a mass-EJR outcome. The central characterization of the one-type case is sound: when the sole type approves every project, mass-EJR outcomes are exactly the budget-feasible subsets having maximum total cost. Consequently, a polynomial-time mass-EJR finder would decide Subset Sum by checking whether the returned cost equals the target.
The argument establishes weak NP-hardness under a polynomial-time oracle reduction. There are two minor rigor issues, neither affecting the conclusion.
For fixed \(W\), the definition
\[ \beta_W(T)= \sum_{\substack{A\in\mathcal T:\\ T\subseteq A,\; c(A\cap W)<c(T)}} \sigma_A \]
correctly measures the total mass that can participate in a violation associated with \(T\).
In the forward direction, the support of a violating \(z\) consists only of types counted by \(\beta_W(T)\). Hence
\[ q(z)\leq \beta_W(T), \]
and the cohesiveness condition implies
\[ c(T)\leq q(z)b\leq \beta_W(T)b. \]
This direction is correct.
In the converse direction, setting \(z_A=\sigma_A\) precisely for the types counted by \(\beta_W(T)\) is legitimate. The assumption \(c(T)\leq b\beta_W(T)\), together with nonempty \(T\) and positive project costs, ensures \(\beta_W(T)>0\). The constructed \(z\) then satisfies every condition for a violation. This direction is also correct.
There is one local logical imprecision: the sentence “Because \(q(z)>0\) and all project costs are positive, \(T\) is nonempty” does not follow from those two facts. An admissible pair may have \(T=\varnothing\) and \(q(z)>0\). Here \(T\neq\varnothing\) instead follows from the additional failure condition
\[ c(A\cap W)<c(T) \]
for supported types, since \(T=\varnothing\) would give \(c(T)=0\), whereas \(c(A\cap W)\geq0\). The intended conclusion is nevertheless valid from the assumptions already written.
When \(\mathcal T=\{P\}\) and \(\sigma_P=1\), the identity
\[ c(P\cap W)=c(W) \]
is correct.
If \(W\) is mass-EJR, then for every feasible \(S\), the choice \(T=S\) and \(z_P=1\) is admissible. Mass-EJR gives \(c(W)\geq c(S)\), proving that \(W\) is an optimal budget-feasible subset.
Conversely, for any admissible \(T,z\), the condition \(q(z)>0\) implies \(z_P>0\), and
\[ c(T)\leq z_Pb\leq b. \]
Thus \(T\) is budget-feasible, so optimality of \(W\) gives \(c(W)\geq c(T)\). The unique supported type \(P\) consequently witnesses the mass-EJR condition. This proves the equivalence without a gap.
The existence statement is also correct: the finite collection of feasible subsets is nonempty because it contains \(\varnothing\), so a maximum-cost feasible subset exists.
The construction preserves binary encoding size: the project costs are the positive integers \(a_i\), the budget is \(B\), and the only mass is \(1\). It is therefore polynomial-time.
Every returned mass-EJR outcome is an optimal subset for the capacity \(B\). Hence:
The final comparison is polynomial-time and exact. Thus a polynomial-time mass-EJR finder would yield a polynomial-time algorithm for Subset Sum.
Strictly, this is a polynomial-time oracle reduction from the decision problem Subset Sum to the mass-EJR search problem. Because the target is a search problem, the prover should name the reduction convention under which “NP-hard” is being used. Regardless of terminology, the demonstrated consequence that a polynomial-time finder would imply \(\mathrm P=\mathrm{NP}\) is rigorous.
The reduction uses binary-encoded integers, so it establishes ordinary, weak NP-hardness. The prover correctly refrains from claiming strong NP-hardness.
⟨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.