AFTD Auto-Formalizing Theoretical Domains

ef1cost_bundle_ite

lemmaverified

For two agents, the allocation giving the items of Y to p and the rest to q has bundles Y and its complement.

Statement

lemma ef1cost_bundle_ite {m : ℕ} (p q : Fin 2) (hpq : p ≠ q) (Y : Finset (Fin m)) :
    bundle_of (fun j => if j ∈ Y then p else q) p = Y ∧
      bundle_of (fun j => if j ∈ Y then p else q) q = Yᶜ
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 1
  • 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 1
  • ef1cost_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of is_ef1_chores.

Lean source view module on GitHub

lemma ef1cost_bundle_ite {m : ℕ} (p q : Fin 2) (hpq : p ≠ q) (Y : Finset (Fin m)) :    bundle_of (fun j => if j ∈ Y then p else q) p = Y ∧      bundle_of (fun j => if j ∈ Y then p else q) q = Yᶜ := by  constructor  · ext j    simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and]    split_ifs with h    · simp [h]    · simp [h, Ne.symm hpq]  · ext j    simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_compl]    split_ifs with h    · simp [h, hpq]    · simp [h]
See it in the graphDiscuss this resultChallenge it