AFTD Auto-Formalizing Theoretical Domains

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

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)
See it in the graphDiscuss this resultChallenge it