A successful prefix cut adds at most one Cut and one Eval per participating agent
ProvedEnvyFreeCake104.Divide.prefixCut_query_bound__p2m_c286858a_9e65_4696_8505_9d74071d7a32_a1cake-cuttingenvy-freefair-divisionp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Every successful execution of prefixCut adds at most N.card + 1 query events to its incoming transcript. No validity, well-formedness, positivity, or participation assumptions are needed for this execution-count bound.
Preamble
import Definitions.Def_EnvyFreeCake104_Divide_Query open EnvyFreeCake104.Divide
Formal statement
theorem EnvyFreeCake104.Divide.prefixCut_query_bound__p2m_c286858a_9e65_4696_8505_9d74071d7a32_a1
{ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(i : ι) (Q : Piece) (w : ℝ) (s : Rec ι)
(o : ChoiceOracle ι) (tr₀ : List (Event ι))
(p : Pos) (s' : Rec ι) (tr : List (Event ι))
(hrun : Prog.run V o ((prefixCut N i Q w).run s) tr₀ =
some ((p, s'), tr)) :
queryCount tr ≤ queryCount tr₀ + (N.card + 1) := 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.6, Lemma 3 (restated p.10)