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
- ef1cost_fin_two_casesWith two agents p != q, every agent is p or q.
- Used by 1
- exists_ef1_social_cost_le_opt_add_two_agentsFor two agents with normalized additive chores, some EF1 allocation has social cost at most the optimum plus 3 - 2 sqrt 2.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _