Answer: \(\mathrm{NP}\)-complete
Theorem 7.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen there are n ≥3 agents and at least 2n items, checking the existence of NDDEF allocations is NP-complete (as a function of n).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite item categories \(G\), finite agent types \(R\) with complete strict rankings \(\succ_r\), rational masses \(\mu_r\) summing to \(1\), and rational per-capita supplies \(q_g\in[0,1]\) with \(\sum_{g\in G}q_g=\ell\), does there exist \(x_{r,B}\ge0\) over integral bundles \(B\in\binom{G}{\ell}\) such that \(\sum_Bx_{r,B}=\mu_r\), \(\sum_{r\in R}\sum_{B\ni g}x_{r,B}=q_g\), and \(x_{r,B}x_{s,C}>0\Rightarrow B\succeq_{\mathrm{NDD}}^r C\) for all \(r,s,B,C\)?
Let \(G\) be a set of \(m\) goods categories and let \(\ell\) be an input integer with \(2\le\ell\le m\). Each individual receives an integral bundle containing at most one item per category.
A society is given by its support: the list \(R\) of \(\tau\ge1\) types with positive masses \(\mu_r\), each a binary rational, with \(\sum_r\mu_r=1\), and complete strict rankings \(\succ_r\) of \(G\). Here \(\tau\) is the support size, not the number of possible rankings. Supplies are binary rationals \(q_g\in[0,1]\) with \(\sum_gq_g=\ell\); let \(L\) be the total input bit length.
For a ranking \(g_1\succ_r\cdots\succ_r g_m\), a DD utility is a strictly positive real additive utility consistent with that ranking and satisfying \(u(g_j)-u(g_{j+1})\ge u(g_{j+1})-u(g_{j+2})\) for \(1\le j\le m-2\). Define \(B\succeq^r_{\mathrm{NDD}}C\) to mean \(u(B)\ge u(C)\) for every such utility.
Write \(\mathcal B=\binom{G}{\ell}\). An allocation consists of real masses \(x_{r,B}\ge0\), indexed by \(r\in R\) and \(B\in\mathcal B\), satisfying \(\sum_{B\in\mathcal B}x_{r,B}=\mu_r\) and \(\sum_{r\in R}\sum_{B\ni g}x_{r,B}=q_g\).
Require \(x_{r,B}>0\land x_{s,C}>0\Rightarrow B\succeq^r_{\mathrm{NDD}}C\) for every \(r,s\in R\) and \(B,C\in\mathcal B\), including \(r=s\).
Is deciding whether such an allocation exists solvable in polynomial time in \(m,\tau,L,\ell\), or is it \(\mathrm{NP}\)-hard?
For finitely many agents and distinct indivisible goods, existence of a necessary-DD-envy-free allocation is \(\mathrm{NP}\)-complete with an unbounded number \(n\ge3\) of agents, already with exactly \(2n\) goods; checking a specified allocation is polynomial-time. [Source](https://www.jair.org/index.php/jair/article/download/11994/26566/23118).
No result settling this exact supportwise mass-allocation problem was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, already when \(\ell=2\) and \(m=2\tau\). Hardness holds even when all masses and supplies are dyadic rationals.
The key is that the requirement including \(r=s\) forces every type to receive a single fixed bundle.
Lemma. For a fixed strict ranking, if \(B\succeq_{\mathrm{NDD}}C\) and \(C\succeq_{\mathrm{NDD}}B\), then \(B=C\).
Proof. Write the ranking as \(g_1\succ\cdots\succ g_m\), and consider the additive utility defined by
\(u(g_j)=2^{m-j}\).
It is strictly positive and consistent with the ranking. Its consecutive differences are \(2^{m-j-1}\), so they decrease as \(j\) increases. Thus it is a DD utility.
Distinct subsets have distinct utility totals: at the first position where two subsets differ, the corresponding power of two exceeds the sum of all subsequent powers. Mutual necessary dominance would imply \(u(B)=u(C)\), which therefore forces \(B=C\). \(\square\)
Now suppose an allocation satisfies the task’s conditions. If \(x_{r,B}>0\) and \(x_{r,C}>0\), applying the envy condition in both orders gives mutual necessary dominance under ranking \(r\). The lemma implies \(B=C\).
Since \(\mu_r>0\), exactly one bundle \(B_r\) has positive mass for type \(r\), and that mass is \(\mu_r\). Consequently, feasibility is equivalent to choosing bundles \(B_r\in\binom{G}{\ell}\) satisfying
\(\displaystyle \sum_{r:g\in B_r}\mu_r=q_g\quad\text{for every }g\in G,\)
and
\(\displaystyle B_r\succeq^r_{\mathrm{NDD}}B_s\quad\text{for every }r,s\in R.\)
This equivalence eliminates the potentially exponential allocation support and all real-valued certificate variables.
A certificate lists the bundle \(B_r\) for every type. Its length is \(O(\tau\ell\log m)\). Supply equalities can be checked using exact rational arithmetic in polynomial time.
For completeness, the necessary-DD comparisons also admit the following explicit polynomial-time test.
Fix a ranking \(g_1\succ\cdots\succ g_m\). For \(1\le k\le m-1\), define
\(\displaystyle H_k(B)=\sum_{j:g_j\in B}\max\{k-j+1,0\}.\)
For equal-cardinality bundles,
\(\displaystyle B\succeq_{\mathrm{NDD}}C\quad\Longleftrightarrow\quad H_k(B)\ge H_k(C)\text{ for every }1\le k\le m-1.\)
To prove this, let \(d_j=u(g_j)-u(g_{j+1})\). The DD conditions say
\(d_1\ge\cdots\ge d_{m-1}>0.\)
Set \(a_{m-1}=d_{m-1}>0\), and \(a_k=d_k-d_{k+1}\ge0\) for \(k<m-1\). Telescoping gives
\(\displaystyle u(g_j)=u(g_m)+\sum_{k=1}^{m-1}a_k\max\{k-j+1,0\}.\)
Because \(|B|=|C|\), the constant term cancels, giving
\(\displaystyle u(B)-u(C)=\sum_{k=1}^{m-1}a_k\bigl(H_k(B)-H_k(C)\bigr).\)
Thus all the stated inequalities imply necessary dominance.
Conversely, if the inequality fails for \(k=m-1\), choose \(u(g_m)=1\), \(a_{m-1}=1\), and all other coefficients zero. If it fails for some \(k<m-1\), make the same choices but additionally set \(a_k=T\), where \(T>0\) is sufficiently large. The resulting utility is strictly positive, strictly decreasing, and DD, and satisfies \(u(B)<u(C)\). This proves the characterization.
All \(H_k\) are integers of polynomial bit length and can be computed in polynomial time. Checking every ordered pair of types therefore gives a polynomial-time verifier. The problem belongs to \(\mathrm{NP}\).
We use the established \(\mathrm{NP}\)-hardness of necessary-DD-envy-free allocation for an unbounded number \(n\ge3\) of agents and exactly \(2n\) distinct goods. Moreover, the construction in Appendix C gives different top goods to all agents, so its rankings are pairwise distinct. These properties are verified directly in [Segal-Halevi, Hassidim, and Aziz, Theorem 7.4 and Appendix C](https://www.jair.org/index.php/jair/article/download/11994/26566/23118).
Every necessary-DD-envy-free allocation in such a finite instance gives exactly two goods to each agent. Indeed, for any ranking, the utilities
\(u_K(g_j)=K+2n-j,\qquad K>0,\)
are strictly positive DD utilities. If an agent’s bundle were smaller than another bundle, then for sufficiently large \(K\) that agent would envy the larger bundle. Hence envy-freeness forces equal cardinalities, and partitioning \(2n\) goods among \(n\) agents forces cardinality two.
Thus the source problem asks whether the original goods can be partitioned into pairs \(B_1,\ldots,B_n\) with
\(B_i\succeq_{\mathrm{NDD}}^i B_j\)
for every ordered pair of agents.
Let a source instance have goods \(G_0\), where \(|G_0|=2n\), and the pairwise distinct rankings described above.
Let \(D\) be the smallest power of two satisfying \(D\ge2n\), and put
\(\displaystyle \delta=1-\frac nD.\)
Construct the target instance as follows:
There are \(\tau=n+1\) types and \(m=2n+2=2\tau\) goods. The types have distinct rankings because the original top goods are distinct and the additional type has top good \(a\).
All masses and supplies are positive dyadic rationals. They satisfy
\(\displaystyle \sum_r\mu_r=\frac nD+\delta=1,\)
and
\(\displaystyle \sum_gq_g=\frac{2n}{D}+2\delta=2=\ell.\)
Furthermore, \(\delta\ge1/2>1/D\). Since \(2n\le D<4n\), the numerical encoding length is polynomial.
For an original type, its extended ranking preserves necessary-DD comparisons between bundles contained in \(G_0\).
One direction follows because restricting any DD utility for the extended ranking to its initial segment \(G_0\) gives a DD utility for the original ranking.
For the converse, take any original DD utility \(v\). Let \(z\) be its worst good, and let \(d>0\) be its last consecutive utility difference. Choose
\(\displaystyle 0<\varepsilon<\min\{d,v(z)/2\},\)
and extend it by
\(v(a)=v(z)-\varepsilon,\qquad v(b)=v(z)-2\varepsilon.\)
These values are positive. The appended differences are \(\varepsilon,\varepsilon\), both at most \(d\), so the extended utility remains DD and respects the extended ranking. Therefore every original DD utility has an admissible extension, establishing preservation in both directions.
Suppose the source instance has a necessary-DD-envy-free partition \(B_1,\ldots,B_n\).
Assign mass \(1/D\) of original type \(i\) to \(B_i\), and assign the entire additional type to \(\{a,b\}\). The supply equations hold because each original good occurs in exactly one original bundle.
Comparisons between original types hold by preservation of necessary-DD comparisons.
For every original type, both goods in its bundle rank above both \(a\) and \(b\), so its bundle has strictly greater utility than \(\{a,b\}\) under every consistent additive utility. For type \(*\), both \(a\) and \(b\) rank above every original good, so the reverse cross-type comparisons also hold. Within-type comparisons are reflexive because each type receives only one bundle.
Thus the target instance is feasible.
Suppose the target instance is feasible. Section 1 implies that each type receives one fixed pair.
The additional type cannot receive any original good \(g\): doing so would consume mass \(\delta\) of that good, exceeding its entire supply \(q_g=1/D\). Its bundle must therefore be \(\{a,b\}\).
This consumes the full supplies of \(a\) and \(b\). Since every original type has positive mass, none can receive either good. Hence every original type receives a pair \(B_i\subseteq G_0\).
For each original good \(g\), its supply equation becomes
\(\displaystyle \frac1D\left|\{i:g\in B_i\}\right|=\frac1D.\)
Therefore exactly one original type receives \(g\), and the pairs \(B_1,\ldots,B_n\) partition \(G_0\).
The target envy conditions give necessary-DD dominance between every ordered pair of original bundles under the extended rankings. By the comparison-preservation argument, these are precisely the required comparisons under the original rankings. Hence the source instance has a necessary-DD-envy-free allocation.
The construction is a polynomial-time many-one reduction, and its two implications establish equivalence. Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness, even for \(\ell=2\), \(m=2\tau\), and dyadic input masses and supplies. Consequently, a polynomial-time algorithm in the stated parameters would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument establishes \(\mathrm{NP}\)-completeness for the exact supportwise mass-allocation problem. I found no substantive mathematical error. There is one minor omission in specifying the constructed rankings; it does not affect either implication of the reduction.
The utility \(u(g_j)=2^{m-j}\) is positive, strictly consistent with the ranking, and DD: its adjacent differences are positive and decrease with \(j\).
Distinct subsets have distinct totals under this utility. The power corresponding to their highest-ranked differing good exceeds the sum of all lower powers. Thus mutual necessary-DD dominance implies equality of subsets.
The allocation condition explicitly includes \(r=s\) and both ordered choices of bundles. Consequently, any two bundles with positive mass for the same type must coincide. Since \(\mu_r>0\), each type receives exactly one bundle, with mass \(\mu_r\).
The stated discrete reformulation is therefore equivalent to the original allocation problem, including its real-valued allocation variables.
Listing one bundle for each type gives the claimed polynomial-size certificate. Exact rational supply checks have polynomial bit complexity: summing input rationals increases intermediate bit lengths by at most a polynomial in the total input length.
The comparison characterization is correct. Strict ranking consistency and DD give
\[
d_1\ge\cdots\ge d_{m-1}>0.
\]
The coefficients defined in the output satisfy \(a_k\ge0\) for \(k<m-1\) and \(a_{m-1}>0\). The telescoping representation has the correct indices and coefficients, and equal cardinalities cancel the constant utility term.
The converse witnesses are also valid. A negative final coefficient comparison is witnessed by the specified linear utility. A negative comparison at an earlier index dominates the fixed final contribution when its coefficient \(T\) is sufficiently large. Both constructions preserve positivity, strict ranking consistency, and DD.
Thus every ordered pair of types can be checked in polynomial time. The characterization also covers \(m=2\), where only the final coefficient exists.
I checked the cited paper. Its definitions use strict rankings, positive additive utilities, and the same adjacent-difference DD condition. Allocations partition all goods.
Although Theorem 7.4 is phrased for at least twice as many goods as agents, Appendix C constructs \(3t\) agents and \(6t\) goods. The cyclic orders on disjoint dummy triples give every agent a different top good. Hence the construction establishes hardness with exactly twice as many goods as agents and pairwise distinct rankings. [Theorem 7.4 and Appendix C](https://www.jair.org/index.php/jair/article/download/11994/26566/23118)
The prover’s equal-cardinality argument is valid: the term proportional to \(K\) eventually makes any smaller bundle worse than a larger bundle. Necessary-DD envy-freeness therefore forces equal cardinalities, and a partition of \(2n\) goods gives two goods per agent.
The mass and supply sums are correct:
\[
\frac nD+\delta=1,\qquad \frac{2n}{D}+2\delta=2.
\]
Since \(n\ge3\) and \(D\ge2n\), the claimed inequality \(\delta\ge1/2>1/D\) holds. All masses and supplies are positive and at most one.
The smallest-power-of-two choice gives \(2n\le D<4n\). Hence the dyadic numbers have polynomial encoding length, and the ranking lists also have polynomial size.
The dimensions are correctly computed as \(\tau=n+1\) and \(m=2n+2=2\tau\). Distinct original top goods, together with the additional type’s top good \(a\), ensure distinct support rankings.
Minor issue: the additional type’s ranking does not specify the relative order of goods in \(G_0\). The target requires a complete strict ranking. The minimum clarification is to state that these goods are placed in any fixed strict order below \(b\). The proof uses only their position below \(a,b\), so this omission has no mathematical effect.
Restricting an extended DD utility to the original initial segment preserves positivity, strict consistency, and all original DD inequalities.
Conversely, the original final difference \(d\) is positive. The stipulated choice of \(\varepsilon\) makes both appended utilities positive and adds differences \(\varepsilon,\varepsilon\), each compatible with the preceding difference \(d\).
Thus every original admissible utility extends, and every extended admissible utility restricts. This verifies equality of the relevant universal comparison relations.
The source partition supplies every original good exactly once at mass \(1/D\), while the additional type supplies \(a,b\) at mass \(\delta\).
Original-type comparisons follow from preservation. The cross-type comparisons follow from equal bundle sizes and strict separation in the rankings: both goods of the preferred pair lie above both goods of the other pair. Within-type comparisons are reflexive.
The single-bundle lemma applies first. If the additional type received an original good, its contribution \(\delta\) would exceed that good’s total supply \(1/D\); nonnegative allocation masses preclude compensation.
Its pair must therefore be \(\{a,b\}\), exhausting their supplies. Original types must consequently receive original goods only.
The supply equation then forces each original good to occur in exactly one original bundle. These pairs form a partition, and comparison preservation transfers every required envy comparison back to the source instance.
The construction is polynomial, respects support size rather than counting possible rankings, and establishes both directions of feasibility. Combined with the certificate verifier, it proves the claimed restricted \(\mathrm{NP}\)-completeness. No additional mathematical lemma 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.