AFTD Auto-Formalizing Theoretical Domains

online_ef1_approximation_ratio_le_one

theoremverified

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.

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

    lines 4–5

    uses Real.sSup_le

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

    lines 6–7

      · intro x hx
        exact hx.2.1
  3. 0 ≤ 1 automation

    The remaining condition 0 ≤ 1 is verified by basic numerical evaluation (`norm_num`).

    line 8

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

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