AFTD Auto-Formalizing Theoretical Domains

op561_exists_of_ratio_gt

theoremverified

If the online EF1 approximation ratio for four agents strictly exceeds (3 - sqrt 5)/2, then there exists an achievable approximation ratio alpha strictly exceeding (3 - sqrt 5)/2.

Statement

theorem op561_exists_of_ratio_gt (h : (3 - Real.sqrt 5) / 2 < online_ef1_approximation_ratio 4) :
    ∃ α : ℝ, (3 - Real.sqrt 5) / 2 < α ∧ has_online_alpha_ef1_algorithm 4 α
Source
step towards op561_exists_online_algorithm_gt_sqrt5
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • has_online_alpha_ef1_algorithm_zeroFor any positive number of agents n, there exists a deterministic online algorithm guaranteeing a 0-EF1 allocation under exact frequency…
  • 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 four agents is defined as the supremum of the set of achievable ratios $\alpha \in [0, 1]$. Because this set contains $0$ and is therefore nonempty, and the given bound $(3 - \sqrt{5})/2$ is strictly below the supremum, the characteristic property of the supremum (`exists_lt_of_lt_csSup`) yields an achievable ratio $\alpha$ strictly greater than $(3 - \sqrt{5})/2$.

  1. The set of ratios $\alpha \in [0, 1]$ admitting an online EF1 algorithm for 4 agents is nonempty.

    The value $0$ belongs to this set: $0 \le 0$ holds by reflexivity (`le_rfl`), $0 \le 1$ holds by numerical evaluation (`norm_num`), and an online $0$-EF1 algorithm exists for 4 agents by `has_online_alpha_ef1_algorithm_zero`.

    lines 4–5

    uses le_rfl, has_online_alpha_ef1_algorithm_zero

      have h_ne : {α : ℝ | 0 ≤ α ∧ α ≤ 1 ∧ has_online_alpha_ef1_algorithm 4 α}.Nonempty :=
        ⟨0, le_rfl, by norm_num, has_online_alpha_ef1_algorithm_zero 4⟩
  2. There exists an element $\alpha$ in the set strictly greater than $(3 - \sqrt{5})/2$.

    The online EF1 approximation ratio is defined as the supremum of this set. Since the set is nonempty and its supremum strictly exceeds $(3 - \sqrt{5})/2$, the lemma `exists_lt_of_lt_csSup` extracts an element $\alpha$ in the set with $(3 - \sqrt{5})/2 < \alpha$.

    line 6

    uses exists_lt_of_lt_csSup

      obtain ⟨α, hα, hlt⟩ := exists_lt_of_lt_csSup h_ne h
  3. There exists an achievable approximation ratio $\alpha$ strictly exceeding $(3 - \sqrt{5})/2$.

    The witness $\alpha$ satisfies both $(3 - \sqrt{5})/2 < \alpha$ and the property that an online $\alpha$-EF1 algorithm exists for 4 agents (which is the third component of membership in the set).

    line 7

      exact ⟨α, hlt, hα.2.2⟩
le_rfl
Any element $a$ in a preorder satisfies $a \le a$.
has_online_alpha_ef1_algorithm_zero
For any positive number of agents $n$, there exists an online $0$-EF1 algorithm.
exists_lt_of_lt_csSup
In a conditionally complete linear order, if a set $s$ is nonempty and strictly bounded from above by some $b < \sup s$, then there is an element $a \in s$ such that $b < 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

/-- If the online EF1 approximation ratio for four agents strictly exceeds (3 - sqrt 5)/2, then there exists an achievable approximation ratio alpha strictly exceeding (3 - sqrt 5)/2. -/theorem op561_exists_of_ratio_gt (h : (3 - Real.sqrt 5) / 2 < online_ef1_approximation_ratio 4) :    ∃ α : ℝ, (3 - Real.sqrt 5) / 2 < α ∧ has_online_alpha_ef1_algorithm 4 α := by  have h_ne : {α : ℝ | 0 ≤ α ∧ α ≤ 1 ∧ has_online_alpha_ef1_algorithm 4 α}.Nonempty :=    ⟨0, le_rfl, by norm_num, has_online_alpha_ef1_algorithm_zero 4⟩  obtain ⟨α, hα, hlt⟩ := exists_lt_of_lt_csSup h_ne h  exact ⟨α, hlt, hα.2.2⟩
See it in the graphDiscuss this resultChallenge it