online_ef1_approximation_ratio_nonneg
For any number of agents n, the online EF1 approximation ratio under exact frequency predictions is nonnegative.
Statement
theorem online_ef1_approximation_ratio_nonneg (n : ℕ) :
0 ≤ online_ef1_approximation_ratio n- Source
- arXiv:2610.34625
- Verified
- 30 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…
Read back from the Lean
For every natural number n, the online EF1 approximation ratio for n agents is greater than or equal to 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The online EF1 approximation ratio is defined as the supremum of the set of values α ∈ [0, 1] for which an online α-EF1 algorithm exists under exact frequency predictions. By Real.sSup_nonneg, the supremum of a set of real numbers is nonnegative whenever all of its elements are nonnegative. Because the condition 0 ≤ α is explicitly required by the definition of the set, the result follows immediately.
It suffices to show that every element in the set defining the online EF1 approximation ratio is nonnegative.
By definition, online_ef1_approximation_ratio n is the supremum of the set of real numbers α such that 0 ≤ α ≤ 1 and an online α-EF1 algorithm exists. By Real.sSup_nonneg, the supremum of any set in ℝ is nonnegative provided all of its members are nonnegative, reducing the goal to showing that every element in this set is at least 0.
uses
Real.sSup_nonnegunfold online_ef1_approximation_ratio apply Real.sSup_nonneg
Every element of the set is nonnegative.
Let x be an arbitrary element of the set. Membership in {α | 0 ≤ α ∧ α ≤ 1 ∧ has_online_alpha_ef1_algorithm n α} directly includes the condition 0 ≤ x as its first conjunct, which establishes the claim.
intro x hx exact hx.1
Real.sSup_nonneg- If every element of a set of real numbers is nonnegative, then the supremum of the set is also nonnegative.
- In Mathlib's conditionally complete lattice structure on ℝ, the supremum of the empty set is defined to be 0. Consequently, Real.sSup_nonneg does not require the set 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 under exact frequency predictions is always nonnegative. -/theorem online_ef1_approximation_ratio_nonneg (n : ℕ) : 0 ≤ online_ef1_approximation_ratio n := by unfold online_ef1_approximation_ratio apply Real.sSup_nonneg intro x hx exact hx.1