round_robin_alpha
The best guaranteed EF1 factor α_RR(n) for n agents under Round-Robin is the supremum of factors α that are guaranteed for n agents under Round-Robin.
Statement
noncomputable def round_robin_alpha (n : ℕ) [NeZero n] : ℝ
- Defined in
- arXiv:2610.23686, Sec. 6
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- 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,…
- Used by 1
- round_robin_alpha_three_eq_of_two_directionsIf 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…
Read back from the Lean
Given a number of agents n : ℕ with [NeZero n], round_robin_alpha n is defined as the supremum (sSup) in ℝ of the set of all real numbers α such that is_guaranteed_round_robin_ef1_factor n α holds.
Here, is_guaranteed_round_robin_ef1_factor n α asserts that:
For every number of goods m : ℕ,
and every valuation matrix w : Fin n → Fin m → ℝ satisfying ∀ i g, 0 ≤ w i g,
and every ranking profile rank : Fin n → Fin m ≃ Fin m,
if rank is a pure Nash equilibrium of the picking sequence game under the round-robin sequence of length m for n agents with valuations given additively by w (that is, for every agent i and every alternative ranking r : Fin m ≃ Fin m, agent i's bundle value under deviation to r is at most their bundle value under rank),
then the allocation resulting from the round-robin picking sequence under rank is α-EF1 with respect to w (that is, for every pair of distinct agents i ≠ j, if agent j's bundle is nonempty, there exists a good g in j's bundle such that α * v_i(A_j \ {g}) ≤ v_i(A_i), where v_i is agent i's additive valuation).
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 best guaranteed EF1 factor α_RR(n) for n agents under Round-Robin, defined as the supremum of guaranteed factors α. -/ noncomputable def round_robin_alpha (n : ℕ) [NeZero n] : ℝ := sSup {α : ℝ | is_guaranteed_round_robin_ef1_factor n α}