ef1cost_pair_ok
def
Two-bundle EF1 condition: the owner of A, with costs w, is EF1 towards B.
Statement
def ef1cost_pair_ok {m : ℕ} (w : Fin m → ℝ) (A B : 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
- Used by 5
- 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.
- ef1cost_coreCore lemma (greedy transfer by cost ratio). Agent
P(costsu) holdsX, agentQ(costsv) holdsXᶜ; every chore is held by an… - ef1cost_stageA stage of the greedy transfer:
S(moved from the complement ofX) still leaves the donor non-EF1, and every moved item has cost ratio… - ef1cost_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of
is_ef1_chores.
- ef1cost_from_coreFrom the core lemma to an EF1 allocation within
Lean source view module on GitHub
/-- Two-bundle EF1 condition: the owner of `A`, with costs `w`, is EF1 towards `B`. -/ def ef1cost_pair_ok {m : ℕ} (w : Fin m → ℝ) (A B : Finset (Fin m)) : Prop := ∑ j ∈ A, w j ≤ ∑ j ∈ B, w j ∨ ∃ e ∈ A, ∑ j ∈ A, w j - w e ≤ ∑ j ∈ B, w j