Answer: Exactly solvable in polynomial time; the requested approximation holds with \(c=1\).
Theorem 3. — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen all agents have piecewise constant den- sity functions, it is NP-hard to approximate the optimum ef- ficiency within a ratio of Ω 1 √n , even if all functions have at most 2 segments.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), and for each type a rational piecewise-constant density \(f_t\) with at most two positive segments, let \(F_t=\int_0^1 f_t(x)\,dx\). Choose measurable shares \(q_t(x)\in[0,1]\) with \(\sum_{t\in T}q_t(x)=1\) almost everywhere, and set \(W_t=\int_0^1q_t(x)f_t(x)\,dx\). Compute a welfare-maximizing allocation subject to \(W_t\geq\mu_tF_t\) for every type, with the type mass apportioned among its cake intervals so each infinitesimal resident receives one connected slice and at least \(F_t\) value per unit mass.
A society is given by its support: a list of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. Each type has a nonnegative density \(f_t\) on \([0,1]\), specified by at most two positive constant segments with rational endpoints and heights, and zero elsewhere; \(F_t=\int_0^1 f_t(x)\,dx>0\). Valuations need not be normalized.
An allocation partitions the entire cake, up to endpoints, into finitely many connected intervals \(I_j\), each labelled by a type \(t_j\) and assigned positive mass \(w_j\), with \(\sum_{j:t_j=t}w_j=\mu_t\). Types may label several intervals; there is no prescribed order or bound on the number of intervals.
The atomless connected-slice convention is that mass within \(I_j\) is ordered by cumulative \(f_{t_j}\)-value: every consecutive subpopulation of mass \(\delta\) receives one connected subinterval worth \(\delta v_j/w_j\), where \(v_j=\int_{I_j}f_{t_j}(x)\,dx\). Require \(v_j\geq w_jF_{t_j}\) for every interval. Zero-value stretches may be attached to adjacent slices.
Set \(q_t=\mathbf{1}_{\bigcup_{j:t_j=t}I_j}\), \(W_t=\int_0^1q_t(x)f_t(x)\,dx\), and maximize welfare \(\sum_tW_t\); in particular, \(W_t\geq\mu_tF_t\). Let \(\mathrm{OPT}\) be the supremum welfare over these feasible allocations.
Let \(m\) count the intervals in the common refinement of all density breakpoints, \(L\) be the total input bit length, and \(N=1/\min_t\mu_t\). State running times in \(m,\tau,L\), with any dependence on \(N\) explicit.
Does this continuous problem admit a polynomial-time approximation with welfare at least \(c\,\mathrm{OPT}/\sqrt{N}\), for some universal constant \(c>0\), while preserving all fairness and connected-slice requirements, or is obtaining such a guarantee NP-hard?
For finite societies of \(n\) agents, proportional welfare maximization with one connected piece per agent has reported \(\Omega(n^{-1/2})\) approximation hardness even with at most two positive segments per density ([Bei et al.](https://ojs.aaai.org/index.php/AAAI/article/view/8243/8102)).
Without connected-piece restrictions, optimal envy-free welfare for finite piecewise-constant societies is computable in polynomial time ([Cohler et al.](https://econcs.seas.harvard.edu/sites/g/files/omnuum6346/files/econcs/files/cohler_aaai11.pdf)); this concerns a different feasibility condition. No result settling the specified atomless problem was identified.
The specified problem is exactly solvable in polynomial time. Consequently, the requested approximation holds with the universal constant \(c=1\).
The proof uses the stated freedom to repeat type labels and choose arbitrary positive interval masses. It constructs an optimal allocation with at most \(m\tau\) intervals, preserves every fairness requirement, and verifies the connected-slice convention.
Let the common refinement have endpoints \(0=a_0<a_1<\cdots<a_m=1\). Write \(C_k=(a_{k-1},a_k)\), \(\ell_k=a_k-a_{k-1}\), and let \(d_{tk}\) be the constant value of \(f_t\) on \(C_k\). Endpoint values do not affect any integral. Thus
\(F_t=\sum_{k=1}^m d_{tk}\ell_k\).
Introduce a variable \(x_{tk}\) representing the length of cell \(C_k\) assigned to type \(t\). Consider the linear program
\(\displaystyle \operatorname{maximize}\quad \sum_{t=1}^{\tau}\sum_{k=1}^{m}d_{tk}x_{tk}\),
subject to
\(\displaystyle \sum_{t=1}^{\tau}x_{tk}=\ell_k\quad\text{for every }k,\)
\(\displaystyle \sum_{k=1}^{m}d_{tk}x_{tk}\geq\mu_tF_t\quad\text{for every }t,\)
\(x_{tk}\geq0\quad\text{for every }t,k.\)
Denote its optimal value by \(P\).
Feasibility and attainment. Setting \(x_{tk}=\mu_t\ell_k\) satisfies the cell constraints because \(\sum_t\mu_t=1\), and gives
\(\displaystyle \sum_kd_{tk}x_{tk}=\mu_tF_t.\)
The feasible region is closed and bounded: its constraints imply \(0\leq x_{tk}\leq\ell_k\). Therefore the linear objective attains its maximum.
Upper bound on allocation welfare. Given any feasible allocation, define
\(\displaystyle x_{tk}=\sum_{j:t_j=t}|I_j\cap C_k|.\)
Because the intervals partition the cake up to endpoints, the cell constraints hold. Moreover,
\(\displaystyle \sum_kd_{tk}x_{tk}=W_t =\sum_{j:t_j=t}v_j \geq F_t\sum_{j:t_j=t}w_j =\mu_tF_t.\)
Its welfare therefore equals the objective of a feasible LP solution. Taking the supremum over allocations proves
\(\mathrm{OPT}\leq P.\)
Let \(x^*\) be an optimal LP solution.
Call a cell *active* if at least one type has positive density there. We first prove that an active cell assigns no positive length to a type whose density there is zero.
Suppose otherwise that \(x^*_{tk}>0\), \(d_{tk}=0\), and \(d_{sk}>0\) for some type \(s\). Transfer the entire amount \(x^*_{tk}\) from variable \(x^*_{tk}\) to \(x^*_{sk}\). The cell constraint remains satisfied. Type \(t\)'s value does not decrease, because its density in that cell is zero; type \(s\)'s value increases. All fairness constraints remain satisfied, while welfare increases by
\(d_{sk}x^*_{tk}>0.\)
This contradicts optimality. Hence
\(x^*_{tk}>0\text{ in an active cell implies }d_{tk}>0.\)
In each active cell, list the types with \(x^*_{tk}>0\) in any fixed order and partition the cell into consecutive intervals of these lengths. Label each interval by its corresponding type. Every resulting interval has strictly positive value for its label.
The remaining cells have zero density for every type. Attach each maximal run of such cells to an adjacent constructed interval. For an initial or terminal run, use the first or last constructed interval; for an internal run, use the interval immediately to its left. At least one constructed interval exists because every \(F_t\) is positive.
These attachments preserve connectedness and change no type's value. We have obtained a partition of the entire cake into at most \(m\tau\) intervals, each having positive value for its label, with
\(\displaystyle W_t=\sum_kd_{tk}x^*_{tk}\geq\mu_tF_t>0.\)
In particular, every supported type labels at least one interval.
For each constructed interval \(I_j\), let \(t=t_j\) and \(v_j=\int_{I_j}f_t(x)\,dx>0\). Assign it mass
\(\displaystyle w_j=\mu_t\frac{v_j}{W_t}.\)
These masses are strictly positive, and for every type,
\(\displaystyle \sum_{j:t_j=t}w_j =\frac{\mu_t}{W_t}\sum_{j:t_j=t}v_j =\mu_t.\)
Furthermore,
\(\displaystyle \frac{v_j}{w_j}=\frac{W_t}{\mu_t}\geq F_t,\)
so \(v_j\geq w_jF_t\) holds on every interval.
We now verify the connected-slice convention, including zero-value stretches. Fix an interval \(I_j=[a,b]\), with mass \(w=w_j\), value \(v=v_j>0\), and label \(t\). Define
\(\displaystyle H(x)=\int_a^x f_t(z)\,dz.\)
The function \(H\) is continuous and nondecreasing, with \(H(a)=0\) and \(H(b)=v\). For \(0<u<w\), define the cut
\(\displaystyle c(u)=\min\{x\in[a,b]:H(x)\geq uv/w\},\)
and set \(c(0)=a\), \(c(w)=b\).
Continuity gives \(H(c(u))=uv/w\), including the two endpoint cases. The map \(c\) is nondecreasing. Thus a consecutive subpopulation indexed by \(u_1<u_2\) receives the connected subinterval between \(c(u_1)\) and \(c(u_2)\), whose value is exactly
\(\displaystyle H(c(u_2))-H(c(u_1)) =(u_2-u_1)\frac{v}{w}.\)
For any finite subdivision of the population, these intervals partition \(I_j\) up to endpoints. Flat portions of \(H\) are attached to adjacent slices through the same cut convention. This verifies precisely the required atomless connected-slice rule.
The constructed allocation consequently is feasible and has welfare \(P\). Together with the upper bound,
\(\mathrm{OPT}=P.\)
In particular, the supremum is attained.
The LP has \(m\tau\) variables, \(m\) cell equalities, and \(\tau\) fairness inequalities, besides nonnegativity constraints.
All coefficients are rational. Under the specified two-segment representation, each \(d_{tk}\), \(\ell_k\), and \(\mu_tF_t\) has bit length \(O(L)\). A dense encoding of this LP therefore has length
\(B=O\!\left(m\tau(m+\tau+L)\right).\)
We use the standard theorem that a rational LP can be solved exactly in time polynomial in its binary encoding length, with a rational optimal solution of polynomial encoding length. Exact polynomial-time rational LP algorithms and rational recovery are discussed in [Gleixner and Steffy, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf). Its hypotheses hold here: the data are rational, and the feasible region is nonempty and bounded.
Constructing the refinement, solving the LP, forming the interval endpoints, and computing the masses therefore take
\(\operatorname{poly}(m,\tau,L)\)
bit operations. The output has at most \(m\tau\) intervals and polynomial total encoding length. The slice rule above specifies the internal atomless allocation without enumerating subpopulations.
There is no numerical dependence on \(N\); small masses matter only through their input bit lengths. The two-segment restriction also implies \(m\leq4\tau+1\), although the proof extends to arbitrary finitely represented rational piecewise-constant densities.
Finally, \(N\geq1\), so the exact solution satisfies
\(\displaystyle \text{welfare}=\mathrm{OPT}\geq\frac{\mathrm{OPT}}{\sqrt N}.\)
The finite-agent problem studied by [Bei et al.](https://ojs.aaai.org/index.php/AAAI/article/view/8243/8102) requires each agent to receive one connected piece. Its hardness construction explicitly uses that restriction to limit an agent to one of several separated available regions.
Here, a type may label several intervals, and its mass can be divided among them. The formula \(w_j=\mu_{t_j}v_j/W_{t_j}\) makes every such interval fair while preserving connected slices within it. This permitted division is the reason the LP realization works; substituting \(N\) for the finite agent count does not preserve the finite problem's restriction.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed exact polynomial-time solvability of the specified continuous problem. The LP upper bound, its realization by connected intervals, the assignment of positive masses, and the connected-slice verification are all valid. No major or minor mathematical issues were found.
The result depends on permissions explicitly present in USER_TASK: a type may label multiple intervals, and each interval’s mass may be chosen freely subject to the type’s total mass constraint.
The common refinement makes every density constant on each open cell. Endpoint values do not affect lengths or integrals, so
\(F_t=\sum_k d_{tk}\ell_k\)
is correct.
The variables \(x_{tk}\) encode assigned lengths within cells. Nonnegativity and the cell equalities ensure that the entire length of each cell is assigned. The fairness inequalities impose exactly the necessary aggregate conditions \(W_t\geq\mu_tF_t\).
The proposed feasible point \(x_{tk}=\mu_t\ell_k\) satisfies both sets of constraints. Each variable lies in \([0,\ell_k]\), so the feasible region is nonempty and compact. The objective therefore attains a finite maximum \(P\).
Assessment: Correct. At this stage the LP is a relaxation; the output appropriately proves realizability separately.
For any allocation allowed by the task, the lengths
\(x_{tk}=\sum_{j:t_j=t}|I_j\cap C_k|\)
satisfy the cell equalities because the allocation partitions the cake up to endpoints.
Constancy of the densities within cells gives
\(\sum_k d_{tk}x_{tk}=W_t=\sum_{j:t_j=t}v_j\).
Summing the interval fairness inequalities for a fixed type yields
\(W_t\geq F_t\sum_{j:t_j=t}w_j=\mu_tF_t\).
Thus every feasible allocation produces a feasible LP point with identical welfare. Taking the supremum gives \(\mathrm{OPT}\leq P\), even before attainment of the allocation optimum is established.
Assessment: Correct, including the treatment of the supremum.
The exchange argument is valid. If an active cell assigns positive length to a type with zero density there, transferring that length to a type with positive density:
There are no upper bounds on type values or assigned lengths across different cells that would invalidate this transfer. Consequently, every positive-length assignment in an active cell has positive value for its label.
Assessment: Correct. This step ensures that the later mass assignment never creates zero-mass intervals.
Within an active cell, the positive assigned lengths sum to the cell length. Consecutive intervals of these lengths therefore realize the LP assignments exactly. Their labelled values are strictly positive.
An inactive cell has zero density for every type. Attaching a maximal run of inactive cells to a neighboring constructed interval changes no valuation and preserves connectedness. The initial, terminal, and internal cases are all specified.
At least one active cell exists because every supported type has positive total value. The construction consequently covers the entire cake up to endpoints.
There are at most \(\tau\) constructed intervals per active cell. Attaching inactive cells creates no additional intervals, so the bound of \(m\tau\) holds. Finally, \(W_t\geq\mu_tF_t>0\) ensures that every supported type labels at least one interval.
Assessment: Correct. Repeated labels are permitted by the task, so separate intervals of the same type need not be merged.
For each constructed interval,
\(w_j=\mu_{t_j}v_j/W_{t_j}\)
is well-defined and strictly positive.
Summing over intervals of a fixed type gives exactly its prescribed mass. Moreover,
\(v_j/w_j=W_t/\mu_t\geq F_t\),
which proves the required fairness inequality on every interval individually.
No normalization of valuations is used. The argument remains valid for arbitrary positive \(F_t\).
Assessment: Correct. The output explicitly closes the gap between aggregate LP fairness and interval-level fairness.
The cumulative-value function \(H\) is continuous and nondecreasing because the density is integrable and nonnegative.
For every interior population index \(u\), the defining set for \(c(u)\) is nonempty and compact, so its minimum exists. Continuity gives \(H(c(u))=uv/w\). The separately defined endpoint cuts satisfy the same identity.
The cuts are nondecreasing. Hence any consecutive subpopulation indexed by \(u_1<u_2\) receives a connected interval of value
\((u_2-u_1)v/w\), exactly as required.
Flat portions of \(H\) can make the cut map discontinuous, but the task does not require continuity of that map. Such portions have zero value and are included in adjacent slices by the specified convention. For every finite subdivision, the consecutive cut intervals cover the parent interval up to endpoints.
Assessment: Correct, including leading, trailing, and internal zero-value stretches.
The constructed allocation is feasible and has welfare \(P\). Together with \(\mathrm{OPT}\leq P\), this proves \(\mathrm{OPT}=P\).
Because an actual finite allocation achieves \(P\), the assertion that the supremum is attained is also justified.
Assessment: Correct.
The LP dimensions are stated correctly.
Under the two-segment representation, cell densities and lengths have bit length \(O(L)\). Each \(F_t\) can be computed from the type’s at most two segments, so \(\mu_tF_t\) also has bit length \(O(L)\).
The dense encoding bound
\(B=O(m\tau(m+\tau+L))\)
is valid: the constraint matrix has \(O(m\tau(m+\tau))\) entries, but only \(O(m\tau)\) potentially nonzero entries requiring \(O(L)\) bits each. The remaining entries are constant-size zeros.
The exact rational LP theorem is stated sufficiently precisely for this application. Its rational-data, feasibility, and finite-optimum hypotheses have been verified. The cited discussion does support exact polynomial-time solution and rational recovery. [Gleixner and Steffy, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
Using a polynomial-encoding rational optimal solution, the endpoint sums, interval values, and assigned masses also have polynomial total encoding length. The bound \(m\leq4\tau+1\) follows from at most four segment endpoints per type, together with the cake boundaries.
The running time is polynomial in \(m,\tau,L\). There is no additional numerical dependence on \(N\); mass sizes enter through their binary encodings.
Assessment: Correct.
Since positive masses sum to one, \(N\geq1\). Exact optimal welfare therefore satisfies the requested guarantee with \(c=1\).
The distinction from finite-agent connected-piece hardness is accurate. The cited finite problem gives each agent one connected interval, and its construction uses this restriction to limit an agent to one of several remaining regions. [Bei et al.](https://ojs.aaai.org/index.php/AAAI/article/view/8243/8102).
The atomless task instead permits repeated type labels and freely chosen positive interval masses. The output’s realization uses precisely those permissions. Accordingly, the finite-agent hardness does not contradict the established algorithm.
Assessment: Correct.
None. The output settles the target and preserves all stipulated fairness and connected-slice requirements.
⟨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.