AFTD Auto-Formalizing Theoretical Domains

eefx_overestimate_threshold

def

For n agents, the error threshold is the real supremum of all error factors ρ ≥ 1 for which there exists a consistent online algorithm guaranteeing α-EEFX for some α > 0.

Statement

noncomputable def eefx_overestimate_threshold (n : ℕ) : ℝ
Defined in
arXiv:2610.34625 Sec. 7
Verified
27 Oct 2026
Axioms
none listed
Built on 1
  • has_consistent_eefx_algorithmThere exists an online, consistent algorithm alg for n agents and a positive constant α > 0 such that alg guarantees α-EEFX under error…

Read back from the Lean

For a given number of agents n : ℕ, eefx_overestimate_threshold n is defined as the supremum (sSup in ℝ) of the set of all real numbers ρ such that: 1. 1 ≤ ρ, and 2. There exists an allocation algorithm alg and a strictly positive approximation factor α > 0 such that: - **Online condition**: For every item count m : ℕ, predicted valuation a_hat, actual valuations v and v', and item t : Fin m, if v and v' agree on all agents for all items s ≤ t, then alg m a_hat v t = alg m a_hat v' t. - **Consistency**: For every item count m : ℕ, non-negative valuation v (i.e. ∀ i g, 0 ≤ v i g), and prediction a_hat, if a_hat is an exact prediction of v (meaning sorted_tuple (a_hat i) = sorted_tuple (v i) for all i : Fin n), then the allocation alg m a_hat v is a 1-EEFX allocation with respect to the additive valuations induced by v (meaning for every agent i : Fin n, is_alpha_eefx_bundle holds for agent i's additive valuation, n, approximation ratio 1, and bundle_of (alg m a_hat v) i). - **Robustness / Guarantee under ρ-overestimate**: For every item count m : ℕ, non-negative valuation v, and prediction a_hat, if a_hat is a ρ-overestimate of v (meaning for every agent i : Fin n and item rank r : Fin m, sorted_tuple (v i) r ≤ sorted_tuple (a_hat i) r ≤ ρ * sorted_tuple (v i) r), then the allocation alg m a_hat v is an α-EEFX allocation with respect to the additive valuations induced by v (meaning for every agent i : Fin n, is_alpha_eefx_bundle holds for agent i's additive valuation, n, approximation ratio α, and bundle_of (alg m a_hat v) 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

/-- The supremum of error factors rho >= 1 admitting a consistent online algorithm guaranteeing alpha-EEFX for some alpha > 0. -/
noncomputable def eefx_overestimate_threshold (n : ℕ) : ℝ :=
  sSup {ρ : ℝ | 1 ≤ ρ ∧ has_consistent_eefx_algorithm n ρ}
See it in the graphDiscuss this resultChallenge it