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.
- ef1cost_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of
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_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]