is_alpha_eefx_allocation
An allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
Statement
def is_alpha_eefx_allocation {m n : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- arXiv:2610.34625 Def. 2.1
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 2
- is_alpha_eefx_bundleA 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…
- 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 4
- 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…
- is_consistent_algorithmAn online algorithm alg for n agents is consistent if for every m : ℕ and all nonnegative valuations v and predictions a_hat with exact…
- guarantees_alpha_eefxAn algorithm alg guarantees alpha-EEFX for n agents under error factor ρ if for every m : ℕ, all nonnegative valuations v and all…
- 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
The definition is_alpha_eefx_allocation asserts that an allocation σ : Fin m → Fin n of m items among n agents is an α-EEFX (epistemic envy-free up to any good) allocation with respect to the valuation profile v : Fin n → Finset (Fin m) → ℝ and approximation factor α : ℝ. Specifically, it asserts that for every agent i : Fin n, the bundle allocated to i (the set of items x such that σ x = i) satisfies is_alpha_eefx_bundle. That is, there exists a partition Y : Fin (n - 1) → Finset (Fin m) of the items not allocated to i into n - 1 pairwise disjoint bundles such that for every bundle p : Fin (n - 1) and every item g ∈ Y p, α * (v i (Y p \ {g})) ≤ v i S, where S is agent i's allocated bundle.
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 alpha-EEFX if each agent's bundle is alpha-EEFX for that agent. -/ def is_alpha_eefx_allocation {m n : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop := ∀ i : Fin n, is_alpha_eefx_bundle (v i) n α (bundle_of σ i)