Answer: \(\text{polynomial-time solvable}\)
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateConsider an instance of the two-layered cake-cutting problem with n agents, n ⩾3, whose valuation functions satisfy monotonicity and the Lipschitz condition with constant K. Then, for any ε > 0, one can find in time O(n log2 K ε ) a feasible and contiguous multi-division into three layered pieces where no matter which layered piece the birthday agent chooses, the remaining agents can be assigned to the layered pieces while satisfying the following two properties: • each of the remaining agents is assigned to one of her ε-approximate preferred layered pieces. • the number of agents assigned to each layered piece differs by at most one.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two layers of \([0,1]\), a finite set \(T\) of monotone \(K\)-Lipschitz valuation types, rational masses \(\mu_t>0\) summing to \(1\), and \(\varepsilon>0\), compute a feasible contiguous three-piece division \(A(x,y)\) using one short and one long knife, together with assignments for each external birthday choice \(r\in\{1,2,3\}\). Represent each assignment by masses \(z^{(r)}_{tj}\ge 0\) satisfying \(\sum_{j=1}^3 z^{(r)}_{tj}=\mu_t\) and \(\sum_{t\in T}z^{(r)}_{tj}=1/3\); require \(z^{(r)}_{tj}>0\) only if \(v_t(A_j(x,y))+\varepsilon\ge\max_{k\in\{1,2,3\}}v_t(A_k(x,y))\).
A society is given by its support: the list of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not all possible types. There are \(m=2\) layers, each \([0,1]\), and positive binary-rational parameters \(K,\varepsilon\). Let \(L\) be the total bit length of these rational inputs.
Each type has a real-valued valuation on layered pieces, monotone under inclusion in each layer, satisfying \(|v_t(B)-v_t(C)|\le K\sum_{\ell=1}^{2}\lambda(B_\ell\triangle C_\ell)\), where \(\lambda\) is Lebesgue measure; additivity, nonnegativity, and value normalization are not assumed. Exact valuation queries and real arithmetic/comparisons have unit cost.
The layers may be relabeled so that the types weakly preferring the entire top layer to the entire bottom layer have total mass at least \(1/2\). For \((x,y)\in[0,1]^2\), define \(A_1=([0,y],\varnothing)\), \(A_2=([\max\{x,y\},1],[0,x])\), and \(A_3=([y,\max\{x,y\}],[x,1])\), with coordinates ordered top, bottom. Zero-length intervals are allowed; shared endpoints are ignored.
These bundles allocate both layers completely, are contiguous within each layer, and have disjoint interval interiors across layers within each bundle. The short knife at \(y\) takes priority over the long knife at \(x\).
Compute rational \(x,y\) and, for every external birthday choice \(r\in\{1,2,3\}\), rational assignment masses \(z^{(r)}_{tj}\ge0\) with \(\sum_jz^{(r)}_{tj}=\mu_t\) and \(\sum_tz^{(r)}_{tj}=1/3\), allowing \(z^{(r)}_{tj}>0\) only when \(v_t(A_j)+\varepsilon\ge\max_kv_t(A_k)\). Ties are unrestricted. The external birthday individual has zero society mass and chooses bundle \(r\) without a preference constraint.
Is this additive \(\varepsilon\)-approximation problem solvable in time polynomial in \(m,\tau,L,\log(1+K/\varepsilon)\) in the stated computational model, or is it NP-hard?
For a finite society of \(n\ge3\) agents, a birthday-compatible division with additive error \(\varepsilon\) and group sizes differing by at most one can be computed using \(O(n\log^2(1+K/\varepsilon))\) unit-cost operations; assignments can subsequently be computed in \(O(n^2)\) time. [Igarashi–Meunier](https://arxiv.org/abs/2106.02262v4)
No result settling the specified rational-mass problem was located in the literature search.
The problem is polynomial-time solvable in the stated oracle model. The algorithm uses \(O(\tau s^2)\) valuation queries and unit-cost arithmetic operations, apart from polynomial overhead for rational input and output, where \(s=1+\lceil\log_2(1+K/\varepsilon)\rceil\).
Because the external birthday individual has zero society mass, the assignment requirements are identical for all three choices. We construct one assignment \(z\) and set \(z^{(r)}=z\) for every \(r\).
The proof adapts the weighted-preference and partial-monotonicity ideas in [Igarashi–Meunier, Section 4](https://arxiv.org/html/2106.02262v4). The essential additional ingredient is a rational-lattice argument: denominator clearing is used only for arithmetic, never to create replicated agents.
Write each mass as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\), and let \(D=\prod_{t\in T}b_t\). Then \(D\mu_t\) is an integer, and \(\log_2D\le L\).
Relabel the layers, if necessary, so that the supported types weakly preferring the entire top layer to the entire bottom layer have total mass at least \(\frac12\). This takes \(O(\tau)\) queries.
Choose the smallest power of two \(N\) satisfying \(N\ge\max\{1,6K/\varepsilon\}\). Consider the grid with vertices \(u=(k/N,h/N)\), where \(0\le k,h\le N\).
At every queried vertex \(u=(x,y)\), give each type \(t\) a label \(c_t(u)\in\{1,2,3\}\), selecting an exactly most valuable bundle according to these rules:
These rules always select a maximizer. Indeed, Lipschitz continuity gives every zero-length bundle the value of the empty bundle. Monotonicity gives every bundle at least that value. If the maximum exceeds the empty-bundle value, every maximizer has positive length; otherwise every bundle is a maximizer and some bundle has positive length.
Define the weighted label vector by
\(F_j(u)=\sum_{t:c_t(u)=j}\mu_t,\qquad F(u)=(F_1(u),F_2(u),F_3(u)).\)
Thus \(F(u)\) belongs to the simplex \(\Delta=\{z\in\mathbb R_{\ge0}^3:z_1+z_2+z_3=1\}\), and every coordinate of \(F(u)\) is an integer multiple of \(1/D\). Evaluating \(F(u)\), including all labels, costs \(O(\tau)\) operations.
Fix a grid column \(x=k/N\). As \(y\) increases, bundle \(A_1\) grows, while \(A_2\) and \(A_3\) shrink, up to ignored endpoints.
Consequently, once a type chooses label \(1\), it continues choosing label \(1\) at every higher vertex of that column. Its chosen bundle remains a maximizer by monotonicity, and the tie rule continues selecting it. Therefore \(F_1(k/N,h/N)\) is nondecreasing in \(h\).
At the lower boundary, bundle \(A_1\) has zero length and is excluded, so \(F_1(x,0)=0\).
At the upper boundary, bundle \(A_1\) is the entire top layer, and each other bundle is contained in the bottom layer. Every type weakly preferring the entire top layer therefore selects label \(1\). Hence \(F_1(x,1)\ge\frac12\).
Finally, the divisions at \((0,y)\) and \((1,y)\) have identical bundle \(1\), with bundles \(2\) and \(3\) exchanged. The tie rules respect this exchange:
\(F(1,y)=(F_1(0,y),F_3(0,y),F_2(0,y)).\)
For \(y<1\), the rule for a tie between \(2\) and \(3\) selects exchanged labels. At \(y=1\), one of these bundles is empty. If bundle \(1\) is not selected, the nonempty bottom-layer bundle must strictly exceed its value, and so the exchanged label is again selected.
Set
\(\omega=(\frac13,\frac13,\frac13),\qquad \delta=\frac{1}{12D^2},\qquad q=(\frac13-\delta,\frac13+\frac{\delta}{2},\frac13+\frac{\delta}{2}).\)
Write \(\alpha=q_1\) and \(\beta=q_2=q_3\).
Every integer multiple of \(1/D\) strictly below \(\frac13\) is at least \(1/(3D)\) below it. Since \(\delta<1/(3D)\), there is no such multiple in \([\alpha,\frac13)\). In particular, \(\alpha\) is not an integer multiple of \(1/D\).
Lemma. Let \(P\) be a finite set of points in \(\Delta\), each having coordinates that are integer multiples of \(1/D\). If \(q\in\operatorname{conv}P\), then \(\omega\in\operatorname{conv}P\).
Proof. For distinct \(u,v\in P\), consider \(\phi(z)=\det(z,u,v)\), with the three vectors as rows. Since \(Du,Dv\) have integer coordinates, cofactor expansion gives integers \(A,B,C\), each of absolute value at most \(D^2\), such that
\(\phi(z)=(Az_1+Bz_2+Cz_3)/D^2.\)
Therefore
\(\phi(\omega)=(A+B+C)/(3D^2),\)
and
\(\phi(q)-\phi(\omega)=\delta(-A+(B+C)/2)/D^2.\)
The latter difference has absolute value at most \(2\delta=1/(6D^2)\). Whenever \(\phi(\omega)\ne0\), its absolute value is at least \(1/(3D^2)\). Thus a nonzero \(\phi(\omega)\) has the same sign as \(\phi(q)\). In particular,
If \(\operatorname{conv}P\) is two-dimensional in the plane \(z_1+z_2+z_3=1\), it is the intersection of the closed halfplanes supported by its polygon edges. Each edge joins two points of \(P\). The implications above show that \(\omega\) satisfies every supporting halfplane satisfied by \(q\), proving membership.
If the hull is a segment \([u,v]\), its endpoints belong to \(P\). Neither endpoint has first coordinate \(\alpha\), so, after exchanging them, \(u_1<\alpha<v_1\). The lattice observation gives \(u_1<\frac13\le v_1\). Also \(\phi(q)=0\), hence \(\phi(\omega)=0\), so \(\omega\) lies on the same affine line as \(u,v\). Because the first coordinates of the endpoints differ, the first coordinate parametrizes this line, and the preceding inequalities place \(\omega\) in the segment.
A singleton hull cannot contain \(q\), since its first coordinate would have to equal the nonlattice number \(\alpha\). This exhausts the cases. \(\square\)
We now find a grid square \(S\) such that \(q\) belongs to the convex hull of the weighted label vectors at its four corners. The lattice lemma will then give the same conclusion for \(\omega\).
For a column \(k\), monotonicity and the boundary inequalities imply that there is a unique index \(h_k\in\{0,\ldots,N-1\}\) satisfying
\(F_1(k/N,h_k/N)<\alpha<F_1(k/N,(h_k+1)/N).\)
Strictness holds because no vertex first coordinate equals \(\alpha\). Binary search finds \(h_k\) using \(O(\log N)\) vertex evaluations.
Let \(G_k\) be the unique point of the segment joining these two weighted label vectors whose first coordinate is \(\alpha\). It is computed by rational interpolation. Define \(\sigma_k=G_{k,2}-\beta\).
If \(\sigma_k=0\), then \(G_k=q\), so either square incident to that vertical grid edge has the desired convex-hull property.
Otherwise, boundary symmetry gives
\(G_N=(G_{0,1},G_{0,3},G_{0,2}),\qquad \sigma_N=-\sigma_0,\)
because \(\beta=(1-\alpha)/2\).
Starting with columns \(0,N\), binary search on the column index therefore either finds a zero sign or produces adjacent columns \(k,k+1\) with opposite signs. No monotonicity of these signs is needed: at each step retain the subinterval whose endpoints have opposite signs.
This stage costs \(O(\tau(1+\log N)^2)\).
Let \(a=h_k\) and \(b=h_{k+1}\).
If \(a=b\), the two crossing segments are opposite vertical edges of the same square. Their crossing images have first coordinate \(\alpha\) and second coordinates on opposite sides of \(\beta\). Their joining segment therefore contains \(q\), proving that this square works.
Suppose next that \(a<b\). At every horizontal grid edge in the strip at height \(h/N\), where \(a+1\le h\le b\), the left endpoint has first preference coordinate above \(\alpha\), and the right endpoint has it below \(\alpha\). Its image segment therefore has a unique crossing point \(H_h\) with first coordinate \(\alpha\).
Consider the list
\(G_k,\ H_{a+1},\ H_{a+2},\ldots,H_b,\ G_{k+1}.\)
Every consecutive pair comes from two edges of a common grid square:
The first and last points have opposite signs of the second coordinate minus \(\beta\). Binary search on the list therefore finds either a point equal to \(q\), or a consecutive pair with opposite signs. Every intermediate list point can be evaluated directly from its two grid-edge endpoints.
For a consecutive pair with opposite signs, \(q\) lies on their joining segment. Each point is itself a convex combination of two corner images of their common square. Hence \(q\) belongs to the convex hull of that square’s four corner images.
When \(a>b\), the same construction starts from the right column, which has the lower crossing row, and ends at the left column.
This second search uses \(O(\tau(1+\log N))\) operations. We have therefore found the required square without traversing all rows or columns.
Let \(u_1,\ldots,u_4\) be the corners of the resulting square \(S\). By the lattice lemma,
\(\omega\in\operatorname{conv}\{F(u_1),F(u_2),F(u_3),F(u_4)\}.\)
Compute nonnegative rational coefficients \(\lambda_i\) satisfying
\(\sum_{i=1}^4\lambda_i=1,\qquad \sum_{i=1}^4\lambda_iF(u_i)=\omega.\)
For completeness, these coefficients can be found by enumerating the subsets of at most three corner images and solving their rational linear systems. Such a subset suffices: choose a convex representation with minimum positive support. If its support is affinely dependent, an affine dependence permits changing the coefficients, while preserving their sum and represented point, until one positive coefficient becomes zero. This contradicts minimality. The support is therefore affinely independent and has size at most three in the two-dimensional simplex. Its coefficients are the unique solution of a rational linear system and hence are rational.
Choose any corner \(p=(x,y)\) of \(S\) as the output division. Define
\(z_{tj}=\mu_t\sum_{i:c_t(u_i)=j}\lambda_i.\)
These are nonnegative rational numbers. Since each corner gives each type exactly one label,
\(\sum_{j=1}^3z_{tj}=\mu_t.\)
Moreover,
\(\sum_tz_{tj}=\sum_{i=1}^4\lambda_iF_j(u_i)=\frac13.\)
Thus the row and column constraints hold exactly.
Any two points \(u,p\) in the same grid square differ by at most \(1/N\) in each coordinate. The function \((x,y)\mapsto\max\{x,y\}\) also changes by at most \(1/N\).
For intervals, the measure of symmetric difference is at most the sum of the absolute changes in their two endpoints. Applying this layer by layer gives
\(\sum_{\ell=1}^2\lambda(A_j(u)_\ell\triangle A_j(p)_\ell)\le3/N\)
for every bundle \(j\). Indeed, bundle \(1\) contributes at most \(1/N\), bundle \(2\) at most \(2/N\), and bundle \(3\) at most \(3/N\).
Consequently, for every type \(t\) and bundle \(j\),
\(\lvert v_t(A_j(u))-v_t(A_j(p))\rvert\le3K/N.\)
If \(c_t(u)=j\), then \(j\) is an exact maximizer at \(u\). For every bundle \(k\),
\(v_t(A_k(p))-v_t(A_j(p))\le v_t(A_k(u))-v_t(A_j(u))+6K/N\le6K/N\le\varepsilon.\)
If \(z_{tj}>0\), some corner with positive coefficient has label \(j\) for type \(t\). Applying the inequality at that corner proves
\(v_t(A_j(p))+\varepsilon\ge\max_kv_t(A_k(p)).\)
Set \(z^{(r)}_{tj}=z_{tj}\) for all birthday choices \(r\). These assignments satisfy every requested condition.
The grid size satisfies \(\log N=O(1+\log(1+K/\varepsilon))\). The searches use \(O(\tau(1+\log N)^2)\) unit-cost operations.
Although \(D\) can be exponentially large numerically, its bit length is at most \(L\). The algorithm performs arithmetic with \(D\) and the masses; it never performs a loop of length \(D\). The perturbation has bit length \(O(L)\), and all search interpolations have polynomial bit length.
The final coefficients come from linear systems of order at most three with rational coefficients of polynomial bit length. Thus the assignment masses have polynomial encoding length. The output coordinates have denominator \(N\) and bit length \(O(1+\log(1+K/\varepsilon))\).
This establishes the required polynomial-time bound in the supported-type input model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time solvability for the specified rational-mass problem in the stated oracle model. I found no major or minor mathematical issues requiring repair.
The argument addresses supported types directly, constructs rational coordinates and rational assignment masses, and satisfies the exact mass constraints and additive preference inequalities. Its handling of the external birthday choice agrees with the task’s explicit requirements.
The observation that all three birthday choices have identical assignment requirements is correct. The birthday individual has zero society mass, and the task specifies the same row sums, column sums, and preference constraints for each \(r\). There is no additional constraint reserving society mass or excluding the chosen bundle.
Consequently, constructing one valid assignment and setting \(z^{(r)}=z\) for every \(r\) fully addresses the birthday requirement.
Writing \(D=\prod_t b_t\) correctly makes every \(D\mu_t\) an integer. Its bit length is bounded by the total input length. The proof never iterates over \(D\) replicated agents.
The labeling rules select actual maximizers:
This reasoning accommodates negative valuation offsets, constant valuations, and unrestricted ties. Neither nonnegativity nor normalization is used.
Each weighted coordinate \(F_j(u)\) is therefore a nonnegative integer multiple of \(1/D\), and the coordinates sum to one. Computing the three bundle values for each supported type gives the stated \(O(\tau)\) evaluation cost.
For fixed \(x\), increasing \(y\) enlarges \(A_1\) and shrinks both competing bundles, modulo measure-zero endpoints. The Lipschitz condition makes such endpoint differences irrelevant to valuations.
Thus, once bundle \(1\) is selected, it remains a maximizer, remains nonempty, and retains priority under the tie rule. The claimed monotonicity of \(F_1\) follows.
Both boundary inequalities are valid:
Relabeling is justified: every type weakly prefers at least one entire layer to the other, so one of the two weak-preference masses is at least \(1/2\).
The boundary exchange identity is also correct. The bundles at \(x=0\) and \(x=1\) exchange labels \(2\) and \(3\), while preserving bundle \(1\). The stated tie rules respect this exchange, including \(y=0\) and the exceptional endpoint \(y=1\).
This is the essential additional ingredient, and its proof is valid.
For a lattice coordinate \(k/D<1/3\), the positive integer \(D-3k\) gives the asserted gap of at least \(1/(3D)\). Since \(0<\delta<1/(3D)\), \(\alpha=1/3-\delta\) is not a lattice coordinate.
The determinant calculation and constants check out. The cofactor coefficients are integers of absolute value at most \(D^2\). Hence a nonzero determinant at \(\omega\) has magnitude at least \(1/(3D^2)\), whereas the perturbation changes it by at most
\[
2\delta=\frac{1}{6D^2}.
\]
Therefore every nonzero determinant at \(\omega\) retains its sign at \(q\), and a zero determinant at \(q\) forces a zero determinant at \(\omega\).
All possible hull dimensions are covered:
No missing geometric case or unsupported implication remains.
Because \(\alpha\) lies strictly between the lower and upper boundary values and is never attained at a vertex, each column has exactly one adjacent pair satisfying the strict crossing inequalities. Plateaus in \(F_1\) do not invalidate this assertion.
The crossing point \(G_k\) is uniquely defined by rational interpolation. Since its coordinates sum to one and its first coordinate is \(\alpha\), the condition \(\sigma_k=0\) is exactly the condition \(G_k=q\).
Boundary symmetry yields opposite endpoint signs unless an endpoint already equals \(q\). The binary search is valid without sign monotonicity: after testing a midpoint, an interval with opposite endpoint signs can always be retained. It terminates with either a zero or adjacent columns.
The claimed \(O(\tau(1+\log N)^2)\) cost correctly accounts for a column crossing search inside each column-index search step.
The strip argument correctly handles every ordering of the two crossing rows.
When the rows agree, the two crossing points belong to opposite edges of one square. Their opposite signs place \(q\) on their joining segment.
When \(a<b\), column monotonicity supplies the required strict inequalities at every horizontal edge with \(a+1\le h\le b\). Each listed horizontal crossing exists uniquely. The specified consecutive pairs belong to edges of a common square, including the first and last pairs.
Binary search on this list again requires only opposite endpoint signs. Each intermediate crossing is directly computable from two vertex evaluations, so the list need not be traversed.
The case \(a>b\) is correctly obtained by starting with the other column. Zero crossing points also suffice, since their edges are incident to valid grid squares. The construction remains valid for \(N=1\).
Thus the algorithm finds a square whose corner-image hull contains \(q\), and the lattice lemma transfers that membership to \(\omega\).
The coefficient construction is justified. A convex representation with minimum positive support must be affinely independent; otherwise the stated affine-dependence adjustment removes a positive coefficient. The simplex plane has dimension two, so at most three corner images suffice.
Enumerating these constant-size subsets and solving their rational systems produces rational, nonnegative coefficients.
The assignment formula then gives exactly the required constraints:
If an assignment entry is positive, at least one positively weighted corner assigns that type the corresponding label. This is precisely the witness needed for the subsequent preference bound.
The symmetric-difference estimates are correct. Within one grid square, each coordinate and \(\max\{x,y\}\) changes by at most \(1/N\). The resulting bundle bounds are respectively \(1/N\), \(2/N\), and \(3/N\).
Lipschitz continuity therefore gives the uniform valuation change bound \(3K/N\). Comparing a corner maximizer with any competing bundle at the output point incurs at most two such changes, yielding \(6K/N\le\varepsilon\).
This proves the preference constraint for every positive assignment entry. Choosing an arbitrary corner of the square also guarantees rational output coordinates.
The encoding claims are consistent with the construction:
Exact valuation comparisons use the explicitly permitted unit-cost oracle operations. The algorithm’s search cost and rational overhead are polynomial in the requested parameters, with \(m=2\) fixed.
The citation to [Igarashi–Meunier, Section 4](https://arxiv.org/html/2106.02262v4) supplies methodological context. The submitted argument does not rely on an unstated theorem from that source: its lattice, search, and assignment arguments are supplied explicitly.
No corrective clarification or additional lemma is needed. The proof resolves the specified rational-mass problem.
⟨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.