AFTD Auto-Formalizing Theoretical Domains

is_alpha_ef1_goods

def

An allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j with j's bundle nonempty, there exists a good g in j's bundle such that alpha times i's value for j's bundle without g is at most i's value for i's own bundle.

Statement

def is_alpha_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop
Defined in
arXiv:2610.34625 Sec. 2.1
Verified
27 Oct 2026
Axioms
none listed
Built on 2
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 5

Read back from the Lean

Given implicit natural numbers $m$ and $n$, a utility profile $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, a real parameter $\alpha : \mathbb{R}$, and an allocation $\sigma : \text{Fin } m \to \text{Fin } n$, is_alpha_ef1_goods asserts that for all agents $i, j : \text{Fin } n$ such that $i \neq j$, if agent $j$'s assigned bundle bundle_of σ j is nonempty, then there exists an item $g \in \text{bundle_of } \sigma\ j$ such that $\alpha$ times the additive valuation by agent $i$ of agent $j$'s bundle with $g$ removed is less than or equal to the additive valuation by agent $i$ of their own bundle bundle_of σ 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 σ is α-EF1 for additive valuations u if for all distinct agents i ≠ j with non-empty bundle A_j, some item g in A_j satisfies α * u_i(A_j \ {g}) ≤ u_i(A_i). -/
def is_alpha_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop :=
  ∀ (i j : Fin n), i ≠ j → (bundle_of σ j).Nonempty →
    ∃ g ∈ bundle_of σ j, α * additive_valuation (u i) ((bundle_of σ j).erase g) ≤
      additive_valuation (u i) (bundle_of σ i)
See it in the graphDiscuss this resultChallenge it