Answer: \(\mathrm{NP}\)-hard for fixed \(\rho=1\) and \(\epsilon=\tfrac12\), even with \(\tau=1\) and \(P=4\); no such PTAS unless \(\mathrm{P}=\mathrm{NP}\).
Theorem 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is an algorithm to solve the B-MMS problem for the case MMS ≥0, that runs in time O(mnL), where L is the number of bits needed to represent function v.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(P\in\mathbb{N}\), \(d\) item types, rational per-capita supplies \(q\in\mathbb{Q}_{\ge 0}^d\), rational signed values \(v\in\mathbb{Q}^d\), and fixed \(\rho,\epsilon>0\), consider distributions over integral bundles \(b\in\mathbb{Z}_{\ge 0}^d\) with masses \(\lambda_b>0\), \(\sum_b\lambda_b=1\), and \(\sum_b\lambda_b b=q\). Let \(\mathrm{CMMS}(q,v)\) be the supremum, over such distributions, of \(\min_{\lambda_b>0} v\cdot b\). Under the promise \(\mathrm{CMMS}\ge 0\), compute a distribution whose every positive-mass bundle has value at least \((1-\epsilon)\mathrm{CMMS}\) when \(\mathrm{CMMS}\ge P\min\{V^+,V^-\}/\rho\), where \(V^+=\sum_{v_j>0}q_jv_j\) and \(V^-=\sum_{v_j<0}q_j|v_j|\); otherwise report that the threshold fails.
Fix rational constants \(\rho\ge 1\) and \(0<\epsilon<1\). The input consists of \(m=d\ge1\) item types, per-capita supplies \(q\in\mathbb Q_{\ge0}^m\), common additive signed values \(v\in\mathbb Q^m\), and a positive binary-encoded population scale \(P\); total supplies are \(Pq\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here all agents have valuation \(v\), so the normalized society has one valuation type of mass \(1\) and \(\tau=1\); \(\tau\) denotes support size, not the number of possible types.
A feasible allocation is a finite distribution over bundles \(b\in\mathbb Z_{\ge0}^m\), represented by its support and positive binary-rational masses \(\lambda_b\), satisfying \(\sum_b\lambda_b=1\) and \(\sum_b\lambda_b b=q\). Empty bundles are allowed; all supplies must be allocated.
Define \(\mathrm{CMMS}(q,v)=\sup_{\lambda\text{ feasible}}\min_{\lambda_b>0}v\cdot b\), \(V^+=\sum_{v_j>0}q_jv_j\), \(V^-=\sum_{v_j<0}q_j|v_j|\), and \(T=P\min\{V^+,V^-\}/\rho\).
Under the promise \(\mathrm{CMMS}\ge0\), return a feasible distribution with every supported bundle worth at least \((1-\epsilon)\mathrm{CMMS}\) when \(\mathrm{CMMS}\ge T\); otherwise report \(\mathrm{CMMS}<T\).
Does this bounded continuous MMS approximation problem admit a PTAS, with polynomial running time and output length in \(m,\tau,L\) for each fixed \(\rho,\epsilon\), where \(L\) is the total binary input length including \(P\), or is the stated guarantee NP-hard for some fixed \(\rho,\epsilon\)?
For identical additive agents with nonnegative MMS, the discrete bounded MMS problem has a PTAS with claimed running time \(O(mnL)\), using the threshold given by total goods or chores value divided by \(\rho\). [Discrete bounded MMS PTAS](https://cdn.aaai.org/ojs/16695/16695-13-20189-1-2-20210518.pdf).
No result settling this exact continuous formulation was identified in the literature search.
The stated guarantee is \(\mathrm{NP}\)-hard for the fixed constants \(\rho=1\) and \(\epsilon=\tfrac12\). Consequently, it admits no PTAS with the requested polynomial running time unless \(\mathrm{P}=\mathrm{NP}\).
I interpret “otherwise report \(\mathrm{CMMS}<T\)” as requiring that report whenever the optimum is below the threshold. The proof uses this exact reporting requirement. It applies to nondegenerate instances with \(\tau=1\), \(P=4\), positive threshold, integral valuations, and integral total supplies.
We reduce from PARTITION: given binary-encoded positive integers \(a_1,\ldots,a_n\), determine whether some subset sums to half their total. This problem is \(\mathrm{NP}\)-complete. [Karp, “Reducibility Among Combinatorial Problems”](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
We may assume that \(S=\sum_{i=1}^n a_i\) is even: doubling every input integer preserves the answer and ensures this condition.
Define
\(B=n+1,\qquad C=nS+1,\qquad D=\sum_{i=1}^n B^{i-1}.\)
For each index, introduce two positive integer weights:
\(w_i^0=C(B^n+B^{i-1}),\qquad w_i^1=C(B^n+B^{i-1})+a_i.\)
Define the integer target
\(H=C(nB^n+D)+S/2.\)
Encoding lemma. A nonnegative integer vector satisfying
\(\sum_{i=1}^n(w_i^0z_i^0+w_i^1z_i^1)=H\)
exists if and only if the PARTITION instance is a YES instance. Moreover, every such vector satisfies \(z_i^0+z_i^1=1\) for every index.
Proof. Let \(k=\sum_i(z_i^0+z_i^1)\). Every weight is at least \(CB^n\). Since \(D\le B^n-1\) and \(S/2<C\),
\(H=C(nB^n+D)+S/2<C(n+1)B^n.\)
Thus \(k\le n\). Consequently,
\(0\le\sum_i a_i z_i^1\le nS<C.\)
Reducing the weight equation modulo \(C\), with both remainders lying between zero and \(C-1\), gives
\(\sum_i a_i z_i^1=S/2.\)
Subtracting this equality and dividing by \(C\) gives
\(kB^n+\sum_i(z_i^0+z_i^1)B^{i-1}=nB^n+D.\)
Every coefficient on the left is at most \(n<B\), so this expression has no carries in base \(B\). Uniqueness of base-\(B\) expansion implies
\(k=n,\qquad z_i^0+z_i^1=1\quad\text{for every }i.\)
Therefore the indices with \(z_i^1=1\) form a partition.
Conversely, from a subset summing to \(S/2\), select weight \(w_i^1\) for indices in the subset and weight \(w_i^0\) for the other indices. Their sum is \(H\). This proves the lemma.
The lemma explicitly handles unbounded bundle multiplicities; no upper bounds on the coordinates were assumed.
Fix \(\rho=1\), \(\epsilon=\tfrac12\), and \(P=4\). Introduce \(m=d=2n+2\) item types:
| Item types | Per-capita supply | Value |
|---|---:|---:|
| Original type \((i,0)\) | \(1/2\) | \(w_i^0\) |
| Original type \((i,1)\) | \(1/2\) | \(w_i^1\) |
| Auxiliary good | \(1/4\) | \(H\) |
| Auxiliary chore | \(1/4\) | \(-H\) |
The society has one valuation type of mass \(1\), hence \(\tau=1\). All total supplies \(Pq\) are integers.
The original types have per-capita total value
\(\frac12\sum_i(w_i^0+w_i^1)=C(nB^n+D)+S/2=H.\)
The auxiliary types cancel in the average. Therefore,
\(v\cdot q=H,\qquad V^+=H+H/4=5H/4,\qquad V^-=H/4.\)
The threshold is exactly
\(T=P\min\{V^+,V^-\}/\rho=4(H/4)=H>0.\)
For every feasible distribution, its average bundle value is
\(\sum_b\lambda_b(v\cdot b)=v\cdot q=H.\)
Its minimum supported value is therefore at most \(H\), implying
\(\mathrm{CMMS}\le H.\)
The nonnegativity promise always holds. Indeed, assign mass \(1/4\) to the integer bundle \(4q\) and mass \(3/4\) to the empty bundle. This distribution is feasible, and its supported values are \(4H\) and zero. Hence
\(\mathrm{CMMS}\ge0.\)
Suppose the PARTITION instance has a solution. Let \(A\) be the bundle selecting the corresponding one of the two original types at every index. Let \(\overline A\) select the other type at every index.
Both bundles have value \(H\): the chosen subset and its complement each sum to \(S/2\).
Let \(e_+\) and \(e_-\) denote one copy of the auxiliary good and chore, respectively. Use the distribution
\(\lambda_A=1/2,\qquad \lambda_{\overline A}=1/4,\qquad \lambda_{\overline A+e_++e_-}=1/4.\)
Each original type has expected count \(1/2\), and each auxiliary type has expected count \(1/4\). Thus the distribution is feasible. All three supported bundles have value \(H\), because the auxiliary pair has net value zero.
Together with the average-value upper bound, this proves
\(\mathrm{CMMS}=H=T.\)
This attaining distribution has constant support size and constant-length rational masses.
Suppose the PARTITION instance is a NO instance. Assume, for contradiction, that a feasible distribution gives every supported bundle value at least \(H\).
Its average value is exactly \(H\). Since every supported mass is positive, every supported bundle must therefore have value exactly \(H\).
Write \(b_+\) and \(b_-\) for the counts of the auxiliary good and chore. Their expected counts are both \(1/4\). Because these counts are nonnegative integers,
\(\sum_{b:b_+>0}\lambda_b\le\sum_b\lambda_b b_+=1/4,\)
and likewise
\(\sum_{b:b_->0}\lambda_b\le1/4.\)
Thus the total mass of bundles containing either auxiliary type is at most \(1/2\). In particular, some supported bundle contains neither auxiliary type.
That bundle consists only of original types and has value \(H\). Its integer multiplicities consequently solve the equation in the encoding lemma, contradicting that PARTITION is a NO instance.
Therefore no feasible distribution has minimum supported value at least \(H\). All valuations are integers, so every supported bundle value, and hence every distribution’s minimum supported value, is an integer. It follows that every feasible distribution has minimum value at most \(H-1\). Taking the supremum gives
\(\mathrm{CMMS}\le H-1<T.\)
This integer bound also resolves the possible concern that the supremum could equal \(H\) without being attained.
The construction establishes
\(\text{PARTITION is YES}\quad\Longleftrightarrow\quad\mathrm{CMMS}\ge T.\)
It has polynomial binary encoding length. In particular, \(B^n\) has \(O(n\log(n+1))\) bits, and every constructed weight and \(H\) has
\(O(\log S+n\log(n+1))\)
bits. There are \(2n+2\) item types; \(P=4\) and \(\tau=1\) are constant.
An algorithm satisfying the stated guarantee must return an allocation on YES instances and report \(\mathrm{CMMS}<T\) on NO instances. Observing which output it returns decides PARTITION in polynomial time. The approximation factor does not affect this argument; hardness holds for every fixed \(\epsilon\) with \(0<\epsilon<1\).
The obstruction is mandatory exact threshold reporting. The proof does not establish hardness for a weaker specification that permits returning an approximate allocation below the threshold.
This distinction also matters for the [cited discrete bounded MMS statement](https://cdn.aaai.org/ojs/16695/16695-13-20189-1-2-20210518.pdf). Indeed, the same construction gives a discrete instance with four agents and total supplies \(4q\). A YES instance has the four bundles \(A,A,\overline A,\overline A+e_++e_-\), each worth \(H\). Conversely, a discrete allocation with minimum value at least \(H\) induces a feasible continuous distribution by assigning mass \(1/4\) to each agent’s bundle, so the NO-instance proof applies.
Consequently, exact threshold recognition is already \(\mathrm{NP}\)-hard in that discrete setting. An allocation approximation guarantee alone cannot justify mandatory exact reporting. Under the explicit reporting requirement in this task, the hardness conclusion is complete.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated task. The reduction is correct, respects the nonnegativity promise, and establishes hardness for the fixed constants \(\rho=1\) and \(\epsilon=\tfrac12\). I found no major or minor mathematical issues.
The conclusion depends on the task’s mandatory reporting requirement: below the threshold, the algorithm must report \(\mathrm{CMMS}<T\). The prover explicitly identifies this dependence.
The prover states the decision version of PARTITION precisely: positive binary-encoded integers, with a subset required to sum to half the total. Its NP-completeness is the standard result cited from [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Doubling all integers preserves the answer: a subset of the doubled integers sums to half their doubled total exactly when its original sum equals half the original total. This ensures that the subsequent target \(H\) is integral. The construction applies for every \(n\ge1\).
All weights are positive integers and at least \(CB^n\). The inequalities \(D\le B^n-1\) and \(S/2<C\) correctly imply
\[
H<C(n+1)B^n.
\]
Therefore a nonnegative integer solution to the weight equation has total multiplicity \(k<n+1\), hence \(k\le n\).
It follows that
\[
0\le\sum_i a_i z_i^1\le nS<C.
\]
This bound is valid even though the coordinates initially have no upper bounds.
Reduction modulo \(C\) is justified because both \(\sum_i a_i z_i^1\) and \(S/2\) lie in the interval from zero through \(C-1\). Their congruence therefore implies equality.
After subtraction and division by \(C\), every coefficient in
\[
kB^n+\sum_i(z_i^0+z_i^1)B^{i-1}=nB^n+D
\]
is a valid base-\(B\) digit: each is at most \(n<B=n+1\). The displayed representations have no carries. Uniqueness of positional representation therefore gives \(k=n\) and \(z_i^0+z_i^1=1\) for every index.
Thus every integer solution encodes a partition. The converse construction also satisfies the weight equation exactly. The lemma is fully proved.
The construction has \(m=d=2n+2\), one valuation type of mass one, rational nonnegative supplies, integral signed valuations, and positive population scale \(P=4\). Its total supplies are integral.
The original types contribute
\[
\frac12\sum_i(w_i^0+w_i^1)=H.
\]
The auxiliary types contribute equal and opposite average values. Consequently,
\[
v\cdot q=H,\qquad V^+=\frac{5H}{4},\qquad V^-=\frac H4,\qquad T=H>0.
\]
Every calculation is correct.
Because feasible distributions have finite support and mean bundle \(q\), their mean value is exactly \(v\cdot q=H\). Their minimum supported value is therefore at most \(H\), giving \(\mathrm{CMMS}\le H\).
The bundle \(4q\) is an admissible integer bundle. Assigning it mass \(1/4\), with mass \(3/4\) on the empty bundle, yields mean bundle \(q\) and supported values \(4H\) and zero. Both masses are positive binary rationals. Thus every constructed instance satisfies \(\mathrm{CMMS}\ge0\).
A partition and its complement each select one original type per index and have value \(H\). In the proposed distribution, \(A\) has total mass \(1/2\), while the two bundles containing \(\overline A\) have combined mass \(1/2\). Hence every original type has expected count \(1/2\).
Each auxiliary type occurs once in the bundle of mass \(1/4\), giving its required expected count. The auxiliary pair has zero net value, so every supported bundle is worth \(H\).
The masses sum to one and satisfy the specified representation requirements. Combined with the upper bound, this proves \(\mathrm{CMMS}=H=T\).
If every supported bundle were worth at least \(H\), positivity of the masses and mean value \(H\) would force every supported value to equal \(H\).
The mass of bundles containing an auxiliary good is at most its expected count \(1/4\), since any such bundle contains at least one copy. The same holds for the auxiliary chore. The union therefore has mass at most \(1/2\).
At least half the distribution’s mass lies on bundles containing neither auxiliary type. Since the support is finite, some supported bundle has this property. Its original-item multiplicities solve the encoding equation at value \(H\), contradicting the NO assumption. No unsupported independence assumption is used.
All bundle values are integers because both valuations and bundle coordinates are integral. Each feasible distribution therefore has an integer minimum supported value.
Having excluded minimum values at least \(H\), the proof correctly concludes that every feasible minimum is at most \(H-1\). This uniform bound survives taking the supremum:
\[
\mathrm{CMMS}\le H-1<T.
\]
Thus the argument does not assume that the supremum is attained.
The bit length of \(B^n\) is \(O(n\log(n+1))\). The stated bit bounds for the weights and \(H\) are valid, and the construction uses polynomially many arithmetic operations on polynomial-length integers.
All reduced instances satisfy the promise. On YES instances the specification requires an allocation; on NO instances it requires the threshold report. These output forms distinguish PARTITION answers without computing the optimum or inspecting the allocation’s approximation quality.
A polynomial-time algorithm for the requested guarantee would therefore decide PARTITION in polynomial time. Fixing \(\epsilon=\tfrac12\) suffices to exclude the requested PTAS unless \(\mathrm P=\mathrm{NP}\).
The four discrete bundles stated in the proof allocate exactly the total supplies \(4q\). Conversely, a four-agent discrete allocation induces a feasible continuous distribution with rational masses by merging any repeated bundles. The discrete threshold-recognition consequence is therefore valid.
The [cited paper](https://cdn.aaai.org/ojs/16695/16695-13-20189-1-2-20210518.pdf) does explicitly include below-threshold reporting in its informal Theorem 1.1. The prover’s reduction establishes that enforcing this as mandatory exact recognition is NP-hard; it does not establish hardness for the weaker approximation-only specification. This distinction is accurately stated, and the continuous hardness proof does not depend on accepting the paper’s reporting claim.
No additional clarification or mathematical 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.