AFTD Auto-Formalizing Theoretical Domains

op826_online_single_high_efx_upper_bound_two

theoremverified

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

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.

  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.

    line 4

    uses op826_envelope_at_two

      rw [op826_envelope_at_two]
  2. 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.

    line 5

    uses op826_online_single_high_efx_ratio_le_one

      exact 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

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