ef1cost_social_cost_eq
lemmaverified
The social cost of an allocation equals the sum over items of the cost of each item to its owner.
Statement
lemma ef1cost_social_cost_eq {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) :
social_cost c σ = ∑ j, c (σ j) j- Source
- step towards cost_of_ef1_two_le / one_sixth_le_cost_of_ef1_two (cost of EF1 for two agents lies in [1/6, 3 - 2 sqrt 2]; A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Thm 7 states the lower bound 1 - 1/n, whose construction needs n >= 3)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- social_costThe social cost of an allocation: the sum over agents of their cost for their own bundle.
- Used by 4
- ef1cost_from_coreFrom the core lemma to an EF1 allocation within
3 - 2√2of the optimum. - 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.
- 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…
- ef1cost_from_coreFrom the core lemma to an EF1 allocation within
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.
lemma ef1cost_social_cost_eq {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : social_cost c σ = ∑ j, c (σ j) j := by classical simp only [social_cost, additive_valuation, bundle_of, Finset.sum_filter] rw [Finset.sum_comm] refine Finset.sum_congr rfl (fun j _ => ?_) simp