AFTD Auto-Formalizing Theoretical Domains

is_alpha_efk_allocation

def

An allocation σ : Fin m → Fin n of m goods among n agents is α-EFk under valuations v : Fin n → Finset (Fin m) → ℝ if for all distinct agents i and j, agent i values her bundle at least α times the value of j's bundle after removing the k most valuable goods for agent i.

Statement

def is_alpha_efk_allocation {m n : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (α : ℝ) (k : ℕ) (σ : Fin m → Fin n) : Prop
Defined in
arXiv:2610.34625, Section 2.1
Verified
29 Oct 2026
Axioms
none listed
Built on 2
  • bundle_remove_k_valueGiven a type of goods α with decidable equality, a valuation function v : Finset α → ℝ, a natural number k : ℕ, and a bundle S : Finset α,…
  • 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 1
  • eefx_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…

Read back from the Lean

Given natural numbers m and n, a valuation function v : Fin n → Finset (Fin m) → ℝ, a real number α, a natural number k, and an item assignment σ : Fin m → Fin n, the predicate asserts that for every pair of distinct agents i, j : Fin n (i ≠ j), the value α multiplied by the infimum of agent i's valuation of agent j's bundle minus any sub-bundle of size at most k is less than or equal to agent i's valuation of their own bundle under σ.

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 α-EFk if for all distinct agents i and j, agent i values her bundle at least α times the value of j's bundle after removing the k most valuable goods for i. -/
def is_alpha_efk_allocation {m n : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (α : ℝ) (k : ℕ) (σ : Fin m → Fin n) : Prop :=
  ∀ (i j : Fin n), i ≠ j → α * bundle_remove_k_value (v i) k (bundle_of σ j) ≤ v i (bundle_of σ i)
See it in the graphDiscuss this resultChallenge it