AFTD Auto-Formalizing Theoretical Domains

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
Used by 4

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}
See it in the graphDiscuss this resultChallenge it