Permute keeps records valid and returns well-formed aligned pieces
ProvedEnvyFreeCake104.Divide.permute_invariantsPermute keeps pieces well formed. Let be a set of agents and pairwise disjoint pieces, each a finite list of pairwise disjoint intervals of , all of whose endpoints are recorded in a record state valid for .
Then every successful run of (Algorithm 5; 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 whose endpoints are recorded in ; and the returned residue (the list of all trimmed prefixes) is a well-formed piece whose endpoints are recorded in .
This is the §1.3 convention ("every piece our protocols handle is a union of intervals in the partition determined by 0, 1, and all previously returned Cut points") for the outputs of Permute.
import Definitions.Def_EnvyFreeCake104_Divide_Protocols set_option autoImplicit false
namespace EnvyFreeCake104.Divide
/-- Run invariant of Permute (Algorithm 5): from valid records in which the pairwise disjoint,
well-formed input pieces are 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 permute_invariants {ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(P : ι → Piece) (hP : ∀ i ∈ N, (P i).WF)
(hPdisj : ∀ i ∈ N, ∀ j ∈ N, i ≠ j → Disjoint (P i).toSet (P j).toSet)
(s : Rec ι) (hs : s.Valid V N) (hPs : ∀ i ∈ N, s.Aligned (P i))
(o : ChoiceOracle ι) (tr₀ : List (Event ι))
(Y : ι → Piece) (U : Piece) (s' : Rec ι) (tr : List (Event ι))
(hrun : Prog.run V o ((permute N P).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