Dominate keeps the records valid and returns a well-formed aligned residue
ProvedEnvyFreeCake104.Divide.dominate_invariantsRun invariant of Dominate. Let be a set of agents, a well-formed piece (a finite list of pairwise disjoint intervals of ), and a record state that is valid for (§1.3: are recorded points and every recorded cell value of every agent of is her true value) and in which every endpoint of is a recorded point.
Then every successful run of (Algorithm 2, any fuel, any choice oracle, any prior transcript) ends in records that are again valid for , and the residue it returns is a well-formed piece all of whose endpoints are recorded in .
This is the standing convention of §1.3 ("every piece our protocols handle is a union of intervals in the partition determined by 0, 1, and all previously returned Cut points ... subroutine and recursive calls inherit these records"), stated for the residue that Divide (Algorithm 1, Line 8) passes to its recursive call .
import Definitions.Def_EnvyFreeCake104_Divide_Protocols set_option autoImplicit false
namespace EnvyFreeCake104.Divide
/-- Run invariant of Dominate (Algorithm 2) used by the recursion of Divide (p.5): from valid
records in which the cake is aligned, every successful run of `Dominate(N, C)` leaves valid
records, and the returned residue `R` is a well-formed piece aligned with the final records. -/
theorem dominate_invariants {ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(hN : 3 ≤ N.card) (C : Piece) (hC : C.WF) (s : Rec ι) (hs : s.Valid V N)
(hCs : s.Aligned C) (fuel : ℕ) (o : ChoiceOracle ι) (tr₀ : List (Event ι))
(X : ι → Piece) (R : Piece) (E : Finset ι) (s' : Rec ι) (tr : List (Event ι))
(hrun : Prog.run V o ((dominate fuel N C).run s) tr₀ = some (((X, R, E), s'), tr)) :
s'.Valid V N ∧ R.WF ∧ s'.Aligned R := by sorry
end EnvyFreeCake104.Divide