Answer: Achieving some fixed multiplicative approximation factor \(c>1\) is \(\mathrm{NP}\)-hard; no PTAS exists unless \(\mathrm{P}=\mathrm{NP}\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a cake-division instance with piecewise-constant valuations, the problem of computing an allocation that maximizes Nash social welfare is $\APX$-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete piecewise-constant valuation types on \([0,1]\), rational masses \(\mu_t>0\) with \(\sum_t\mu_t=1\), and type-dependent densities \(\nu_t\), choose a permutation \(\pi\) and cuts \(0=x_0\leq\cdots\leq x_{|T|}=1\), assigning \(I_{\pi(j)}=[x_{j-1},x_j]\), to maximize \(\operatorname{NSW}_{\infty}=\prod_{t\in T}\left(v_t(I_t)/\mu_t\right)^{\mu_t}\), where each type block can be subdivided among its mass into contiguous individual pieces.
A society is given by its support: a nonempty list \(T\) of \(\tau\) distinct valuation types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly specified nonnegative piecewise-constant density \(\nu_t\) on \([0,1]\), with binary-rational breakpoints and heights, normalized by \(\int_0^1\nu_t(x)\,dx=1\); set \(v_t(I)=\int_I\nu_t(x)\,dx\). Let \(m\) count the elementary intervals in the common breakpoint refinement and \(L\) be the total input bit length.
A feasible allocation chooses a permutation \(\pi\) of \(T\) and real cuts \(0=x_0\leq\cdots\leq x_\tau=1\), assigning the single block \(I_{\pi(j)}=[x_{j-1},x_j]\) to type \(\pi(j)\). Shared endpoints have zero value; the entire cake is allocated.
Define per-unit-mass utility as \(u_t=v_t(I_t)/\mu_t\) and maximize \(\operatorname{NSW}_{\infty}=\prod_{t\in T}u_t^{\mu_t}\), with value zero if any \(u_t=0\). Within-type subdivision means that every finite replication can divide each block into contiguous pieces of equal value for its identical members; it imposes no further constraint on blocks.
Does maximizing \(\operatorname{NSW}_{\infty}\) admit a PTAS, or is achieving some fixed multiplicative approximation factor \(c>1\) NP-hard?
State running times in \(m,\tau,L\) and the approximation parameter \(\varepsilon\).
For finitely many equal-entitlement agents with normalized piecewise-constant valuations and one interval each, NSW maximization is APX-hard and admits a polynomial-time \((3+o(1))\)-approximation. [Source](https://arxiv.org/pdf/1907.11019)
No result settling this precise mass-weighted, single-block-per-type problem was identified in the literature search.
Achieving some fixed multiplicative approximation factor \(c>1\) is \(\mathrm{NP}\)-hard. Consequently, the problem has no PTAS unless \(\mathrm{P}=\mathrm{NP}\).
The hardness holds even when all masses equal \(1/\tau\), all valuation types are distinct, and all breakpoints, heights, and masses are dyadic rationals. Thus it holds under either usual interpretation of “binary-rational.”
The proof transfers the cited hardness result, with two explicit modifications: rounding valuation data to dyadic rationals and padding the number of types to a power of two.
Write \(r\) for the number of variables and \(s\) for the number of clauses in the source construction, avoiding confusion with the task’s \(m\).
We use the following established properties of the hard instances in Theorem 8 and Section 5.1 of [Arunachaleswaran–Barman–Kumar–Rathi](https://arxiv.org/pdf/1907.11019):
These statements provide the source gap theorem. The remaining steps below establish its transfer to the precise problem asked here.
In particular, the source valuations are already distinct: each nonauxiliary agent has a private positive cell, while the auxiliary agent has no positive value outside \(G\).
Choose a constant integer \(b\) sufficiently large that, putting \(\eta=12\cdot 2^{-b}\), we have
\(\displaystyle 0<\eta<1,\qquad \kappa:=q\frac{1+\eta}{1-\eta}<1.\)
Such a choice exists because \(q<1\). Both \(b\) and \(\eta\) are constants independent of the input.
For an agent \(a\), let \(p_{a,j}\) be its value for cell \(j\). Its positive cell values sum to one. Choose one positive cell as distinguished. Round every other positive cell value downward to a multiple of \(2^{-b}\), leave every zero value zero, and assign the distinguished cell the remaining value needed to make the sum exactly one. Denote the resulting cell values by \(\widehat p_{a,j}\).
There are at most four positive cells. Therefore, on a nondistinguished positive cell the rounding error is less than \(2^{-b}\); on the distinguished cell it is less than \(3\cdot 2^{-b}\). Every original positive cell value is at least \(1/4\). Consequently,
\(\displaystyle (1-\eta)p_{a,j}\leq \widehat p_{a,j}\leq(1+\eta)p_{a,j}\)
for every cell, including zero cells.
Thus every rounded positive value remains positive, every zero remains zero, and every rounded valuation is normalized. All rounded cell values are dyadic.
Let \(\widehat v_a\) denote the valuation obtained by using these rounded values as constant densities on the original unit cells. The cellwise inequalities imply, by integration, that for every interval \(I\),
\(\displaystyle (1-\eta)v_a(I)\leq\widehat v_a(I)\leq(1+\eta)v_a(I).\)
Multiplying over the agents gives the same inequalities for every feasible allocation:
\(\displaystyle (1-\eta)^n\prod_a v_a(I_a)\leq\prod_a\widehat v_a(I_a)\leq(1+\eta)^n\prod_a v_a(I_a).\)
Taking maxima is valid because the allocation spaces are identical. Hence the rounded optimum \(\widehat P^*\) satisfies
\(\displaystyle \text{YES: }\widehat P^*\geq(1-\eta)^nA_\varphi,\qquad \text{NO: }\widehat P^*\leq(1+\eta)^nq^nA_\varphi.\)
Since rounding preserves all zero supports, it also preserves the distinctness argument from Section 1.
Let \(N\) be the smallest power of two satisfying \(N\geq n\). Then
\(\displaystyle n\leq N<2n.\)
Add \(N-n\) dummy agents. Each dummy values only its own new unit cell, placed after the original \(B\) cells, and has constant density one there.
Choose a power of two \(Q\geq B+N-n\). Map every unit cell to a cell of length \(1/Q\) in \([0,1]\). On mapped cell \(j\), original agent \(a\) receives density \(Q\widehat p_{a,j}\); a dummy receives density \(Q\) on its private cell. All densities are zero elsewhere, including any remaining suffix of the cake.
These densities integrate to one. Their breakpoints and heights are dyadic. Give every type mass
\(\displaystyle \mu_t=\frac1N.\)
The masses are positive dyadic rationals and sum to one. Original types remain distinct, and the dummy types are distinct from one another and from every original type. The support size is therefore exactly \(\tau=N\).
Let \(P_{\mathrm{pad}}^*\) be the maximum product of the \(N\) block values in the padded instance. We claim that
\(\displaystyle P_{\mathrm{pad}}^*=\widehat P^*.\)
For the lower bound, take an optimal rounded allocation on the original prefix and give each dummy its entire private cell. Any unused suffix can be attached to the rightmost block. This is a feasible full allocation, and every dummy obtains value one. Therefore \(P_{\mathrm{pad}}^*\geq\widehat P^*\).
For the upper bound, consider any padded allocation. Each dummy obtains value at most one. If an original agent obtains value zero, the full product is zero and the desired inequality is immediate.
Otherwise, intersect each original agent’s block with the original prefix. These intersections are nonempty, ordered, pairwise interior-disjoint intervals, and they preserve all original agents’ values. They can be extended to a partition of the prefix: between successive intersections choose a cut in the intervening gap, and use the prefix endpoints for the outer cuts. Nonnegative densities ensure that extension does not decrease any value.
The resulting original-agent product is at most \(\widehat P^*\). Since the dummy factors are at most one, the padded product is also at most \(\widehat P^*\). This proves the claim.
For the padded instance, all masses equal \(1/N\). Thus, for every allocation,
\(\displaystyle \operatorname{NSW}_{\infty} =\prod_{t=1}^{N}\bigl(Nv_t(I_t)\bigr)^{1/N} =N\left(\prod_{t=1}^{N}v_t(I_t)\right)^{1/N}.\)
The factor \(N\) is independent of the allocation. This identity uses exactly one block per distinct type, as required by the task.
Define
\(\displaystyle Y_\varphi =N\left((1-\eta)^nA_\varphi\right)^{1/N}.\)
Sections 2 and 3 imply that in the YES case,
\(\displaystyle \operatorname{OPT}_{\infty}\geq Y_\varphi.\)
In the NO case,
\(\displaystyle \operatorname{OPT}_{\infty} \leq N\left((1+\eta)^nq^nA_\varphi\right)^{1/N} =Y_\varphi\kappa^{n/N} \leq Y_\varphi\sqrt{\kappa}.\)
The last inequality follows from \(n/N>1/2\) and \(0<\kappa<1\).
Choose a fixed rational constant \(c\) satisfying
\(\displaystyle 1<c<\kappa^{-1/2}.\)
Suppose a polynomial-time \(c\)-approximation algorithm existed, with the maximization convention that its output value is at least \(\operatorname{OPT}_{\infty}/c\).
In a YES instance its output would exceed \(Y_\varphi\sqrt{\kappa}\), because \(1/c>\sqrt{\kappa}\). In a NO instance every feasible output has value at most \(Y_\varphi\sqrt{\kappa}\). Hence the algorithm would distinguish the source promise cases.
The comparison can be made in the binary bit model without evaluating irrational roots. Choose a fixed rational \(d\) with
\(\displaystyle \sqrt{\kappa}<d<1/c.\)
For an output allocation with product \(P_{\mathrm{out}}\), its society value exceeds \(dY_\varphi\) exactly when
\(\displaystyle P_{\mathrm{out}}>d^N(1-\eta)^n2^{-r}3^{-s}.\)
The right-hand side is rational with polynomial bit length. Rational output cuts allow the left-hand side to be evaluated and compared in polynomial time.
Therefore achieving this fixed factor \(c>1\) is \(\mathrm{NP}\)-hard.
Within-type subdivision does not alter the reduction: each constructed valuation is nonatomic, so its cumulative value on a block is continuous. The intermediate value theorem supplies cuts dividing that block into any prescribed finite number of equal-value contiguous pieces.
The reduction produces
\(\displaystyle \tau=N=O(s),\qquad m=O(s)=O(\tau),\qquad L=O\bigl(\tau\log(\tau+2)\bigr).\)
Indeed, each type has only constantly many positive cells; specifying its positive regions and intervening zero regions requires constantly many breakpoints. The rounding precision is constant, while coordinates, heights, and masses require \(O(\log(\tau+2))\) bits. The reduction runs in time polynomial in the source input length.
Consequently, unless \(\mathrm{P}=\mathrm{NP}\), there is no algorithm achieving the fixed factor \(c\) in time \(\operatorname{poly}(m,\tau,L)\), even on this restricted family.
For the approximation convention \(1+\varepsilon\), fix \(\varepsilon_0=c-1>0\). A PTAS would run in polynomial time in \(m,\tau,L\) at this fixed parameter and achieve factor \(c\), contradicting the hardness result. This excludes a PTAS, including running times of the form \((m+\tau+L)^{f(1/\varepsilon)}\).
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and resolves the hardness alternative, subject to two minor clarifications about the computational model and the choice of scaling parameter. No false mathematical step or gap requiring new mathematics was found.
The appropriate classification is proved_with_minor_gaps.
The source theorem is applicable to allocations consisting of one connected interval per agent, with the entire cake allocated. Its construction uses normalized piecewise-constant valuations.
I checked the specific properties invoked in Section 1:
Thus the prover has stated a sufficiently precise source gap theorem, and the construction satisfies its stated hypotheses. Using this established theorem does not require reproving its internal structural claims.
The distinctness inference is correct: a private positive cell distinguishes its owner from every other agent, and the auxiliary agent is distinguished by having no positive value outside \(G\).
The rounding calculation is correct.
For each nondistinguished positive cell, the error is strictly less than \(2^{-b}\). Since there are at most three such cells, the distinguished cell receives a total increment strictly less than \(3\cdot 2^{-b}\).
Every positive original cell value is at least \(1/4\), so the largest possible relative error is strictly less than
\[
12\cdot 2^{-b}=\eta.
\]
Consequently, the displayed multiplicative inequalities hold for every cell. Zero cells remain zero, and positive cells remain positive because \(\eta<1\).
Normalization is preserved exactly: the distinguished value is the residual needed to make the sum one. That residual is dyadic because all other rounded values and the total one are dyadic.
Integration preserves the inequalities because they hold pointwise for the constant densities. Multiplying the nonnegative inequalities over agents is valid, including allocations with a zero factor. Taking maxima over the same feasible allocation space gives the stated YES and NO bounds.
The choice of constant precision is also justified: as \(\eta\) tends to zero, \(\kappa=q(1+\eta)/(1-\eta)\) tends to \(q<1\).
No issue found in this section.
The power-of-two padding satisfies \(n\leq N<2n\), including the case where \(n\) is already a power of two.
The rescaling preserves each original cell value: multiplying the density by \(Q\) and dividing the cell length by \(Q\) leaves its integral unchanged. Dummy valuations are normalized and have disjoint private supports. All constructed types remain distinct.
Both directions of the product-preservation argument are valid:
The zero-original-value case is handled explicitly and correctly. Hence \(P_{\mathrm{pad}}^*=\widehat P^*\).
Minor issue: the magnitude of \(Q\) is not specified.
The instruction “Choose a power of two \(Q\geq B+N-n\)” establishes valid densities, but this inequality alone does not establish the subsequently claimed bit-length bound: arbitrarily large powers of two also satisfy it.
Minimum clarification: specify that \(Q\) is the smallest qualifying power of two, or explicitly impose a polynomial magnitude bound sufficient for the stated encoding size.
For equal masses, the identity
\[
\operatorname{NSW}_{\infty}
=N\left(\prod_{t=1}^{N}v_t(I_t)\right)^{1/N}
\]
is exact, including the zero-product convention. It uses one block per distinct type and therefore matches the task.
The NO-case comparison is correct:
\[
\operatorname{OPT}_{\infty}
\leq Y_\varphi\kappa^{n/N}
\leq Y_\varphi\sqrt{\kappa}.
\]
The inequality direction is correct because \(0<\kappa<1\) and \(n/N>1/2\).
The interval \(1<c<\kappa^{-1/2}\) is nonempty. With this choice, a feasible \(c\)-approximation separates the promise cases strictly. The additional rational threshold \(d\), satisfying \(\sqrt{\kappa}<d<1/c\), also exists.
Raising the comparison to the \(N\)-th power yields exactly
\[
P_{\mathrm{out}}>d^N(1-\eta)^n2^{-r}3^{-s}.
\]
The threshold is rational and has polynomial bit length because \(d\) and \(\eta\) are fixed rational constants.
Minor issue: the output representation assumption needs to be explicit.
The statement “Rational output cuts allow the left-hand side to be evaluated and compared in polynomial time” is correct. However, the preceding hypothetical algorithm is not expressly required to output rational cuts.
Under the usual binary model with explicitly encoded rational cuts, polynomial running time bounds the output length, and the stated exact comparison is valid. The task specifies real feasible cuts but does not specify their algorithmic output encoding.
Minimum clarification: state that the hardness claim uses this standard rational-cut output convention. If another representation of real cuts is intended, identify it and justify the comparison for that representation.
The subdivision observation is correct. Piecewise-constant densities induce continuous cumulative-value functions on every block, so the intermediate value theorem applies to the required equal-value divisions. Zero-value blocks cause no difficulty.
Each type has constantly many positive regions and therefore admits an explicit description with constantly many intervening zero regions. With the bounded choice of \(Q\) requested above, the coordinate, height, and mass encodings have the stated logarithmic size.
The bounds \(\tau=O(s)\), \(m=O(s)=O(\tau)\), and \(L=O(\tau\log(\tau+2))\) are consequently valid for the intended compact descriptions.
Finally, fixing \(\varepsilon_0=c-1\) correctly excludes a PTAS: its running time would be polynomial in \(m,\tau,L\) at that fixed parameter. The prover need not provide an approximation algorithm after establishing the requested hardness alternative.
⟨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.