AFTD Auto-Formalizing Theoretical Domains

online_ef1_approximation_ratio_nonneg

theoremverified

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.

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

    lines 4–5

    uses Real.sSup_nonneg

      unfold online_ef1_approximation_ratio
      apply Real.sSup_nonneg
  2. 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.

    lines 6–7

      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.

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

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