round_robin_universal_alpha
def
The universal EF1 approximation factor α_RR for Round-Robin picking sequences is the infimum over all Round-Robin sequences with at least two agents of their guaranteed EF1 factor picking_sequence_alpha.
Statement
noncomputable def round_robin_universal_alpha : ℝ
- Defined in
- arXiv:2610.23686, Sec. 6
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 2
- picking_sequence_alphaThe best EF1 approximation factor guaranteed for a picking sequence mechanism seq with n agents is the supremum of factors α that are…
- is_round_robin_sequenceA picking sequence seq of type List (Fin n) is a Round-Robin sequence if there exists an instance of NeZero n such that seq equals…
- Used by 1
- recursively_balanced_alpha_le_round_robin_universal_alphaThe universal EF1 approximation factor for recursively balanced sequences recursively_balanced_alpha is at most the universal factor for…
Read back from the Lean
round_robin_universal_alpha is defined as the real number equal to the infimum (sInf) of the set of all y : ℝ for which there exist a natural number n and a sequence seq : List (Fin n) such that:
1. seq is a round-robin sequence for n agents (is_round_robin_sequence n seq),
2. 2 ≤ n, and
3. y equals the guaranteed EF1 picking sequence factor for seq (picking_sequence_alpha n seq).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The universal EF1 approximation factor α_RR for all Round-Robin picking sequence instances with at least two agents. -/ noncomputable def round_robin_universal_alpha : ℝ := sInf {y : ℝ | ∃ (n : ℕ) (seq : List (Fin n)), is_round_robin_sequence n seq ∧ 2 ≤ n ∧ y = picking_sequence_alpha n seq}