AFTD Auto-Formalizing Theoretical Domains

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 costs w, is EF1 towards B.
  • 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.
Used by 1

Lean source view module on GitHub

/-- 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 τ]
See it in the graphDiscuss this resultChallenge it