AFTD Auto-Formalizing Theoretical Domains

cost_of_ef1_two_lt_one_sub_inv

theoremverifiederratum

The cost of EF1 for two agents is less than 1 - 1/2.

Statement

theorem cost_of_ef1_two_lt_one_sub_inv : cost_of_ef1 2 < 1 - 1 / (2 : ℕ)
Corrects
A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Theorem 7 ('the cost of EF1 is at most 1 and at least 1 - 1/n'): false at n = 2, where the cost is at most 3 - 2 sqrt 2 < 1/2; the lower-bound construction needs EF1 among agents 1, 3, ..., n and so a third agent
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • cost_of_ef1_two_leThe cost of EF1 for two agents is at most 3 - 2 sqrt 2.
  • ef1cost_alpha_lt_half3 - 2 sqrt 2 is less than 1/2.
Used by 1

Read back from the Lean

The theorem asserts that for 2 agents ($n = 2$), the value of cost_of_ef1 2 is strictly less than 1 - 1 / (2 : ℕ) (which evaluates to $1 - 1/2 = 1/2$ if the denominator is coerced to ℝ, or $1 - 0 = 1$ if natural number division is performed). Here, cost_of_ef1 2 is the supremum over all numbers of chores $m : ℕ$ and all normalized chore cost matrices $c : \text{Fin } 2 → \text{Fin } m → ℝ$ of the difference between the optimal EF1 social cost and the optimal unconstrained social cost: $\text{opt\_ef1\_social\_cost } c - \text{opt\_social\_cost } c$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- **Refutation of the lower bound in arXiv:2410.15738, Thm. 7, at `n = 2`.** Thm. 7 states "The cost of EF1 is at most 1 and at least 1 - 1/n"; for `n = 2` the cost of EF1 is `≤ 3 - 2√2 < 1/2 = 1 - 1/2`. -/theorem cost_of_ef1_two_lt_one_sub_inv : cost_of_ef1 2 < 1 - 1 / (2 : ℕ) := by  have := cost_of_ef1_two_le  have h := ef1cost_alpha_lt_half  push_cast  linarith
See it in the graphDiscuss this resultChallenge it