AFTD Auto-Formalizing Theoretical Domains

is_guaranteed_sequence_ef1_factor

def

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

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