AFTD Auto-Formalizing Theoretical Domains

ef1_gap_le_two_agents

theoremverifiedoriginal

For two agents with normalized additive chores, the best EF1 social cost exceeds the optimal social cost by at most 3 - 2 sqrt 2.

Statement

theorem ef1_gap_le_two_agents {m : ℕ} (c : Fin 2 → Fin m → ℝ)
    (hc : is_normalized_chores_instance c) :
    opt_ef1_social_cost c - opt_social_cost c ≤ 3 - 2 * Real.sqrt 2
Related work
operator (Claude), 2026-10-03: the cost of EF1 for two agents lies in [1/6, 3 - 2 sqrt 2], refuting the lower bound 1 - 1/n of arXiv:2410.15738 v1, Thm 7, at n = 2 (its construction needs a third agent)
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 1

Lean source view module on GitHub

/-- For two agents, the gap `min_{EF1} SC - OPT` of every normalised instance is at most `3 - 2√2`. -/theorem ef1_gap_le_two_agents {m : ℕ} (c : Fin 2 → Fin m → ℝ)    (hc : is_normalized_chores_instance c) :    opt_ef1_social_cost c - opt_social_cost c ≤ 3 - 2 * Real.sqrt 2 := by  obtain ⟨σ, hσ, hle⟩ := exists_ef1_social_cost_le_opt_add_two_agents c hc  have hnn : ∀ τ, 0 ≤ social_cost c τ := by    intro τ    rw [ef1cost_social_cost_eq]    exact Finset.sum_nonneg (fun j _ => hc.1 _ _)  have h1 : opt_ef1_social_cost c ≤ social_cost c σ := by    refine csInf_le ⟨0, ?_⟩ ⟨σ, hσ, rfl⟩    rintro _ ⟨τ, -, rfl⟩    exact hnn τ  have h2 : social_cost c σ - (3 - 2 * Real.sqrt 2) ≤ opt_social_cost c :=    le_ciInf (fun τ => by linarith [hle τ])  linarith
See it in the graphDiscuss this resultChallenge it