has_consistent_eefx_algorithm
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
- eefx_overestimate_thresholdFor n agents, the error threshold is the real supremum of all error factors ρ ≥ 1 for which there exists a consistent online algorithm…
- op562_not_consistent_eefx_of_ge_three_halvesFor any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive…
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 ρ α