AFTD Auto-Formalizing Theoretical Domains

is_alpha_efx_goods

def

An allocation of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j, and every good g in j's bundle, alpha times i's value for j's bundle without g is at most i's value for i's own bundle.

Statement

def is_alpha_efx_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop
Defined in
arXiv:2610.34625, Sec. 4
Verified
02 Nov 2026
Axioms
none listed
Built on 2
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 3
  • op819_has_online_single_high_alpha_monoIf a deterministic online algorithm guarantees a beta-EFX allocation for n agents and m goods under single-high valuations with ratio R >=…
  • op819_single_high_efx_one_goodFor any number of agents $n \ge 1$, $m = 1$ good, and parameter $R \ge 0$, there exists a deterministic online algorithm that achieves a…
  • has_online_single_high_alpha_efxThere exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every…

Read back from the Lean

Given natural numbers m and n, a valuation profile u : Fin n → Fin m → ℝ, a real parameter α, and an allocation of goods to agents σ : Fin m → Fin n, the predicate asserts that: For all agents i, j : Fin n such that i ≠ j, and for every good g in agent j's bundle (i.e., g ∈ bundle_of σ j), α times agent i's additive valuation of agent j's bundle with g removed is less than or equal to agent i's additive valuation of their own bundle (bundle_of σ i).

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 of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j, and every good g in j's bundle, alpha times i's value for j's bundle without g is at most i's value for i's own bundle. -/
def is_alpha_efx_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (α : ℝ) (σ : Fin m → Fin n) : Prop := ∀ i j : Fin n, i ≠ j → ∀ g ∈ bundle_of σ j,
    α * additive_valuation (u i) ((bundle_of σ j).erase g) ≤ additive_valuation (u i) (bundle_of σ i)
See it in the graphDiscuss this resultChallenge it