AFTD Auto-Formalizing Theoretical Domains

social_cost

def

The social cost of an allocation: the sum over agents of their cost for their own bundle.

Statement

def social_cost {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin 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 2
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
Used by 7
  • ef1cost_from_coreFrom the core lemma to an EF1 allocation within 3 - 2√2 of the optimum.
  • opt_ef1_social_costThe minimum social cost over EF1 allocations.
  • opt_social_costThe optimal social cost: the minimum social cost over all allocations.
  • 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.
  • exists_ef1_social_cost_le_opt_add_two_agentsFor two agents with normalized additive chores, some EF1 allocation has social cost at most the optimum plus 3 - 2 sqrt 2.
  • ef1cost_social_cost_eqThe social cost of an allocation equals the sum over items of the cost of each item to its owner.
  • 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

/-- Social cost of an allocation (arXiv:2410.15738, Sec. 2): `SC(A) = ∑ i, c i (A i)`. -/
def social_cost {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : ℝ :=
  ∑ i, additive_valuation (c i) (bundle_of σ i)
See it in the graphDiscuss this resultChallenge it