ef1cost_ef1_of_pair
lemmaverified
Bridging: an EF1 two-bundle split gives an EF1 allocation in the sense of is_ef1_chores.
Statement
lemma ef1cost_ef1_of_pair {m : ℕ} (c : Fin 2 → Fin m → ℝ) (p q : Fin 2) (hpq : p ≠ q) (Y : Finset (Fin m)) (hp : ef1cost_pair_ok (c p) Y Yᶜ) (hq : ef1cost_pair_ok (c q) Yᶜ Y) : is_ef1_chores c (fun j => if j ∈ Y then p else q)
- 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 4
- ef1cost_bundle_iteFor two agents, the allocation giving the items of Y to p and the rest to q has bundles Y and its complement.
- ef1cost_fin_two_casesWith two agents p != q, every agent is p or q.
- ef1cost_pair_okTwo-bundle EF1 condition: the owner of
A, with costsw, is EF1 towardsB. - 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.
- Used by 3
- ef1cost_from_coreFrom the core lemma to an EF1 allocation within
3 - 2√2of the optimum. - 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.
/-- Bridging: an EF1 two-bundle split gives an EF1 allocation in the sense of `is_ef1_chores`. -/lemma ef1cost_ef1_of_pair {m : ℕ} (c : Fin 2 → Fin m → ℝ) (p q : Fin 2) (hpq : p ≠ q) (Y : Finset (Fin m)) (hp : ef1cost_pair_ok (c p) Y Yᶜ) (hq : ef1cost_pair_ok (c q) Yᶜ Y) : is_ef1_chores c (fun j => if j ∈ Y then p else q) := by obtain ⟨hbp, hbq⟩ := ef1cost_bundle_ite p q hpq Y intro i j by_cases hij : i = j · subst hij left exact le_refl _ rcases ef1cost_fin_two_cases p q hpq i with hi | hi <;> rcases ef1cost_fin_two_cases p q hpq j with hj | hj · exact absurd (hi.trans hj.symm) hij · rw [hi, hj, hbp, hbq]; exact hp · rw [hi, hj, hbp, hbq]; exact hq · exact absurd (hi.trans hj.symm) hij