is_alpha_efk_allocation
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)