AFTD Auto-Formalizing Theoretical Domains

guarantees_alpha_eefx

def

An algorithm alg guarantees alpha-EEFX for n agents under error factor ρ if for every m : ℕ, all nonnegative valuations v and all predictions a_hat that are overestimates with factor ρ, the allocation alg m a_hat v is alpha-EEFX.

Statement

def guarantees_alpha_eefx (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n))
    (ρ α : ℝ) : Prop
Defined in
arXiv:2610.34625 Sec. 6.1
Verified
27 Oct 2026
Axioms
none listed
Built on 3
  • is_overestimate_predictionPredictions a_hat : Fin n → Fin m → ℝ are overestimates of valuations v : Fin n → Fin m → ℝ with error factor ρ if for every agent i : Fin…
  • is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 2

Read back from the Lean

guarantees_alpha_eefx n alg ρ α asserts that for a fixed number of agents n, an allocation algorithm alg (which takes the number of goods m, a predicted valuation profile a_hat, and a true valuation profile v, and outputs an allocation Fin m → Fin n), and real parameters ρ and α: For every number of goods m : ℕ, and for all valuation profiles v, a_hat : Fin n → Fin m → ℝ: If: 1. Every valuation in v is non-negative (∀ i g, 0 ≤ v i g), and 2. a_hat is a ρ-overestimate prediction of v in the sense that for every agent i : Fin n and rank r : Fin m, the r-th entry of v i sorted non-decreasingly is bounded above by the r-th entry of a_hat i sorted non-decreasingly, which in turn is bounded above by ρ times the r-th entry of v i sorted non-decreasingly, Then: The allocation σ = alg m a_hat v is an α-EEFX allocation for the additive valuations induced by v. That is, for every agent i : Fin n, agent i's assigned bundle S = {g : Fin m | σ g = i} is an α-EEFX bundle: there exists a partition of all remaining goods Finset.univ \ S into n - 1 pairwise disjoint subsets Y : Fin (n - 1) → Finset (Fin m) such that for every p : Fin (n - 1) and every good g ∈ Y p, α * (∑ j ∈ (Y p).erase g, v i j) ≤ ∑ j ∈ S, v i j.

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 algorithm guarantees alpha-EEFX under error factor rho if its allocations are alpha-EEFX for all valid instances. -/
def guarantees_alpha_eefx (n : ℕ) (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n))
    (ρ α : ℝ) : Prop :=
  ∀ (m : ℕ) (v a_hat : Fin n → Fin m → ℝ),
    (∀ i g, 0 ≤ v i g) →
    is_overestimate_prediction ρ v a_hat →
    is_alpha_eefx_allocation (fun i => additive_valuation (v i)) α (alg m a_hat v)
See it in the graphDiscuss this resultChallenge it