AFTD Auto-Formalizing Theoretical Domains

not_forall_cost_of_ef1_ge_one_sub_inv

theoremverifiederratum

It is false that the cost of EF1 is at least 1 - 1/n for every n >= 1 (arXiv:2410.15738, Thm 7, fails at n = 2).

Statement

theorem not_forall_cost_of_ef1_ge_one_sub_inv :
    ¬ ∀ n : ℕ, 1 ≤ n → 1 - 1 / (n : ℝ) ≤ cost_of_ef1 n
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 2
  • 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_lt_one_sub_invThe cost of EF1 for two agents is less than 1 - 1/2.

Read back from the Lean

The declaration not_forall_cost_of_ef1_ge_one_sub_inv asserts the negation of a universal statement: it is NOT the case that for every natural number $n \ge 1$, the cost of EF1 for $n$ agents is at least $1 - 1/n$. Equivalently, there exists some natural number $n \ge 1$ such that $\operatorname{cost\_of\_ef1}(n) < 1 - 1/n$, where $\operatorname{cost\_of\_ef1}(n)$ is defined as the supremum over all chore instances (with any number of chores $m$ and non-negative costs normalized so each agent's total cost for all chores is 1) of the difference between the optimal social cost achievable under an EF1 allocation and the unconstrained optimal social cost.

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

/-- The lower bound `cost_of_ef1 n ≥ 1 - 1/n` of arXiv:2410.15738, Thm. 7, does not hold for all `n ≥ 1`. -/theorem not_forall_cost_of_ef1_ge_one_sub_inv :    ¬ ∀ n : ℕ, 1 ≤ n → 1 - 1 / (n : ℝ) ≤ cost_of_ef1 n := by  intro h  have := h 2 (by norm_num)  have := cost_of_ef1_two_lt_one_sub_inv  linarith
See it in the graphDiscuss this resultChallenge it