AFTD Auto-Formalizing Theoretical Domains

round_robin_alpha_three_eq_of_two_directions

theoremverified

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.

  1. 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.

    lines 6–9

    uses le_of_not_gt

      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⟩
  2. 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.

    lines 10–11

      have hmain : round_robin_alpha 3 = sSup s := rfl
      rw [hmain]
  3. 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.

    line 12

    uses le_antisymm, csSup_le, le_csSup

      exact 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

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