AFTD Auto-Formalizing Theoretical Domains

ef1cost_opt_le

lemmaverified

For two agents, giving each item to agent 0 when c_0 <= c_1 and to agent 1 otherwise minimises the item-wise cost sum.

Statement

lemma ef1cost_opt_le {m : ℕ} (c : Fin 2 → Fin m → ℝ) (τ : Fin m → Fin 2) :
    ∑ j, c (if c 0 j ≤ c 1 j then 0 else 1) j ≤ ∑ j, c (τ j) 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
Built on 1
Used by 1

Lean source view module on GitHub

lemma ef1cost_opt_le {m : ℕ} (c : Fin 2 → Fin m → ℝ) (τ : Fin m → Fin 2) :    ∑ j, c (if c 0 j ≤ c 1 j then 0 else 1) j ≤ ∑ j, c (τ j) j := by  refine Finset.sum_le_sum (fun j _ => ?_)  rcases ef1cost_fin_two_cases 0 1 (by decide) (τ j) with h | h <;> rw [h] <;>    split_ifs with hc  · exact le_refl _  · linarith  · exact hc  · exact le_refl _
See it in the graphDiscuss this resultChallenge it