Core keeps records valid and returns well-formed aligned pieces
ProvedEnvyFreeCake104.Divide.core_invariantscake-cuttingenvy-freefair-divisionquery-complexity
Core keeps pieces well formed. Let be a set of agents, a designated cutter, and a well-formed piece (a finite list of pairwise disjoint intervals of ) whose endpoints are recorded in a record state that is valid for .
Then every successful run of (Algorithm 3; any choice oracle, any prior transcript) ending in records satisfies: is valid for , every point recorded in is recorded in , every returned bundle () is a well-formed piece with endpoints recorded in , and so is the returned residue .
This is the §1.3 convention for the outputs of Core, used whenever Dominate passes Core's outputs to Repair or to a later Core call.
Preamble
import Definitions.Def_EnvyFreeCake104_Divide_Protocols set_option autoImplicit false
Formal statement
namespace EnvyFreeCake104.Divide
/-- Run invariant of Core (Algorithm 3): from valid records in which the well-formed cake is
aligned, every successful run keeps the records valid, only adds recorded points, and returns
well-formed aligned bundles and a well-formed aligned residue. -/
theorem core_invariants {ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(hN : 2 ≤ N.card) (c : ι) (hc : c ∈ N) (C : Piece) (hC : C.WF)
(s : Rec ι) (hs : s.Valid V N) (hCs : s.Aligned C)
(o : ChoiceOracle ι) (tr₀ : List (Event ι))
(Y : ι → Piece) (U : Piece) (s' : Rec ι) (tr : List (Event ι))
(hrun : Prog.run V o ((core N c C).run s) tr₀ = some (((Y, U), s'), tr)) :
s'.Valid V N ∧ s.pts ⊆ s'.pts ∧ (∀ i ∈ N, (Y i).WF ∧ s'.Aligned (Y i)) ∧
U.WF ∧ s'.Aligned U := by sorry
end EnvyFreeCake104.Divide
Source
Alexandros Psomas, Cutting a Cake For Human Consumption: An Elementary n-agent Cake Cutting Protocol, arXiv:2610.30370v1, §1.3 (pp.4-5); Algorithm 3 (p.10)