Answer: \(\mathrm{NP}\)-hard, even for \(\tau=1\) and dyadic input data.
Theorem 7 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateA proportional complete multi-allocation that is feasible and contiguous exists for any number m of layers and any number n ≥m of agents where m = 2a for some a ∈Z+.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m=2^a\), a finite type set \(\Theta\) with masses \(\mu_\theta\), valuation densities \(v_{\theta j}\), and per-capita capacities \(\kappa_j(x)\), compute a finite mass allocation \(\{(w_{\theta r},B^{\theta r})\}\) such that \(\sum_r w_{\theta r}=\mu_\theta\), every \(B^{\theta r}\) is contiguous and non-overlapping across layers, \(\sum_{\theta,r}w_{\theta r}\mathbf 1[x\in B^{\theta r}_j]=\kappa_j(x)\) almost everywhere, and \(V_\theta(B^{\theta r})\ge p_\theta=\sum_j\int_0^1\kappa_j(x)v_{\theta j}(x)\,dx\) for every supported bundle.
Let \(m=2^a\), with \(a\in\mathbb Z_{\ge0}\), and let each layer be \([0,1]\).
A society is given by its support: the list of \(\tau\) types with positive masses \(\mu_\theta\), each a binary rational, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
The densities \(v_{\theta j}\) and per-capita capacities \(\kappa_j\) are explicitly given nonnegative piecewise-constant functions with binary-rational breakpoints and values; require \(\sum_j\int_0^1v_{\theta j}(x)\,dx=1\) and \(\sum_j\kappa_j(x)\le1\) almost everywhere. Let \(L\) be the total input bit length.
A bundle \(B=(B_j)_{j=1}^m\) contains one interval, possibly empty, in each layer; intervals in different layers must have disjoint interiors. Define \(V_\theta(B)=\sum_j\int_{B_j}v_{\theta j}(x)\,dx\) and \(p_\theta=\sum_j\int_0^1\kappa_j(x)v_{\theta j}(x)\,dx\).
A finite mass allocation consists of finitely many bundles \(B^{\theta r}\) with positive weights \(w_{\theta r}\), satisfying \(\sum_r w_{\theta r}=\mu_\theta\), \(\sum_{\theta,r}w_{\theta r}\mathbf1[x\in B^{\theta r}_j]=\kappa_j(x)\) almost everywhere for every layer, and \(V_\theta(B^{\theta r})\ge p_\theta\) for every supported bundle. Weights and interval endpoints must be binary rationals; endpoint conventions are immaterial.
Can such an allocation be computed, or nonexistence decided, in time polynomial in \(m,\tau,L\), or is deciding existence \(\mathrm{NP}\)-hard?
For finitely many agents, a complete proportional allocation with contiguous, non-overlapping bundles exists whenever \(n\ge m=2^a\). [Hosseini–Igarashi–Searns](https://www.ijcai.org/proceedings/2020/0026.pdf)
Later work establishes finite-agent existence for every \(n\ge m\); it does not settle the prescribed-capacity mass problem above. [Igarashi–Meunier](https://arxiv.org/pdf/2106.02262)
Deciding existence is \(\mathrm{NP}\)-hard, even when \(\tau=1\), all numerical data are dyadic rationals, and each capacity takes only the values \(0\) and \(1/2\).
We prove this by a polynomial-time reduction from PARTITION. Consequently, an algorithm that computes an allocation or decides nonexistence in time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
PARTITION asks whether given positive integers \(b_1,\ldots,b_k\), encoded in binary, admit a subset \(T\subseteq\{1,\ldots,k\}\) satisfying
\(\displaystyle \sum_{j\in T}b_j=\frac12\sum_{j=1}^k b_j.\)
This problem is \(\mathrm{NP}\)-complete; see the [MIT lecture notes on NP-completeness](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf).
Let \(m\) be the smallest power of two at least \(k\), and pad the list by setting \(b_j=0\) for \(k<j\le m\). Define
\(\displaystyle S=\sum_{j=1}^m b_j,\qquad Q=2^{\lceil\log_2 S\rceil},\qquad \ell=\frac1{4m}.\)
There is one supported type, with mass \(\mu=1\); we suppress its type index.
For each layer \(j\), define two windows of length \(\ell\):
\(\displaystyle A_j=[(4j-4)\ell,(4j-3)\ell],\qquad C_j=[(4j-2)\ell,(4j-1)\ell].\)
All these windows have pairwise disjoint interiors. Within each layer, the two windows are separated by a gap of length \(\ell\).
Set
\(\displaystyle \kappa_j(x)=\frac12\mathbf1_{A_j\cup C_j}(x).\)
To normalize the valuation, let \(R=[\ell,2\ell]\), which is the gap between \(A_1\) and \(C_1\), and set
\(\displaystyle v_j(x)=\frac{b_j}{Q\ell}\mathbf1_{A_j}(x)+\mathbf1_{\{j=1\}}\frac{Q-S}{Q\ell}\mathbf1_R(x).\)
Endpoint conventions do not affect any integral.
All densities are nonnegative because \(Q\ge S\). Their total integral is
\(\displaystyle \sum_{j=1}^m\int_0^1v_j(x)\,dx=\frac{S}{Q}+\frac{Q-S}{Q}=1.\)
Since the capacity windows have pairwise disjoint interiors,
\(\displaystyle \sum_{j=1}^m\kappa_j(x)\le\frac12\le1\)
almost everywhere.
The normalization density on \(R\) encounters zero capacity in layer \(1\). Thus the required value of every supported bundle is
\(\displaystyle p=\sum_{j=1}^m\int_0^1\kappa_j(x)v_j(x)\,dx=\frac{S}{2Q}.\)
Every breakpoint and density value is dyadic: both \(4m\) and \(Q\) are powers of two. Each function has only a constant number of pieces. Also \(m<2k\), and \(\log_2 Q\) is bounded by the binary encoding length of the source instance. Therefore the construction has polynomial bit length and is computable in polynomial time.
Suppose a finite allocation exists. Write its bundles as \(B^r\), with positive weights \(w_r\) satisfying \(\sum_r w_r=1\). Let \(\lambda\) denote Lebesgue measure.
Fix a layer \(j\). Integrating the capacity equation outside its two windows gives
\(\displaystyle 0=\int_{[0,1]\setminus(A_j\cup C_j)}\kappa_j(x)\,dx=\sum_r w_r\,\lambda\bigl(B_j^r\setminus(A_j\cup C_j)\bigr).\)
Every term is nonnegative, and every weight is positive. Hence
\(\displaystyle \lambda\bigl(B_j^r\setminus(A_j\cup C_j)\bigr)=0\)
for every \(r\).
An interval having positive-length intersection with both windows would contain their intervening gap. Therefore each interval \(B_j^r\) lies, up to a null set, in at most one window. In particular,
\(\displaystyle \lambda(B_j^r)\le\ell.\)
Integrating the capacity equation over the entire layer yields
\(\displaystyle \sum_r w_r\lambda(B_j^r)=\int_0^1\kappa_j(x)\,dx=\ell.\)
Because the weights sum to one and every interval has length at most \(\ell\),
\(\displaystyle \sum_r w_r\bigl(\ell-\lambda(B_j^r)\bigr)=0.\)
Positivity again forces \(\lambda(B_j^r)=\ell\) for every \(r\). Consequently, every supported bundle takes exactly one whole window, \(A_j\) or \(C_j\), in each layer, up to endpoint conventions.
In particular, no supported bundle obtains positive value from the normalization region \(R\).
For each supported bundle, define
\(\displaystyle T_r=\{j:B_j^r=A_j\text{ up to a null set}\}.\)
Its value is therefore
\(\displaystyle V(B^r)=\frac1Q\sum_{j\in T_r}b_j.\)
The capacity equations also determine the weighted average value. Using the finite sum and integrating them against the densities gives
\(\displaystyle \sum_r w_rV(B^r)=\sum_j\int_0^1v_j(x)\sum_r w_r\mathbf1[x\in B_j^r]\,dx=\sum_j\int_0^1v_j(x)\kappa_j(x)\,dx=p.\)
Fairness requires \(V(B^r)\ge p\) for every \(r\). Hence
\(\displaystyle \sum_r w_r\bigl(V(B^r)-p\bigr)=0\)
is a sum of nonnegative terms with positive weights. It follows that every supported bundle has value exactly \(p\). Thus
\(\displaystyle \sum_{j\in T_r}b_j=Qp=\frac S2.\)
Removing the padded zero entries gives a solution of the original PARTITION instance.
This proves that a NO-instance of PARTITION cannot admit an allocation.
Conversely, suppose \(T\subseteq\{1,\ldots,k\}\) satisfies \(\sum_{j\in T}b_j=S/2\).
Construct two bundles:
Assign each bundle weight \(1/2\).
All chosen windows across different layers have disjoint interiors, so both bundles satisfy the non-overlap condition. In every layer, exactly one bundle takes \(A_j\) and the other takes \(C_j\). Their weighted indicators therefore equal \(\kappa_j\) almost everywhere.
Their values are
\(\displaystyle V(B^1)=\frac1Q\sum_{j\in T}b_j=\frac S{2Q}=p,\)
and
\(\displaystyle V(B^2)=\frac1Q\sum_{j\notin T}b_j=\frac S{2Q}=p.\)
The weights are positive dyadic rationals summing to the type mass \(1\), and all endpoints are dyadic. Thus this is a valid finite mass allocation.
We have proved the exact equivalence
\(\displaystyle \text{the PARTITION instance is YES}\quad\Longleftrightarrow\quad\text{the constructed society admits an allocation}.\)
Together with the polynomial encoding bound, this establishes \(\mathrm{NP}\)-hardness under all the stated restrictions.
The cited finite-agent existence results do not contradict this reduction: their guarantees concern proportional divisions without prescribing the spatial capacity functions used here. See [Hosseini–Igarashi–Searns](https://www.ijcai.org/proceedings/2020/0026.pdf) and [Igarashi–Meunier](https://arxiv.org/pdf/2106.02262). In this construction, exact capacities force discrete window choices, and proportionality then forces an exact partition.
⟨structured verdict parsed — rendered above⟩
The reduction is correct and resolves the requested hardness alternative. Every essential step is justified. I found no major or minor mathematical issues requiring repair.
The prover uses the standard binary-encoded PARTITION problem on a nonempty list of positive integers. Its decision condition is precisely the existence of a subset summing to half the total. The cited [MIT lecture notes, Definition 5](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf) identify PARTITION as weakly NP-complete. This suffices for the claimed NP-hardness; strong NP-hardness is not claimed.
Positivity ensures \(S\ge1\), so \(Q\) is defined. Padding with zero entries preserves the partition condition. Choosing the smallest power of two at least \(k\) gives an admissible layer count and satisfies \(k\le m<2k\).
Both windows in every layer have length \(\ell\). The gap between \(A_j\) and \(C_j\) has length \(\ell\); the gap between \(C_j\) and \(A_{j+1}\) also has length \(\ell\). The first window starts at zero, and the last window ends at
\[
(4m-1)\ell=1-\ell.
\]
Thus every window lies in the required domain, and their interiors are pairwise disjoint.
The normalization region \(R=[\ell,2\ell]\) is exactly the gap in layer \(1\), apart from endpoints. Consequently, its capacity in that layer is zero almost everywhere.
The normalization computation is correct:
\[
\sum_j\int_0^1v_j(x)\,dx
=\frac{S}{Q}+\frac{Q-S}{Q}=1.
\]
All densities are nonnegative because \(Q\ge S\). At almost every position, at most one capacity window is present across all layers, so the capacity sum is at most \(1/2\). The single supported type has the required positive mass \(1\).
The dyadic claim is correct. Since \(m\) and \(Q\) are powers of two, all window endpoints and both possible nonzero density coefficients are dyadic rationals. In particular, the density coefficients can be written as
\[
\frac{4mb_j}{Q}
\quad\text{and}\quad
\frac{4m(Q-S)}{Q}.
\]
Their numerators and denominators have polynomial binary length.
Each function has only a constant number of pieces, including its zero pieces. The number of layers is linear in \(k\), and the binary length of \(S\), hence of \(Q\), is polynomial in the source encoding length. The construction therefore has polynomial output length and can be computed in polynomial time. There is no expansion proportional to the numerical magnitudes of the source integers.
On \(A_j\), the density contribution integrates to \(b_j/Q\), and the capacity is \(1/2\). The windows \(C_j\) have zero valuation, while the normalization region has zero capacity almost everywhere. Therefore
\[
p=\frac{S}{2Q}
\]
is exactly the threshold specified by the task.
Integrating the capacity equation over the complement of the windows is legitimate: the allocation contains finitely many measurable intervals, and all weights are positive.
The resulting sum consists of nonnegative terms and equals zero. Thus every supported interval individually has zero length outside its layer’s two windows. This deduction correctly uses positivity of each weight; cancellation is impossible.
An interval intersecting both windows in positive length must contain their positive-length intervening gap. That contradicts the preceding exclusion. Hence each supported interval occupies, up to a null set, at most one window and has length at most \(\ell\).
The total capacity integral in a layer is
\[
\frac12\ell+\frac12\ell=\ell.
\]
Since the bundle weights sum to \(1\), their weighted average interval length is \(\ell\). The displayed sum of weighted length deficits is therefore zero. Positivity forces every deficit to vanish.
An interval of length \(\ell\) confined almost everywhere to one window of length \(\ell\) equals that window almost everywhere. Thus the whole-window conclusion follows. Empty intervals and singleton intervals cannot remain in any supported bundle, because they would have a positive length deficit.
Once the whole-window conclusion is established, the stated bundle value
\[
V(B^r)=\frac1Q\sum_{j\in T_r}b_j
\]
is correct. No supported bundle obtains positive value from \(R\).
The weighted-average-value identity follows directly from the capacity equations. Interchanging the finite sums and integrals is justified, and multiplying an almost-everywhere equality by these bounded piecewise-constant densities preserves equality of the integrals.
Every supported value is at least \(p\), and their weighted average is exactly \(p\). With positive weights, every value must equal \(p\). Hence each \(T_r\) satisfies
\[
\sum_{j\in T_r}b_j=\frac S2.
\]
At least one supported bundle exists because the weights sum to \(1\). Removing padded zeros therefore produces a partition of the original instance. This establishes the required implication.
The two complementary bundles each contain one interval per layer. All selected windows across layers have disjoint interiors, so each bundle satisfies the non-overlap requirement.
In every layer, one bundle occupies \(A_j\) and the other occupies \(C_j\). Their weights \(1/2\) reproduce exactly the prescribed capacity almost everywhere.
The partition and its complement each have total source weight \(S/2\), so both bundle values equal \(p\). Padded zeros do not affect this calculation. The two positive dyadic weights sum to the supported type’s mass, and all endpoints are dyadic. Every allocation requirement is satisfied.
The construction remains valid when \(m=1\), when \(S=1\), and when \(S\) is a power of two. In the last case, the normalization density is simply zero. Odd totals are handled by the same necessity argument: an integer subset sum cannot equal the noninteger \(S/2\). Endpoint conventions affect only null sets.
The equivalence and polynomial encoding establish NP-hardness of the exact problem posed. A polynomial-time procedure that always outputs an allocation or reports nonexistence would decide PARTITION in polynomial time.
The proof does not establish membership in NP or strong NP-hardness, and it does not claim either. Neither is needed to answer the task.
The finite-agent existence results are contextual references, not premises of the reduction. The distinction drawn by the prover is valid: those results concern complete proportional divisions and do not impose the prescribed weighted spatial capacity equations used here. See [Hosseini–Igarashi–Searns](https://www.ijcai.org/proceedings/2020/0026.pdf) and [Igarashi–Meunier, Theorem 5](https://arxiv.org/pdf/2106.02262).
No additional lemma, clarification, or mathematical repair is required.
⟨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.