Lines 9–11 of Dominate: repeated Core calls shrink the cutter's residue
ProvedEnvyFreeCake104.Divide.shrink_progressThe shrinking loop of Dominate. Let be a set of agents, the cutter, , and a well-formed piece. Let be an envy-free partial allocation of pairwise disjoint well-formed pieces and a well-formed piece disjoint from every , all aligned with valid records (as is ). Suppose that for some
Then for every fuel and every choice oracle, the loop of Lines 9–11 of Dominate ("while : , ") terminates successfully with such that: the records stay valid and only gain points; every and is well formed and aligned; ; the are pairwise disjoint and ; is envy-free; no difference decreases; ; and at most queries are made.
This is the paragraph Repeated Core calls create domination of the proof of Lemma 1: by Lemma 3 the cutter receives exactly of her value of the current residue, so her value of the remaining residue shrinks by a factor at least per call.
import Definitions.Def_EnvyFreeCake104_Divide_Protocols set_option autoImplicit false
namespace EnvyFreeCake104.Divide
/-- Lines 9-11 of Dominate (p.9): repeated Core calls with cutter `i*` on the residue `R'`.
If `K` calls suffice to bring `V_{i*}(R')` below `α V_{i*}(U)` (each call keeps at most a
`(1 - 1/n)` fraction of the cutter's value of the residue), then with fuel at least `K` the
loop terminates; it keeps the allocation envy-free, only enlarges bundles with parts of `R'`,
does not decrease any difference `V_i(W_i) - V_i(W_j)`, leaves `V_{i*}(R'') ≤ α V_{i*}(U)`, and
makes at most `K` Core calls' worth of queries. -/
theorem shrink_progress {ι : Type} [DecidableEq ι] (V : ι → Valuation) (N : Finset ι)
(hN : 2 ≤ N.card) (istar : ι) (hi : istar ∈ N) (α : ℝ) (U : Piece) (hU : U.WF) :
∀ (K fuel : ℕ), K ≤ fuel → ∀ (W : ι → Piece) (R' : Piece) (s : Rec ι)
(o : ChoiceOracle ι) (tr₀ : List (Event ι)),
(∀ i ∈ N, (W i).WF) → R'.WF →
(∀ i ∈ N, ∀ j ∈ N, i ≠ j → Disjoint (W i).toSet (W j).toSet) →
(∀ i ∈ N, Disjoint (W i).toSet R'.toSet) →
EnvyFree V N (fun i => (W i).toSet) →
s.Valid V N → (∀ i ∈ N, s.Aligned (W i)) → s.Aligned R' → s.Aligned U →
(V istar).value R'.toSet * (1 - 1 / (N.card : ℝ)) ^ K ≤ α * (V istar).value U.toSet →
∃ (W' : ι → Piece) (R'' : Piece) (s' : Rec ι) (tr : List (Event ι)),
Prog.run V o ((shrink N istar α U fuel W R').run s) tr₀ =
some (((W', R''), s'), tr) ∧
s'.Valid V N ∧ s.pts ⊆ s'.pts ∧ (∀ i ∈ N, (W' i).WF ∧ s'.Aligned (W' i)) ∧
R''.WF ∧ s'.Aligned R'' ∧
(∀ i ∈ N, (W i).toSet ⊆ (W' i).toSet ∧ (W' i).toSet ⊆ (W i).toSet ∪ R'.toSet) ∧
(∀ i ∈ N, ∀ j ∈ N, i ≠ j → Disjoint (W' i).toSet (W' j).toSet) ∧
R''.toSet = R'.toSet \ ⋃ i ∈ N, (W' i).toSet ∧
EnvyFree V N (fun i => (W' i).toSet) ∧
(∀ i ∈ N, ∀ j ∈ N, (V i).value (W i).toSet - (V i).value (W j).toSet ≤
(V i).value (W' i).toSet - (V i).value (W' j).toSet) ∧
(V istar).value R''.toSet ≤ α * (V istar).value U.toSet ∧
queryCount tr ≤ queryCount tr₀ + K * (N.card ^ 3 * (N.card.factorial) ^ 2) := by sorry
end EnvyFreeCake104.Divide