Answer: $\mathsf{NP}$-complete for every fixed $q\ge3$, even when all masses and supplies are dyadic rationals with precision bounded solely in terms of $q$.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor every fixed integer q ≥3, ExistsNEF, the problem of deciding whether a complete NEF allocation exists, is NP-complete on instances with q agents. Again, ExistsNEF is clearly in NP, so we need to show its NP- hardness.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(q\ge3\), given \(q\) strict rankings over goods \(J\), positive rational type masses \(\mu_t\) summing to \(1\), and rational per-capita supplies \(\rho_j\), does there exist a bundle \(B_t\subseteq J\) for each type such that \(\sum_{t:j\in B_t}\mu_t=\rho_j\) for each good \(j\), and for every ordered pair \(t,u\) there is an injection \(f:B_u\to B_t\) whose matched goods are weakly preferred by type \(t\), with equality allowed only for copies of the same good?
Fix an integer \(q\ge3\). Let \(J\) be a finite set of \(m\) goods. A society is given by its support: \(\tau=q\) distinct strict rankings \(\succ_t\) over \(J\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
Each good \(j\) has binary-rational per-capita supply \(\rho_j\in[0,1]\). An allocation gives every member of type \(t\) the same bundle \(B_t\subseteq J\), with at most one copy of each good per person; different types may receive copies of the same good.
Completeness requires \(\sum_{t:j\in B_t}\mu_t=\rho_j\) for every \(j\in J\). Necessary envy-freeness requires, for every ordered pair \(t,u\), an injection \(f:B_u\to B_t\) such that each \(j\in B_u\) satisfies either \(f(j)=j\) or \(f(j)\succ_t j\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\), with \(q\) fixed.
Is deciding whether a complete necessarily envy-free allocation exists polynomial-time solvable, or is it NP-hard, for each fixed \(q\ge3\)?
For indivisible items allocated as a partition among exactly \(q\) agents with strict rankings, the corresponding existence problem is NP-complete for every fixed \(q\ge3\) ([Aziz, Schlotter and Walsh](https://www.sciencedirect.com/science/article/pii/S0165489623000677)). No result settling this exact mass formulation was identified in the literature search.
For every fixed integer $q\ge3$, the problem is $\mathsf{NP}$-complete.
This holds even when all masses and supplies are dyadic rationals, with numerical precision bounded by a constant depending only on $q$. Thus the classification is the same whether “binary-rational” means dyadic rational or arbitrary rational encoded in binary.
The key new case is $q=3$. Its proof uses masses $1/8,3/8,1/2$ and a reduction from Numerical Three-Dimensional Matching.
For type $t$, let $P_t(k)$ denote the set of its first $k$ goods.
Lemma 1. The required injection from $B_u$ to $B_t$ exists if and only if
$$
|B_t\cap P_t(k)|\ge |B_u\cap P_t(k)|
\qquad\text{for every }k\in\{1,\ldots,m\}.
$$
Proof. Suppose the injection exists. Each good of $B_u\cap P_t(k)$ maps to a distinct good in $B_t\cap P_t(k)$, since an equal or better good remains in the prefix. This proves necessity.
Conversely, list the two bundles in decreasing order under $\succ_t$:
$$
B_t=\{a_1,\ldots,a_r\},
\qquad
B_u=\{b_1,\ldots,b_s\}.
$$
The inequality for $k=m$ gives $r\ge s$. The prefix ending at $b_i$ contains exactly $i$ goods of $B_u$, so it contains at least $i$ goods of $B_t$. Therefore $a_i=b_i$ or $a_i\succ_t b_i$. The map $b_i\mapsto a_i$ is the required injection. Empty bundles are covered by the same argument. $\square$
In particular, injections in both directions imply
$$
|B_t|=|B_u|.
$$
Thus every necessarily envy-free allocation has equally sized bundles.
A certificate consists of $m\tau$ membership bits. All prefix inequalities can be checked with $O(m\tau^2)$ counter operations. Completeness can be checked by exact rational arithmetic: a common denominator obtained by multiplying the mass denominators has $O(L)$ bits, as do the intermediate quantities needed for comparisons with supplies.
Using elementary arithmetic, a conservative verification bound in bit operations is
$$
V(m,\tau,L)
=
O\!\left(
L+(m+1)\tau L^2
+m\tau^2\log(m+2)
\right).
$$
Consequently, the problem belongs to $\mathsf{NP}$.
We use the standard $\mathsf{NP}$-complete problem Numerical Three-Dimensional Matching. Its input consists of three disjoint labeled sets $A_1,A_2,A_3$, each of cardinality $n$, positive integer weights $w(a)$, and a positive integer target $T$. The question is whether the elements can be partitioned into $n$ triples, each containing one element from each set and having total weight $T$. This is problem SP16 in [Garey and Johnson, *Computers and Intractability*](https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf).
If
$$
\sum_{\ell=1}^3\sum_{a\in A_\ell}w(a)\ne nT,
$$
the source instance is immediately a no-instance. Such instances will be mapped to a fixed infeasible target instance, specified below. Hence assume
$$
\sum_{\ell=1}^3\sum_{a\in A_\ell}w(a)=nT.
$$
Let
$$
E=
\left\{
(a_1,a_2,a_3)\in A_1\times A_2\times A_3:
w(a_1)+w(a_2)+w(a_3)=T
\right\},
\qquad M=|E|.
$$
These are labeled triples, so repeated numerical weights cause no identification of goods. We have $M\le n^3$.
For coordinate $\ell$, write its distinct weight values as
$$
v_{\ell,1}<\cdots<v_{\ell,h_\ell}.
$$
Define
$$
g_{\ell,i}
=
|\{a\in A_\ell:w(a)=v_{\ell,i}\}|,
\qquad
R_{\ell,i}=\sum_{j=1}^i g_{\ell,j}.
$$
For a subset $S\subseteq E$, define
$$
C_{\ell,i}(S)
=
|\{e\in S:\text{the coordinate }\ell\text{ of }e
\text{ has weight at most }v_{\ell,i}\}|.
$$
Lemma 2. The source instance has a numerical matching if and only if there is a subset $S\subseteq E$ satisfying
$$
|S|=n
\quad\text{and}\quad
C_{\ell,i}(S)\ge R_{\ell,i}
\quad\text{for every }\ell,i.
$$
Proof. A numerical matching supplies such a subset, with equality in every cumulative constraint.
For the converse, suppose $S$ satisfies the stated conditions. Let $W_\ell(S)$ be the sum of its coordinate-$\ell$ weights, and let
$$
W_\ell=\sum_{a\in A_\ell}w(a).
$$
Since both collections have $n$ entries,
$$
W_\ell-W_\ell(S)
=
\sum_{i=1}^{h_\ell-1}
(v_{\ell,i+1}-v_{\ell,i})
\bigl(C_{\ell,i}(S)-R_{\ell,i}\bigr).
$$
To verify this identity, express each weight $v_{\ell,j}$ as
$$
v_{\ell,h_\ell}
-
\sum_{i=j}^{h_\ell-1}(v_{\ell,i+1}-v_{\ell,i})
$$
and sum over the entries.
Every term in the displayed difference is nonnegative. On the other hand, every triple in $S$ has total weight $T$, so
$$
\sum_{\ell=1}^3 W_\ell(S)=nT
=\sum_{\ell=1}^3 W_\ell.
$$
Therefore all three nonnegative differences vanish. Every consecutive weight gap is positive, so
$$
C_{\ell,i}(S)=R_{\ell,i}
$$
for every intermediate index; equality at the last index follows from $|S|=n$. Subtracting consecutive cumulative equalities shows that the selected triples have exactly the prescribed multiplicity of every weight in every coordinate.
The selected triples might reuse a labeled source element. This is repaired as follows. For each coordinate and each weight value, biject its occurrences among the selected triples with the source elements of that weight. Apply these bijections independently in the three coordinates. The resulting triples use every labeled source element exactly once, and their weights are unchanged. Each still sums to $T$, giving a numerical matching. $\square$
The common target sum is essential: it converts three families of cumulative inequalities into exact multiplicities.
Initially construct three types with masses
$$
\mu_1=\frac18,\qquad
\mu_2=\frac38,\qquad
\mu_3=\frac12.
$$
Introduce the following goods:
Their supplies force the following recipient sets.
| Good | Supply | Possible recipient sets |
|---|---:|---|
| $x_e$ | $1/2$ | $\{1,2\}$ or $\{3\}$ |
| $p_i^1$ | $1/8$ | $\{1\}$ |
| $p_i^2$ | $3/8$ | $\{2\}$ |
| $z_k^1$ | $5/8$ | $\{1,3\}$ |
| $z_k^2$ | $7/8$ | $\{2,3\}$ |
Indeed, enumerating the subsets of the three masses gives precisely these possibilities. The only collision relevant here is
$$
\mu_1+\mu_2=\mu_3=\frac12.
$$
A complete allocation is therefore specified by
$$
S=\{e\in E:x_e\text{ is allocated to types }1\text{ and }2\}.
$$
All other recipients are forced.
Treat a variable good as a one-good unit. After any sequence of whole units, types $1$ and $2$ have identical prefix counts, say $c$, while type $3$ has count $d$. Write
$$
\delta=c-d.
$$
The contribution of a unit to $\delta$ is:
| Unit | Contribution |
|---|---:|
| Positive unit | $+1$ |
| Negative unit | $-1$ |
| Variable unit with $e\in S$ | $+1$ |
| Variable unit with $e\notin S$ | $-1$ |
Hence the total difference over all goods is
$$
\delta_{\mathrm{total}}
=
M-2n+2|S|-M
=
2(|S|-n).
$$
Necessary envy-freeness requires equal bundle sizes, so it forces $|S|=n$.
For this cardinality, the three bundle sizes are
$$
|B_1|=|B_2|=n+M+2n=M+3n,
$$
and
$$
|B_3|=(M-n)+4n=M+3n.
$$
Set
$$
K=M+3n.
$$
For type $1$, order the two goods of every positive unit as $p_i^1,p_i^2$, and those of every negative unit as $z_k^1,z_k^2$.
For type $2$, use the opposite orders: $p_i^2,p_i^1$ and $z_k^2,z_k^1$.
For type $3$, use $p_i^1,p_i^2$ and $z_k^1,z_k^2$.
These orders have the following precise consequence:
Here is the check of intermediate prefixes. For types $1$ and $2$, putting their own good first ensures that their count never falls below the other type’s count inside a unit. Inside a positive unit, their difference from type $3$ increases before the unit ends. Inside a negative unit, that difference stays unchanged after the first good and decreases by one after the second. Thus nonnegative boundary differences suffice.
For type $3$, inside a positive unit its difference from one of the other types decreases by one before the second difference does; the ending boundary condition therefore suffices. Inside a negative unit, its difference from one type stays unchanged while its difference from the other increases; the starting boundary condition suffices. Necessity follows because all unit boundaries are ranking prefixes.
This checks every ordered comparison, including the comparisons between types $1$ and $2$.
For coordinate $\ell$, partition the variable goods into groups
$$
G_{\ell,i}
=
\{x_e:\text{coordinate }\ell\text{ of }e
\text{ has weight }v_{\ell,i}\},
\qquad
d_{\ell,i}=|G_{\ell,i}|.
$$
Construct an abstract unit sequence $W_\ell$ by concatenating, for each $i$ in increasing order:
Assign positive-unit labels in increasing order as they are used, and likewise negative-unit labels. Do this independently for each $W_\ell$. Since
$$
\sum_i d_{\ell,i}=M,
\qquad
\sum_i 2g_{\ell,i}=2n,
$$
each sequence contains every unit exactly once.
Define the rankings as follows:
The reversal changes the order of whole units; it does not reverse their internal orders.
At the end of block $i$ in $W_\ell$, the difference is
$$
\delta_{\ell,i}
=
2\bigl(C_{\ell,i}(S)-R_{\ell,i}\bigr).
$$
Indeed, the positive units and negative units contribute
$$
\sum_{j\le i}d_{\ell,j}-2R_{\ell,i},
$$
and the variable units contribute
$$
2C_{\ell,i}(S)-\sum_{j\le i}d_{\ell,j}.
$$
Moreover, nonnegativity at these block endpoints is equivalent to nonnegativity at every unit boundary of $W_\ell$. To prove sufficiency, suppose the difference entering a block is $\delta_0\ge0$. Its $d_{\ell,i}$ positive units increase it to $\delta_0+d_{\ell,i}$. After $h$ variable units, of which $y$ belong to $S$, it is
$$
\delta_0+d_{\ell,i}+2y-h\ge\delta_0,
$$
because $h\le d_{\ell,i}$. The subsequent negative units decrease the difference monotonically to the block endpoint. If that endpoint is nonnegative, every intervening boundary is nonnegative. Necessity is immediate.
Consequently, types $1$ and $2$ enforce exactly the quota systems for coordinates $1$ and $2$.
Suppose $|S|=n$, so the total unit contribution is zero. If $W_3$ contains $H$ units, then the difference after the first $k$ units of its reversal is
$$
\delta_{\mathrm{rev}}(k)
=
-\delta_{W_3}(H-k).
$$
Therefore nonpositivity at every boundary in the reversed sequence is equivalent to nonnegativity at every boundary in $W_3$. Type $3$ thus enforces exactly the quota system for coordinate $3$.
Combining these calculations with the intermediate-prefix checks and Lemma 1 proves:
$$
\text{The complete allocation is necessarily envy-free}
$$
$$
\Longleftrightarrow
\quad
|S|=n
\text{ and }
C_{\ell,i}(S)\ge R_{\ell,i}
\text{ for every }\ell,i.
$$
By Lemma 2, this holds if and only if the numerical matching instance is a yes-instance.
Finally, append three zero-supply goods, ordered in three different cyclic orders at the ends of the rankings. Positive masses prevent any allocation of these goods. They do not affect comparisons and ensure that the three supported rankings are distinct.
This proves $\mathsf{NP}$-hardness for $q=3$ with dyadic inputs.
Fix $q\ge4$, and write
$$
r=q-3,
\qquad
s=2^{-(r+1)}.
$$
Use the preceding core gadget before appending its zero-supply goods. Scale its three masses and every core supply by $s$, giving active masses
$$
\mu_1=\frac{s}{8},
\qquad
\mu_2=\frac{3s}{8},
\qquad
\mu_3=\frac{s}{2}.
$$
Introduce $r$ additional types with masses
$$
b_i=2^{-(i+1)}
\quad(1\le i<r),
\qquad
b_r=\frac12+s.
$$
All masses are positive and dyadic. They sum to one because
$$
\sum_{i=1}^{r-1}b_i
=
\frac12-2^{-r}
=
\frac12-2s,
$$
and hence
$$
s+\sum_{i=1}^r b_i
=
s+\left(\frac12-2s\right)+\left(\frac12+s\right)
=
1.
$$
The formula includes $r=1$, where the first sum is empty.
Every additional mass exceeds $s$, whereas every scaled core supply is less than $s$. Thus additional types cannot receive core goods. Dividing the completeness equations for core goods by $s$ recovers exactly the recipient possibilities of the three-type gadget.
Furthermore, a subset of types has mass $b_i$ only when it consists of additional type $i$ alone.
For $i<r$, any individually larger mass is unusable. The sum of all individually smaller masses is
$$
s+\sum_{k=i+1}^{r-1}b_k
=
s+b_i-2s
=
b_i-s<b_i.
$$
Thus a subset omitting the designated type cannot attain $b_i$. A subset including it and another type exceeds $b_i$.
For $b_r$, the designated mass exceeds $1/2$, whereas all other masses together are less than $1/2$. Again, it is the unique possible recipient.
For each additional type $i$, introduce a private set $F_i$ of $K=M+3n$ goods, each with supply $b_i$. Completeness forces these goods exclusively to that type.
Each active type ranks all core goods first, in its gadget order, followed by all private goods. Additional type $i$ ranks all goods of $F_i$ above all core goods and all other private goods.
Append $q$ zero-supply goods at the ends of all rankings, using different cyclic orders. The supported rankings are therefore pairwise distinct.
If the source has a numerical matching, the core gadget gives each active type a necessarily envy-free bundle of size $K$. Give $F_i$ to additional type $i$. Comparisons among active types remain valid. For any comparison involving an additional type, the comparing type ranks every good of its own bundle above every good of the other bundle. Since both bundles have size $K$, any bijection certifies the required comparison. Self-comparisons use identity injections.
Conversely, in any complete necessarily envy-free allocation, active types receive only core goods, and every private good has its forced recipient. Comparisons among the active types therefore give a necessarily envy-free allocation of the core gadget. The three-type equivalence then yields a numerical matching.
This establishes $\mathsf{NP}$-hardness for every fixed $q\ge4$.
For a source instance whose total weight is not $nT$, use the masses specified above for the desired support size. Introduce one good with supply
$$
\frac12\min_t\mu_t
$$
and $q$ zero-supply goods. No subset of types has the positive good’s supply: the empty subset has mass zero, and every nonempty subset has mass at least $\min_t\mu_t$. Cyclic orders of the zero-supply goods ensure distinct rankings. This is a fixed infeasible target instance.
For normalized source instances, the construction has
$$
m
=
3M+4n+(q-3)(M+3n)+q
=
qM+(3q-5)n+q
$$
goods. Since $M\le n^3$, this is polynomial for fixed $q$.
Let $L_0$ be the source binary input length. Enumerating feasible triples takes $O(n^3L_0)$ bit operations using elementary arithmetic. Sorting coordinate weights and producing the rankings can be included in the conservative total construction bound
$$
O\!\left(
n^3L_0
+
\tau m\bigl(\log(m+2)+\tau\bigr)
\right),
\qquad \tau=q.
$$
All target numerical values have $O(q)$-bit encodings. The target input length satisfies
$$
L
=
O\!\left(
\tau m\bigl(\log(m+2)+\tau\bigr)
\right).
$$
Thus, for fixed $q$, the reduction is polynomial and its numerical precision is constant.
The polynomial verifier from Section 1 establishes membership in $\mathsf{NP}$. If an explicit deterministic decision bound is desired, enumerating all membership certificates gives
$$
O\!\left(2^{m\tau}V(m,\tau,L)\right).
$$
The reduction and verifier together prove $\mathsf{NP}$-completeness for every fixed $q\ge3$, including the previously unresolved dyadic three-type case.
⟨structured verdict parsed — rendered above⟩
The output resolves the task: its reduction and verifier establish $\mathsf{NP}$-completeness for every fixed $q\ge3$, including with dyadic masses and supplies of precision bounded solely by $q$. I found no major or minor mathematical issues.
1. Prefix characterization
Lemma 1 correctly characterizes the required injection.
Necessity holds because an equal or better good than a good in $P_t(k)$ also lies in $P_t(k)$, and injectivity preserves the count.
For sufficiency, the prefix ending at $b_i$ contains exactly $i$ members of $B_u$. The assumed inequality therefore places at least $i$ members of $B_t$ in that prefix, so its $i$th best member $a_i$ is equal to or better than $b_i$. The condition at $k=m$ ensures that every required $a_i$ exists. Empty source bundles cause no exception.
Applying the cardinality condition in both ordered directions correctly yields equal bundle sizes. The argument uses the comparing type’s ranking throughout, as required by the task.
2. Membership in $\mathsf{NP}$
The certificate of $m\tau$ membership bits specifies exactly the allocation allowed by the task: one bundle per type, with membership indicating at most one copy per person.
The prefix inequalities require $O(m\tau^2)$ counter operations, with counters bounded by $m$. This supports the stated counter bit cost.
For completeness, multiplying the mass denominators produces a common denominator of $O(L)$ bits. Scaling numerators, summing the participating masses, and comparing with each supply by cross multiplication all involve integers of $O(L)$ bits. The supply denominators need not divide the common mass denominator; exact comparison remains possible by cross multiplication.
The conservative bound
$$
V(m,\tau,L)
=
O\!\left(
L+(m+1)\tau L^2+m\tau^2\log(m+2)
\right)
$$
is consequently sufficient. Membership in $\mathsf{NP}$ is established for both numerical encodings discussed.
3. Source problem and normalization
The cited Numerical Three-Dimensional Matching premise matches the version used: three disjoint labeled sets of equal cardinality, positive integer weights, and a common positive target. The cited source lists precisely this problem as $\mathsf{NP}$-complete. [Garey and Johnson, problem SP16](https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf)
The normalization test is valid. A matching necessarily has total weight $nT$, so instances failing that test may be mapped to a fixed infeasible target.
Enumerating $E$ considers labeled triples and does not mistakenly identify equal numerical weights. Its size is correctly bounded by $n^3$.
4. Cumulative-quota lemma
Both directions of Lemma 2 are correct.
A matching selects $n$ distinct feasible triples and satisfies every cumulative constraint with equality.
In the converse, the displayed identity has the correct sign:
$$
W_\ell-W_\ell(S)
=
\sum_{i=1}^{h_\ell-1}
(v_{\ell,i+1}-v_{\ell,i})
\bigl(C_{\ell,i}(S)-R_{\ell,i}\bigr).
$$
It applies because both coordinate collections contain $n$ entries. The cumulative inequalities make each summand nonnegative. The common target and normalization make the sum of the three coordinate differences zero, so every coordinate difference vanishes.
Positive consecutive weight gaps then force all intermediate cumulative constraints to be equalities. The last constraint is an equality because $|S|=n$. Taking consecutive differences gives exactly the required weight multiplicities.
The relabeling argument is sufficient: for each coordinate and weight, the established multiplicity permits the stated bijection between occurrences and source elements. Independent coordinate bijections preserve every triple’s weight sum and ensure that each labeled element occurs exactly once. Reuse of labels in the initially selected triples therefore does not invalidate the converse.
A coordinate with only one distinct weight causes no problem: its intermediate sum is empty, and its multiplicity is already determined by $|S|=n$.
5. Three-type supplies and bundle counts
The subset sums of the masses are
$$
0,\quad \frac18,\quad \frac38,\quad
\frac12,\quad \frac12,\quad
\frac58,\quad \frac78,\quad 1.
$$
Thus every recipient-set entry in the table is correct. Completeness leaves exactly the choices represented by $S$.
The unit contributions to $\delta$ are also correct. In particular,
$$
\delta_{\mathrm{total}}=2(|S|-n).
$$
Equal bundle sizes therefore force $|S|=n$. Under that condition, all three bundle counts equal
$$
K=M+3n.
$$
These calculations concern counts of goods, rather than masses, which is the correct quantity for the injection conditions.
6. Intermediate prefixes
The internal ordering checks cover every comparison.
For types $1$ and $2$, their own good appears first in each two-good unit. Their count relative to the other active type temporarily increases and returns to equality at the unit boundary. Relative to type $3$, a positive unit increases the difference before its end, while a negative unit leaves it unchanged after the first good and decreases it after the second. Nonnegative boundary differences therefore suffice.
For type $3$, a positive unit decreases one comparison difference after its first good and the other after its second; the ending boundary condition controls both. A negative unit leaves one comparison difference unchanged and increases the other after its first good, then increases the remaining difference after its second; the starting boundary condition controls both.
Variable units contain a single good, so introduce no additional intermediate prefix. Necessity follows from checking the unit boundaries themselves. The claimed equivalences with the signs of $\delta$ are valid.
7. Rankings enforce precisely the quotas
Each $W_\ell$ uses every unit exactly once. The independent assignment of unit labels causes no inconsistency: rankings may order the same goods differently.
At block endpoints, the positive and variable contributions cancel their dependence on group size, giving exactly
$$
\delta_{\ell,i}
=
2\bigl(C_{\ell,i}(S)-R_{\ell,i}\bigr).
$$
The within-block estimate is valid because $y\ge0$ and $h\le d_{\ell,i}$. The negative-unit portion decreases monotonically to the endpoint. Consequently, nonnegative block endpoints are equivalent to nonnegative differences at every unit boundary.
For the reversed third sequence, the identity
$$
\delta_{\mathrm{rev}}(k)
=
-\delta_{W_3}(H-k)
$$
correctly uses the hypothesis that the total contribution is zero. This hypothesis is available because necessary envy-freeness forces $|S|=n$, and allocations constructed from matchings also satisfy it.
Both directions of the resulting allocation–quota equivalence follow. Together with Lemma 2, this proves the three-type reduction.
Appending zero-supply goods preserves the comparisons: positive masses force these goods into no bundle. Different cyclic tail orders ensure distinct strict supported rankings.
8. Extension to larger support sizes
The additional masses are positive, dyadic, and sum with the active masses to one. The displayed calculation also works when $r=1$.
Every additional mass exceeds $s$, while every core supply is smaller than $s$. Hence additional types cannot receive core goods.
For $i<r$, the sum of all individually smaller masses is correctly computed as $b_i-s<b_i$. Larger masses cannot participate in a subset totaling $b_i$. For the final additional type, its mass exceeds the sum of all other masses. Thus every private good has its claimed unique recipient.
In the forward direction, every bundle has size $K$. Active types rank their core bundles above additional types’ private bundles; each additional type ranks its own private bundle above every other bundle. The stated bijections therefore certify all comparisons involving additional types.
In the converse, forced recipients restrict active bundles to core goods. Their mutual comparisons recover precisely a necessarily envy-free allocation of the core gadget. The extension preserves both directions of the reduction.
9. Exceptional instances, size, and encoding
The exceptional positive supply is strictly between zero and the smallest type mass, so no recipient subset realizes it. The target is infeasible and still has distinct supported rankings.
The goods count is correct:
$$
m=qM+(3q-5)n+q.
$$
Together with $M\le n^3$, this gives polynomial output size for fixed $q$. The stated construction bound accommodates enumeration, sorting, and explicit ranking output.
All target numerical values have $O(q)$-bit encodings, independent of source weights. The constant-precision dyadic hardness claim therefore follows. Such instances also establish hardness when arbitrary binary-encoded rationals are permitted.
The exponential enumeration bound is consistent with the polynomial verifier; it does not assert polynomial-time solvability.
No repair or additional clarification is required for the mathematical conclusion.
⟨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.