Answer: \(\mathrm{NP}\text{-hard}\)
Proposition 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing an MmS allocation for chores - if it exists - is strongly NP-hard. The problem is weakly NP- hard even for two agents. Due to the intractability in general of computing MmS allocations for chores, in the following sections, we will de- velop different approximation and heuristic algorithms. 2-MmS-Approximation for Chores The purpose of this section is to present a polynomial-time 2-MmS-approximation algorithm (Algorithm 1) for chores, i.e., where each agent is guaranteed a utility of at least twice her (negative) max-min share guarantee.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita chore supplies \(q_j\), and nonnegative additive burdens \(a_{tj}\), define \(b_t=\min_{\pi}\max_{B:\pi_B>0} a_t\cdot B\), where \(\pi\) ranges over finite-support distributions on integral bundles \(B\in\mathbb{Z}_{\ge0}^{J}\) with \(\sum_B\pi_B=1\) and \(\sum_B\pi_B B=q\). Determine whether there is a finite-support mass assignment \(x_{t,B}\ge0\) with \(\sum_Bx_{t,B}=\mu_t\), \(\sum_{t,B}B_jx_{t,B}=q_j\) for every chore category \(j\), and \(x_{t,B}>0\) only if \(a_t\cdot B\le b_t\); if so, output such an assignment, and otherwise report infeasibility.
A society is given by its support: a list \(T\) of \(\tau\geq1\) types 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 categories \(J\), binary-rational per-capita supplies \(q_j\geq0\), and binary-rational additive burdens \(a_{tj}\geq0\), with \(a_t\cdot q>0\) for every type. Let \(L\) be the total input bit length.
Bundles are vectors \(B\in\mathbb Z_{\geq0}^{J}\), including the empty bundle, with burden \(a_t\cdot B\).
Define \(b_t=\min_{\pi}\max_{B:\pi_B>0}a_t\cdot B\), where \(\pi\) ranges over finite-support probability distributions satisfying \(\sum_B\pi_B B=q\). These benchmarks are defined by the input, not supplied separately.
The computational problem is to output a finite list of bundles and nonnegative rational masses \(x_{t,B}\) satisfying \(\sum_Bx_{t,B}=\mu_t\), \(\sum_{t,B}B_jx_{t,B}=q_j\) for every \(j\), and \(x_{t,B}>0\Rightarrow a_t\cdot B\leq b_t\), or report infeasibility.
Is this computational problem solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite agents and indivisible chores, computing a maximin-share allocation when one exists is strongly \(\mathrm{NP}\)-hard, and weakly \(\mathrm{NP}\)-hard even for two agents ([Aziz–Rauchecker–Schryen–Walsh](https://arxiv.org/html/1604.01435)).
No result settling this exact mass-assignment problem was identified in the literature search.
The required output problem is \(\mathrm{NP}\)-hard, even when \(\tau=1\), \(\mu_1=1\), every supply is \(q_j=\tfrac12\), and all burdens are positive integers.
We prove this by a polynomial-time reduction from PARTITION using one call to the proposed solver. Every instance constructed below is feasible and admits a polynomial-size rational output.
Binary-encoded PARTITION is \(\mathrm{NP}\)-complete: given positive integers \(w_1,\ldots,w_n\), decide whether some subset sums to half their total. See [Theorem 6.4 in this complexity text](https://hardness.mit.edu/drafts/2022-09-21.pdf). We may restrict to even total \(W=\sum_{i=1}^n w_i\), because doubling every integer preserves the answer and makes the total even.
Define
\[ R=n(W+1)+1,\qquad H=R^{n+1}. \]
Create one type of mass \(1\), and two chore categories \((i,0),(i,1)\) for each \(i\in\{1,\ldots,n\}\). Set
\[ q_{i,0}=q_{i,1}=\tfrac12,\qquad a_{i,0}=H+R^i,\qquad a_{i,1}=H+R^i+w_i. \]
Suppress the type index. The expected burden prescribed by the supplies is the integer
\[ C=a\cdot q=nH+\sum_{i=1}^n R^i+\frac W2. \]
This is a valid input: every burden is positive, all supplies and the type mass are binary-rational, and \(a\cdot q=C>0\).
The construction has polynomial bit length. Indeed, \(\log R=O(\log n+\log W)\), so every burden requires \(O(n(\log n+\log W))\) bits, and there are \(2n\) categories. No benchmark is supplied.
Lemma. There exists a nonnegative integral bundle \(B\) with \(a\cdot B=C\) if and only if the PARTITION instance is a yes-instance. Furthermore, every such bundle satisfies
\[ B_{i,0}+B_{i,1}=1 \quad\text{for every }i, \qquad \sum_{i=1}^n w_iB_{i,1}=\frac W2. \]
Proof. First observe that \(nW<R\) and \(n+1<R\). Consequently,
\[ n(R^n+W)<(n+1)R^n<R^{n+1}=H. \]
Writing \(d=\sum_{i=1}^nR^i+W/2\), we therefore have \(0<d<H\), and hence
\[ nH<C<(n+1)H. \]
Suppose \(a\cdot B=C\), and define
\[ k=\sum_{i=1}^n(B_{i,0}+B_{i,1}),\qquad c_i=B_{i,0}+B_{i,1},\qquad r=\sum_{i=1}^n w_iB_{i,1}. \]
Since every chore has burden at least \(H\), we have \(kH\le C<(n+1)H\), so \(k\le n\). Expanding the burden gives
\[ a\cdot B=kH+\sum_{i=1}^n c_iR^i+r. \]
The term after \(kH\) lies between \(0\) and \(k(R^n+W)\), and thus is strictly less than \(H\). Comparing the integer quotients upon division by \(H\) in \(a\cdot B=C=nH+d\) yields \(k=n\). Therefore,
\[ \sum_{i=1}^n c_iR^i+r = \sum_{i=1}^nR^i+\frac W2. \]
Here \(0\le c_i\le n<R\), while \(0\le r\le nW<R\) and \(0\le W/2<R\). Both sides are thus base-\(R\) representations without carries. Uniqueness of that representation gives \(c_i=1\) for every \(i\), and \(r=W/2\).
Thus each \(B_{i,1}\) belongs to \(\{0,1\}\), and the indices with \(B_{i,1}=1\) constitute a partition subset.
Conversely, given a subset \(S\) with \(\sum_{i\in S}w_i=W/2\), set \(B_{i,1}=1\) and \(B_{i,0}=0\) when \(i\in S\), and reverse these values otherwise. Direct substitution gives \(a\cdot B=C\). This proves the lemma.
Let \(b\) denote the benchmark of the single type.
For any finite-support distribution with mean \(q\), linearity gives
\[ \sum_B\pi_B(a\cdot B)=a\cdot q=C. \]
Its maximum supported burden is therefore at least \(C\). Hence \(b\ge C\).
If PARTITION has a solution, let \(B\) be its bundle from the lemma, and let \(\overline B=\mathbf1-B\), where \(\mathbf1\) has every coordinate equal to \(1\). Both bundles are nonnegative integral, and
\[ a\cdot\overline B=a\cdot\mathbf1-a\cdot B=2C-C=C. \]
Giving each bundle probability \(\tfrac12\) produces mean \(q\) and maximum burden \(C\). Thus \(b=C\).
Conversely, if a distribution with mean \(q\) has maximum burden at most \(C\), then every positive-probability bundle must have burden exactly \(C\): their average is \(C\), and any strictly smaller supported burden would make that average smaller. The encoding lemma then produces a partition subset.
We have proved
\[ b=C \quad\Longleftrightarrow\quad \text{PARTITION is a yes-instance}. \]
Attainment of \(b\), including on no-instances, is established next.
The distribution assigning probability \(\tfrac12\) to the empty bundle and probability \(\tfrac12\) to \(\mathbf1\) has mean \(q\) and maximum burden \(2C\).
Because all burdens are integers, the maximum burden of every finite-support distribution is a nonnegative integer. The nonempty set of achievable maxima therefore has a least element \(b\), achieved by some distribution, with \(b\le2C\).
There are only finitely many bundles of burden at most \(b\). Indeed, every coordinate of such a bundle satisfies
\[ B_jH\le a\cdot B\le b\le2C<2(n+1)H, \]
so \(B_j\le2n+1\).
Choose a distribution with mean \(q\), supported on these bundles, whose support size \(s\) is smallest. Its augmented bundle vectors \((1,B)\) are linearly independent. Otherwise, a nonzero dependence would give coefficients summing to zero and preserving every supply coordinate. Such coefficients have both positive and negative entries. Subtracting a suitable positive multiple of them from the positive distribution weights preserves all equations and nonnegativity while making at least one weight zero, contradicting minimality.
Consequently, \(s\le2n+1\). The weights solve a rational linear system with independent columns, so an invertible \(s\)-row subsystem and Cramer’s rule show that all weights are rational.
They also have polynomial bit length. The subsystem’s integer matrix entries are at most \(2n+1\). Multiplying the weights by \(2\) makes its right-hand side integral with entries at most \(2\). The determinants in Cramer’s rule have absolute value at most \(s!(2n+1)^s\), giving \(O(n\log n)\) bits per weight.
These rational weights, used as the single type’s assignment masses, form a valid output. Thus infeasibility cannot be reported on any constructed instance.
Suppose a polynomial-time algorithm solves the problem as stated. Run it on the constructed instance and compute
\[ M=\max_{B:x_{1,B}>0}a\cdot B. \]
The output weights form a finite-support distribution with mean \(q\), so the benchmark definition gives \(M\ge b\). Output validity gives \(M\le b\). Therefore \(M=b\).
By Section 3, accept the PARTITION instance exactly when \(M=C\). Construction and postprocessing take polynomial time, and the hypothetical solver’s output has polynomial length because its running time is polynomial.
This would solve PARTITION in polynomial time.
The exact mass-assignment output problem is \(\mathrm{NP}\)-hard already for one supported type. A solver running in time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The hardness concerns producing an allocation satisfying the input-defined benchmark: all instances used in the reduction are feasible.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the requested computational question: producing a valid assignment is \(\mathrm{NP}\)-hard, already with one supported type. No major or minor mathematical issues were found.
The reduction establishes hardness of the output problem through one solver call. It does not establish hardness of deciding feasibility: every constructed instance is feasible.
The source problem is binary-encoded PARTITION on positive integers. Its NP-completeness is a standard result, also stated in the cited authors’ [complexity text](https://hardness.mit.edu/drafts/2025-02-02.pdf).
Restricting to even total is valid. Doubling all input integers preserves whether a subset sums to half the total, and increases encoding length only polynomially.
The constructed instance satisfies every relevant input requirement:
The encoding-length estimate is correct. Both \(R^i\) and \(H=R^{n+1}\) have polynomial bit length in the source input. Constructing these integers also takes polynomial time.
All bounds used to separate the high-order and low-order terms are valid.
From the definition of \(R\), the inequalities \(nW<R\) and \(n+1<R\) hold. The displayed bound
\[
n(R^n+W)<(n+1)R^n<H
\]
is correct, and it implies \(0<d<H\). Consequently, \(nH<C<(n+1)H\).
For a bundle of burden exactly \(C\), the inequality \(kH\le C\) gives \(k\le n\). Its remaining burden is nonnegative and strictly less than \(H\). Comparing integer quotients upon division by \(H\) therefore legitimately gives \(k=n\).
The base-\(R\) argument is also sound:
Thus both sides have valid base-\(R\) representations without carries. Uniqueness forces \(c_i=1\) and \(r=W/2\). Integrality and nonnegativity then ensure that each \(B_{i,1}\) is either zero or one.
The converse construction directly satisfies the required burden equation. The lemma proves both its existence equivalence and its stronger characterization of every exact-burden bundle.
The expected-burden identity holds for every admissible finite-support distribution. Hence its maximum supported burden is at least \(C\).
On a yes-instance, the complementary bundles are valid nonnegative integral bundles. The identity \(a\cdot\mathbf1=2C\) is correct, so both have burden \(C\), and their equal mixture has the prescribed mean.
Conversely, a finite distribution with maximum burden at most \(C\) and average burden \(C\) must assign positive probability only to bundles of burden exactly \(C\). The encoding lemma then applies.
The stated equivalence \(b=C\) if and only if PARTITION is a yes-instance relies on attainment of the benchmark. Section 4 explicitly establishes that attainment, so this forward reference introduces no gap.
The empty/full-bundle mixture has mean \(q\) and maximum burden \(2C\). The set of achievable maximum burdens is therefore nonempty. Because all burdens are integers, this set has a least element, attained by a distribution. Thus the use of a minimum rather than an infimum is justified for these instances.
The coordinate bound \(B_j\le2n+1\) is correct. It makes the set of bundles eligible at burden at most \(b\) finite.
The minimal-support argument correctly proves linear independence of the augmented vectors. A nonzero dependence has coefficients summing to zero, hence both signs; the described weight adjustment preserves all constraints and removes at least one supported bundle. This contradicts minimality.
It follows that \(s\le2n+1\). An invertible row subsystem exists because the columns are independent. Cramer’s rule applies to an integer matrix with a rational right-hand side, proving rationality of the weights.
The determinant estimate is valid for both the denominator and replacement-column numerators after scaling the weights by two. It gives polynomial encoding length. Together with the coordinate and support bounds, this establishes a polynomial-size valid rational output on every constructed instance.
For a valid single-type output, the assignment masses are a probability distribution with mean \(q\). Therefore its maximum positive-mass burden \(M\) satisfies both \(M\ge b\), by benchmark minimality, and \(M\le b\), by output validity. Thus \(M=b\).
The positive-mass support is nonempty because its masses sum to one. Zero-mass listed bundles are correctly excluded from the maximum.
Computing \(M\) and comparing it with \(C\) uses exact integer and rational arithmetic of polynomial bit complexity. A polynomial-time solver necessarily emits polynomial-length output, so the postprocessing is polynomial.
The resulting one-call reduction correctly decides PARTITION from any valid solver output.
The write-up establishes the claimed NP-hardness. No repair or additional mathematical clarification is needed. It correctly separates allocation-production hardness from feasibility and does not claim strong NP-hardness or NP-completeness.
⟨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.