ef1cost_from_core
lemmaverified
From the core lemma to an EF1 allocation within 3 - 2√2 of the optimum.
Statement
lemma ef1cost_from_core {m : ℕ} (c : Fin 2 → Fin m → ℝ) (p q : Fin 2) (hpq : p ≠ q) (X : Finset (Fin m)) (hopt : ∀ τ : Fin m → Fin 2, ∑ j, c (if j ∈ X then p else q) j ≤ ∑ j, c (τ j) j) (hcore : ∃ Y : Finset (Fin m), X ⊆ Y ∧ ef1cost_pair_ok (c p) Y Yᶜ ∧ ef1cost_pair_ok (c q) Yᶜ Y ∧ ∑ j ∈ Y \ X, (c p j - c q j) ≤ 3 - 2 * Real.sqrt 2) : ∃ σ, is_ef1_chores c σ ∧ ∀ τ, social_cost c σ ≤ social_cost c τ + (3 - 2 * Real.sqrt 2)
- 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 6
- ef1cost_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of
is_ef1_chores. - ef1cost_pair_okTwo-bundle EF1 condition: the owner of
A, with costsw, is EF1 towardsB. - ef1cost_shiftFor two agents and X inside Y, giving Y (instead of X) to agent p and the rest to q raises the item-wise cost sum by the sum over Y minus…
- ef1cost_social_cost_eqThe social cost of an allocation equals the sum over items of the cost of each item to its owner.
- 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.
- ef1cost_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of
- Used by 1
- 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.
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.
/-- From the core lemma to an EF1 allocation within `3 - 2√2` of the optimum. -/lemma ef1cost_from_core {m : ℕ} (c : Fin 2 → Fin m → ℝ) (p q : Fin 2) (hpq : p ≠ q) (X : Finset (Fin m)) (hopt : ∀ τ : Fin m → Fin 2, ∑ j, c (if j ∈ X then p else q) j ≤ ∑ j, c (τ j) j) (hcore : ∃ Y : Finset (Fin m), X ⊆ Y ∧ ef1cost_pair_ok (c p) Y Yᶜ ∧ ef1cost_pair_ok (c q) Yᶜ Y ∧ ∑ j ∈ Y \ X, (c p j - c q j) ≤ 3 - 2 * Real.sqrt 2) : ∃ σ, is_ef1_chores c σ ∧ ∀ τ, social_cost c σ ≤ social_cost c τ + (3 - 2 * Real.sqrt 2) := by obtain ⟨Y, hXY, hp, hq, hcost⟩ := hcore refine ⟨fun j => if j ∈ Y then p else q, ef1cost_ef1_of_pair c p q hpq Y hp hq, fun τ => ?_⟩ rw [ef1cost_social_cost_eq, ef1cost_social_cost_eq, ef1cost_shift c p q X Y hXY] linarith [hopt τ]