ef1_gap_set_two_agents_le
theoremverified
The set of gaps whose supremum is cost_of_ef1 2 is bounded by 3 - 2√2.
Statement
theorem ef1_gap_set_two_agents_le :
∀ d ∈ {d : ℝ | ∃ (m : ℕ) (c : Fin 2 → Fin m → ℝ), is_normalized_chores_instance c ∧
d = opt_ef1_social_cost c - opt_social_cost c}, d ≤ 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- Built on 4
- ef1_gap_le_two_agentsFor two agents with normalized additive chores, the best EF1 social cost exceeds the optimal social cost by at most 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.
- Used by 2
- one_sixth_le_cost_of_ef1_twoThe cost of EF1 for two agents is at least 1/6.
- cost_of_ef1_two_leThe cost of EF1 for two agents is at most 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.
/-- The set of gaps whose supremum is `cost_of_ef1 2` is bounded by `3 - 2√2`. -/theorem ef1_gap_set_two_agents_le : ∀ d ∈ {d : ℝ | ∃ (m : ℕ) (c : Fin 2 → Fin m → ℝ), is_normalized_chores_instance c ∧ d = opt_ef1_social_cost c - opt_social_cost c}, d ≤ 3 - 2 * Real.sqrt 2 := by rintro d ⟨m, c, hc, rfl⟩ exact ef1_gap_le_two_agents c hc