eefx_overestimate_threshold
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 ρ}