Answer: \(\mathrm{NP}\)-hard for every fixed rational \(0<\alpha<\tfrac12\), even with \(\tau=3\) and dyadic rational data.
Theorem 5 — class: hardness
Given chore classes \(J\), cost types \(T\) with rational masses \(\mu_t\), normalized additive costs \(c_t\), and rational per-worker supplies \(b_j\), let \(x_{t,A}\) be the mass of type \(t\) assigned integral bundle \(A\subseteq J\). Require \(\sum_A x_{t,A}=\mu_t\), \(\sum_{t,A:j\in A}x_{t,A}=b_j\), and, for every pair with \(x_{t,A},x_{u,B}>0\), require some \(j\in A\) such that \(c_t(A\setminus\{j\})\leq c_u(B)\). Find a feasible assignment minimizing \(\sum_{t,A}x_{t,A}c_t(A)\), or determine its approximation complexity.
A society is an atomless population of total mass \(1\), given by its support: the list of \(\tau\) cost types \(t\in T\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) chore classes \(J\). Each worker receives an integral bundle \(A\subseteq J\), containing at most one chore per class. Costs are nonnegative binary rationals, additive and normalized by \(c_t(J)=1\); per-worker supplies are binary rationals \(b_j\in[0,1]\).
An assignment consists of masses \(x_{t,A}\geq0\) satisfying \(\sum_{A\subseteq J}x_{t,A}=\mu_t\) and \(\sum_{t,A:j\in A}x_{t,A}=b_j\).
It is equitable up to one chore (EQ1) if every ordered pair \((t,A),(u,B)\) with positive assigned mass and \(A\neq\varnothing\) satisfies \(c_t(A\setminus\{j\})\leq c_u(B)\) for some \(j\in A\). Empty source bundles satisfy EQ1 automatically; comparisons use weak inequalities, including ties.
Define \(C(x)=\sum_{t,A}x_{t,A}c_t(A)\) and let \(\mathrm{OPT}\) be its minimum over feasible EQ1 assignments. Restrict the approximation question to instances admitting such an assignment.
For each fixed rational \(0<\alpha<\tfrac12\), can a feasible EQ1 assignment with \(C(x)\leq\mathrm{OPT}+\alpha\) be computed in polynomial time, or is achieving this additive guarantee NP-hard? State running times in \(m,\tau,L\), and any accuracy parameters, where \(L\) is the total input bit length.
For discrete normalized additive chores, achieving additive error below \(\tfrac12\) for minimum-total-cost EQ1 allocation is NP-hard for every fixed number \(n\geq3\) of agents; a polynomial-time additive guarantee of \(1\) is available. [Source](https://arxiv.org/html/2410.15738v1)
No result settling this exact atomless, integral-bundle, prescribed-supply approximation problem was located.
Achieving the requested additive guarantee is \(\mathrm{NP}\)-hard for every fixed rational \(0<\alpha<\tfrac12\), even with exactly \(\tau=3\) cost types and dyadic rational data. Every instance produced by the reduction admits an EQ1 assignment.
The reduction gives the exact optimum values
\(\mathrm{OPT}_{\mathrm{yes}}=\tfrac{7}{32}\) and
\(\mathrm{OPT}_{\mathrm{no}}=\tfrac{63}{64}\).
Their difference is \(\tfrac{49}{64}\).
Consequently, unless \(\mathrm{P}=\mathrm{NP}\), no algorithm running in \(\operatorname{poly}(m,\tau,L)\) achieves the requested guarantee. An exact algorithm runs in \(2^{O(m)}\operatorname{poly}(m,\tau,L)\), as proved below.
We reduce from the standard \(\mathrm{NP}\)-complete Partition problem: given positive integers \(p_1,\ldots,p_r\), decide whether some subset sums to half their total. See [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let \(W=\sum_{i=1}^r p_i\), and choose a power of two \(B>2W\). Define \(k=r+2\) weights by
\(w_i=2p_i\) for \(1\leq i\leq r\), and
\(w_{r+1}=w_{r+2}=B-W\).
Then \(\sum_{i=1}^k w_i=2B\), and every weight satisfies \(0<w_i<B\).
There is a subset of these weights summing to \(B\) if and only if the original Partition instance is a yes-instance. Indeed, a subset summing to \(B\) must contain exactly one of the two added weights:
After including exactly one added weight, the selected original weights must sum to \(W\), equivalently the selected original integers must sum to \(W/2\).
This preparation has polynomial bit complexity.
Let \(D=\{d_1,\ldots,d_k\}\) be partition chore classes. Add four further classes \(g,h,p,q\), so \(m=r+6\).
There are three types, denoted \(a,b,z\), with the following masses and costs:
| Type | Mass | \(g\) | \(h\) | \(p\) | \(q\) | \(d_i\) |
|---|---|---|---|---|---|---|
| \(a\) | \(\tfrac{7}{16}\) | \(\tfrac18\) | \(0\) | \(\tfrac78\) | \(0\) | \(0\) |
| \(b\) | \(\tfrac{7}{16}\) | \(\tfrac18\) | \(0\) | \(0\) | \(\tfrac78\) | \(0\) |
| \(z\) | \(\tfrac18\) | \(0\) | \(\tfrac34\) | \(0\) | \(0\) | \(\tfrac{w_i}{8B}\) |
The supplies are
\(b_g=b_h=1\),
\(b_p=b_q=\tfrac{7}{16}\), and
\(b_{d_i}=\tfrac{15}{16}\) for every \(i\).
All masses are positive and sum to one. The costs are normalized: for types \(a,b\), the two positive costs sum to one; for type \(z\),
\(\displaystyle c_z(J)=\frac34+\frac{\sum_i w_i}{8B}=\frac34+\frac14=1.\)
Because \(B\) is a power of two, all data are dyadic rationals.
The supplies \(b_g=b_h=1\) force every positive-mass bundle to contain both \(g\) and \(h\): otherwise the assigned mass containing that class would be strictly less than the total population mass.
For a bundle \(A\), write
\(\displaystyle R(A)=\sum_{i:d_i\in A}\frac{w_i}{8B}.\)
Every used type-\(z\) bundle consequently has cost
\(c_z(A)=\tfrac34+R(A)\).
Moreover, \(h\) is its most costly chore, since every partition chore costs less than \(\tfrac18\). Thus
\(\displaystyle \min_{j\in A}c_z(A\setminus\{j\})=R(A).\)
For any feasible assignment, let
\(\displaystyle y_i=\sum_{A:d_i\in A}x_{z,A}\)
be the type-\(z\) mass receiving \(d_i\).
Types \(a,b\) together have mass \(\tfrac78=\tfrac{14}{16}\), and each worker can receive at most one copy of \(d_i\). Therefore
\(\displaystyle y_i\geq b_{d_i}-\frac78=\frac1{16}.\)
The total partition-chore cost borne by type \(z\), denoted \(E\), satisfies
\(\displaystyle E=\sum_Ax_{z,A}R(A) =\sum_i\frac{w_i}{8B}y_i \geq\frac1{16}\sum_i\frac{w_i}{8B} =\frac1{64}.\)
Every type-\(a\) or type-\(b\) worker incurs at least the mandatory cost \(\tfrac18\), while every type-\(z\) worker incurs the mandatory cost \(\tfrac34\). Hence every feasible assignment satisfies
\(\displaystyle C(x)\geq \frac78\cdot\frac18+\frac18\cdot\frac34+\frac1{64} =\frac7{32}.\)
Let \(H=\{g,h\}\). Consider the following assignment:
| Type | Bundle | Assigned mass |
|---|---|---|
| \(a\) | \(H\cup D\cup\{p\}\) | \(\tfrac{7}{16}\) |
| \(b\) | \(H\cup D\cup\{q\}\) | \(\tfrac{7}{16}\) |
| \(z\) | \(H\) | \(\tfrac1{16}\) |
| \(z\) | \(H\cup D\) | \(\tfrac1{16}\) |
Its type masses and supplies are correct. In particular, every \(d_i\) is assigned to mass \(\tfrac78+\tfrac1{16}=\tfrac{15}{16}\).
The two main-type bundles have cost \(1\); removing their expensive private chore leaves cost \(\tfrac18\). The two type-\(z\) bundles have costs \(\tfrac34\) and \(1\); removing \(h\) leaves costs \(0\) and \(\tfrac14\).
Every target bundle has cost at least \(\tfrac34\), and every source bundle has a deletion leaving cost at most \(\tfrac14\). Thus every ordered-pair EQ1 comparison holds.
Its total cost is
\(\displaystyle C(x)=\frac78+\frac1{16}\cdot\frac34+\frac1{16}\cdot1 =\frac{63}{64}.\)
The feasibility promise therefore holds independently of the Partition answer.
Suppose \(S\subseteq D\) corresponds to weights summing to \(B\). Its complement also corresponds to weights summing to \(B\). Assign:
| Type | Bundle | Assigned mass |
|---|---|---|
| \(a\) | \(H\cup D\cup\{q\}\) | \(\tfrac{7}{16}\) |
| \(b\) | \(H\cup D\cup\{p\}\) | \(\tfrac{7}{16}\) |
| \(z\) | \(H\cup S\) | \(\tfrac1{16}\) |
| \(z\) | \(H\cup(D\setminus S)\) | \(\tfrac1{16}\) |
Again all supplies are exact.
Both main-type bundles cost \(\tfrac18\), and deleting \(g\) leaves cost zero. Both type-\(z\) bundles cost \(\tfrac34+\tfrac18=\tfrac78\), and deleting \(h\) leaves cost \(\tfrac18\).
Thus every source bundle has a deletion leaving cost at most the minimum target cost \(\tfrac18\). Equality is permitted, so this assignment is EQ1.
Its cost is
\(\displaystyle C(x)=\frac78\cdot\frac18+\frac18\cdot\frac78=\frac7{32}.\)
Together with the preceding lower bound, this proves
\(\mathrm{OPT}_{\mathrm{yes}}=\tfrac7{32}\).
Suppose there is no subset of weights summing to \(B\). Consider any feasible EQ1 assignment.
Assume first that some positive-mass type-\(a\) bundle omits \(p\), or some positive-mass type-\(b\) bundle omits \(q\). That bundle has cost exactly \(\tfrac18\).
Comparing every used type-\(z\) bundle against this bundle, EQ1 requires
\(\displaystyle R(A)\leq\frac18 \quad\text{whenever }x_{z,A}>0.\)
Consequently,
\(\displaystyle E=\sum_Ax_{z,A}R(A) \leq\mu_z\cdot\frac18=\frac1{64}.\)
The supply-forced lower bound gives \(E\geq\tfrac1{64}\), so equality holds. Since every used type-\(z\) bundle has \(R(A)\leq\tfrac18\), equality in this weighted average forces
\(\displaystyle R(A)=\frac18 \quad\text{for every }A\text{ with }x_{z,A}>0.\)
Type \(z\) has positive mass, so such a bundle exists. Its partition chores satisfy
\(\displaystyle \sum_{i:d_i\in A}w_i=B,\)
contradicting the no-instance assumption.
Therefore every type-\(a\) worker must receive \(p\), and every type-\(b\) worker must receive \(q\). All these workers incur cost \(1\). Using the mandatory type-\(z\) cost and its partition-cost lower bound gives
\(\displaystyle C(x)\geq \frac78+\frac18\cdot\frac34+\frac1{64} =\frac{63}{64}.\)
The universal EQ1 assignment attains this value. Hence
\(\mathrm{OPT}_{\mathrm{no}}=\tfrac{63}{64}\).
The argument applies to arbitrary real assignment masses: splitting types cannot avoid the implication triggered by any positive mass of a cheap main-type bundle.
Fix rational \(0<\alpha<\tfrac12\). Suppose a polynomial-time algorithm always returns a feasible EQ1 assignment with \(C(x)\leq\mathrm{OPT}+\alpha\).
On a yes-instance, its output satisfies
\(\displaystyle C(x)\leq\frac7{32}+\alpha <\frac{23}{32}<\frac34.\)
On a no-instance, every feasible EQ1 output satisfies
\(C(x)\geq\tfrac{63}{64}>\tfrac34\).
Comparing the returned cost with \(\tfrac34\) therefore decides Partition in polynomial time.
If the original Partition input has bit length \(N\), the reduction has \(m=r+6\), \(\tau=3\), and total encoding length \(L=O(N^2)\). Construction and evaluation of a polynomial-size rational output take polynomial time.
Thus the requested approximation is \(\mathrm{NP}\)-hard. In particular, an additive scheme running in \(\operatorname{poly}(m,\tau,L,1/\varepsilon)\) is impossible unless \(\mathrm{P}=\mathrm{NP}\), by fixing any \(0<\varepsilon<\tfrac12\).
For completeness, define
\(d_t(A)=c_t(A)\), and define
\(r_t(A)=c_t(A)-\max_{j\in A}c_t(j)\) for nonempty \(A\), with \(r_t(\varnothing)=0\).
An assignment is EQ1 exactly when
\(\displaystyle \max_{x_{t,A}>0}r_t(A) \leq \min_{x_{u,B}>0}d_u(B). \)
Indeed, deleting a most costly chore minimizes the remaining source cost.
Enumerate all thresholds in
\(\mathcal D=\{d_t(A):t\in T,\ A\subseteq J\}\).
For each \(q\in\mathcal D\), retain only variables satisfying
\(r_t(A)\leq q\leq d_t(A)\), and solve the rational linear program minimizing \(C(x)\) subject to the prescribed type masses and supplies.
Every feasible point of such a program is EQ1. Conversely, every EQ1 assignment belongs to the program with threshold equal to its minimum used bundle cost. Taking the cheapest feasible program therefore computes \(\mathrm{OPT}\) exactly.
There are at most \(\tau2^m\) thresholds and variables per program. Their coefficients have polynomial bit length. Polynomial-time rational linear programming thus gives total running time
\(\displaystyle 2^{O(m)}\operatorname{poly}(m,\tau,L),\)
with no accuracy parameter.
Each feasible program is bounded. An optimal vertex has at most \(\tau+m\) positive variables, because there are only \(\tau+m\) equality constraints. Its positive masses have polynomial bit length: the constraint matrix has entries zero or one, and Cramer’s rule together with Hadamard’s determinant bound gives polynomial-size rational coordinates. Hence an optimal assignment always has a polynomial-size explicit representation.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the assigned problem. The reduction is correct, its feasibility promise holds in both cases, and its optimum gap establishes the claimed approximation hardness. The exact algorithm and representation-size claims also stand. I found no major or minor mathematical issues.
The source problem is the standard binary-encoded, positive-integer Partition problem, whose NP-completeness is the cited result. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
The transformation satisfies all its stated properties:
Thus a subset summing to \(B\) contains exactly one added weight, and its original weights sum to \(W\). This is equivalent to the original integers having a subset summing to \(W/2\). The equivalence also handles odd \(W\): no subset of the even original weights can sum to odd \(W\).
Choosing a power of two greater than \(2W\) requires only polynomially many bits. The preparation is a valid polynomial-time reduction.
The constructed instance meets the task’s requirements.
The three masses are positive and sum to \(1\). All supplies lie in \([0,1]\). Costs are nonnegative and normalized: the main types have total cost \(1\), and type \(z\) has total cost
\[
\frac34+\frac{2B}{8B}=1.
\]
All data are dyadic rationals because \(B\) is a power of two.
The assertion that supplies \(b_g=b_h=1\) force every positive-mass bundle to contain both classes is correct. A bundle omitting either class would leave strictly less than total mass \(1\) receiving that class.
For type \(z\), each partition chore costs less than \(1/8\), while \(h\) costs \(3/4\). Therefore \(h\) is its most costly chore, and the minimum cost obtainable by deleting one chore is exactly \(R(A)\). Zero-cost appearances of \(g,p,q\) do not affect this conclusion.
For each partition class, types \(a,b\) together can receive at most mass \(7/8\). Consequently,
\[
y_i\geq\frac{15}{16}-\frac78=\frac1{16}.
\]
The resulting partition-cost bound is correct:
\[
E\geq\frac1{16}\frac{2B}{8B}=\frac1{64}.
\]
Adding the mandatory costs gives
\[
C(x)\geq\frac7{64}+\frac6{64}+\frac1{64}
=\frac7{32}.
\]
This bound uses only feasibility and applies to arbitrary real assignment masses.
The proposed universal assignment has the prescribed type masses and supplies. In particular, each partition class receives mass
\[
\frac78+\frac1{16}=\frac{15}{16},
\]
and the private classes receive their required masses.
Its used bundle costs are \(1,1,3/4,1\). The minimum residual costs after deleting one chore are \(1/8,1/8,0,1/4\). Hence every source has a deletion leaving cost at most \(1/4\), while every target has cost at least \(3/4\). This verifies every ordered-pair EQ1 comparison, including comparisons within a type.
Its cost is
\[
\frac78+\frac3{64}+\frac4{64}=\frac{63}{64}.
\]
Thus every reduced instance satisfies the feasibility promise.
When a subset of weights sums to \(B\), its complement also sums to \(B\). The two type-\(z\) bundles therefore each have partition cost \(1/8\).
The proposed assignment meets every supply: each partition class appears in both main-type bundles and exactly one of the two type-\(z\) bundles. Swapping the private classes gives the main types zero private-chore cost.
The main-type costs are \(1/8\), with residual cost \(0\). The type-\(z\) costs are \(7/8\), with residual cost \(1/8\). Consequently, the largest residual equals the smallest target cost. The weak inequalities specified in the task make this EQ1.
The cost calculation gives \(7/32\). Together with the established lower bound, this proves the claimed yes-instance optimum.
This is the central step, and it is valid.
Any positive-mass main-type bundle omitting its costly private chore has cost exactly \(1/8\). Using that bundle as a target forces every positive-mass type-\(z\) bundle to satisfy
\[
R(A)\leq\frac18.
\]
Since type \(z\) has mass \(1/8\), this implies \(E\leq1/64\). The supply lower bound gives the reverse inequality. Equality in this finite weighted sum, with all used masses positive, forces every used type-\(z\) bundle to have \(R(A)=1/8\).
There is at least one such bundle because type \(z\) has positive mass. Its partition weights sum to \(B\), contradicting the no-instance assumption.
Therefore every positive-mass main-type bundle contains its costly private chore and has cost \(1\). The resulting lower bound is
\[
C(x)\geq\frac78+\frac3{32}+\frac1{64}
=\frac{63}{64}.
\]
The universal assignment attains it.
The reasoning correctly excludes evasion by splitting types into arbitrarily small positive masses.
The optimum gap is correctly computed:
\[
\frac{63}{64}-\frac7{32}=\frac{49}{64}.
\]
For every fixed \(0<\alpha<1/2\), the guaranteed yes-instance output has cost less than \(23/32\), hence less than \(3/4\). Every feasible no-instance output has cost at least \(63/64>3/4\). Therefore comparison with \(3/4\) decides Partition.
The construction has \(m=r+6\), \(\tau=3\), and polynomial encoding length. The stated bound \(L=O(N^2)\) is valid for the explicit cost table. Evaluating a polynomial-size rational assignment also takes polynomial time.
The fixed-accuracy implication for an algorithm polynomial in \(m,\tau,L,1/\varepsilon\) follows directly. No numerical precision gap is present because the decision threshold is separated from both output ranges by a constant.
The stated EQ1 characterization is correct. For nonempty bundles, deleting a most costly chore minimizes residual cost. For empty bundles, setting the residual to zero is consistent with their automatic EQ1 status because every target cost is nonnegative.
The threshold programs have both required directions:
That minimum is attained among finitely many used bundles and belongs to the enumerated threshold set. Taking the best feasible program therefore computes the exact optimum.
There are at most \(\tau2^m\) programs, each with at most \(\tau2^m\) variables and polynomial-bit rational coefficients. The standard polynomial-time theorem for rational linear programming applies, yielding the claimed total runtime \(2^{O(m)}\operatorname{poly}(m,\tau,L)\).
The vertex claims also hold. Type-mass constraints bound every variable. A vertex has at most the constraint-matrix rank, hence at most \(\tau+m\), positive variables. The zero-one matrix and rational right-hand side give polynomial-bit coordinates through the stated determinant bounds.
No additional clarification or repair is needed.
⟨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.