not_forall_cost_of_ef1_ge_one_sub_inv
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
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 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