AFTD Auto-Formalizing Theoretical Domains

ef1cost_shift

lemmaverified

For two agents and X inside Y, giving Y (instead of X) to agent p and the rest to q raises the item-wise cost sum by the sum over Y minus X of c_p - c_q.

Statement

lemma ef1cost_shift {m : ℕ} (c : Fin 2 → Fin m → ℝ) (p q : Fin 2) (X Y : Finset (Fin m))
    (hXY : X ⊆ Y) :
    ∑ j, c (if j ∈ Y then p else q) j =
      ∑ j, c (if j ∈ X then p else q) j + ∑ j ∈ Y \ X, (c p j - c q j)
Source
step towards cost_of_ef1_two_le / one_sixth_le_cost_of_ef1_two (cost of EF1 for two agents lies in [1/6, 3 - 2 sqrt 2]; A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Thm 7 states the lower bound 1 - 1/n, whose construction needs n >= 3)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • ef1cost_from_coreFrom the core lemma to an EF1 allocation within 3 - 2√2 of the optimum.

Lean source view module on GitHub

lemma ef1cost_shift {m : ℕ} (c : Fin 2 → Fin m → ℝ) (p q : Fin 2) (X Y : Finset (Fin m))    (hXY : X ⊆ Y) :    ∑ j, c (if j ∈ Y then p else q) j =      ∑ j, c (if j ∈ X then p else q) j + ∑ j ∈ Y \ X, (c p j - c q j) := by  classical  rw [← Fintype.sum_ite_mem (Y \ X), ← Finset.sum_add_distrib]  refine Finset.sum_congr rfl (fun j _ => ?_)  by_cases hX : j ∈ X  · have hY : j ∈ Y := hXY hX    simp [hX, hY]  · by_cases hY : j ∈ Y    · simp [hX, hY]    · simp [hX, hY]
See it in the graphDiscuss this resultChallenge it