cost_of_ef1
def
The cost of EF1 for n agents: the supremum over normalized instances of the minimum social cost of an EF1 allocation minus the optimal social cost.
Statement
noncomputable def cost_of_ef1 (n : ℕ) : ℝ
- Defined in
- A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Sec. 2 (normalized additive costs, social cost, Def. 4 cost of fairness); formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Built on 3
- is_normalized_chores_instanceA chores instance is normalized if all costs are nonnegative and every agent's total cost is 1.
- opt_ef1_social_costThe minimum social cost over EF1 allocations.
- opt_social_costThe optimal social cost: the minimum social cost over all allocations.
- Used by 4
- cost_of_ef1_two_lt_one_sub_invThe cost of EF1 for two agents is less than 1 - 1/2.
- one_sixth_le_cost_of_ef1_twoThe cost of EF1 for two agents is at least 1/6.
- cost_of_ef1_two_leThe cost of EF1 for two agents is at most 3 - 2 sqrt 2.
- not_forall_cost_of_ef1_ge_one_sub_invIt 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).
Lean source view module on GitHub
/-- The cost of EF1 with `n` agents (arXiv:2410.15738, Def. 4): the supremum, over all normalised instances (any number `m` of chores), of `min_{A ∈ EF1(I)} SC(A) - OPT(I)`. -/ noncomputable def cost_of_ef1 (n : ℕ) : ℝ := sSup {d : ℝ | ∃ (m : ℕ) (c : Fin n → Fin m → ℝ), is_normalized_chores_instance c ∧ d = opt_ef1_social_cost c - opt_social_cost c}