AFTD Auto-Formalizing Theoretical Domains

opt_ef1_social_cost

def

The minimum social cost over EF1 allocations.

Statement

noncomputable def opt_ef1_social_cost {m n : ℕ} (c : Fin n → Fin m → ℝ) : ℝ
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 2
  • is_ef1_choresEF1 for chores with additive costs: whenever agent i envies agent j, removing some chore from i's own bundle removes the envy.
  • social_costThe social cost of an allocation: the sum over agents of their cost for their own bundle.
Used by 5
  • ef1_gap_set_two_agents_leThe set of gaps whose supremum is cost_of_ef1 2 is bounded by 3 - 2√2.
  • ef1_gap_le_two_agentsFor two agents with normalized additive chores, the best EF1 social cost exceeds the optimal social cost by at most 3 - 2 sqrt 2.
  • one_sixth_le_cost_of_ef1_twoThe cost of EF1 for two agents is at least 1/6.
  • 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…
  • ef1_cost_gap_instance_specIn the instance (0, 1/2, 1/2), (1/3 - 2d, 1/3 + d, 1/3 + d) with 0 < d <= 1/6, the optimal social cost is 2/3 + 2d and the best EF1 social…

Lean source view module on GitHub

/-- `min_{A ∈ EF1(I)} SC(A)`: the minimum social cost over EF1 allocations (arXiv:2410.15738, Def. 4 with `P` = EF1). -/
noncomputable def opt_ef1_social_cost {m n : ℕ} (c : Fin n → Fin m → ℝ) : ℝ :=
  sInf (social_cost c '' {σ | is_ef1_chores c σ})
See it in the graphDiscuss this resultChallenge it