Answer: Polynomial-time solvable in the stated exact oracle model, and in polynomial bit time for explicitly given positive rational piecewise-constant densities.
Theorem 4.8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe cake-cutting protocol in Figure~\ref{algo:n} is finite bounded.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(N\) agents summarized by \(\tau\) complete additive valuation types with rational masses \(\mu_t=n_t/N\), and cut/evaluation oracles for those types, can one produce a type-mass representation of a disjoint cake division that realizes finite assignments giving every type-\(t\) agent a bundle with \(v_t(B)\ge 1/N\), using \(\mathrm{poly}(\tau,L,\log N)\) valuation queries?
A society is given by its support: the list of the \(\tau\) valuation types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Also given is a binary integer \(N\geq3\), with \(n_t=N\mu_t\in\mathbb{Z}_{>0}\). Let \(L\) be the total bit length of these numerical inputs.
The cake is \([0,1]\). Each type has a normalized, nonatomic additive value measure \(v_t\), strictly positive on every interval of positive length, accessible through exact Robertson–Webb cut and evaluation oracles. Portions may be finite unions of intervals; shared endpoints have zero value and are assigned arbitrarily.
A type-mass representation lists a partition \((A_t)_{t=1}^{\tau}\) of the entire cake into type portions. It realizes finite proportional assignments if each \(A_t\) admits a partition into \(n_t\) nonempty bundles \(B_{t,j}\), each a finite union of intervals, satisfying \(v_t(B_{t,j})\geq1/N\). These individual bundles need not be output.
Let \(m\) count the intervals listed in the representation. Count exact oracle calls and arithmetic/comparison operations separately, treating oracle-returned real numbers as exact registers; require \(m\) and both operation counts to be polynomial in \(\tau,L,\log N\).
Is producing such a type-mass representation solvable in polynomial time in this oracle model, using \(\operatorname{poly}(\tau,L,\log N)\) valuation queries, or is it \(\mathrm{NP}\)-hard even for explicitly given positive rational piecewise-constant densities?
For individually listed agents, a proportional protocol is known to terminate within a valuation-independent finite bound, polynomial in the number of agents ([Lindner–Rothe](https://arxiv.org/abs/0902.0620)).
For a related problem, proportional cake division among \(k\) players with positive integer demands totaling \(D\) has a protocol using at most \(2(k-1)\lceil\log_2 D\rceil\) queries when \(2\leq k<D\); this result concerns unequal entitlements rather than the finite-realization representation specified here ([Cseh–Fleiner](https://arxiv.org/pdf/1709.03152)).
The problem is polynomial-time solvable in the stated exact oracle model. Put \(h=\lceil\log_2 N\rceil\). A type-mass representation can be produced with
\(m\leq 1+(\tau-1)h\)
listed intervals and at most
\(4(\tau-1)h\)
ordinary interval-evaluation and arbitrary-start cut queries. Arithmetic and comparison operations are also polynomial in \(\tau,L,\log N\).
The construction uses the near-halves recursion from [Cseh–Fleiner, Section 4](https://arxiv.org/pdf/1709.03152). Below, we prove correctness and all the required bounds directly, including the finite-realization condition. The proof covers both \(\tau=1\) and \(\tau=N\).
Lemma. Let \(A\) be a finite union of intervals, let \(v\) be a nonatomic finite measure, and let \(n\) be a positive integer. Then \(A\) admits a partition into \(n\) nonempty finite unions of intervals, each of value at least \(1/N\), if and only if
\(v(A)\geq n/N\).
Proof. Necessity follows from additivity: the values of the \(n\) bundles sum to \(v(A)\).
For sufficiency, write \(V=v(A)\) and define
\(F(x)=v(A\cap[0,x])\), for \(x\in[0,1]\).
Nonatomicity implies that \(F\) is continuous: the measure \(E\mapsto v(A\cap E)\) has no atoms, so its cumulative distribution has no jumps. Also, \(F\) is nondecreasing, with \(F(0)=0\) and \(F(1)=V\).
For each \(j\in\{1,\ldots,n-1\}\), continuity gives a point \(x_j\) satisfying
\(F(x_j)=jV/n\).
These points occur in strictly increasing order because their prescribed values strictly increase. Set \(x_0=0\) and \(x_n=1\). Intersecting \(A\) with the successive intervals between these points gives a partition into finite unions of intervals, with endpoints assigned arbitrarily. Each bundle has value
\(V/n\geq 1/N>0\),
and hence is nonempty. This proves the lemma.
Consequently, the task is exactly to produce a finite interval partition satisfying
\(v_t(A_t)\geq n_t/N=\mu_t\)
for every type \(t\). The potentially enormous individual subdivisions need not be computed.
A recursive instance consists of:
Write \(k=|S|\) and \(D=\sum_{t\in S}d_t\). We maintain the invariant
\(v_t(I)\geq D/N\quad\text{for every }t\in S.\)
Initially, take \(I=[0,1]\), all types active, and \(d_t=n_t\). Then \(D=N\), and normalization establishes the invariant.
If \(k=1\), assign the entire interval to its sole active type and stop this branch.
Otherwise \(D\geq2\). Define
\(a=\lfloor D/2\rfloor,\qquad b=D-a=\lceil D/2\rceil.\)
For each active type \(t\), evaluate \(V_t=v_t(I)\) and ask for its mark \(x_t\) satisfying
\(v_t([\ell,x_t])=(a/D)V_t.\)
These marks exist uniquely in the interior of \(I\). Indeed, nonatomicity makes cumulative value continuous, strict positivity on every positive-length interval makes it strictly increasing, and \(0<a/D<1\).
Order the active types as \(t_1,\ldots,t_k\) so that
\(x_{t_1}\leq\cdots\leq x_{t_k},\)
breaking ties by type index. Let \(j\) be the smallest index satisfying
\(\sum_{i=1}^{j}d_{t_i}\geq a.\)
Set
\(s=\sum_{i=1}^{j-1}d_{t_i},\qquad u=a-s,\qquad w=d_{t_j}-u.\)
Minimality of \(j\) gives \(s<a\leq s+d_{t_j}\), so
\(1\leq u\leq d_{t_j},\qquad w\geq0.\)
Cut \(I\) at \(c=x_{t_j}\), and create two children:
The child demand totals are \(a\) and \(b\), respectively. Both are positive, so both children are nonempty instances.
For a type \(t_i\) in the left child, its mark satisfies \(x_{t_i}\leq c\). By monotonicity and the parent invariant,
\(v_{t_i}([\ell,c])\geq v_{t_i}([\ell,x_{t_i}])=(a/D)v_{t_i}(I)\geq a/N.\)
Thus the left child satisfies the invariant with total demand \(a\).
For a type \(t_i\) in the right child, its mark satisfies \(x_{t_i}\geq c\). Therefore,
\(v_{t_i}([\ell,c])\leq v_{t_i}([\ell,x_{t_i}])=(a/D)v_{t_i}(I).\)
Endpoints have zero value, so subtraction gives
\(v_{t_i}([c,r])\geq (b/D)v_{t_i}(I)\geq b/N.\)
This also applies to the pivot type when it belongs to the right child. Hence that child satisfies the invariant.
At each split, every type’s demand is conserved across the two children: only the pivot demand can split, and its two parts sum to its parent demand.
We next verify termination. Since \(N\leq2^h\), every instance at depth \(q\) has total demand at most \(2^{h-q}\): this follows inductively because a child’s total is at most the ceiling of half its parent’s total. At depth \(h\), therefore, the total demand is at most \(1\). Positive integer demands then force \(k=1\), so the recursion stops.
Each leaf interval assigned to type \(t\) has value at least its leaf demand divided by \(N\). Let \(A_t\) be the union of all leaf intervals assigned to \(t\). Demand conservation gives
\(\sum_{\text{leaves assigned to }t}d_t=n_t.\)
The leaf intervals partition the cake, so additivity yields
\(v_t(A_t)\geq \sum_{\text{leaves assigned to }t}d_t/N=n_t/N.\)
Each \(A_t\) is a finite union of intervals. The lemma in Section 1 now proves that the output realizes the required finite proportional assignments.
The crucial bound concerns the number of active types, rather than the numerical demand total.
For a node with \(k\) active types, give it potential \(k-1\). If its children have \(k_{\mathrm L}\) and \(k_{\mathrm R}\) active types, at most the pivot appears in both, so
\(k_{\mathrm L}+k_{\mathrm R}\leq k+1.\)
Consequently,
\((k_{\mathrm L}-1)+(k_{\mathrm R}-1)\leq k-1.\)
Leaves have potential zero. It follows by induction that the sum of potentials over all nodes at any fixed depth is at most \(\tau-1\).
Every internal node has \(k\geq2\), so it has potential at least \(1\). There are therefore at most \(\tau-1\) internal nodes at each depth. Since internal nodes occur only at depths \(0,\ldots,h-1\), their total number \(J\) satisfies
\(J\leq(\tau-1)h.\)
Every internal node has exactly two children, so the tree has \(J+1\) leaves. Listing one interval per leaf gives
\(m\leq J+1\leq1+(\tau-1)h.\)
For queries, observe that \(k\leq2(k-1)\) at every internal node. Thus, at each depth,
\(\sum_{\text{internal nodes}}k\leq2(\tau-1).\)
Each active type requires one interval evaluation and one arbitrary-start cut query. The total query count is therefore at most
\(Q\leq4(\tau-1)h.\)
If the Robertson–Webb interface instead uses prefix evaluations and prefix cuts, each such pair can be implemented with two prefix evaluations and one prefix cut. This only changes the constant.
At a node, sorting the marks uses \(O(k\log(k+1))\) comparisons. The remaining demand calculations, query-target calculations, and child-list construction use \(O(k)\) arithmetic and list operations, apart from binary-integer bookkeeping. Every demand is at most \(N\), and therefore has \(O(h)\) bits.
Summing over all depths gives polynomial operation counts; for example, allowing \(O(h)\) work per integer calculation gives
\(O\bigl(\operatorname{poly}(L)+\tau h(\log(\tau+1)+h)\bigr).\)
Output assembly takes \(O(J+\tau)\) additional operations. All required bounds are polynomial in \(\tau,L,\log N\).
The same construction also has polynomial bit complexity when densities are given explicitly. Here the ordinary input length includes their descriptions.
Let \(H\) be their total description length. For each type, its cumulative value function \(F_t(x)=v_t([0,x])\) is piecewise affine with rational coefficients whose bit lengths are polynomial in \(H\). Evaluation and cutting can be performed by scanning the listed segments and solving one affine equation; positivity guarantees a nonzero slope.
We must also control the bit lengths of generated endpoints. A mark \(c\) inside a recursive interval \([\ell,r]\) satisfies
\(F_t(c)=(1-a/D)F_t(\ell)+(a/D)F_t(r).\)
On the segments containing \(\ell,r,c\), write
\(F_t(x)=\alpha_x x+\beta_x,\)
where the subscript identifies the relevant segment. Solving for \(c\) expresses it as
\(c=A\ell+Br+C,\)
with rational coefficients
\(A=(1-a/D)\alpha_\ell/\alpha_c,\qquad B=(a/D)\alpha_r/\alpha_c,\)
\(C=((1-a/D)\beta_\ell+(a/D)\beta_r-\beta_c)/\alpha_c.\)
Because \(\alpha_c>0\), these expressions are defined. Their bit lengths are bounded by some polynomial \(P\) in \(H+\log N\).
To bound endpoint growth, maintain a common denominator \(R\) for all endpoints generated so far. After generating \(c\), a common denominator is obtained by multiplying \(R\) by the denominators of \(A,B,C\). Its bit length increases by at most \(3P\). Starting from endpoints \(0,1\), after all \(O(\tau h)\) marks its bit length is therefore \(O(\tau hP)\). Every endpoint lies in \([0,1]\), so its numerator has no greater bit length.
Thus all oracle simulations and arithmetic use rationals of polynomial bit length, and their total bit cost is polynomial in the full explicit input length. The output still has the interval bound proved above.
The finite-realization requirement therefore preserves polynomial-time solvability; it does not create the proposed hardness alternative.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The recursive construction satisfies the required value inequalities, the finite-realization lemma applies to its output, and the output size and operation counts have the claimed polynomial bounds. I found no major or minor issues.
The equivalence in Section 1 is correct.
Necessity follows from finite additivity over the bundles. For sufficiency, restricting the nonatomic measure to \(A\) preserves nonatomicity, so the cumulative function \(F\) is continuous and nondecreasing. Its endpoint values are correctly stated because singletons have zero measure.
Under the sufficient-condition hypothesis, \(V\geq n/N>0\). Thus the prescribed cumulative values \(jV/n\) strictly increase, and any points realizing them must occur in strictly increasing order. Intersecting \(A\) with successive intervals preserves the finite-union property. Each resulting bundle has positive value \(V/n\), so it is nonempty. Arbitrary endpoint ownership does not change these values.
The case \(n=1\) is also covered: there are no intermediate cut points, and the sole bundle is \(A\).
Consequently, the reduction of the task to \(v_t(A_t)\geq n_t/N\) is valid. It does not require computing or outputting the individual bundles.
The initial invariant \(v_t(I)\geq D/N\) holds because initially \(D=N\) and every valuation is normalized.
At an internal node, positive integer demands and at least two active types imply \(D\geq2\). Therefore \(a\) and \(b\) are positive and \(0<a/D<1\).
The claimed existence and uniqueness of each mark are justified by the stated valuation assumptions: nonatomicity gives continuity, and strict positivity on positive-length intervals gives strict increase. The invariant also ensures that the current interval has positive value and hence positive length.
The pivot index exists because the demands sum to \(D\geq a\). Its minimality gives the asserted bounds on \(u\) and \(w\). The left demand total is exactly \(a\), and the right demand total is exactly \(b\). Omitting the pivot from the right child when \(w=0\) preserves the requirement that every active demand be positive.
Ties between marks cause no difficulty: both invariant arguments use non-strict inequalities.
Both child-invariant calculations are correct.
For every left-child type, its mark lies at or before the pivot cut, which gives the required lower bound \(a/N\). For every right-child type, its mark lies at or after that cut; subtracting the left value from the parent value gives the lower bound \(b/N\). The pivot satisfies the right-child argument whenever its right demand is positive.
Demand conservation holds separately for every type, including the split pivot.
The termination argument is valid. The ceiling in the child-demand bound does not invalidate the induction: before depth \(h\), the comparison bound \(2^{h-q}\) is an even integer. At depth \(h\), total demand is at most one, which forces a single active type.
At a leaf, the invariant supplies at least the leaf demand divided by \(N\). Summing over a type’s leaf intervals is legitimate because the intervals are disjoint up to zero-valued endpoints. Demand conservation then gives \(v_t(A_t)\geq n_t/N\). The finite-realization lemma therefore establishes the requested property.
The boundary cases are covered: \(\tau=1\) immediately produces the entire cake as one portion, and \(\tau=N\) is permitted throughout the argument.
The potential calculation is correct. Only the pivot can occur in both children, so the sum of child potentials is at most the parent potential. Terminal nodes have zero potential. Consequently, the total potential at any depth is at most \(\tau-1\).
Every internal node has positive integer potential, giving at most \(\tau-1\) internal nodes per depth and hence \(J\leq(\tau-1)h\). The recursion tree is a finite full binary tree, so its leaf count is \(J+1\). Listing its leaf intervals gives the claimed bound on \(m\).
The query bound also follows as written. At each internal node, \(k\leq2(k-1)\). Summing over depths bounds the number of active-type occurrences by \(2(\tau-1)h\); one evaluation and one cut per occurrence give at most \(4(\tau-1)h\) queries.
The stated prefix-oracle conversion is valid: two prefix evaluations determine the interval value and the absolute prefix target, after which one prefix cut produces the mark.
Sorting, demand accumulation, target calculation, and child construction have the stated per-node costs. Every demand remains a positive integer bounded by \(N\), so its bit length is \(O(h)\).
The potential bound controls the sum of active-type counts across the recursion. Together with \(k\leq\tau\), it therefore controls both sorting comparisons and the remaining arithmetic work polynomially in \(\tau,L,\log N\). Exact comparisons of oracle-returned marks are permitted by the specified exact-register model.
Output assembly is also polynomial. No operation proportional to the number of individual agents is required.
The additional bit-complexity argument is sound under the explicitly stated inclusion of density descriptions in the input length.
The cumulative functions have rational affine coefficients of polynomial bit length. Their evaluations and inverse calculations can be implemented by scanning the finite segment lists. Positive density supplies the nonzero slope required for inversion.
The displayed formula for \(c=A\ell+Br+C\) is algebraically correct. Each coefficient has bit length polynomial in \(H+\log N\).
The common-denominator argument correctly prevents uncontrolled endpoint growth. If the denominators of existing endpoints divide \(R\), multiplying \(R\) by the denominators of \(A,B,C\) suffices for the new mark. This reasoning applies to all queried marks, whose total number is already bounded by \(O(\tau h)\), including marks that are not selected as cuts. The resulting common denominator has polynomial bit length. Because every mark lies in \([0,1]\), its numerator over that denominator is bounded accordingly.
Thus the explicit oracle simulations and rational arithmetic have polynomial bit cost.
None. The cited protocol is contextual; the submitted argument establishes the necessary correctness and complexity bounds directly.
⟨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.