Prefix cuts succeed and retain the largest admissible suffix
ProvedEnvyFreeCake104.Divide.prefixCut_maximal_suffix__p2m_28b14736_b9c5_4b5f_8ea1_07aaaeb21183_a2cake-cuttingenvy-freefair-divisionp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
For valid records, a participating cutter, an aligned well-formed piece Q, and 0 ≤ w ≤ Vᵢ(Q), prefixCut succeeds from any initial transcript. It preserves valid records and recorded points, produces aligned well-formed prefix and suffix of the prescribed values, and retains every suffix whose value is at most Vᵢ(Q)−w.
Preamble
import Definitions.Def_EnvyFreeCake104_Divide_Protocols open EnvyFreeCake104.Divide set_option autoImplicit false
Formal statement
theorem EnvyFreeCake104.Divide.prefixCut_maximal_suffix__p2m_28b14736_b9c5_4b5f_8ea1_07aaaeb21183_a2
{ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(i : ι) (hi : i ∈ N) (Q : Piece) (hQ : Q.WF)
(s : Rec ι) (hs : s.Valid V N) (hQs : s.Aligned Q)
(w : ℝ) (hw : 0 ≤ w) (hwQ : w ≤ (V i).value Q.toSet)
(o : ChoiceOracle ι) (tr₀ : List (Event ι)) :
∃ (p : Pos) (s' : Rec ι) (tr : List (Event ι)),
Prog.run V o ((prefixCut N i Q w).run s) tr₀ = some ((p, s'), tr) ∧
s'.Valid V N ∧ s.pts ⊆ s'.pts ∧
(prefixList Q p).WF ∧ (suffixList Q p).WF ∧
s'.Aligned (prefixList Q p) ∧ s'.Aligned (suffixList Q p) ∧
(V i).value (prefixList Q p).toSet = w ∧
(V i).value (suffixList Q p).toSet = (V i).value Q.toSet - w ∧
IsSuffix (suffixList Q p).toSet Q ∧
∀ S : Set ℝ, IsSuffix S Q →
(V i).value S ≤ (V i).value Q.toSet - w →
S ⊆ (suffixList Q p).toSet := by sorrySource
Alexandros Psomas, Cutting a Cake For Human Consumption: An Elementary n-agent Cake Cutting Protocol, STOC 2027 submission #104 preprint (arXiv:2610.30370, version not pinned), source.pdf SHA-256 7bef7efb85003ee7fad0a7305c0adb56e7aa074946a39d69e18fd9526572e39f, p.14, Claim 7