Answer: For every \(n\geq1\), an aggregate non-exploitable non-adaptive forced-cut protocol exists with \(n\) forced cuts and \(2n\) segment-cut operations, totaling \(3n\).
Theorem 1.6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a non-adaptive non-exploitable n- day forced-cut protocol for the set (0, 1) × (0, 1) that uses 3n cuts.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For an \(n\)-day repeated cut-and-choose service on the square, does there exist a non-adaptive forced-cut protocol using \(3n\) cuts such that, after every reachable history of divisions and exact aggregate choice shares, each legal next division admits two finite-support rational distributions over chooser types consistent with that history whose next shares choosing one side are respectively below and above \(1/2\)?
Let \(n\geq1\) and \(C=(0,1)^2\). A chooser type is a nonnegative Borel probability measure \(u\) on \(C\), absolutely continuous with respect to area, together with a deterministic tie rule selecting the same physical piece whenever a division is repeated. Types remain unchanged across days and choose myopically.
A society \(\mu\) is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; rationality concerns masses, not valuations. Any running-time bounds must specify dependence on \(n\), \(m=2\) offered pieces, \(\tau\), and binary data length \(L\), and identify the representation of valuations.
A non-adaptive forced-cut protocol fixes before play each day's forced straight-line cuts, permitted cutter-cut directions, and slice assignments. Forced cuts partition the square into segments of positive area; the cutter makes one straight-line cut through each segment's interior, producing two slices of positive area. Every interior offset in each permitted direction is legal, and each segment contributes one slice to each offered piece. Count forced cuts and segment-cut operations separately, summed over all days.
For a legal division \(D=(X,C\setminus X)\), let \(c_u(D)\in\{0,1\}\) indicate whether the type chooses \(X\), including its tie rule, and define \(s_\mu(D)=\sum_{u\in\operatorname{supp}(\mu)}\mu(u)c_u(D)\).
A history \(H=((D_1,q_1),\ldots,(D_{t-1},q_{t-1}))\) is reachable if its divisions are legal and some such society satisfies \(s_\mu(D_j)=q_j\) for every earlier day. Only divisions and exact aggregate shares are observed; alternative consistent societies may have different supports.
Call a protocol aggregate non-exploitable if, for every \(1\leq t\leq n\), every reachable history \(H\) (including the empty history), and every legal next division \(D\), there exist finite-support societies \(\mu^-\) and \(\mu^+\) consistent with \(H\) such that \(s_{\mu^-}(D)<\tfrac12<s_{\mu^+}(D)\).
For every \(n\geq1\), does an aggregate non-exploitable non-adaptive forced-cut protocol on \(C\) using at most \(3n\) cuts exist, or is there some \(n\) for which none exists?
For a single persistent chooser, a non-adaptive non-exploitable square protocol using \(3n\) cuts is known: every legal next division permits either individual choice consistently with previous choices. [Tamuz, Vardi, and Ziani](https://www.tamuz.caltech.edu/papers/repeated_cake_cutting.pdf)
No result settling the exact aggregate-share formulation was located in the literature search.
Yes. For every \(n\geq1\), there is an aggregate non-exploitable non-adaptive protocol using exactly \(n\) forced cuts and \(2n\) segment-cut operations.
In fact, for every reachable history and every legal next division, consistent societies can make the next aggregate share equal to \(0\) or \(1\). The crucial point is that the witnesses may have different supports.
Use the geometry of Protocol 5.1 of [Tamuz, Vardi, and Ziani](https://www.tamuz.caltech.edu/papers/repeated_cake_cutting.pdf). We give a self-contained proof of the stronger aggregate property.
Before play, fix \(a_j=j/(n+1)\) for every day \(j\in\{1,\ldots,n\}\). On day \(j\):
\(X_j=((0,a_j)\times(0,\alpha_j))\cup((a_j,1)\times(\beta_j,1))\)
and its complement.
Assign points on the cut lines by a fixed convention. Their assignment does not affect any absolutely continuous valuation.
Both segments and all four slices have positive area. Every interior horizontal offset is legal. The forced cuts, permitted directions, and slice assignments are fixed before play.
Summed over all days, the protocol uses \(n\) forced cuts and \(2n\) segment-cut operations, hence \(3n\) cuts in total.
Lemma. Fix \(r\in\{1,\ldots,n\}\), any legal divisions \(D_1,\ldots,D_r\) under this protocol, and any prescribed choices \(b_1,\ldots,b_r\in\{0,1\}\). There is an absolutely continuous Borel probability measure \(u\) such that, for every \(j\leq r\),
\(u(X_j)=\frac12+\frac{2b_j-1}{4(r+1)}.\)
Consequently, the myopic choices are exactly the prescribed choices, irrespective of the tie rule.
Proof. Define the extreme cutter heights
\(\ell=\min_{1\leq j\leq r}\{\alpha_j,\beta_j\},\qquad h=\max_{1\leq j\leq r}\{\alpha_j,\beta_j\}.\)
Legality gives \(0<\ell\leq h<1\).
For this proof, set \(a_0=0\), retain \(a_i=i/(n+1)\) for \(1\leq i\leq r\), and set \(a_{r+1}=1\). Thus the last strip extends from the last observed forced cut to the right boundary. Define the positive-area rectangles
\(R_i^-=(a_{i-1},a_i)\times(0,\ell),\qquad R_i^+=(a_{i-1},a_i)\times(h,1)\)
for \(1\leq i\leq r+1\).
Set
\(e_0=e_{r+1}=0,\qquad e_i=2b_i-1\quad(1\leq i\leq r),\)
and define
\(B=\frac{1}{2(r+1)},\qquad \varepsilon=\frac{1}{4(r+1)},\qquad d_i=\varepsilon(e_i-e_{i-1}).\)
Assign rectangle masses
\(u(R_i^-)=B+\frac{d_i}{2},\qquad u(R_i^+)=B-\frac{d_i}{2}.\)
These assignments define a density by making it constant on each rectangle, with value equal to the assigned mass divided by its area, and zero elsewhere.
We verify that this is a probability measure. Since \(|e_i-e_{i-1}|\leq2\), we have \(|d_i|\leq2\varepsilon=B\). Each assigned mass is therefore at least \(B/2>0\). Telescoping gives
\(\sum_{i=1}^{r+1}d_i=\varepsilon(e_{r+1}-e_0)=0.\)
Consequently,
\(\sum_{i=1}^{r+1}u(R_i^-)=\sum_{i=1}^{r+1}u(R_i^+)=(r+1)B=\frac12.\)
The density is nonnegative, Borel measurable, and integrates to \(1\), so it defines an absolutely continuous Borel probability measure.
Now fix a day \(j\leq r\). For \(i\leq j\), the rectangle \(R_i^-\) lies in \(X_j\), while \(R_i^+\) lies in its complement. For \(i>j\), the reverse holds. This follows because every lower rectangle lies below both cutter heights and every upper rectangle lies above both cutter heights.
All valuation mass is on these rectangles. Hence
\(u(X_j)=\sum_{i=1}^{j}\left(B+\frac{d_i}{2}\right)+\sum_{i=j+1}^{r+1}\left(B-\frac{d_i}{2}\right).\)
Using \(\sum_i d_i=0\), this simplifies to
\(u(X_j)=\frac12+\sum_{i=1}^{j}d_i=\frac12+\varepsilon e_j.\)
If \(b_j=1\), the value is strictly above \(1/2\); if \(b_j=0\), it is strictly below \(1/2\). This proves the lemma. \(\square\)
Each witness can be equipped with a deterministic tie rule—for example, among equally valued pieces, select the piece containing a fixed point of \(C\). Because the offered pieces form a partition, this selects the same physical piece whenever a division is repeated. The lemma’s choices are all strict.
Fix any day \(t\leq n\), any reachable history
\(H=((D_1,q_1),\ldots,(D_{t-1},q_{t-1})),\)
and any legal next division \(D_t\).
By reachability, there is a finite-support society consistent with \(H\). Write its distinct types as \(u_1,\ldots,u_\tau\), with positive binary-rational masses \(w_1,\ldots,w_\tau\). Thus
\(\sum_{i=1}^{\tau}w_i=1,\qquad q_j=\sum_{i=1}^{\tau}w_i c_{u_i}(D_j)\quad(j<t).\)
For each \(b\in\{0,1\}\) and each original type \(u_i\), prescribe the length-\(t\) choice sequence
\((c_{u_i}(D_1),\ldots,c_{u_i}(D_{t-1}),b).\)
Apply the lemma with \(r=t\) to obtain a replacement type \(v_i^{(b)}\) realizing this entire sequence with strict preferences.
Define a society \(\mu^{(b)}\) by placing mass \(w_i\) on \(v_i^{(b)}\). If replacement types coincide, merge their masses. Merging preserves positive binary-rational masses and total mass \(1\); the resulting support size is at most \(\tau\).
For every earlier day \(j<t\),
\(s_{\mu^{(b)}}(D_j)=\sum_{i=1}^{\tau}w_i c_{v_i^{(b)}}(D_j)=\sum_{i=1}^{\tau}w_i c_{u_i}(D_j)=q_j.\)
Thus both replacement societies preserve every exact observed aggregate share. On the next day, all replacement types make choice \(b\), so
\(s_{\mu^{(b)}}(D_t)=\sum_{i=1}^{\tau}w_i b=b.\)
Taking \(\mu^-=\mu^{(0)}\) and \(\mu^+=\mu^{(1)}\) gives
\(s_{\mu^-}(D_t)=0<\frac12<1=s_{\mu^+}(D_t).\)
For \(t=1\), the same argument starts with any singleton society; there are no earlier constraints. Hence the required property holds for the empty history as well.
This proves aggregate non-exploitability for every \(n\geq1\). \(\square\)
The protocol offers \(m=2\) pieces. Its cut count is independent of the witnessing society’s support size \(\tau\) and binary data length \(L\).
The constructed valuations have an explicit representation as piecewise constant densities on \(2(t+1)\) rectangles. Their rectangle coordinates may be real, as legal cutter offsets are unrestricted real numbers. The society masses retain the original binary-rational weights, with merging if needed.
This is an existence proof, with no running-time claim for arbitrary valuations or real cut coordinates.
⟨structured verdict parsed — rendered above⟩
The prover’s claimed result is proved. The construction satisfies the protocol requirements, the strict valuation witnesses are valid, and replacing types preserves every exact historical aggregate share. No major or minor mathematical issues were found.
For every \(n\geq1\), the forced locations \(a_j=j/(n+1)\) satisfy
\(0<a_1<\cdots<a_n<1\). Each day’s vertical forced cut therefore creates two segments of positive area.
The horizontal offsets \(\alpha_j,\beta_j\in(0,1)\) give two positive-area slices in each segment. Every interior horizontal offset is permitted. The offered piece contains the lower left slice and the upper right slice; its complement contains the other two slices. Thus each segment contributes exactly one slice to each piece.
The forced locations, permitted directions, and slice assignments depend only on the day and \(n\), so the protocol is non-adaptive. The count is exactly \(n\) forced cuts and \(2n\) segment-cut operations, totaling \(3n\).
The attribution to Protocol 5.1 is accurate: the cited paper specifies the same forced locations, horizontal segment cuts, and opposite-slice assignments. The submitted proof establishes the aggregate property independently of the paper’s theorem. [Tamuz, Vardi, and Ziani, Section 5](https://www.tamuz.caltech.edu/papers/repeated_cake_cutting.pdf)
Quantifiers and domains. The lemma covers every prefix length \(1\leq r\leq n\), every legal sequence of divisions for that prefix, and every prescribed binary choice sequence. These are exactly the witnesses required later.
Rectangle geometry. Legality ensures \(0<\ell\leq h<1\). All strip widths are positive, including the last width
\(1-a_r=1-r/(n+1)>0\). Consequently, all \(2(r+1)\) supporting rectangles have positive area and are pairwise disjoint. The case \(\ell=h\) causes no difficulty: both supporting bands still have positive height.
Nonnegative masses. The constants satisfy \(2\varepsilon=B\). Since \(\lvert e_i-e_{i-1}\rvert\leq2\), the bound \(\lvert d_i\rvert\leq B\) is correct. Thus both assigned masses \(B+d_i/2\) and \(B-d_i/2\) are at least \(B/2>0\).
Normalization and admissibility. The telescoping identity \(\sum_i d_i=0\) is correct. Each band receives total mass \((r+1)B=1/2\), so the full density integrates to \(1\). Constant densities on finitely many Borel rectangles, with zero density elsewhere, define a nonnegative Borel probability measure absolutely continuous with respect to area.
Membership calculation. For day \(j\), strips with \(i\leq j\) lie to the left of \(a_j\), and strips with \(i>j\) lie to its right. Every lower rectangle lies strictly below both cutter heights, and every upper rectangle lies strictly above them. Therefore the asserted rectangle memberships in \(X_j\) are correct, including when a cutter height equals \(\ell\) or \(h\).
Value calculation. The displayed sum has baseline \((r+1)B=1/2\). Using \(\sum_i d_i=0\), its remaining contribution is \(\sum_{i=1}^{j}d_i=\varepsilon e_j\). Hence
\(u(X_j)=1/2+(2b_j-1)/(4(r+1))\), as claimed.
Because the complementary piece has value \(1-u(X_j)\), these values produce precisely the prescribed myopic choices, with strict preferences. The witness remains one fixed valuation throughout the prefix.
Selecting the piece containing a fixed point is a valid deterministic tie rule for an exact partition: exactly one piece contains that point. It selects the same physical piece when the division is repeated.
The fixed boundary convention makes this rule well-defined on cut lines. Those lines have area zero, so their assignment does not affect the valuation calculations. All choices used in the lemma are strict, so the tie rule does not affect the witnesses’ prescribed behavior.
Reachability supplies a finite-support society with positive binary-rational masses \(w_i\) and the stated historical shares.
For each original type and each \(b\in\{0,1\}\), the lemma supplies a persistent replacement type reproducing all of that type’s historical choices and making next choice \(b\). The replacement is justified for the entire length-\(t\) sequence simultaneously.
Retaining each weight \(w_i\) therefore preserves every historical weighted indicator sum exactly. This argument preserves aggregate shares without requiring the alternative societies to retain the original support.
Merging coincident replacement types is legitimate: identical types have identical choices, and finite sums of positive binary-rational masses remain positive binary rational. Total mass remains \(1\), and support size is at most \(\tau\).
Every replacement type makes next choice \(b\), so the next aggregate share is exactly \(b\). Thus the two societies provide shares \(0<1/2<1\), satisfying the required strict inequalities.
The empty history at \(t=1\) is handled by a singleton society of mass \(1\). The lemma applies with \(r=1\), so this also covers \(n=1\). It applies through \(r=n\), covering the final day.
The stated piecewise constant density representation is explicit and permits real rectangle coordinates, as the task allows. Society masses retain the required binary-rational form. The prover makes no running-time claim, so no dependence on valuation encoding or binary data length is left unjustified.
No additional clarification or repair is required. The result settles the existence question, but does not classify computational complexity.
⟨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.