op826_online_single_high_efx_upper_bound_two
For three agents and value ratio R = 2, the online single-high EFX competitive ratio is at most the conjectured envelope min (1 / floor(sqrt 2)) (ceil(sqrt 2) / 2).
Statement
theorem op826_online_single_high_efx_upper_bound_two :
online_single_high_efx_ratio 2 ≤ min (1 / (⌊Real.sqrt (2 : ℝ)⌋ : ℝ)) ((⌈Real.sqrt (2 : ℝ)⌉ : ℝ) / (2 : ℝ))- Source
- arXiv:2610.34625
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- op826_envelope_at_twoFor value ratio R = 2, the discrete envelope min (1 / floor(sqrt 2)) (ceil(sqrt 2) / 2) equals 1.
- op826_online_single_high_efx_ratio_le_oneFor every real value ratio R, the online single-high EFX competitive ratio for three agents is at most 1.
- 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…
Read back from the Lean
The theorem asserts that online_single_high_efx_ratio 2 is less than or equal to min (1 / ⌊Real.sqrt 2⌋) (⌈Real.sqrt 2⌉ / 2). That is, the supremum of all α ∈ [0, 1] such that for all m ≥ 1 there exists an online allocator for 3 agents and m items achieving α-EFX under single-high valuation profiles with parameter R = 2 is at most min(1 / ⌊√2⌋, ⌈√2⌉ / 2) (which evaluates 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 proof establishes the conjectured envelope bound at R = 2 by direct evaluation. First, it simplifies the envelope expression min (1 / ⌊√2⌋) (⌈√2⌉ / 2) to 1. The result then follows immediately from the general fact that the competitive ratio is always bounded above by 1.
The upper bound simplifies to 1, leaving the goal to show that the competitive ratio at R = 2 is at most 1.
Rewriting with `op826_envelope_at_two` evaluates the right-hand side: since ⌊√2⌋ = 1 and ⌈√2⌉ = 2, min(1/1, 2/2) simplifies to 1.
uses
op826_envelope_at_tworw [op826_envelope_at_two]The competitive ratio at R = 2 is at most 1, completing the proof.
By `op826_online_single_high_efx_ratio_le_one`, the online single-high EFX competitive ratio cannot exceed 1 for any ratio R, which immediately matches the goal for R = 2.
uses
op826_online_single_high_efx_ratio_le_oneexact op826_online_single_high_efx_ratio_le_one 2
op826_envelope_at_two- The envelope value min (1 / ⌊√2⌋) (⌈√2⌉ / 2) equals 1.
op826_online_single_high_efx_ratio_le_one- For every valuation ratio R, the online single-high EFX competitive ratio is at most 1.
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 upper envelope bound holds at R = 2: online_single_high_efx_ratio 2 <= envelope(2). -/theorem op826_online_single_high_efx_upper_bound_two : online_single_high_efx_ratio 2 ≤ min (1 / (⌊Real.sqrt (2 : ℝ)⌋ : ℝ)) ((⌈Real.sqrt (2 : ℝ)⌉ : ℝ) / (2 : ℝ)) := by rw [op826_envelope_at_two] exact op826_online_single_high_efx_ratio_le_one 2