Answer: \(\mathrm{NP}\text{-hard}\); the threshold decision problem is \(\mathrm{NP}\text{-complete}\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a single-peaked instance I = (N, H, ≻ , ✄), minimizing the number of envious agents admits a poly- nomial time algorithm with run time O(|H|2). Notations. For a house h, we denote the set of agents who prefer it to all other houses as base(h). That is, base(h) = {i ∈N | h ≻i h′ for all h′ ̸= h} = {i ∈N | h = peak(i)}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given housing classes \(H\) on a common axis, a list of \(\tau\) complete strict single-peaked rankings \(r\), rational type masses \(\mu_r\geq 0\) summing to \(1\), and rational per-capita class capacities \(\sigma_h\) with \(\sum_h \sigma_h>1\), choose assignment masses \(y_{r,h}\geq 0\) satisfying \(\sum_h y_{r,h}=\mu_r\) and \(\sum_r y_{r,h}\leq \sigma_h\). Let \(S(y)=\{h:\sum_r y_{r,h}>0\}\) and \(\mathcal E(y)=\sum_{r,h}y_{r,h}\mathbf{1}[\exists g\in S(y):g\succ_r h]\). Find a feasible assignment minimizing \(\mathcal E(y)\).
Let \(H\) be a nonempty set of \(m\) housing classes with a supplied common axis. Types are complete strict rankings \(\succ_r\) of \(H\), single-peaked on that axis.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_r\) a binary rational, with \(\sum_r\mu_r=1\). Here \(\tau\) is the support size, not the number of possible rankings.
Class capacities are binary rationals \(\sigma_h\geq0\), with \(\sum_h\sigma_h>1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
An assignment consists of real masses \(y_{r,h}\geq0\) satisfying \(\sum_h y_{r,h}=\mu_r\) and \(\sum_r y_{r,h}\leq\sigma_h\); types may be split among classes and capacity may remain unused.
Define \(S(y)=\{h\in H:\sum_r y_{r,h}>0\}\) and the envious mass \(\mathcal E(y)=\sum_{r,h}y_{r,h}\mathbf 1[\exists g\in S(y):g\succ_r h]\). Thus any positive occupied mass in a preferred class triggers envy, including mass of the same type.
Is finding a feasible assignment minimizing \(\mathcal E(y)\) solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For discrete injective allocations with more houses than agents and complete strict single-peaked rankings on a common axis, minimizing the number of envious agents admits a polynomial-time algorithm, with reported runtime \(O(m^2)\). [Source](https://arxiv.org/html/2511.07022v1)
No result settling this exact mass-and-occupied-support formulation was located in the literature search.
Finding an assignment minimizing envious mass is \(\mathrm{NP}\text{-hard}\). The threshold decision problem is \(\mathrm{NP}\text{-complete}\).
The hardness holds even when every mass and capacity is a positive dyadic rational and \(\tau=m\). Thus a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
We reduce from Subset Sum: given positive binary integers \(a_1,\ldots,a_n\) and an integer \(B\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies
\(\displaystyle \sum_{i\in I}a_i=B.\)
Subset Sum is a standard \(\mathrm{NP}\text{-hard}\) problem; see, for example, [Polak, Rohwedder, and Węgrzycki](https://arxiv.org/abs/2105.04035). Write \(A=\sum_{i=1}^n a_i\). We may restrict to \(0<B<A\): cases outside this range are immediately decidable and can be mapped to fixed yes or no instances within the range.
Let \(D\) be the smallest power of two satisfying \(D\geq 8(n+1)A\). Define
\(\displaystyle c_i=\frac{a_i}{D},\qquad C=\frac{A}{D},\qquad \delta=\frac{B}{D},\qquad G=2C,\qquad K=1-2(n+1)C-\delta.\)
These numbers are dyadic rationals. Moreover,
\(\displaystyle 0<\delta<C\leq\frac{1}{8(n+1)}\leq\frac{1}{16},\)
and
\(\displaystyle K\geq\frac34-\delta>\frac34-C\geq\frac{11}{16}>C.\)
In particular, all parameters used as masses or capacities below are positive.
Use the \(2n+1\) classes on the supplied axis
\(\displaystyle z<p_1<q_1<p_2<q_2<\cdots<p_n<q_n.\)
Their capacities are
\(\displaystyle \sigma_z=K,\qquad \sigma_{p_i}=G+2c_i,\qquad \sigma_{q_i}=c_i.\)
There are \(2n+1\) supported types:
| Type | Mass | Peak |
|---|---:|---|
| Anchor type \(r_0\) | \(K+\delta\) | \(z\) |
| Guard type \(s_i\) | \(G\) | \(p_i\) |
| Item type \(r_i\) | \(2c_i\) | \(q_i\) |
For each type, complete its ranking as follows: rank its peak first, then all classes to its left in decreasing axis order, then all classes to its right in increasing axis order.
Each ranking is complete and strict. On either side of its peak, classes become less preferred as their distance along the axis increases, so every ranking is single-peaked. In particular, item type \(r_i\) ranks \(q_i\) first and \(p_i\) second. The types have distinct peaks and hence are distinct.
The masses sum to one:
\(\displaystyle (K+\delta)+nG+2\sum_i c_i=K+\delta+2(n+1)C=1.\)
The total capacity is
\(\displaystyle K+\sum_i(G+2c_i+c_i)=1-\delta+C>1.\)
Thus the construction satisfies every input promise.
All numerical data have bit length \(O(\log n+\log A)\), because \(D<16(n+1)A\). Explicitly writing the rankings and numerical data takes polynomial time and produces
\(\displaystyle m=\tau=2n+1,\qquad L=O\!\left(n^2\log(n+1)+n(\log(n+1)+\log A)\right).\)
Let
\(\displaystyle F=\{z,p_1,\ldots,p_n\}.\)
Its total capacity is
\(\displaystyle \sum_{h\in F}\sigma_h=K+nG+2C=1-\delta.\)
Every class in \(F\) has capacity greater than \(C\): this follows from \(K>C\) and \(\sigma_{p_i}=2C+2c_i>C\).
Suppose a feasible assignment left some \(h\in F\) unoccupied. The total capacity available in its occupied support would then be at most
\(\displaystyle \sum_{g\in H}\sigma_g-\sigma_h =1-\delta+C-\sigma_h<1-\delta<1.\)
That cannot accommodate population mass one. Therefore every feasible assignment occupies every class in \(F\).
For a feasible assignment \(y\), define
\(\displaystyle I(y)=\{i:q_i\in S(y)\},\qquad t(y)=\sum_{i\in I(y)}c_i.\)
Its support is precisely \(F\cup\{q_i:i\in I(y)\}\). Consequently, feasibility requires
\(\displaystyle 1\leq\sum_{h\in S(y)}\sigma_h=1-\delta+t(y),\)
so
\[\displaystyle t(y)\geq\delta.\tag{1}\]
Because \(z\) is occupied and is the anchor type’s peak, all anchor-type mass assigned outside \(z\) is envious. The anchor type has mass \(K+\delta\), whereas \(z\) has capacity \(K\). Thus its envious mass is at least \(\delta\).
For each \(i\in I(y)\), class \(q_i\) is occupied and is item type \(r_i\)’s peak. Hence every part of that type assigned outside \(q_i\) is envious. Its mass is \(2c_i\), while \(q_i\) has capacity \(c_i\), so its envious mass is at least \(c_i\).
These are different types, and all remaining envy contributions are nonnegative. Therefore
\[\displaystyle \mathcal E(y)\geq\delta+\sum_{i\in I(y)}c_i=\delta+t(y).\tag{2}\]
Set the decision threshold to \(\eta=2\delta\). If \(\mathcal E(y)\leq\eta\), inequalities (1) and (2) imply
\(\displaystyle \delta\leq t(y)\leq\delta.\)
Thus \(t(y)=\delta\), equivalently
\(\displaystyle \sum_{i\in I(y)}a_i=B.\)
This proves that a housing yes-instance implies a Subset Sum yes-instance. The argument applies to arbitrary real assignments and arbitrary positive occupation amounts.
Conversely, suppose \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=B\), so \(\sum_{i\in I}c_i=\delta\).
Define the assignment by the following nonzero entries; all other entries are zero:
Every type receives its prescribed total mass. In particular, the anchor row sums to \(K+\sum_{i\in I}c_i=K+\delta\).
Class \(z\) receives exactly \(K\). Each \(p_i\) receives exactly \(G+2c_i\), and each occupied \(q_i\) receives exactly \(c_i\). Hence the assignment is feasible, with support \(F\cup\{q_i:i\in I\}\).
Its envy is exactly:
Guards are at their peaks. For \(i\notin I\), item type \(r_i\) is at its second choice \(p_i\), and its only preferred class \(q_i\) is unoccupied. Item mass at \(q_i\) is at its peak. Therefore
\(\displaystyle \mathcal E(y)=2\delta=\eta.\)
We have proved the exact equivalence
\(\displaystyle \exists I:\sum_{i\in I}a_i=B \quad\Longleftrightarrow\quad \exists\text{ feasible }y:\mathcal E(y)\leq2\delta.\)
This establishes \(\mathrm{NP}\text{-hardness}\).
The use of real assignments does not obstruct membership in \(\mathrm{NP}\).
For any nonempty \(S\subseteq H\), let \(b_r(S)\) be type \(r\)’s most preferred class in \(S\). Consider the rational linear program with variables \(y_{r,h}\) for \(h\in S\), the usual row and capacity constraints, and objective
\(\displaystyle C_S(y)=\sum_r\sum_{h\in S\setminus\{b_r(S)\}}y_{r,h}.\)
Classes in \(S\) may receive zero mass. If the resulting actual support is \(T\subseteq S\), then
\(\displaystyle \mathcal E(y)\leq C_S(y),\)
because every preferred occupied class belongs to \(S\).
A decision certificate is the subset \(S\). Verify it by checking feasibility of this linear program with the additional inequality \(C_S(y)\leq\eta\).
This verifier is sound by the preceding inequality. It is complete because, for any assignment satisfying the threshold, choosing \(S=S(y)\) gives \(C_S(y)=\mathcal E(y)\). The linear program has at most \(m\tau\) variables, rational coefficients, and polynomial encoding length. Rational linear programming therefore verifies the certificate in time polynomial in \(m,\tau,L+\ell(\eta)\), where \(\ell(\eta)\) is the threshold’s bit length. The decision problem is consequently \(\mathrm{NP}\text{-complete}\).
For completeness, minimizing \(C_S\) over all nonempty subsets \(S\) gives an exact algorithm running in
\(\displaystyle 2^m\operatorname{poly}(m,\tau,L).\)
Indeed, let \(v\) be the smallest feasible linear-program optimum. Every assignment \(y\), evaluated using \(S(y)\), satisfies \(\mathcal E(y)=C_{S(y)}(y)\geq v\). An optimizer of a linear program attaining \(v\) has actual envy at most \(v\), and therefore exactly \(v\). This also proves that a rational optimal assignment exists.
The known polynomial result concerns [discrete injective allocations](https://arxiv.org/html/2511.07022v1). Here, occupying \(q_i\) makes all of its type’s mass outside \(q_i\) envious, although \(q_i\) can accommodate only half that type. Together with the forced baseline support, this produces the exact subset-sum constraint.
⟨structured verdict parsed — rendered above⟩
Verdict: the proof is correct and resolves the target. The reduction establishes NP-hardness for the exact mass-and-occupied-support formulation, including arbitrary real assignments. The decision-membership argument also establishes NP-completeness for binary-rational thresholds. I found no major or minor issues requiring repair.
The source problem is Subset Sum with positive binary integers, a standard NP-hard problem, as also identified in the [cited source](https://arxiv.org/abs/2105.04035).
Restricting to \(0<B<A\), where \(A=\sum_i a_i\), is legitimate. With positive items, cases outside this range are immediately decidable, including the boundary cases \(B=0\) and \(B=A\). Replacing those cases by fixed instances of the appropriate answer preserves a polynomial-time reduction.
The restricted instances have \(n\geq1\) and \(A>0\), so all subsequent definitions are well-defined.
The choice of \(D\) gives
\[
C=\frac{A}{D}\leq\frac{1}{8(n+1)},\qquad 0<\delta<C.
\]
Since \(n\geq1\), the bound \(C\leq1/16\) is valid.
The claimed lower bound on \(K\) follows from
\[
2(n+1)C\leq\frac14.
\]
Thus
\[
K\geq\frac34-\delta>\frac34-C\geq\frac{11}{16}>C.
\]
Every constructed mass and capacity is therefore positive.
All parameters are dyadic rationals: their denominators divide the power of two \(D\). Minimality of \(D\) gives \(D<16(n+1)A\), so the stated numerical bit-length bound is correct. Explicitly listing all rankings requires the stated polynomial amount of space. In particular, the reduction is polynomial in the binary input size; it does not expand the integers into unary data.
The ranking rule produces a complete strict ranking for every type. On each side of the peak, preference decreases as one moves away from the peak along the axis. Ranking the entire left side before the right side is compatible with single-peakedness; single-peakedness does not require a particular comparison between opposite sides.
For item type \(r_i\), \(p_i\) is the immediate predecessor of its peak \(q_i\), so \(p_i\) is indeed its second choice. Distinct peaks ensure that the listed types are distinct. Hence \(\tau=m=2n+1\) is the actual support size.
Both normalization calculations are correct:
\[
(K+\delta)+nG+2C=1,
\]
and
\[
K+nG+3C=1-\delta+C>1.
\]
The constructed instance satisfies all the task’s promises.
The baseline capacity calculation is correct:
\[
\sum_{h\in F}\sigma_h=K+nG+2C=1-\delta.
\]
Each baseline class has capacity greater than \(C\).
If a baseline class \(h\) were unoccupied, all assigned mass would lie in the other classes, whose total capacity is at most
\[
1-\delta+C-\sigma_h<1-\delta<1.
\]
This contradicts the row constraints, which require total assigned mass one. This argument permits unused capacity and applies to arbitrary real assignments.
Consequently, the support has precisely the asserted form. Its capacity must accommodate mass one, giving
\[
t(y)\geq\delta.
\]
No lower bound on individual positive occupation amounts is assumed or needed.
Since \(z\) is occupied and is the anchor’s peak, all anchor mass outside \(z\) is envious. Capacity at \(z\) limits the anchor’s nonenvious mass to at most \(K\), giving envious mass at least \(\delta\).
For each occupied \(q_i\), that class is item type \(r_i\)’s peak. Its capacity is \(c_i\), while the type’s mass is \(2c_i\). Thus at least \(c_i\) of that type is envious.
These contributions belong to distinct types and cannot double-count assignment mass. Therefore
\[
\mathcal E(y)\geq\delta+t(y).
\]
Combining this with feasibility and the threshold \(\mathcal E(y)\leq2\delta\) forces \(t(y)=\delta\), exactly the required subset-sum equality.
This implication correctly uses the task’s convention that occupation by the same type also triggers envy. It remains valid even when a selected class has arbitrarily small positive occupation.
The proposed assignment has the correct row sums. The anchor row sums to \(K+\delta\); every guard and item row also receives its prescribed mass.
For an unselected index, \(p_i\) receives \(G+2c_i\). For a selected index, it receives \(G+c_i+c_i=G+2c_i\). Class \(z\) and every selected \(q_i\) also receive exactly their capacities. Unselected \(q_i\) receive zero. Thus feasibility and the asserted support are verified.
The envy calculation is exhaustive:
Hence \(\mathcal E(y)=2\delta\). Together with the reverse implication, this establishes the claimed many-one reduction and NP-hardness of finding an exact minimizing assignment.
For nonempty \(S\), strict rankings give a unique \(b_r(S)\). If an LP solution has actual support \(T\subseteq S\), every positive assignment entry counted as envious under \(T\) is counted by \(C_S\). An entry at \(b_r(S)\) cannot be envious under \(T\). Thus
\[
\mathcal E(y)\leq C_S(y)
\]
is correct.
The subset certificate is sound by this inequality and complete by choosing \(S=S(y)\). The verifier invokes the standard polynomial-time feasibility theorem for rational linear programs. Its hypotheses are satisfied: there are at most \(m\tau\) variables, polynomially many rational constraints, and coefficient encoding length polynomial in the instance length and threshold length. Consequently, the stated NP-membership argument is valid.
The exponential algorithm also handles the potential mismatch between declared and actual support correctly. Every assignment has envy at least the smallest LP optimum \(v\), while an optimizer attaining \(v\) has actual envy at most \(v\).
The LP optima used here exist: feasible regions are closed and bounded by the row constraints, and the full-set LP is feasible under the task’s capacity promise. Rational LP data admit a rational optimal solution. Thus the claims of exact optimization, attainment, and a rational optimal assignment are justified.
The [discrete result cited for comparison](https://arxiv.org/html/2511.07022v1) concerns injective allocations of indivisible houses. It is not used as a premise of the reduction. The continuous hardness conclusion follows independently from the verified construction.
No additional clarification or mathematical repair is needed.
⟨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.