AFTD Auto-Formalizing Theoretical Domains

round_robin_alpha

def

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
Used by 1

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 α}
See it in the graphDiscuss this resultChallenge it