Repair returns a partial allocation of the residue plus the old bundles
ProvedEnvyFreeCake104.Divide.repair_partitioncake-cuttingenvy-freefair-divisionquery-complexity
Repair allocates part of and returns the rest as residue. Let be a set of agents, , pairwise disjoint well-formed pieces and a well-formed piece disjoint from every , all with endpoints recorded in a record state valid for .
Then every successful run of (Algorithm 4; any choice oracle, any prior transcript) returning bundles and residue satisfies
This is Line 9 of Algorithm 4 ("return allocation and residue "), stated for every run, without the value hypotheses of Lemma 4.
Preamble
import Definitions.Def_EnvyFreeCake104_Divide_Protocols set_option autoImplicit false
Formal statement
namespace EnvyFreeCake104.Divide
/-- Repair (Algorithm 4) returns a partial allocation of `R ∪ ⋃ D_i` with the residue of
Line 9: every successful run returns pairwise disjoint bundles inside `R ∪ ⋃ D_i`, and its
residue is `(R ∪ ⋃ D_i) \ ⋃ W_i`. -/
theorem repair_partition {ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(D : ι → Piece) (R : Piece) (ε : ℝ) (hD : ∀ i ∈ N, (D i).WF) (hR : R.WF)
(hDdisj : ∀ i ∈ N, ∀ j ∈ N, i ≠ j → Disjoint (D i).toSet (D j).toSet)
(hDR : ∀ i ∈ N, Disjoint (D i).toSet R.toSet)
(s : Rec ι) (hs : s.Valid V N) (hDs : ∀ i ∈ N, s.Aligned (D i)) (hRs : s.Aligned R)
(o : ChoiceOracle ι) (tr₀ : List (Event ι))
(W : ι → Piece) (U : Piece) (s' : Rec ι) (tr : List (Event ι))
(hrun : Prog.run V o ((repair N D R ε).run s) tr₀ = some (((W, U), s'), tr)) :
(∀ i ∈ N, ∀ j ∈ N, i ≠ j → Disjoint (W i).toSet (W j).toSet) ∧
(∀ i ∈ N, (W i).toSet ⊆ R.toSet ∪ ⋃ j ∈ N, (D j).toSet) ∧
U.toSet = (R.toSet ∪ ⋃ j ∈ N, (D j).toSet) \ ⋃ i ∈ N, (W i).toSet := by sorry
end EnvyFreeCake104.Divide
Source
Alexandros Psomas, Cutting a Cake For Human Consumption: An Elementary n-agent Cake Cutting Protocol, arXiv:2610.30370v1, Algorithm 4 (p.11), Line 9