op561_exists_of_ratio_gt
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$.
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`.
uses
le_rfl,has_online_alpha_ef1_algorithm_zerohave h_ne : {α : ℝ | 0 ≤ α ∧ α ≤ 1 ∧ has_online_alpha_ef1_algorithm 4 α}.Nonempty := ⟨0, le_rfl, by norm_num, has_online_alpha_ef1_algorithm_zero 4⟩
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$.
uses
exists_lt_of_lt_csSupobtain ⟨α, hα, hlt⟩ := exists_lt_of_lt_csSup h_ne hThere 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).
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
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.
/-- 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⟩