ef1cost_arith
lemmaverified
The arithmetic heart of the upper bound.
Statement
lemma ef1cost_arith (a s t ρ x su ue ρu : ℝ)
(h1 : a + s + t + ρ = 1) (h2 : x + su + ue + ρu = 1)
(hx0 : 0 ≤ x) (hxa : x ≤ a) (hs0 : 0 ≤ s) (hρ0 : 0 ≤ ρ)
(ht : 0 < t) (hue : t ≤ ue)
(hF4 : su * t ≤ ue * s) (hF5 : ue * ρ ≤ ρu * t) (hF6 : a + s < ρ) :
x + su ≤ ρu ∧ (ue + su) - (t + s) ≤ 3 - 2 * Real.sqrt 2- 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_coreCore lemma (greedy transfer by cost ratio). Agent
P(costsu) holdsX, agentQ(costsv) holdsXᶜ; every chore is held by an…
- ef1cost_coreCore lemma (greedy transfer by cost ratio). Agent
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.
/-- The arithmetic heart of the upper bound. -/lemma ef1cost_arith (a s t ρ x su ue ρu : ℝ) (h1 : a + s + t + ρ = 1) (h2 : x + su + ue + ρu = 1) (hx0 : 0 ≤ x) (hxa : x ≤ a) (hs0 : 0 ≤ s) (hρ0 : 0 ≤ ρ) (ht : 0 < t) (hue : t ≤ ue) (hF4 : su * t ≤ ue * s) (hF5 : ue * ρ ≤ ρu * t) (hF6 : a + s < ρ) : x + su ≤ ρu ∧ (ue + su) - (t + s) ≤ 3 - 2 * Real.sqrt 2 := by have ha0 : 0 ≤ a := le_trans hx0 hxa have hue0 : 0 ≤ ue := le_trans ht.le hue constructor · have k1 : ue * (a + s) ≤ ue * ρ := mul_le_mul_of_nonneg_left hF6.le hue0 have k2 : t * a ≤ ue * a := mul_le_mul_of_nonneg_right hue ha0 have k3 : t * x ≤ t * a := mul_le_mul_of_nonneg_left hxa ht.le have : t * (x + su) ≤ t * ρu := by nlinarith exact le_of_mul_le_mul_left this ht · set U := ue + su with hU set T := t + s with hT have hT0 : 0 ≤ T := by linarith have hi : U * t ≤ ue * T := by rw [hU, hT]; nlinarith have hUle : U ≤ 1 - ρu := by linarith have hii : U * t ≤ t - ue * ρ := by have := mul_le_mul_of_nonneg_right hUle ht.le nlinarith have hi' := mul_le_mul_of_nonneg_right hi hρ0 have hii' := mul_le_mul_of_nonneg_right hii hT0 have hiii : t * (U * (T + ρ)) ≤ t * T := by nlinarith have hiv : U * (T + ρ) ≤ T := le_of_mul_le_mul_left hiii ht have hTρ : T + ρ = 1 - a := by rw [hT]; linarith rw [hTρ] at hiv have hTa : T ≤ 1 - 2 * a := by rw [hT]; linarith have ha1 : 0 < 1 - a := by linarith have hv : (U - T) * (1 - a) ≤ a * (1 - 2 * a) := by have := mul_le_mul_of_nonneg_right hTa ha0 nlinarith have h2' := Real.sq_sqrt (show (0 : ℝ) ≤ 2 by norm_num) have hsq : a * (1 - 2 * a) ≤ (3 - 2 * Real.sqrt 2) * (1 - a) := by nlinarith [sq_nonneg (2 * a - (2 - Real.sqrt 2))] have : (U - T) * (1 - a) ≤ (3 - 2 * Real.sqrt 2) * (1 - a) := le_trans hv hsq exact le_of_mul_le_mul_right this ha1