op826_online_single_high_efx_ratio_le_one
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
- op826_online_single_high_efx_upper_bound_twoFor three agents and value ratio R = 2, the online single-high EFX competitive ratio is at most the conjectured envelope min (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.
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).
uses
Real.sSup_leunfold online_single_high_efx_ratio apply Real.sSup_le
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.
· intro x hx exact hx.2.1
0 ≤ 1.
The remaining non-negativity condition 0 ≤ 1 holds by `zero_le_one`.
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.
- In Mathlib, the supremum of the empty set of real numbers is defined to be 0 (`Real.sSup ∅ = 0`). Consequently, `Real.sSup_le` requires the hypothesis `0 ≤ a` (here `0 ≤ 1`) to ensure the bound holds even when the set is empty.
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.
/-- 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