Almost Envy-Freeness in Group Resource Allocation (d4-conf-ijcai-2019-0800)

Given finite indivisible goods \(G\) and a rational distribution \(\mu\) over types \(t=(i,v)\), where \(i\in\{1,2\}\) is the fixed group and \(v\in\{0,1\}^{|G|}\) is a binary additive valuation, choose a partition \(B_1\dot\cup B_2=G\) minimizing \(D_\mu(B_1,B_2)=\sum_t\mu_t\mathbf{1}[t\text{ is not EF1 under }(B_1,B_2)]\); decide whether \(D_\mu\le\varepsilon\), with \(\varepsilon=0\) as the exact analogue of Proposition 3.7.

Given finite indivisible goods \(G\), an explicitly listed rational distribution \(\mu\) over types \(t=(i,v)\), where \(i\in\{1,2\}\) and \(v\in\{0,1\}^{|G|}\) is additive, choose a partition \(B_1\dot\cup B_2=G\).
A type \(t=(i,v)\) is EF1 if there is \(S\subseteq B_{3-i}\) with \(|S|\leq 1\) such that \(v(B_i)\geq v(B_{3-i}\setminus S)\). Define \(D_\mu(B_1,B_2)=\sum_t\mu_t\mathbf{1}[t\text{ is not EF1}]\).

Is deciding whether some partition has \(D_\mu(B_1,B_2)\leq\varepsilon\) solvable in polynomial time, or is it NP-hard? In particular, this includes \(\varepsilon=0\).

For finite lists of agents in two fixed groups with binary valuations, deciding existence of an EF1 allocation is NP-complete.

The decision problem is NP-complete, already when \(\varepsilon=0\), using the NP-completeness premise supplied in the question.

First, we verify membership in NP. A certificate is a partition \((B_1,B_2)\), encoded by one bit per good. For a listed type \(t=(i,v)\), put
\[ a_t=v(B_i),\qquad b_t=v(B_{3-i}). \]
Because valuations are binary, removing at most one good from the other bundle can reduce its value by at most one. If \(b_t>0\), this reduction is achievable by removing a positively valued good; if \(b_t=0\), the type is already envy-free. Consequently,
\[ t\text{ is EF1}\quad\Longleftrightarrow\quad a_t\geq b_t-1, \]
and therefore
\[ D_\mu(B_1,B_2)=\sum_{t:\,b_t\geq a_t+2}\mu_t. \]
All bundle values can be computed in polynomial time. The rational sum and comparison with the rational threshold \(\varepsilon\) can also be performed exactly in polynomial time: a common denominator obtained by multiplying the input denominators has bit length at most the sum of their bit lengths. Thus the problem belongs to NP.

For NP-hardness, use the supplied NP-complete problem: agents belong to two fixed groups, each group receives one bundle in a partition of the goods, and every agent must satisfy EF1 according to that agent’s binary additive valuation.

Let an instance have agents \(A=\{1,\ldots,N\}\), where \(N>0\). Agent \(a\) belongs to group \(i_a\in\{1,2\}\) and has valuation vector \(v_a\). Keep the same goods and define a distribution on the distinct occurring types by
\[ \mu_{(i,v)} = \frac{\bigl|\{a\in A:i_a=i,\ v_a=v\}\bigr|}{N}. \]
Set \(\varepsilon=0\). This explicitly listed distribution has at most \(N\) types, has total mass one, and has polynomial encoding length. Aggregating agents with identical types is valid because their EF1 conditions coincide for every partition.

For every partition, the construction gives the exact identity
\[ D_\mu(B_1,B_2) = \frac{1}{N} \bigl|\{a\in A:\text{agent }a\text{ is not EF1 under }(B_1,B_2)\}\bigr|. \]
Indeed, each distinct type contributes precisely the fraction of agents with that type when its EF1 condition fails, and contributes zero otherwise. Hence
\[ D_\mu(B_1,B_2)\leq 0 \quad\Longleftrightarrow\quad \text{every agent is EF1}. \]
Thus the constructed instance admits a qualifying partition exactly when the original fixed-group instance does. This is a polynomial-time many-one reduction, proving NP-hardness for \(\varepsilon=0\). Together with membership in NP, it proves NP-completeness both for that restriction and for the problem with an input threshold.

⟨structured verdict parsed — rendered above⟩

The proof is correct and rigorous relative to the NP-completeness premise explicitly supplied in USER_TASK. It establishes NP-completeness already for \(\varepsilon=0\). No major or minor mathematical issues were found.

• Source problem and scope. The prover uses exactly the supplied fixed-group problem: two prescribed groups receive bundles forming a partition, and every agent must satisfy EF1 under their own binary additive valuation. This is a given premise, so no independent hardness proof or external theorem verification is needed. The reduction preserves the goods, group labels, and valuations.

• EF1 characterization. For binary additive valuations, removing at most one good decreases the other bundle’s value by at most one. If \(b_t>0\), some good in that bundle has value one, so that decrease is attainable. If \(b_t=0\), EF1 holds automatically, and \(a_t\geq b_t-1\) also holds because \(a_t\geq0\). Thus the claimed equivalence is valid in all cases, including empty bundles and zero valuations. Since bundle values are integers, failure is exactly \(b_t\geq a_t+2\).

• Membership in NP. A partition requires one bit per good. Each listed type’s bundle values and failure indicator can be computed in polynomial time in the explicit input size. Exact rational summation and comparison also take polynomial time: the product of the input denominators has polynomial bit length, and the resulting numerators and arithmetic operations remain polynomially bounded. This establishes membership in NP for a rational input threshold and for the restriction \(\varepsilon=0\).

• Validity and size of the reduction. Each distinct occurring type receives its multiplicity divided by \(N\). These probabilities are positive and sum to one. There are at most \(N\) distinct types, and each multiplicity and denominator has polynomial encoding length. Identical types can be identified by comparing their explicit group labels and valuation vectors in polynomial time. Restricting to \(N>0\) creates no substantive omission: instances with no agents are automatically feasible and cannot be the source of hardness.

• Preservation of feasibility. Agents with identical types have identical EF1 conditions for every partition. Consequently, the displayed identity equating \(D_\mu\) to the fraction of agents failing EF1 is exact. All occurring types have positive probability, so \(D_\mu\leq0\) holds precisely when no agent fails EF1. This proves both directions of the required equivalence between source and target instances.

• Complexity conclusion. The construction is a polynomial-time many-one reduction with threshold fixed to zero. It proves NP-hardness of that restriction. Membership in NP gives NP-completeness of the restriction, and the general rational-threshold problem inherits hardness while remaining in NP.

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩