Answer: \(\mathrm{NP}\)-complete, even for deletion-closed catalogues containing only bundles of size at most two, with coordinates in \(\{0,1\}\), equal positive type masses, and dyadic masses and supplies.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a fair division instance with negative Boolean valuations, Algorithm NegBooleanEF1 returns an EF1 allocation in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(T\) with rational masses \(\mu_t\), repeated item classes \(J\) with rational per-capita supplies \(\sigma_j\), a finite deletion-closed bundle catalogue \(\mathcal B\), and valuations \(v_t(B)\in\{0,-1\}\), find or decide existence of nonnegative masses \(y_{t,B}\) satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_j=\sigma_j\), such that whenever \(y_{t,B}>0\), \(y_{u,D}>0\), and \(v_t(B)<v_t(D)\), either some \(j\) with \(B_j>0\) satisfies \(v_t(B-\mathbf e_j)\ge v_t(D)\), or some \(j\) with \(D_j>0\) satisfies \(v_t(B)\ge v_t(D-\mathbf e_j)\).
Let \(J=\{1,\ldots,m\}\) be item classes. A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
The input also gives nonnegative binary-rational per-capita supplies \(\sigma_j\), a nonempty explicitly listed catalogue \(\mathcal B\subseteq\mathbb Z_{\ge0}^m\), and explicit valuation tables \(v_t:\mathcal B\to\{0,-1\}\) with \(v_t(\mathbf0)=0\). Bundle coordinates are binary encoded; deletion closure means \(B-\mathbf e_j\in\mathcal B\) whenever \(B\in\mathcal B\) and \(B_j>0\), where \(\mathbf e_j\) is the unit vector for class \(j\).
An allocation consists of real masses \(y_{t,B}\ge0\) satisfying \(\sum_{B\in\mathcal B}y_{t,B}=\mu_t\) and \(\sum_{t\in T,B\in\mathcal B}y_{t,B}B_j=\sigma_j\) for every \(j\); each individual receives one whole catalogue bundle, and all supplies are allocated.
It is EF1 if, for every \(t,u\in T\) and \(B,D\in\mathcal B\) with \(y_{t,B}>0\), \(y_{u,D}>0\), and \(v_t(B)<v_t(D)\), either some \(j\) with \(B_j>0\) satisfies \(v_t(B-\mathbf e_j)\ge v_t(D)\), or some \(j\) with \(D_j>0\) satisfies \(v_t(B)\ge v_t(D-\mathbf e_j)\). This includes comparisons within one type.
Is deciding whether such an EF1 allocation exists in \(\mathrm P\), with running time polynomial in \(m,\tau,|\mathcal B|,L\), or is it \(\mathrm{NP}\)-hard, where \(L\) is the total input bit length?
For unrestricted discrete bundles and possibly nonidentical negative Boolean valuations, a complete EF1 allocation always exists and can be computed in polynomial time ([Bhaskar et al.](https://arxiv.org/pdf/2411.19881)). For identical negative Boolean valuations, the stronger EFX allocation can be computed in polynomial time with an evaluation oracle ([Bérczi et al.](https://real.mtak.hu/206338/1/1-s2.0-S0304397524002111-main.pdf)).
No result settling this exact mass-allocation problem with an explicit deletion-closed catalogue was located.
The decision problem is \(\mathrm{NP}\)-complete, even when every bundle has coordinates in \(\{0,1\}\), contains at most two items, and all masses and supplies are dyadic rationals.
The proof below allows arbitrary real mass splitting.
A certificate is a set \(S\subseteq T\times\mathcal B\) of permitted type–bundle pairs.
First, verify the EF1 condition for every ordered pair \((t,B),(u,D)\in S\). This is polynomial time: all valuations and all one-item deletions are explicitly available.
Next, check feasibility of the allocation equations with the additional constraints \(y_{t,B}=0\) whenever \((t,B)\notin S\). This is a rational linear program with at most \(\tau|\mathcal B|\) variables and polynomial encoding length. Rational linear-programming feasibility is decidable in polynomial time.
If this linear program is feasible, its allocation is EF1: every pair of positive coordinates belongs to \(S\), whose pairs already passed the EF1 check. Conversely, an EF1 allocation supplies a valid certificate by taking its actual support.
Thus the problem belongs to \(\mathrm{NP}\); no assumption that the initially given allocation masses are rational is needed.
We reduce from Independent Set: given a simple graph \(G=(V,E)\) and an integer \(k\), decide whether \(G\) has an independent set of size at least \(k\). Its \(\mathrm{NP}\)-completeness follows equivalently from Clique by complementing the graph; see [Karp’s completeness theorem](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may restrict to instances with \(E\ne\varnothing\) and \(1\le k<|V|\). All excluded cases are directly decidable, so they can be mapped to fixed yes- or no-instances satisfying these restrictions.
We may also assume that \(n=|V|\) is a power of two. Indeed, add isolated vertices until the vertex count is the next power of two, and increase \(k\) by the number added. Adding \(s\) isolated vertices increases the maximum independent-set size by exactly \(s\), preserving the answer. This adds fewer than the original number of vertices and preserves \(k<n\).
Write \(E=\{e_1,\ldots,e_r\}\), where \(r\ge1\). Let \(Q\) be the least power of two with \(Q\ge r\), and define positive dyadic weights by
Their sum is \(1\). For each edge, set
\(\delta_e=(n-k)w_e/(2n)\).
Then every \(\delta_e\) is positive and dyadic, and
\(\sum_{e\in E}\delta_e=(n-k)/(2n)\).
There is one supported type for each vertex \(t\in V\), with mass \(\mu_t=1/n\).
The item classes are:
All these classes are distinct. Markers will have zero supply and serve only to make the valuation tables distinct.
Include the zero bundle and every singleton bundle. Also include the special bundle
\(P=\mathbf e_p+\mathbf e_q\).
For each edge \(e=\{u,v\}\), choose an ordering of its endpoints and include four bundles:
The two bundles labelled \(u\), taken together, contain each of the four edge classes once. The same holds for the two bundles labelled \(v\).
Every bundle has coordinates in \(\{0,1\}\) and size at most two. The catalogue is deletion-closed because every singleton and the zero bundle are included.
Set
Consequently,
\(\sum_j\sigma_j=2k/n+4\sum_e\delta_e=2\).
For every type \(t\), specify its entire valuation table as follows:
In particular, the marker singletons distinguish all supported types.
The construction has
\(m=4r+n+2\), \(\tau=n\), and \(|\mathcal B|=8r+n+4\).
All numerical quantities have bit length polynomial in the graph input length. Because \(n,Q\) are powers of two, every mass and supply is dyadic. The explicitly listed bundle vectors and valuation tables therefore have polynomial total size.
Let \(y\) be any feasible allocation. Define the size of a bundle by
\(\|B\|_1=\sum_j B_j\).
The type equations give \(\sum_{t,B}y_{t,B}=1\), while the supply equations give \(\sum_{t,B}y_{t,B}\|B\|_1=2\). Hence
\(\displaystyle \sum_{t,B}y_{t,B}\bigl(2-\|B\|_1\bigr)=0.\)
Every summand is nonnegative because every catalogue bundle has size at most two. Thus every positively allocated bundle has size exactly two. No singleton or zero bundle is allocated.
Since \(P\) is the only size-two bundle containing \(p\), its aggregate allocated mass is
\(\displaystyle \sum_{t\in V}y_{t,P}=\sigma_p=k/n.\)
Define
\(I=\{t\in V:y_{t,P}>0\}\).
Each type has total mass \(1/n\), so
\(k/n=\sum_{t\in I}y_{t,P}\le |I|/n\).
Therefore \(|I|\ge k\).
We now prove that \(I\) is independent. Suppose, to the contrary, that an edge \(e=\{u,v\}\) has both endpoints in \(I\).
Consider either bundle \(D_{e,u}^{i}\). If it were allocated with positive mass to any type, type \(u\), which receives \(P\), would have an EF1 violation:
Thus neither allowed deletion can remove the envy. Both bundles labelled \(u\) must consequently have zero aggregate mass. The identical argument for type \(v\) excludes both bundles labelled \(v\).
All four bundles of edge \(e\) would then have zero mass. Since singleton bundles also have zero mass, none of its four item classes could be supplied. This contradicts their positive supply \(\delta_e\).
Therefore \(I\) is an independent set of size at least \(k\). This argument uses only positivity and capacity bounds, so it applies to arbitrary real mass splitting.
Suppose \(G\) has an independent set of size at least \(k\). Taking a subset if necessary, fix an independent set \(I\) of size exactly \(k\).
Give every type in \(I\) its entire mass \(1/n\) on \(P\).
For each edge \(e=\{u,v\}\), at least one endpoint lies outside \(I\). Choose such an endpoint \(s_e\), and prescribe aggregate mass \(\delta_e\) on each of
\(D_{e,s_e}^{1}\) and \(D_{e,s_e}^{2}\).
Give all other edge bundles zero mass.
These prescribed bundles supply each of the four edge classes exactly \(\delta_e\), because the chosen pair covers each class once. Their total mass is
\(\displaystyle 2\sum_e\delta_e=(n-k)/n.\)
Distribute every chosen edge bundle equally among the \(n-k\) types outside \(I\): each such type receives mass \(\delta_e/(n-k)\) on each of the two chosen bundles for edge \(e\). Its total received mass is
\(\displaystyle \frac{2\sum_e\delta_e}{n-k}=1/n.\)
This allocation satisfies every type equation and every supply equation.
To verify EF1, consider any recipient type and any positively allocated bundle.
A type \(t\in I\). Its own bundle is \(P\), valued \(-1\). Every allocated edge bundle is labelled by a vertex outside \(I\), so type \(t\) values it at \(-1\) as well. It also values every allocated copy of \(P\) at \(-1\). Thus this type has no envy.
A type \(t\notin I\). Its own bundle is an edge bundle \(B\). If \(v_t(B)=0\), it cannot envy any bundle, since all values are at most \(0\). If \(v_t(B)=-1\), deleting either item from \(B\) leaves an edge singleton of value \(0\). Therefore, whenever it envies a bundle valued \(0\), this deletion removes the envy.
These arguments cover every positive-support comparison, including comparisons within the same type. The allocation is EF1.
The construction proves the equivalence:
\(G\) has an independent set of size at least \(k\) if and only if the constructed instance admits an EF1 allocation.
It is a polynomial-time reduction, and Section 1 establishes membership in \(\mathrm{NP}\). Thus deciding EF1 existence is \(\mathrm{NP}\)-complete, even under the stated additional restrictions. A polynomial-time algorithm in \(m,\tau,|\mathcal B|,L\) would therefore imply \(\mathrm P=\mathrm{NP}\).
This is compatible with the cited unrestricted-bundle existence results: those results permit allocations using bundles outside the prescribed catalogue. Here the catalogue restriction, combined with total supply, forces every recipient to receive exactly two items. [Bhaskar et al.](https://arxiv.org/pdf/2411.19881)
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. The argument establishes \(\mathrm{NP}\)-completeness for the stated continuous mass-allocation problem, including the claimed restrictions. I found no major or minor mathematical issues.
The certificate \(S\subseteq T\times\mathcal B\) has polynomial size because the input explicitly lists both types and bundles.
Checking every ordered pair in \(S\) implements the task’s EF1 definition, including comparisons within a type. Deletion closure ensures that every deletion valuation needed by this check is defined in the input.
The subsequent feasibility problem has rational coefficients, nonnegative variables, the original type and supply equalities, and zero constraints outside \(S\). Its dimensions and coefficient encoding lengths are polynomial in the input size, so the stated polynomial-time rational LP feasibility theorem applies.
There is no missing strict-positivity constraint: a feasible solution may use only a subset of \(S\), and every such subset inherits the checked EF1 property. Conversely, the support of any real EF1 allocation is a valid certificate, since that allocation witnesses feasibility of the corresponding LP. Thus arbitrary real masses cause no certificate problem.
The source is the standard decision version of Independent Set on simple graphs. The appeal to Clique completeness and graph complementation is valid: an independent set in a graph is a clique in its complement, with the same cardinality threshold. This is the applicable consequence of [Karp’s completeness theorem](https://people.seas.harvard.edu/~madhusudan/courses/Fall2020/Lectures/L19-after.pdf).
Restricting to \(E\ne\varnothing\) and \(1\le k<|V|\) removes only directly decidable cases. Mapping these cases to fixed restricted yes- or no-instances is a routine valid reduction step.
Padding with isolated vertices preserves the answer exactly as stated. Increasing both the vertex count and threshold by the number added preserves \(k<n\), and existing edges remain present. The number of added vertices is less than the original vertex count, so padding is polynomial.
The edge weights are positive, including the last weight because \(Q-r+1\ge1\). Their sum is
\[
\frac{r-1}{Q}+\frac{Q-r+1}{Q}=1.
\]
This also covers \(r=1\), when the first family of weights is empty.
Since \(n-k>0\), every \(\delta_e\) is positive. The stated sum
\[
\sum_e\delta_e=\frac{n-k}{2n}
\]
is correct. Powers-of-two denominators ensure dyadic masses and supplies, and their bit lengths are polynomial.
All item classes are distinct. Within each edge gadget, the four two-item bundles are distinct; bundles from different gadgets cannot coincide because their item classes are disjoint.
The catalogue contains every necessary deletion: deleting from a two-item bundle gives an included singleton, and deleting from a singleton gives the included zero bundle.
The counts
\[
m=4r+n+2,\qquad \tau=n,\qquad |\mathcal B|=8r+n+4
\]
are correct.
The valuation rules cover every catalogue bundle without conflicting assignments. They take values only in \(\{0,-1\}\), and the zero bundle has value zero. Marker singletons distinguish the supported types, while zero marker supply is permitted by the task.
Explicit bundle vectors and valuation tables have polynomial total size. The supply calculation is also correct:
\[
\sum_j\sigma_j=\frac{2k}{n}+4\frac{n-k}{2n}=2.
\]
Summing the type equations gives total allocated mass one. Summing the supply equations gives total allocated item mass two. Since every catalogue bundle has size at most two, the displayed nonnegative-sum identity correctly forces every positive coordinate to use a bundle of size exactly two. This argument works for arbitrary real nonnegative masses.
After singleton allocations are excluded, \(P\) is the only positively usable bundle containing \(p\). Its aggregate mass is therefore \(k/n\).
For \(I=\{t:y_{t,P}>0\}\), each type contributes at most \(1/n\). Consequently, the stated inequality gives \(|I|\ge k\), without assuming that these types receive their entire masses on \(P\).
The edge contradiction checks both alternatives in the precise EF1 definition. If \(u\) receives \(P\), any positive allocation of a bundle labelled \(u\), to any recipient type, produces:
\[
v_u(P)=-1<0=v_u(D_{e,u}^{i}).
\]
Every deletion from \(P\) leaves value \(-1\), while every deletion from the compared edge bundle leaves value zero. Neither permitted deletion resolves the envy.
Thus, if both endpoints receive \(P\), all four bundles of their edge gadget have zero aggregate mass. No other size-two bundle contains that gadget’s classes, and singletons already have zero mass. This contradicts their strictly positive supplies. Hence \(I\) is independent.
Taking an independent subset of size exactly \(k\) is valid. Every edge has an endpoint outside that subset, so every prescribed choice \(s_e\) exists.
Each chosen pair of edge bundles covers its four item classes exactly once. Assigning aggregate mass \(\delta_e\) to each therefore satisfies the corresponding supply equations.
The total prescribed edge-bundle mass is \((n-k)/n\). Equal distribution among the \(n-k>0\) outside types gives each total mass \(1/n\). Together with the assignments of \(P\), all type and supply equations hold.
The EF1 verification is exhaustive. A type inside \(I\) values every positively allocated bundle at \(-1\), so it has no strict envy. An outside type receives only edge bundles. If its own bundle has value zero, strict envy is impossible. If its own bundle has value \(-1\), deleting an item leaves an edge singleton of value zero, resolving every possible strict envy.
These checks apply to every positive-support comparison, including comparisons within the same type.
Both directions establish the claimed equivalence, and the construction is polynomial. Together with membership in \(\mathrm{NP}\), this proves the claimed \(\mathrm{NP}\)-completeness.
The compatibility statement is sound: the unrestricted existence theorem does not constrain allocations to this catalogue. [Bhaskar et al., Theorem 3](https://arxiv.org/pdf/2411.19881) concerns unrestricted negative Boolean valuations and is not used as a premise of the reduction.
Repair feedback: None required. The write-up establishes the target with the stated quantifiers, encoding restrictions, and real mass splitting.
⟨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.