picking_sequence_alpha
The best EF1 approximation factor guaranteed for a picking sequence mechanism seq with n agents is the supremum of factors α that are guaranteed for seq.
Statement
noncomputable def picking_sequence_alpha (n : ℕ) (seq : List (Fin n)) : ℝ
- Defined in
- arXiv:2610.23686, Sec. 6
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 1
- is_guaranteed_sequence_ef1_factorA factor α is guaranteed for a picking sequence mechanism seq with n agents if for every nonnegative additive valuation profile and every…
- Used by 4
- picking_sequence_alpha_nil_eq_zeroFor the empty picking sequence every EF1 factor alpha is guaranteed (all bundles are empty), so picking_sequence_alpha, defined as a real…
- 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…
- round_robin_universal_alphaThe universal EF1 approximation factor α_RR for Round-Robin picking sequences is the infimum over all Round-Robin sequences with at least…
- recursively_balanced_alphaThe universal EF1 approximation factor α_RB for recursively balanced picking sequences is the infimum over all recursively balanced…
Read back from the Lean
picking_sequence_alpha n seq is a noncomputable definition of a real number, defined as the supremum (sSup) of the set of all α : ℝ such that is_guaranteed_sequence_ef1_factor n seq α holds.
Here, is_guaranteed_sequence_ef1_factor n seq α asserts that:
For every valuation weight matrix w : Fin n → Fin seq.length → ℝ:
assuming 0 ≤ w i g for all agents i : Fin n and goods g : Fin seq.length,
for every ranking profile rank : Fin n → (Fin seq.length ≃ Fin seq.length):
if rank is a pure Nash equilibrium (PNE) for the picking sequence seq under the additive valuation induced by w,
then the allocation resulting from seq under rank is α-EF1 with respect to the additive valuation induced by w.
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 approximation factor for a picking sequence seq with n agents is the supremum of factors α guaranteed for seq. -/ noncomputable def picking_sequence_alpha (n : ℕ) (seq : List (Fin n)) : ℝ := sSup {α : ℝ | is_guaranteed_sequence_ef1_factor n seq α}