AFTD Auto-Formalizing Theoretical Domains

online_ef1_ratio_ge_of_online_algorithm

theoremverified

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.

  1. 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.

    lines 2–6

      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
  2. 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.

    line 7

      have hmem : α ∈ {β : ℝ | 0 ≤ β ∧ β ≤ 1 ∧ has_online_alpha_ef1_algorithm n β} := ⟨h0, h1, h⟩
  3. α ≤ 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.

    line 8

    uses le_csSup

      exact 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

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
See it in the graphDiscuss this resultChallenge it