AFTD Auto-Formalizing Theoretical Domains

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 2 is bounded by 3 - 2√2.
Used by 1

Lean source view module on GitHub

/-- **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]
See it in the graphDiscuss this resultChallenge it