recursively_balanced_alpha
The universal EF1 approximation factor α_RB for recursively balanced picking sequences is the infimum over all recursively balanced sequences with at least two agents of their guaranteed EF1 factor.
Statement
noncomputable def recursively_balanced_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_recursively_balancedA picking sequence of length m for n agents is recursively balanced if each complete round of n turns contains every agent exactly once…
- 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
recursively_balanced_alpha is defined as the real number given by the infimum (sInf) of the set of all y : ℝ such that there exist a natural number n ≥ 2 and a finite list seq : List (Fin n) such that:
1. seq is "recursively balanced" in the sense of is_recursively_balanced n seq, meaning for every natural number s, the sublist of length n starting at index s * n (i.e. (seq.drop (s * n)).take n) contains no duplicate elements; and
2. y = picking_sequence_alpha n seq, which is the supremum (sSup) of all α : ℝ such that is_guaranteed_sequence_ef1_factor n seq α holds.
Here, is_guaranteed_sequence_ef1_factor n seq α asserts that for every non-negative additive valuation matrix w : Fin n → Fin seq.length → ℝ (with 0 ≤ w i g for all agents i and goods g), and for every ranking profile rank : Fin n → Fin seq.length ≃ Fin seq.length:
if rank is a pure Nash equilibrium (PNE) of the picking sequence game (i.e. no agent i can unilaterally change their ranking r to strictly increase the additive valuation of their allocated bundle under the outcome of seq),
then the resulting allocation A satisfies α-EF1 (i.e. for all agents i ≠ j, if A j is non-empty, there exists some item g ∈ A j such that α * v_i(A j \ {g}) ≤ v_i(A i)).
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 α_RB for all recursively balanced picking sequence mechanisms. -/ noncomputable def recursively_balanced_alpha : ℝ := sInf {y : ℝ | ∃ (n : ℕ) (seq : List (Fin n)), is_recursively_balanced n seq ∧ 2 ≤ n ∧ y = picking_sequence_alpha n seq}