is_guaranteed_sequence_ef1_factor
A factor α is guaranteed for a picking sequence mechanism seq with n agents if for every nonnegative additive valuation profile and every pure Nash equilibrium reported ranking profile, the outcome of the picking sequence is α-EF1.
Statement
def is_guaranteed_sequence_ef1_factor (n : ℕ) (seq : List (Fin n)) (α : ℝ) : Prop
- Defined in
- arXiv:2610.23686, Sec. 2 and Sec. 6
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 5
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - is_alpha_ef1For α in [0,1], an allocation is α-EF1 if for every pair of agents i ≠ j with A_j nonempty there is a good g in A_j with v_i(A_i) ≥ α ·…
- SocialChoice.FairDivision.Indivisible.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle… - picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
- is_picking_sequence_pneA profile of reported strict rankings is a pure Nash equilibrium of the picking-sequence mechanism if no agent can obtain a bundle of…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
- Used by 3
- 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…
- picking_sequence_alphaThe best EF1 approximation factor guaranteed for a picking sequence mechanism seq with n agents is the supremum of factors α that are…
Read back from the Lean
For a given number of agents n : ℕ, picking sequence seq : List (Fin n), and real factor α : ℝ, is_guaranteed_sequence_ef1_factor n seq α asserts:
For all valuation weight profiles w : Fin n → Fin seq.length → ℝ,
if all weights are non-negative (for all agents i and goods g, 0 ≤ w i g),
then for all ranking strategy profiles rank : Fin n → (Fin seq.length ≃ Fin seq.length),
if rank is a pure Nash equilibrium of the picking sequence game (that is, for every agent i and every alternate ranking permutation r, agent i's additive valuation for their bundle under unilateral deviation to r is at most their valuation under rank),
then the resulting allocation satisfies α-EF1 (envy-freeness up to one good scaled by α): for every pair of distinct agents i ≠ j, whenever agent j's bundle is nonempty, there exists a good g in j's bundle such that α times agent i's valuation of (j's bundle \ {g}) is at most agent i's valuation of i's own bundle.
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
/-- A factor α is guaranteed for a picking sequence if at every pure Nash equilibrium under nonnegative additive valuations, the induced allocation is α-EF1. -/ def is_guaranteed_sequence_ef1_factor (n : ℕ) (seq : List (Fin n)) (α : ℝ) : Prop := ∀ (w : Fin n → Fin seq.length → ℝ), (∀ i g, 0 ≤ w i g) → ∀ (rank : Fin n → Fin seq.length ≃ Fin seq.length), is_picking_sequence_pne (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩) seq rank → is_alpha_ef1 α (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩) (picking_sequence_outcome seq rank)