online_ef1_ratio_ge_of_online_algorithm
If alpha lies in [0,1] and some deterministic online algorithm guarantees an alpha-EF1 allocation for n agents under exact frequency predictions, then alpha is at most the online EF1 approximation ratio (the supremum of all such ratios).
Statement
theorem online_ef1_ratio_ge_of_online_algorithm (n : ℕ) {α : ℝ} (h0 : 0 ≤ α) (h1 : α ≤ 1) (h : has_online_alpha_ef1_algorithm n α) : α ≤ online_ef1_approximation_ratio n- Source
- step towards op561_ratio_gt_sqrt5
- Verified
- 01 Nov 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
By definition, the online EF1 approximation ratio for n agents is the supremum of all ratios β ∈ [0, 1] admitting an online β-EF1 algorithm. The set of such ratios is bounded above by 1 because every element is at most 1. Since the given ratio α belongs to this set by hypothesis, α is at most the supremum of the set.
The set of valid ratios {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β} is bounded above by 1.
Unfolding the definition of online_ef1_approximation_ratio reveals that it is the supremum of this set. To work with its supremum in ℝ, we verify that the set is bounded above (BddAbove) by exhibiting 1 as an upper bound: by definition, every member x of the set satisfies x ≤ 1.
unfold online_ef1_approximation_ratio have hbdd : BddAbove {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β} := by use 1 intro x hx exact hx.2.1
The given ratio α belongs to the set {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β}.
By the theorem's hypotheses, α satisfies 0 ≤ α (h0), α ≤ 1 (h1), and admits an online α-EF1 algorithm (h), which matches the three defining conditions of the set.
have hmem : α ∈ {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β} := ⟨h0, h1, h⟩α ≤ online_ef1_approximation_ratio n
Because α belongs to the set and the set is bounded above, le_csSup implies that α is less than or equal to the supremum of the set, which is the definition of online_ef1_approximation_ratio n.
uses
le_csSupexact le_csSup hbdd hmem
le_csSup- In a conditionally complete lattice such as ℝ, if a set s is bounded above and an element a belongs to s, then a ≤ sSup s.
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.
theorem online_ef1_ratio_ge_of_online_algorithm (n : ℕ) {α : ℝ} (h0 : 0 ≤ α) (h1 : α ≤ 1) (h : has_online_alpha_ef1_algorithm n α) : α ≤ online_ef1_approximation_ratio n := by unfold online_ef1_approximation_ratio have hbdd : BddAbove {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β} := by use 1 intro x hx exact hx.2.1 have hmem : α ∈ {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β} := ⟨h0, h1, h⟩ exact le_csSup hbdd hmem