AFTD Auto-Formalizing Theoretical Domains

op826_online_single_high_efx_ratio_le_one

theoremverified

For every real value ratio R, the online single-high EFX competitive ratio for three agents is at most 1.

Statement

theorem op826_online_single_high_efx_ratio_le_one (R : ℝ) :
    online_single_high_efx_ratio R ≤ 1
Source
arXiv:2610.34625
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • online_single_high_efx_ratioFor ratio R, the online single-high EFX competitive ratio for three agents is the supremum of all alpha in [0, 1] such that for every…
  • has_online_single_high_alpha_efxThere exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every…
Used by 1

Read back from the Lean

For any real number $R$, the online single-high EFX ratio online_single_high_efx_ratio R is less than or equal to 1.

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 competitive ratio `online_single_high_efx_ratio R` is defined as the supremum of the set of ratios α ∈ [0, 1] admitting an online single-high EFX allocator. Because every candidate α in this set is bounded above by 1 by definition, applying `Real.sSup_le` shows that the supremum is at most 1.

  1. It suffices to show that every element in the set defining the ratio is at most 1, and that 0 ≤ 1.

    Unfolding the definition of `online_single_high_efx_ratio` expresses it as the supremum of the set of values α satisfying 0 ≤ α ≤ 1 and the existence of an appropriate online allocator. Applying `Real.sSup_le` reduces the upper bound on this supremum to showing that every element in the set is at most 1 and that the upper bound is non-negative (0 ≤ 1).

    lines 4–5

    uses Real.sSup_le

      unfold online_single_high_efx_ratio
      apply Real.sSup_le
  2. Every element of the defining set is at most 1.

    Let x be any element of the set. Membership in the set explicitly requires 0 ≤ x ∧ x ≤ 1 ∧ ..., so the condition x ≤ 1 holds directly by projecting the second conjunct of the hypothesis.

    lines 6–7

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

    The remaining non-negativity condition 0 ≤ 1 holds by `zero_le_one`.

    line 8

    uses zero_le_one

      · exact zero_le_one
Real.sSup_le
The supremum of a set of real numbers s is at most a, provided every element of s is at most a and 0 ≤ a.
zero_le_one
Zero is less than or equal to one in any type equipped with the ZeroLEOneClass.

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 single-high EFX competitive ratio for three agents is at most 1 for any valuation ratio R. -/theorem op826_online_single_high_efx_ratio_le_one (R : ℝ) :    online_single_high_efx_ratio R ≤ 1 := by  unfold online_single_high_efx_ratio  apply Real.sSup_le  · intro x hx    exact hx.2.1  · exact zero_le_one
See it in the graphDiscuss this resultChallenge it