Answer: For every fixed \(0<\epsilon<1/2\), attaining either factor \(m^{1-\epsilon}\) or \(\tau^{1/2-\epsilon}\) is \(\mathrm{NP}\)-hard, even with binary agent and allocator values and dyadic masses and supplies.
Theorem 5.5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any $\epsilon>0$, the problem of maximizing \sw subject to EF-$c$ is NP-hard to approximate within factor $m^{1-\epsilon}$ or $n^{1/2-\epsilon}$, even if both the agents' and the allocator's utility functions are binary and $c=1$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(T\) with rational population masses \(\mu_t\), indivisible item categories \(G\) with rational per-capita supplies \(0\leq\rho_g\leq1\), binary additive agent valuations \(v_t\), and additive allocator valuations \(u_t\), choose masses \(\lambda_{t,S}\) of type-\(t\) agents receiving integral bundles \(S\subseteq G\), subject to \(\sum_S\lambda_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}\lambda_{t,S}\leq\rho_g\). Require that every pair of supported bundles satisfies support-wise EF-\(1\): for \(\lambda_{t,S},\lambda_{t',D}>0\), some \(R\subseteq D\) with \(|R|\leq1\) has \(v_t(S)\geq v_t(D\setminus R)\). Decide whether \(W(\lambda)=\sum_{t,S}\lambda_{t,S}u_t(S)\geq Q\), or maximize \(W(\lambda)\).
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) item categories \(G\), with binary-rational per-capita supplies \(\rho_g\in[0,1]\). Each type specifies binary additive agent values \(v_t(g)\in\{0,1\}\) and nonnegative binary-rational additive allocator values \(u_t(g)\); both assign zero to the empty bundle.
An allocation chooses real masses \(\lambda_{t,S}\geq0\) for integral bundles \(S\subseteq G\), so each recipient gets at most one item per category. Require \(\sum_{S\subseteq G}\lambda_{t,S}=\mu_t\) and complete allocation of supplies: \(\sum_{t,S:g\in S}\lambda_{t,S}=\rho_g\).
Support-wise EF-\(1\) means that for every ordered pair \((t,S),(t',D)\) with positive allocated mass, including pairs within a type, there exists \(R\subseteq D\) with \(|R|\leq1\) such that \(v_t(S)\geq v_t(D\setminus R)\).
On instances admitting such an allocation, maximize \(W(\lambda)=\sum_{t,S}\lambda_{t,S}u_t(S)\). Let \(\mathrm{OPT}\) be this maximum; an approximation factor \(\alpha\geq1\) means obtaining a feasible allocation with \(W\geq\mathrm{OPT}/\alpha\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\) and any approximation parameters.
For each fixed \(0<\epsilon<1/2\), are polynomial-time approximation factors \(m^{1-\epsilon}\) and \(\tau^{1/2-\epsilon}\) achievable for this problem, or is attaining each factor NP-hard, even when allocator values are binary?
For finite agents, maximizing allocator welfare under EF-\(1\) is NP-hard to approximate within \(m^{1-\epsilon}\) or \(n^{1/2-\epsilon}\), even with binary agent and allocator values; an \(m\)-approximation is known ([source](https://arxiv.org/html/2310.03475v2#S5.SS3)).
With finite agents and divisible homogeneous goods, allocator welfare under exact envy-freeness is polynomial-time solvable by linear programming ([source](https://arxiv.org/html/2310.03475v2#A2.SS1)); this uses a different allocation domain. No result settling the specified mass-society approximation problem was located.
For every fixed \(0<\epsilon<1/2\), attaining either approximation factor \(m^{1-\epsilon}\) or \(\tau^{1/2-\epsilon}\) is \(\mathrm{NP}\)-hard, even when both agent and allocator values are binary.
The reduction below produces only feasible instances, uses dyadic rational masses and supplies, and respects \(\tau\) as the number of distinct types in the support.
For a finite simple graph \(H=(V,E)\), let \(N=|V|\), \(q=|E|\), and let \(\alpha(H)\) denote its maximum independent-set size.
For every fixed \(0<\eta<1\), approximating maximum independent set within \(N^{1-\eta}\) is \(\mathrm{NP}\)-hard. This follows from [Zuckerman’s Theorem 1.1 for maximum clique](https://theoryofcomputing.org/articles/v003a006/v003a006.pdf) by graph complementation: independent sets in \(H\) are precisely cliques in its complement, with the same number of vertices and the same optimum.
We use graphs with \(N\geq2\). Excluding smaller graphs does not affect this hardness.
Let \(D\) be the smallest power of two satisfying \(D\geq8(q+N+1)\), and set \(\delta=1/D\).
Create one category \(g_x\) for each vertex \(x\in V\), with supply \(\rho_{g_x}=\delta\). Thus \(m=N\).
Create the following types:
| Type | Mass | Agent values | Allocator values |
|---|---|---|---|
| Special type \(t_\star\) | \(\delta\) | Zero on every category | One on every category |
| Edge type \(t_e\), for \(e=\{a,b\}\in E\) | \(4\delta\) | One on \(g_a,g_b\), zero elsewhere | Zero everywhere |
| Disposal type \(t_d\) | \(1-(4q+1)\delta\) | Zero everywhere | Zero everywhere |
All values are binary. The masses sum to one. Moreover,
\(\mu_{t_d}-N\delta=(D-4q-N-1)/D>0\),
because \(D\geq8(q+N+1)>4q+N+1\). Consequently, every mass is positive, and the disposal type has enough mass to absorb all categories separately.
These are distinct types. Different edges give different agent-value vectors; edge types have nonzero agent values; and the special and disposal types have different allocator-value vectors. Therefore the actual support size is
\(\tau=q+2\).
All masses and supplies are dyadic rationals with \(O(\log N)\) bits. With explicit value tables, the total input length satisfies
\(L=O\bigl(m\tau+(m+\tau)\log m\bigr)=O(N^3)\).
The construction takes polynomial time in \(m,\tau,L\).
Lemma. In every feasible support-wise EF-\(1\) allocation of the constructed society, every bundle with positive allocated mass corresponds to an independent set of \(H\).
Proof. Fix an edge \(e=\{a,b\}\). The total agent value received by its edge type satisfies
\(\sum_{S\subseteq G}\lambda_{t_e,S}v_{t_e}(S)=\sum_{S:g_a\in S}\lambda_{t_e,S}+\sum_{S:g_b\in S}\lambda_{t_e,S}\leq\rho_{g_a}+\rho_{g_b}=2\delta\).
The inequality follows from nonnegativity and the complete-allocation constraints: the amount of either category assigned to this particular type cannot exceed its total supply.
Let \(z_e\) be the mass of this type receiving bundles of agent value zero. Every remaining recipient has integral agent value at least one. Hence
\(4\delta-z_e=\sum_{S:v_{t_e}(S)\geq1}\lambda_{t_e,S}\leq\sum_S\lambda_{t_e,S}v_{t_e}(S)\leq2\delta\),
so \(z_e\geq2\delta>0\). Since there are finitely many bundles, some bundle \(S_e\) satisfies both \(\lambda_{t_e,S_e}>0\) and \(v_{t_e}(S_e)=0\).
Now consider any positively allocated bundle \(B\), of any type. If \(B\) contained both \(g_a\) and \(g_b\), removing at most one category would leave agent value at least one for \(t_e\). Thus, for every \(R\subseteq B\) with \(|R|\leq1\),
\(v_{t_e}(S_e)=0< v_{t_e}(B\setminus R)\).
This contradicts the required support-wise EF-\(1\) comparison from \((t_e,S_e)\) to the recipient of \(B\).
Therefore \(B\) cannot contain both endpoints of any edge. It corresponds to an independent set. \(\square\)
The positive mass of zero-valued recipients is what makes this argument survive arbitrary splitting of type masses.
Proposition. The constructed instance is feasible and satisfies \(\mathrm{OPT}=\delta\,\alpha(H)\).
Upper bound. Only the special type contributes allocator welfare. By the lemma, every bundle it receives with positive mass has at most \(\alpha(H)\) categories. Therefore
\(W(\lambda)=\sum_S\lambda_{t_\star,S}|S|\leq\alpha(H)\sum_S\lambda_{t_\star,S}=\delta\,\alpha(H)\).
Matching construction. Let \(I\subseteq V\) be any independent set, and put \(S_I=\{g_x:x\in I\}\). Allocate as follows:
The remaining disposal mass is positive because \(\mu_{t_d}>N\delta\). Every type receives exactly its prescribed mass. Each category is allocated in amount exactly \(\delta\), either through \(S_I\) or through its disposal singleton. Thus all supply equalities hold.
To verify every support-wise EF-\(1\) comparison, special and disposal recipients have zero agent values, so their comparisons hold with \(R=\emptyset\). An edge type receives the empty bundle. It values every allocated bundle at most one: \(S_I\) contains at most one endpoint of its edge, and each other nonempty bundle is a singleton. Removing the valued category, if one exists, leaves value zero. This also covers comparisons within a type.
Hence the allocation is feasible and has welfare \(\delta|I|\). Taking a maximum independent set proves the matching lower bound.
Taking \(I=\emptyset\) already proves that every constructed instance is feasible. The exhibited allocations use at most \(m+\tau\) positive bundle/mass pairs and have dyadic masses. \(\square\)
Suppose an algorithm returns a feasible allocation with approximation factor \(f\). The proposition gives
\(W(\lambda)\geq\delta\,\alpha(H)/f\).
Choose a largest bundle \(B_\star\) among those assigned positive mass to the special type. Since that type has total mass \(\delta\),
\(|B_\star|\geq\frac{1}{\delta}\sum_S\lambda_{t_\star,S}|S|=\frac{W(\lambda)}{\delta}\geq\alpha(H)/f\).
The lemma proves that \(B_\star\) corresponds to an independent set. Thus an \(f\)-approximation for the society instance yields an \(f\)-approximation for maximum independent set.
Under the usual explicit output representation listing positive bundle/mass pairs, this extraction takes polynomial time in the output length and \(m\).
Here \(m=N\). An \(m^{1-\epsilon}\)-approximation would therefore produce an independent set of size at least
\(\alpha(H)/N^{1-\epsilon}\).
This contradicts maximum-independent-set approximation hardness with \(\eta=\epsilon\), unless \(\mathrm{P}=\mathrm{NP}\).
Because \(H\) is simple and \(N\geq2\),
\(\tau=q+2\leq\binom{N}{2}+2\leq N^2\).
Since \(1/2-\epsilon>0\), it follows that
\(\tau^{1/2-\epsilon}\leq(N^2)^{1/2-\epsilon}=N^{1-2\epsilon}\).
Thus a \(\tau^{1/2-\epsilon}\)-approximation would produce an independent set of size at least
\(\alpha(H)/N^{1-2\epsilon}\).
This contradicts the source hardness with \(\eta=2\epsilon\), whose hypothesis \(0<\eta<1\) holds.
For either factor, an algorithm running in \(\operatorname{poly}(m,\tau,L)\) for fixed \(\epsilon\) would yield a polynomial-time independent-set approximation: the reduction has \(m=N\), \(\tau\leq N^2\), and \(L=O(N^3)\). Both requested hardness conclusions therefore hold on the promised feasible instances.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes both requested approximation-hardness conclusions, even with binary agent and allocator values. No major or minor mathematical issues were found. The approximation transfer uses the explicit allocation-output representation stated in the proof.
The cited [Zuckerman Theorem 1.1](https://theoryofcomputing.org/articles/v003a006/v003a006.pdf) states that, for every fixed \(\eta>0\), approximating maximum clique within \(N^{1-\eta}\) is NP-hard.
Graph complementation preserves the vertex count and identifies cliques in the complement with independent sets in the original graph. Consequently, the stated independent-set hardness for every fixed \(0<\eta<1\) follows with the same approximation factor.
Restricting to \(N\geq2\) excludes only trivially solvable instances and does not affect hardness. Both later choices, \(\eta=\epsilon\) and \(\eta=2\epsilon\), satisfy the stated range.
Assessment: Correct theorem statement and application.
The construction has exactly \(m=N\) categories. Their supplies are \(\delta=1/D\), which are positive dyadic rationals in \([0,1]\).
The type masses sum to one:
\[
\delta+4q\delta+\bigl(1-(4q+1)\delta\bigr)=1.
\]
The disposal-mass calculation is correct:
\[
\mu_{t_d}-N\delta=\frac{D-4q-N-1}{D}>0.
\]
Indeed, the stipulated lower bound on \(D\) strictly exceeds \(4q+N+1\). Thus all listed types have positive mass, and the disposal type can accommodate the proposed singleton allocations.
The support count \(\tau=q+2\) is valid:
This also covers \(q=0\): the remaining two types are distinct.
Since \(D\) is the smallest power of two above the specified threshold, it is less than twice that threshold. With \(q\leq\binom{N}{2}\), its bit length is \(O(\log N)\). The stated explicit-table encoding bound
\[
L=O\bigl(m\tau+(m+\tau)\log m\bigr)=O(N^3)
\]
is therefore valid. The construction is polynomial in the source input size.
Assessment: All input restrictions, support-size claims, and encoding bounds are satisfied.
Fix an edge \(e=\{a,b\}\). Additivity and complete allocation give
\[
\sum_S\lambda_{t_e,S}v_{t_e}(S)
=
\sum_{S:g_a\in S}\lambda_{t_e,S}
+
\sum_{S:g_b\in S}\lambda_{t_e,S}
\leq2\delta.
\]
Each category’s allocation to this particular type is bounded by its total supply because all allocation masses are nonnegative.
The type has total mass \(4\delta\). Every bundle of positive agent value has integer value at least one, so its total mass is at most \(2\delta\). Consequently, the mass receiving value zero satisfies \(z_e\geq2\delta>0\).
There are finitely many bundles. Hence at least one zero-valued bundle \(S_e\) has positive allocated mass. This correctly supplies a comparison required by the support-wise EF-\(1\) definition.
If any positive bundle \(B\) contained both endpoints of \(e\), deleting at most one category would leave value at least one to \(t_e\). The positive recipient pair \((t_e,S_e)\) would then violate EF-\(1\) when compared with the recipient pair carrying \(B\).
The argument applies to every edge and every positive bundle, irrespective of its recipient type. It also respects the requirement to compare recipients within a type.
Assessment: The lemma is rigorous and survives arbitrary splitting of masses.
Only the special type contributes welfare. Its positive bundles are independent sets by the lemma, so each has at most \(\alpha(H)\) categories. Its total mass is \(\delta\), giving
\[
W(\lambda)\leq\delta\alpha(H).
\]
For the proposed allocation associated with an independent set \(I\):
The EF-\(1\) verification covers every ordered positive recipient pair. Special and disposal recipients value all bundles at zero. Edge recipients receive the empty bundle and value every allocated bundle at most one: independence controls \(S_I\), and all other nonempty bundles are singletons. Removing the valued category, when present, satisfies the comparison.
The allocation therefore has welfare \(\delta|I|\). Choosing a maximum independent set proves
\[
\mathrm{OPT}=\delta\alpha(H).
\]
Choosing \(I=\emptyset\) verifies feasibility without needing to solve independent set.
The claimed bound of at most \(m+\tau\) positive bundle/mass pairs is also correct.
Assessment: Both bounds and the feasibility promise are established.
The special type has positive total mass and finitely many possible bundles, so a largest positive bundle \(B_\star\) exists. Its cardinality is at least the weighted average cardinality:
\[
|B_\star|
\geq\frac{W(\lambda)}{\delta}
\geq\frac{\alpha(H)}{f}.
\]
The first equality implicit in this calculation correctly uses the fact that every other type has zero allocator values.
By the lemma, \(B_\star\) is an independent set. Thus the approximation ratio transfers without loss.
The computational qualification is explicit: the algorithm lists positive bundle/mass pairs. A polynomial-time algorithm has polynomial output length, and scanning this list to extract the largest special-type bundle takes polynomial time. The proof does not claim this extraction for an unspecified succinct representation.
Assessment: Correct under the stated, natural explicit-output convention; no missing mathematical step.
For the first factor, \(m=N\), so the transferred guarantee is exactly \(N^{1-\epsilon}\). Source hardness applies with \(\eta=\epsilon\).
For the second factor,
\[
\tau=q+2\leq\binom{N}{2}+2\leq N^2
\]
holds for every \(N\geq2\), including the boundary case \(N=2\). Because \(1/2-\epsilon>0\),
\[
\tau^{1/2-\epsilon}\leq N^{1-2\epsilon}.
\]
The resulting independent-set approximation therefore contradicts source hardness with \(\eta=2\epsilon\).
Finally, \(m=N\), \(\tau\leq N^2\), and \(L=O(N^3)\) ensure that any running time polynomial in \(m,\tau,L\), for fixed \(\epsilon\), transfers to polynomial time in the graph input size.
Assessment: Both requested hardness conclusions follow on feasible instances with binary values.
No repair is required. The explicit allocation-output convention should remain attached to the computational extraction claim.
⟨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.