online_ef1_approximation_ratio
For n agents, the online EF1 approximation ratio is the supremum of all ratios alpha in [0, 1] for which there exists a deterministic online algorithm guaranteeing an alpha-EF1 allocation under exact frequency predictions.
Statement
noncomputable def online_ef1_approximation_ratio (n : ℕ) : ℝ
- Defined in
- arXiv:2610.34625 Sec. 5
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- has_online_alpha_ef1_algorithmThere exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and…
- Used by 4
- online_ef1_approximation_ratio_le_oneFor any number of agents n, the online EF1 approximation ratio is at most 1.
- online_ef1_approximation_ratio_nonnegFor any number of agents n, the online EF1 approximation ratio under exact frequency predictions is nonnegative.
- online_ef1_ratio_ge_of_online_algorithmIf alpha lies in [0,1] and some deterministic online algorithm guarantees an alpha-EF1 allocation for n agents under exact frequency…
- op561_exists_of_ratio_gtIf the online EF1 approximation ratio for four agents strictly exceeds (3 - sqrt 5)/2, then there exists an achievable approximation ratio…
Read back from the Lean
Given the number of agents n : ℕ, online_ef1_approximation_ratio n is defined as the supremum (sSup) in ℝ of the set of all α ∈ ℝ such that:
1. 0 ≤ α ≤ 1, and
2. There exists an online allocation algorithm achieving an α-EF1 (envy-free up to one good) guarantee under exact predictions.
Specifically, has_online_alpha_ef1_algorithm n α asserts the existence of a function
alg : ∀ m : ℕ, (Fin n → Fin m → ℝ) → (Fin n → Fin m → ℝ) → (Fin m → Fin n)
such that:
- alg is an online algorithm: for all m : ℕ, prediction matrices a_hat, actual valuation profiles v and v', and item t : Fin m, if v and v' agree on all agents i and all items s ≤ t, then alg m a_hat v t = alg m a_hat v' t (the allocation of item t depends only on m, a_hat, and the valuation of items up to t).
- For all m : ℕ and all valuation profiles v, a_hat : Fin n → Fin m → ℝ:
- if all valuations in v are non-negative (v i g ≥ 0 for all i, g), and
- a_hat is an exact prediction of v in the sense that for each agent i : Fin n, the sorted tuple of a_hat i equals the sorted tuple of v i (i.e., a_hat i is a permutation of v i),
- then the allocation σ = alg m a_hat v is α-EF1 for goods: for every pair of distinct agents i ≠ j, if agent j's bundle σ⁻¹(j) is non-empty, there exists some item g in j's bundle such that
α * (∑_{k ∈ σ⁻¹(j) \ {g}} v i k) ≤ ∑_{k ∈ σ⁻¹(i)} v i k.
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 approximation ratios α ∈ [0, 1] guaranteed by a deterministic online algorithm for n agents under exact frequency predictions. -/ noncomputable def online_ef1_approximation_ratio (n : ℕ) : ℝ := sSup {α : ℝ | 0 ≤ α ∧ α ≤ 1 ∧ has_online_alpha_ef1_algorithm n α}