AFTD Auto-Formalizing Theoretical Domains

is_alpha_eefx_allocation

def

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)
See it in the graphDiscuss this resultChallenge it