is_ef1_chores
def
EF1 for chores with additive costs: whenever agent i envies agent j, removing some chore from i's own bundle removes the envy.
Statement
def is_ef1_chores {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- Connected EF1 Allocations Exist in Discrete Chore Cutting, arXiv:2609.32545 v1, Sec. 2 (chores on a path, connected bundles, EF1) and Sec. 4 (PO); PO among connected allocations, as usual for connected fair division; formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Built on 2
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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 6
- ef1cost_from_coreFrom the core lemma to an EF1 allocation within
3 - 2√2of the optimum. - opt_ef1_social_costThe minimum social cost over EF1 allocations.
- 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_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of
is_ef1_chores. - ef1_implies_two_sub_one_div_n_mms_choresFor any n ≥ 2 agents with nonnegative additive costs over m indivisible chores, any EF1 allocation satisfies (2 - 1/n)-MMS.
- connected_ef1_po_chores_incompatibleFor chores on a path with additive, strictly positive costs, EF1 and Pareto optimality (among connected allocations) can be incompatible:…
- ef1cost_from_coreFrom the core lemma to an EF1 allocation within
Lean source view module on GitHub
/-- EF1 for chores with additive costs `c`: whenever agent `i` envies `j`, removing some chore from `i`'s own bundle removes the envy. -/ def is_ef1_chores {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ i j, additive_valuation (c i) (bundle_of σ i) ≤ additive_valuation (c i) (bundle_of σ j) ∨ ∃ e ∈ bundle_of σ i, additive_valuation (c i) (bundle_of σ i) - c i e ≤ additive_valuation (c i) (bundle_of σ j)