Answer: \(\mathrm{NP\text{-}complete}\)
Theorem 3.7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor identical binary valuations, EF-DG (#) with 𝑘+ = 1 and EF-DG (e) with ℓ+ = 1 are NP-hard for 𝑛= 2 agents, and EF-DG (#) with 𝑛= 2 agents is W[1]-hard parameterized by 𝑘−. This strong hardness result puts EF1 and EF in a sharp contrast, as EF1-DG (#) is polynomial-time solvable and EF1-DG is solvable in time polynomial in ℓ+.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite good catalogue \(G\), complete agent types \(T\) with rational masses \(\mu_t\), integral initial bundles \(b_t\in\mathbb Z_{\ge0}^{G}\), additive utilities \(u_t\in\mathbb Z_{\ge0}^{G}\), and rational bounds \(D_0,K_0\), decide whether there exist variables \(x_{t,b}\ge0\) for every integral residual bundle \(b\preceq b_t\), with \(\sum_{b\preceq b_t}x_{t,b}=\mu_t\), \(D(x)=\sum_{t,b}x_{t,b}\lVert b_t-b\rVert_1\le D_0\), and \(K(x)=\sum_{t,b}x_{t,b}\lVert b\rVert_1\ge K_0\), such that whenever \(x_{t,b}>0\) and \(x_{t',b'}>0\), \(u_t\cdot b\ge u_t\cdot b'\).
An instance has a finite catalogue \(G\), types \(T\) with rational masses \(\mu_t\), integral initial bundles \(b_t\in\mathbb Z_{\ge0}^{G}\), additive utilities \(u_t\in\mathbb Z_{\ge0}^{G}\), and rational bounds \(D_0,K_0\), all binary-encoded. A residual bundle \(b\preceq b_t\) is integral and coordinatewise bounded by \(b_t\).
Choose masses \(x_{t,b}\ge0\) with \(\sum_{b\preceq b_t}x_{t,b}=\mu_t\). Let \(D(x)=\sum_{t,b}x_{t,b}\lVert b_t-b\rVert_1\) and \(K(x)=\sum_{t,b}x_{t,b}\lVert b\rVert_1\).
The allocation is envy-free if, whenever \(x_{t,b}>0\) and \(x_{t',b'}>0\), \(u_t\cdot b\ge u_t\cdot b'\).
Is deciding whether there is such an envy-free \(x\) with \(D(x)\le D_0\) and \(K(x)\ge K_0\) solvable in polynomial time, or is it NP-hard?
For discrete agents with identical binary additive utilities, the corresponding envy-free donation problem with a bound on donated goods is NP-hard even for two agents and with at least one good required to remain.
That discrete problem is also W[1]-hard when parameterized by the number of donated goods, even for two agents.
The decision problem is NP-complete. NP-hardness already holds with two positive-mass types, unit masses, identical additive utilities, and binary initial bundles.
Here “binary initial bundles” means that every bundle coordinate belongs to \(\{0,1\}\); the utility coefficients remain arbitrary nonnegative integers encoded in binary.
For every residual bundle \(b\preceq b_t\),
\[ \lVert b_t-b\rVert_1 = \lVert b_t\rVert_1-\lVert b\rVert_1, \]
because all coordinates are nonnegative and \(b(g)\le b_t(g)\).
Define the total initial bundle mass by
\[ B=\sum_{t\in T}\mu_t\lVert b_t\rVert_1. \]
Using \(\sum_b x_{t,b}=\mu_t\), we obtain
\[ \begin{aligned} D(x) &=\sum_{t,b}x_{t,b} \bigl(\lVert b_t\rVert_1-\lVert b\rVert_1\bigr)\\ &=\sum_t\mu_t\lVert b_t\rVert_1-K(x)\\ &=B-K(x). \end{aligned} \]
Thus the two numerical constraints are equivalent to
\[ K(x)\ge K_0 \quad\text{and}\quad K(x)\ge B-D_0. \]
In particular, increasing retention simultaneously improves both constraints.
If there is a feasible envy-free mass allocation \(x\), then there is one in which every positive-mass type is assigned entirely to a single residual bundle. Moreover, this deterministic allocation has retention at least \(K(x)\) and donation at most \(D(x)\).
Discard types with \(\mu_t=0\). For every remaining type \(t\), define its positive support
\[ S_t=\{b\preceq b_t:x_{t,b}>0\}. \]
The set \(S_t\) is finite and nonempty. Choose
\[ c_t\in\operatorname*{arg\,max}_{b\in S_t}\lVert b\rVert_1. \]
Define \(y\) by assigning the entire mass of type \(t\) to \(c_t\):
\[ y_{t,c_t}=\mu_t, \qquad y_{t,b}=0\quad\text{for }b\ne c_t. \]
Every bundle in the support of \(y\) was already in the support of \(x\). Therefore, for every pair of types \(t,t'\),
\[ u_t\cdot c_t\ge u_t\cdot c_{t'}, \]
because this inequality was one of the envy-freeness inequalities for \(x\). Hence \(y\) remains envy-free.
For each \(t\),
\[ \sum_b x_{t,b}\lVert b\rVert_1 \le \left(\sum_b x_{t,b}\right)\lVert c_t\rVert_1 = \mu_t\lVert c_t\rVert_1. \]
Summing over all types gives \(K(y)\ge K(x)\). By the identity \(D=B-K\), it follows that \(D(y)\le D(x)\). Thus \(y\) satisfies every lower bound on retention and every upper bound on donation satisfied by \(x\). ∎
Consequently, continuous splitting of a type cannot create additional yes-instances for the present pair of monotone constraints.
By the lemma, every yes-instance has a certificate consisting of one residual bundle \(c_t\preceq b_t\) for each positive-mass type.
The certificate has polynomial length because every coordinate of \(c_t\) is an integer between \(0\) and the corresponding binary-encoded coordinate of \(b_t\). It can be verified by checking:
All operations are exact arithmetic on polynomially many binary-encoded integers and rationals. Therefore the problem belongs to NP.
We reduce from the NP-complete Subset Sum problem.
An instance consists of positive integers \(a_1,\ldots,a_n\) and a positive target \(W\), all encoded in binary. The question is whether there is a subset \(S\subseteq\{1,\ldots,n\}\) such that
\[ \sum_{i\in S}a_i=W. \]
Construct the catalogue
\[ G=\{g_1,\ldots,g_n,z\} \]
and two types \(1,2\), both having mass
\[ \mu_1=\mu_2=1. \]
Their initial bundles are disjoint and binary:
\[ b_1(g_i)=1,\quad b_1(z)=0, \]
and
\[ b_2(g_i)=0,\quad b_2(z)=1. \]
Both types have the same additive utility \(u\), defined by
\[ u_1=u_2=u,\qquad u(g_i)=a_i,\qquad u(z)=W. \]
Finally, set
\[ D_0=n,\qquad K_0=1. \]
The construction is polynomial in the binary encoding of the Subset Sum instance.
Suppose \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in S}a_i=W\).
Let type \(1\) retain exactly the goods \(\{g_i:i\in S\}\), and let type \(2\) retain \(z\). Both retained bundles have utility \(W\). Because the utilities are identical, neither type envies the other.
The retained quantity is
\[ K=|S|+1\ge 1, \]
and the donated quantity is
\[ D=n-|S|\le n. \]
Hence the constructed instance is a yes-instance.
Suppose the constructed instance admits a feasible envy-free mass allocation. By the determinization lemma, it admits one described by residual bundles \(c_1\preceq b_1\) and \(c_2\preceq b_2\).
Since the two utilities are identical, the two directed envy-freeness inequalities imply
\[ u(c_1)=u(c_2). \]
The second residual bundle has only two possibilities: \(c_2=0\) or \(c_2=\{z\}\).
If \(c_2=0\), then \(u(c_1)=0\). Every \(a_i\) is positive, so this forces \(c_1=0\). Consequently \(K=0\), contradicting \(K\ge K_0=1\).
Therefore \(c_2=\{z\}\), and hence \(u(c_2)=W\). Writing
\[ S=\{i:g_i\in c_1\}, \]
the equality of utilities gives
\[ \sum_{i\in S}a_i=u(c_1)=u(c_2)=W. \]
Thus the original Subset Sum instance is a yes-instance.
The reduction proves NP-hardness, while the determinization lemma gives membership in NP. Therefore the decision problem is NP-complete, and hence is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
The reduction establishes ordinary NP-hardness for binary-encoded integer utilities. It does not establish hardness when every utility coefficient is restricted to \(\{0,1\}\).
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the target. The determinization lemma is valid, the NP-membership argument has polynomial-size certificates, and the reduction from Subset Sum correctly proves NP-hardness under the claimed restrictions.
For every integral residual bundle \(b\preceq b_t\), coordinatewise nonnegativity gives
\[
\lVert b_t-b\rVert_1=\lVert b_t\rVert_1-\lVert b\rVert_1.
\]
Summing with weights \(x_{t,b}\) and using \(\sum_b x_{t,b}=\mu_t\) correctly yields
\[
D(x)=B-K(x).
\]
Thus \(D(x)\le D_0\) is equivalent to \(K(x)\ge B-D_0\). This part is correct.
Each type has finitely many residual bundles, so its positive support is finite. For a feasible allocation and a positive-mass type, the support is nonempty.
Choosing \(c_t\) from the existing support preserves envy-freeness: every comparison \(u_t\cdot c_t\ge u_t\cdot c_{t'}\) is already one of the original support-pair inequalities.
Choosing \(c_t\) to maximize \(\lVert b\rVert_1\) within \(S_t\) gives
\[
\sum_bx_{t,b}\lVert b\rVert_1\le\mu_t\lVert c_t\rVert_1.
\]
Hence \(K(y)\ge K(x)\), and the previously established identity gives \(D(y)\le D(x)\). No convexity, rationality, or integrality assumption is missing here.
The determinization lemma supplies one integral residual bundle per positive-mass type. Each coordinate requires at most the bit length of the corresponding coordinate of \(b_t\), so the certificate is polynomial in the input length.
Coordinate bounds, all ordered envy comparisons, and both rational threshold inequalities can be checked with exact polynomial-bit arithmetic. Thus membership in NP is established.
The reduction from positive-integer Subset Sum uses \(n+1\) goods, two types, unit masses, binary initial bundles, and identical nonnegative integer utilities. Its size is polynomial in the binary Subset Sum input.
The claimed bounds are consistent:
\[
B=n+1,\qquad D_0=n,\qquad K_0=1.
\]
In particular, the donation constraint is equivalent to requiring positive retention.
A subset \(S\) summing to \(W\) gives type \(1\) utility \(W\) and type \(2\), retaining \(z\), utility \(W\). Identical utilities therefore make the allocation envy-free in both directions.
The calculations
\[
K=|S|+1\ge1,\qquad D=n-|S|\le n
\]
are correct.
Determinization is legitimately applicable. With identical utilities, the two directed envy inequalities imply
\[
u(c_1)=u(c_2).
\]
Because \(b_2\) contains only \(z\), either \(c_2=0\) or \(c_2=\{z\}\).
In the first case, positivity of every \(a_i\) forces \(c_1=0\), contradicting \(K\ge1\). Therefore \(c_2=\{z\}\), and equality of utilities produces a subset of the \(g_i\) whose weights sum exactly to \(W\). Soundness follows.
The proof establishes NP-completeness for unrestricted binary-encoded nonnegative integer utilities, even when the initial bundle coordinates are in \(\{0,1\}\). The prover correctly notes that it does not establish hardness when utility coefficients themselves must lie in \(\{0,1\}\). That stronger restriction was not required by the target.
⟨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.