AFTD Auto-Formalizing Theoretical Domains

is_alpha_efx_chores

def

An allocation σ of m chores among n agents is α-EFX under additive costs c if for every pair of distinct agents i and j, and every chore e in i's bundle bundle_of σ i, agent i's cost for bundle_of σ i minus e (additive_valuation (c i) (bundle_of σ i) - c i e) is at most α times agent i's cost for j's bundle (additive_valuation (c i) (bundle_of σ j)).

Statement

def is_alpha_efx_chores {m n : ℕ} (α : ℝ) (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
Defined in
scout/2611-00432-online-fair-division-of-chores-with-upgrade-recourse.md:261
Verified
07 Nov 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.

Read back from the Lean

For natural numbers m and n, a real number α, a cost function c : Fin n → Fin m → ℝ, and an item assignment σ : Fin m → Fin n, the predicate asserts that for all agents i and j in Fin n such that i ≠ j, and for every item e in the bundle assigned to i by σ, the additive valuation of i's bundle under c i minus the cost c i e is less than or equal to α times the additive valuation of j's bundle under c i.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An allocation of m chores to n agents is α-EFX under additive costs c if for every pair of distinct agents i and j, and every chore e assigned to i, agent i's cost for her bundle without e is at most α times her cost for j's bundle. -/
def is_alpha_efx_chores {m n : ℕ} (α : ℝ) (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ (i j : Fin n), i ≠ 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