picking_sequence_alpha_nil_eq_zero
For the empty picking sequence every EF1 factor alpha is guaranteed (all bundles are empty), so picking_sequence_alpha, defined as a real sSup, takes the junk value 0.
Statement
theorem picking_sequence_alpha_nil_eq_zero (n : ℕ) :
picking_sequence_alpha n ([] : List (Fin n)) = 0- Source
- Degenerate case of picking_sequence_alpha (OP-345, arXiv:2610.23686 Sec. 6): with no items every alpha is guaranteed, so the sSup is over all of R and takes Lean's junk value 0.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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…
- 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…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - 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.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle… - SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in…
The proof, explained
For the empty picking sequence, no goods exist (the set of goods is indexed by `Fin 0`), so all agents receive empty bundles. Consequently, the EF1 condition is vacuously satisfied for every factor $\alpha \in \mathbb{R}$, meaning the set of guaranteed factors is the entire real line. Because `picking_sequence_alpha` is defined as the real supremum of this set, and Mathlib assigns the default value $0$ to the supremum of $\mathbb{R}$, the sequence alpha evaluates to $0$.
The set of guaranteed EF1 factors for the empty picking sequence is the universal set $\mathbb{R}$.
By set extensionality (`ext α`), it suffices to show that every $\alpha \in \mathbb{R}$ is a guaranteed sequence EF1 factor. Unfolding the definition of an $\alpha$-EF1 allocation, an agent $i$ only requires an envy bound against another agent $j$ when agent $j$'s allocated bundle is nonempty. But for the empty picking sequence `[]`, the available goods are indexed by `Fin [].length`, which is `Fin 0`. If agent $j$'s bundle were nonempty, it would contain an item $g \in \mathrm{Fin}\ 0$; since `Fin 0` has no elements, `Fin.elim0` yields a contradiction. Thus, the EF1 condition is vacuously satisfied for every factor $\alpha$.
uses
Set.mem_setOf_eq,Set.mem_univ,iff_true,Fin.elim0have h : {α : ℝ | is_guaranteed_sequence_ef1_factor n ([] : List (Fin n)) α} = Set.univ := by ext α simp only [Set.mem_setOf_eq, Set.mem_univ, iff_true] intro w _ rank _ i j _ hj exfalso obtain ⟨g, _⟩ := hj exact Fin.elim0 ((rank j).symm g)
The guaranteed EF1 factor for the empty picking sequence is $0$.
By definition, `picking_sequence_alpha` is the supremum (`sSup`) of the set of guaranteed factors. Since this set was shown to be the universal set $\mathbb{R}$, rewriting with this equality and applying `Real.sSup_univ` evaluates the supremum to $0$.
uses
Real.sSup_univunfold picking_sequence_alpha rw [h, Real.sSup_univ]
Set.mem_setOf_eq- Membership in a set comprehension $\{x \mid p(x)\}$ is equal to the predicate $p(x)$.
Set.mem_univ- Every element belongs to the universal set `Set.univ`.
iff_true- An equivalence of the form $p \leftrightarrow \mathrm{True}$ simplifies to $p$.
Fin.elim0- The type `Fin 0` is empty, so an element of `Fin 0` implies `False` (and thus any goal).
Real.sSup_univ- The supremum of the universal set of real numbers is defined to be $0$.
- In standard mathematics, the supremum of all real numbers, $\sup(\mathbb{R})$, is undefined or $+\infty$. In Mathlib, the supremum function on $\mathbb{R}$ (`Real.sSup`) is total; for sets that are not bounded above (such as `Set.univ`), it defaults to the junk value $0$ via `Real.sSup_univ`.
- In line 9, `Fin.elim0` is applied to `(rank j).symm g`. Because $g$ already has type `Fin [].length`, which is definitionally `Fin 0`, applying the permutation `(rank j).symm` has no mathematical effect and `Fin.elim0 g` would suffice.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem picking_sequence_alpha_nil_eq_zero (n : ℕ) : picking_sequence_alpha n ([] : List (Fin n)) = 0 := by have h : {α : ℝ | is_guaranteed_sequence_ef1_factor n ([] : List (Fin n)) α} = Set.univ := by ext α simp only [Set.mem_setOf_eq, Set.mem_univ, iff_true] intro w _ rank _ i j _ hj exfalso obtain ⟨g, _⟩ := hj exact Fin.elim0 ((rank j).symm g) unfold picking_sequence_alpha rw [h, Real.sSup_univ]