one_sixth_le_cost_of_ef1_two
theoremverifiedoriginal
The cost of EF1 for two agents is at least 1/6.
Statement
theorem one_sixth_le_cost_of_ef1_two : 1 / 6 ≤ cost_of_ef1 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 7
- cost_of_ef1The cost of EF1 for n agents: the supremum over normalized instances of the minimum social cost of an EF1 allocation minus the optimal…
- ef1_cost_gap_instanceThe two-agent instance with costs (0, 1/2, 1/2) and (1/3 - 2d, 1/3 + d, 1/3 + d).
- ef1_cost_gap_instance_specIn the instance (0, 1/2, 1/2), (1/3 - 2d, 1/3 + d, 1/3 + d) with 0 < d <= 1/6, the optimal social cost is 2/3 + 2d and the best EF1 social…
- ef1_gap_set_two_agents_leThe set of gaps whose supremum is
cost_of_ef1 2is bounded by3 - 2√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.
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 cost of EF1 for two agents is at least `1/6`.** -/theorem one_sixth_le_cost_of_ef1_two : 1 / 6 ≤ cost_of_ef1 2 := by refine _root_.le_of_forall_pos_le_add (fun ε hε => ?_) set δ := min ε (1 / 6) with hδ have hδ0 : 0 < δ := lt_min hε (by norm_num) have hδ1 : δ ≤ 1 / 6 := min_le_right _ _ have hδε : δ ≤ ε := min_le_left _ _ have hmem : 1 / 6 - δ ∈ {d : ℝ | ∃ (m : ℕ) (c : Fin 2 → Fin m → ℝ), is_normalized_chores_instance c ∧ d = opt_ef1_social_cost c - opt_social_cost c} := ⟨3, ef1_cost_gap_instance δ, (ef1_cost_gap_instance_spec δ hδ0 hδ1).1, (ef1_cost_gap_instance_spec δ hδ0 hδ1).2.2.2.symm⟩ have := le_csSup ⟨3 - 2 * Real.sqrt 2, ef1_gap_set_two_agents_le⟩ hmem unfold cost_of_ef1 linarith