ef1cost_stage
def
A stage of the greedy transfer: S (moved from the complement of X) still leaves the donor non-EF1, and every moved item has cost ratio u/v at most that of every remaining one.
Statement
def ef1cost_stage {m : ℕ} (u v : Fin m → ℝ) (X S : Finset (Fin m)) : Prop
- 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
- none listed
- Built on 1
- ef1cost_pair_okTwo-bundle EF1 condition: the owner of
A, with costsw, is EF1 towardsB.
- ef1cost_pair_okTwo-bundle EF1 condition: the owner of
- Used by 1
- ef1cost_coreCore lemma (greedy transfer by cost ratio). Agent
P(costsu) holdsX, agentQ(costsv) holdsXᶜ; every chore is held by an…
- ef1cost_coreCore lemma (greedy transfer by cost ratio). Agent
Lean source view module on GitHub
/-- A stage of the greedy transfer: `S` (moved from the complement of `X`) still leaves the donor non-EF1, and every moved item has cost ratio `u/v` at most that of every remaining one. -/ def ef1cost_stage {m : ℕ} (u v : Fin m → ℝ) (X S : Finset (Fin m)) : Prop := S ⊆ Xᶜ ∧ ¬ ef1cost_pair_ok v (Xᶜ \ S) (X ∪ S) ∧ ∀ e ∈ S, ∀ f ∈ Xᶜ \ S, u e * v f ≤ u f * v e