AFTD Auto-Formalizing Theoretical Domains

recursively_balanced_alpha

def

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

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