round_robin_alpha_three_eq_of_two_directions
If 2/3 is a guaranteed EF1 factor for three agents and no factor above 2/3 is guaranteed, then the best guaranteed factor for three agents is 2/3.
Statement
theorem round_robin_alpha_three_eq_of_two_directions
(hlow : is_guaranteed_round_robin_ef1_factor 3 (2 / 3))
(hup : ∀ α : ℝ, 2 / 3 < α → ¬ is_guaranteed_round_robin_ef1_factor 3 α) :
round_robin_alpha 3 = 2 / 3- Source
- step towards round_robin_alpha_three_eq_two_thirds
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- round_robin_alphaThe best guaranteed EF1 factor α_RR(n) for n agents under Round-Robin is the supremum of factors α that are guaranteed for n agents under…
- is_guaranteed_round_robin_ef1_factorA factor α is guaranteed for n agents under Round-Robin if for every number of goods m, every nonnegative additive valuation profile w,…
The proof, explained
By definition, round_robin_alpha 3 is the supremum of the set s of all guaranteed round-robin EF1 factors for three agents. The lower-bound hypothesis shows that 2/3 belongs to s, ensuring s is nonempty and that 2/3 ≤ sup s. The upper-bound hypothesis shows that no element of s strictly exceeds 2/3, making 2/3 an upper bound and ensuring sup s ≤ 2/3. By antisymmetry, the supremum must be exactly 2/3.
The set s of guaranteed round-robin EF1 factors for three agents is nonempty and bounded above by 2/3.
Define s to be the set of all real numbers α that are guaranteed round-robin EF1 factors for three agents. Since 2/3 is such a factor by the lower-bound hypothesis (hlow), 2/3 ∈ s, so s is nonempty. Furthermore, the upper-bound hypothesis (hup) asserts that no α > 2/3 belongs to s. Contrapositively, if a ∈ s, we cannot have 2/3 < a, so le_of_not_gt implies a ≤ 2/3. Thus 2/3 is an upper bound for s, showing s is bounded above.
uses
le_of_not_gtset s : Set ℝ := {α : ℝ | is_guaranteed_round_robin_ef1_factor 3 α} with hs have hne : s.Nonempty := ⟨2 / 3, hlow⟩ have hupper : ∀ a ∈ s, a ≤ 2 / 3 := fun a ha => le_of_not_gt fun h => hup a h ha have hbdd : BddAbove s := ⟨2 / 3, hupper⟩
The goal reduces to showing that sup s = 2/3.
By definition, round_robin_alpha 3 is the supremum of the set s of guaranteed factors. Rewriting with this definition reduces the goal round_robin_alpha 3 = 2/3 to sup s = 2/3.
have hmain : round_robin_alpha 3 = sSup s := rfl rw [hmain]
The supremum sup s equals 2/3, completing the proof.
The equality sup s = 2/3 follows by antisymmetry (le_antisymm). In one direction, because s is nonempty and 2/3 is an upper bound on s, csSup_le gives sup s ≤ 2/3. In the other direction, because s is bounded above and 2/3 ∈ s, le_csSup gives 2/3 ≤ sup s.
uses
le_antisymm,csSup_le,le_csSupexact le_antisymm (csSup_le hne hupper) (le_csSup hbdd hlow)
le_of_not_gt- In a linear order, if b < a does not hold, then a ≤ b.
csSup_le- In a conditionally complete lattice, if a set is nonempty and bounded above by a, then its supremum is at most a.
le_csSup- In a conditionally complete lattice, if a set is bounded above and contains an element a, then a is at most the supremum of the set.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
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.
/-- Assembly step: the two halves of the characterisation give round_robin_alpha 3 = 2/3. -/theorem round_robin_alpha_three_eq_of_two_directions (hlow : is_guaranteed_round_robin_ef1_factor 3 (2 / 3)) (hup : ∀ α : ℝ, 2 / 3 < α → ¬ is_guaranteed_round_robin_ef1_factor 3 α) : round_robin_alpha 3 = 2 / 3 := by set s : Set ℝ := {α : ℝ | is_guaranteed_round_robin_ef1_factor 3 α} with hs have hne : s.Nonempty := ⟨2 / 3, hlow⟩ have hupper : ∀ a ∈ s, a ≤ 2 / 3 := fun a ha => le_of_not_gt fun h => hup a h ha have hbdd : BddAbove s := ⟨2 / 3, hupper⟩ have hmain : round_robin_alpha 3 = sSup s := rfl rw [hmain] exact le_antisymm (csSup_le hne hupper) (le_csSup hbdd hlow)