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
- ef1cost_social_cost_eqThe social cost of an allocation equals the sum over items of the cost of each item to its owner.
- 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.
- is_normalized_chores_instanceA chores instance is normalized if all costs are nonnegative and every agent's total cost is 1.
- opt_ef1_social_costThe minimum social cost over EF1 allocations.
- opt_social_costThe optimal social cost: the minimum social cost over all allocations.
- social_costThe social cost of an allocation: the sum over agents of their cost for their own bundle.
- Used by 1
- ef1_gap_set_two_agents_leThe set of gaps whose supremum is
cost_of_ef1 2is bounded by3 - 2√2.
- ef1_gap_set_two_agents_leThe set of gaps whose supremum is
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.
/-- 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