cost_of_ef1_two_le
theoremverifiedoriginal
The cost of EF1 for two agents is at most 3 - 2 sqrt 2.
Statement
theorem cost_of_ef1_two_le : cost_of_ef1 2 ≤ 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 4
- 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.
- Used by 1
- cost_of_ef1_two_lt_one_sub_invThe cost of EF1 for two agents is less than 1 - 1/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 cost of EF1 for two agents is at most `3 - 2√2`.** -/theorem cost_of_ef1_two_le : cost_of_ef1 2 ≤ 3 - 2 * Real.sqrt 2 := by refine csSup_le ⟨1 / 6 - 1 / 12, 3, ef1_cost_gap_instance (1 / 12), ?_, ?_⟩ ef1_gap_set_two_agents_le · exact (ef1_cost_gap_instance_spec (1 / 12) (by norm_num) (by norm_num)).1 · rw [(ef1_cost_gap_instance_spec (1 / 12) (by norm_num) (by norm_num)).2.2.2]