picking_prefix_state_allocated_card_le
After s turns of a picking sequence at most s items have been allocated: every picking_turn inserts at most one item into the allocated set.
Statement
theorem picking_prefix_state_allocated_card_le {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : (picking_prefix_state seq rank s).2.card ≤ s
- Source
- step towards round_robin_item_preserving_swaps_polynomial_convergence
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- picking_prefix_stateThe state of a picking-sequence run after its first s turns: the bundle map together with the set of already allocated items, obtained by…
- picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- picking_phi_entry_leFor the Round-Robin sequence of n agents and m goods, the 0-based rank phi_s of the item selected at turn s is at most s (the paper's 1 <=…
The proof, explained
The theorem is established by first proving a general lemma by induction on the sequence of turns: folding picking_turn over any list of turns increases the number of allocated items by at most the length of the list. In the inductive step, a single turn either allocates an agent's most-preferred available item or leaves the state unchanged, in either case adding at most one item to the allocated set. The main theorem then specializes this lemma to the prefix of the first s turns starting from empty allocations, concluding because the prefix contains at most s turns.
For an empty list of turns, the number of allocated items is at most the initial number of allocated items.
We proceed by induction on the list L of turns, generalizing the initial state st. When L = [], the fold does nothing and the list length is 0, so the inequality st.2.card ≤ st.2.card + 0 holds immediately by simplification.
induction L generalizing st with | nil => simp
In the inductive step for a :: as, the final number of allocated items is bounded by the number of allocated items after turn a plus the length of as.
Simplifying with List.foldl_cons and List.length_cons rewrites the fold over a :: as as executing turn a first and then folding over the tail as. The induction hypothesis ih applied to the intermediate state picking_turn (f a) a st bounds the final allocated count by the count after turn a plus as.length.
uses
List.foldl_cons,List.length_cons| cons a as ih => simp only [List.foldl_cons, List.length_cons] have hstep := ih (picking_turn (f a) a st)A single picking turn adds at most one item to the allocated set, completing the inductive step.
Unfolding picking_turn and splitting on whether agent a finds an unallocated preferred item: if an item is found, it is inserted into the allocated set, increasing cardinality by at most 1 by Finset.card_insert_le; if no item is available, the state is unchanged, satisfying the bound by Nat.le_add_right. Combining this single-turn bound (hone) with the induction hypothesis (hstep) via linear arithmetic (linarith) proves that folding over a :: as increases the allocated set by at most (a :: as).length.
uses
Finset.card_insert_le,Nat.le_add_righthave hone : (picking_turn (f a) a st).2.card ≤ st.2.card + 1 := by unfold picking_turn split · exact Finset.card_insert_le _ _ · exact Nat.le_add_right _ _ linarith
After the first s turns starting from empty allocations, the number of allocated items is at most the length of the prefix of turns.
Unfolding picking_prefix_state, the state is defined by folding picking_turn over the prefix List.take s seq starting from the initial state where no items are allocated. Applying picking_prefix_state_allocated_card_le_foldl bounds the allocated count by ∅.card + (List.take s seq).length. Simplifying with Finset.card_empty and Nat.zero_add leaves (List.take s seq).length.
uses
picking_prefix_state_allocated_card_le_foldl,Finset.card_empty,Nat.zero_addunfold picking_prefix_state have h := picking_prefix_state_allocated_card_le_foldl (fun a => List.ofFn ⇑(rank a)) (List.take s seq) (fun _ => ∅, ∅) simp only [Finset.card_empty, Nat.zero_add] at h
At most s items have been allocated after s turns.
The length of the prefix List.take s seq is at most s by List.length_take_le. Combining this with the previous bound via transitivity proves that at most s items are allocated.
uses
List.length_take_lehave hlen : (List.take s seq).length ≤ s := List.length_take_le s seq exact h.trans hlen
List.foldl_cons- Folding a function over a non-empty list `a :: l` starting from `b` equals folding over `l` starting from the result of the function on `b` and `a`.
List.length_cons- The length of a non-empty list `a :: as` is one more than the length of `as`.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Nat.le_add_right- Any natural number n is at most n + k.
picking_prefix_state_allocated_card_le_foldl- Executing picking turns for a list of agents L via foldl increases the allocated set's cardinality by at most the length of L.
Finset.card_empty- The empty finite set has cardinality 0.
Nat.zero_add- Adding 0 to n equals n.
List.length_take_le- Taking at most i elements from a list yields a list of length at most i.
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_prefix_state_allocated_card_le_foldl {N G : Type*} [DecidableEq N] [DecidableEq G] (f : N → List G) (L : List N) (st : (N → Finset G) × Finset G) : (L.foldl (fun s a => picking_turn (f a) a s) st).2.card ≤ st.2.card + L.length := by induction L generalizing st with | nil => simp | cons a as ih => simp only [List.foldl_cons, List.length_cons] have hstep := ih (picking_turn (f a) a st) have hone : (picking_turn (f a) a st).2.card ≤ st.2.card + 1 := by unfold picking_turn split · exact Finset.card_insert_le _ _ · exact Nat.le_add_right _ _ linarith/-- After s turns at most s items have been allocated. -/theorem picking_prefix_state_allocated_card_le {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : (picking_prefix_state seq rank s).2.card ≤ s := by unfold picking_prefix_state have h := picking_prefix_state_allocated_card_le_foldl (fun a => List.ofFn ⇑(rank a)) (List.take s seq) (fun _ => ∅, ∅) simp only [Finset.card_empty, Nat.zero_add] at h have hlen : (List.take s seq).length ≤ s := List.length_take_le s seq exact h.trans hlen