Permute uses at most n+1 queries per counted prefix cut
ProvedEnvyFreeCake104.Divide.permute_query_meter__p2m_285187a7_b6ea_4e38_bca1_5cfc5b97af68_a2cake-cuttingenvy-freefair-divisionp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Every successful Permute execution makes at most n+1 Robertson–Webb queries per increment of the prefix-cut counter, without validity, positivity, or well-formedness assumptions.
Preamble
import Definitions.Def_EnvyFreeCake104_Divide_Protocols open EnvyFreeCake104.Divide
Formal statement
theorem EnvyFreeCake104.Divide.permute_query_meter__p2m_285187a7_b6ea_4e38_bca1_5cfc5b97af68_a2
{ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(P : ι → Piece) (s : Rec ι) (o : ChoiceOracle ι)
(Y : ι → Piece) (R : Piece) (s' : Rec ι) (tr : List (Event ι))
(hrun : exec V o (permute N P) s = some ((Y, R), s', tr)) :
queryCount tr ≤ (N.card + 1) * (s'.prefixCuts - s.prefixCuts) := 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)