AFTD Auto-Formalizing Theoretical Domains

has_consistent_eefx_algorithm

def

There exists an online, consistent algorithm alg for n agents and a positive constant α > 0 such that alg guarantees α-EEFX under error factor ρ.

Statement

def has_consistent_eefx_algorithm (n : ℕ) (ρ : ℝ) : Prop
Defined in
arXiv:2610.34625 Sec. 6.2
Verified
27 Oct 2026
Axioms
none listed
Built on 3
  • is_online_algorithmFor an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation…
  • 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…
Used by 2

Read back from the Lean

Given a number of agents n : ℕ and a parameter ρ : ℝ, has_consistent_eefx_algorithm n ρ asserts that there exist: 1. an allocation algorithm alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n), and 2. a real number α > 0, such that all of the following hold: - **Online property (is_online_algorithm)**: For every number of items m : ℕ, every predicted valuation profile a_hat : Fin n → Fin m → ℝ, every pair of true valuation profiles v, v' : Fin n → Fin m → ℝ, and every item t : Fin m: if for all items s ≤ t and all agents i : Fin n, v i s = v' i s, then alg m a_hat v t = alg m a_hat v' t. - **Consistency (is_consistent_algorithm)**: For every m : ℕ, true valuation profile v : Fin n → Fin m → ℝ, and predicted valuation profile a_hat : Fin n → Fin m → ℝ: if all valuations are non-negative (∀ i g, 0 ≤ v i g) and the prediction is exact (for every agent i : Fin n, the sorted tuple of a_hat i equals the sorted tuple of v i), then the allocation σ = alg m a_hat v is a 1-EEFX allocation with respect to the additive valuations induced by v. - **Robustness / α-EEFX Guarantee (guarantees_alpha_eefx)**: For every m : ℕ, true valuation profile v : Fin n → Fin m → ℝ, and predicted valuation profile a_hat : Fin n → Fin m → ℝ: if all valuations are non-negative (∀ i g, 0 ≤ v i g) and a_hat is a ρ-overestimate of v (for all agents i : Fin n and indices r : Fin m, the r-th entry of the sorted tuple of v i is ≤ the r-th entry of the sorted tuple of a_hat i, which in turn is ≤ ρ times the r-th entry of the sorted tuple of v i), then the allocation σ = alg m a_hat v is an α-EEFX allocation with respect to the additive valuations induced by v.

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

/-- There exists a consistent online algorithm guaranteeing alpha-EEFX for some alpha > 0 under error factor rho. -/
def has_consistent_eefx_algorithm (n : ℕ) (ρ : ℝ) : Prop :=
  ∃ (alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)) (α : ℝ),
    0 < α ∧ is_online_algorithm n alg ∧ is_consistent_algorithm n alg ∧ guarantees_alpha_eefx n alg ρ α
See it in the graphDiscuss this resultChallenge it