is_alpha_eefx_bundle
A bundle S of goods is alpha-EEFX for an agent with valuation v if there exists a partition of the remaining goods into n-1 parts such that the agent's value for S is at least alpha times her value for any part after removing any item from it.
Statement
def is_alpha_eefx_bundle {m : ℕ} (v : Finset (Fin m) → ℝ) (n : ℕ) (α : ℝ) (S : Finset (Fin m)) : Prop
- Defined in
- arXiv:2610.34625 Def. 2.1
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 3
- eefx_bundle_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…
- is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
- op562_not_consistent_eefx_of_ge_three_halvesFor any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive…
Read back from the Lean
Given an implicit natural number m, a valuation function v : Finset (Fin m) → ℝ, a natural number n, a real number α, and a bundle S : Finset (Fin m), the predicate is_alpha_eefx_bundle v n α S asserts that there exists a family of bundles Y : Fin (n - 1) → Finset (Fin m) such that:
1. The bundles are pairwise disjoint: for all p, q : Fin (n - 1), if p ≠ q then Disjoint (Y p) (Y q);
2. The union of all bundles in Y is the complement of S: Finset.biUnion Finset.univ Y = Finset.univ \ S; and
3. For every agent p : Fin (n - 1) and every item g ∈ Y p, α * v ((Y p).erase g) ≤ v S.
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
/-- A bundle S is alpha-EEFX for an agent if there is an (n-1)-partition of G \ S such that v(S) >= alpha * v(Y_p \ {g}) for all parts and items. -/ def is_alpha_eefx_bundle {m : ℕ} (v : Finset (Fin m) → ℝ) (n : ℕ) (α : ℝ) (S : Finset (Fin m)) : Prop := ∃ Y : Fin (n - 1) → Finset (Fin m), (∀ p q : Fin (n - 1), p ≠ q → Disjoint (Y p) (Y q)) ∧ (Finset.biUnion Finset.univ Y = Finset.univ \ S) ∧ ∀ p : Fin (n - 1), ∀ g ∈ Y p, α * v ((Y p).erase g) ≤ v S