online_ef1_approximation_ratio_le_one
For any number of agents n, the online EF1 approximation ratio is at most 1.
Statement
theorem online_ef1_approximation_ratio_le_one (n : ℕ) :
online_ef1_approximation_ratio n ≤ 1- Source
- step towards op561_tight_ef1_factor_four_agents
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- online_ef1_approximation_ratioFor n agents, the online EF1 approximation ratio is the supremum of all ratios alpha in [0, 1] for which there exists a deterministic…
- 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…
The proof, explained
The online EF1 approximation ratio for n agents is defined as the supremum of the set of α ∈ [0, 1] for which an online α-EF1 algorithm exists. Applying `Real.sSup_le`, the supremum is bounded by 1 provided that every member of the set is at most 1 and 0 ≤ 1. The first condition holds immediately from the definition of the set, and the second is trivial arithmetic.
To show that the online EF1 approximation ratio is at most 1, it suffices to show that every element in its defining set is at most 1 and that 0 ≤ 1.
By definition, `online_ef1_approximation_ratio n` is the supremum of the set of values α ∈ ℝ satisfying 0 ≤ α ≤ 1 for which an online α-EF1 algorithm exists. By `Real.sSup_le`, bounding the supremum by 1 reduces to checking that 1 is an upper bound for all members of the set and that 0 ≤ 1.
uses
Real.sSup_leunfold online_ef1_approximation_ratio apply Real.sSup_le
Every element in the defining set is at most 1.
Let x be any element in the set. By definition of the set, x satisfies the conjunction 0 ≤ x ∧ x ≤ 1 ∧ has_online_alpha_ef1_algorithm n x, from which the upper bound x ≤ 1 follows directly.
· intro x hx exact hx.2.1
0 ≤ 1 automation
The remaining condition 0 ≤ 1 is verified by basic numerical evaluation (`norm_num`).
· norm_num
Real.sSup_le- For any set of real numbers s and real number a, if every element of s is at most a and 0 ≤ a, then the supremum of s is at most a.
- In Mathlib, the supremum of the empty set of real numbers is defined to be 0 (sSup ∅ = 0), which is why `Real.sSup_le` requires 0 ≤ a to conclude sSup s ≤ a without requiring s to be nonempty.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The online EF1 approximation ratio for any number of agents is at most 1, by definition as the supremum of a subset of [0, 1]. -/theorem online_ef1_approximation_ratio_le_one (n : ℕ) : online_ef1_approximation_ratio n ≤ 1 := by unfold online_ef1_approximation_ratio apply Real.sSup_le · intro x hx exact hx.2.1 · norm_num