picking_prefix_state_eq_of_agree
If two bid profiles assign the same ranking to every agent that appears among the first s entries of the sequence, then the states of the two runs after s turns coincide.
Statement
theorem picking_prefix_state_eq_of_agree {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank rank' : N → Fin m ≃ G) (s : ℕ) (h : ∀ a ∈ seq.take s, rank a = rank' a) : picking_prefix_state seq rank s = picking_prefix_state seq rank' s
- Source
- step towards round_robin_item_preserving_swaps_polynomial_convergence
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
The proof, explained
The theorem establishes that if two ranking profiles agree for all agents appearing in the first s turns of a sequence, the resulting states after s turns are identical. By definition, computing the state after s turns is a left fold of the single-turn transition function over the prefix of length s starting from the empty state. A general helper lemma, proved by structural induction on lists, shows that two left folds produce the same result whenever their transition functions agree at each element in the list. Because the two ranking profiles assign the same ranking to every agent in the prefix, the transition functions coincide at each turn, making the final states identical.
Two left folds over an empty list produce identical results.
We prove the general fold lemma picking_prefix_state_eq_of_agree_foldl by induction on the list l, generalizing the accumulator b. When l is empty, both List.foldl f b [] and List.foldl g b [] reduce definitionally to b, so the base case holds by reflexivity.
induction l generalizing b with | nil => rfl
Two left folds produce identical results on a :: l if their step functions agree on every element of a :: l.
For the inductive step, applying List.foldl_cons unfolds the left fold over a :: l to a fold over l with updated accumulator f b a on the left and g b a on the right. By the induction hypothesis applied with accumulator f b a, the folds over l agree because every element of l is in a :: l (by List.mem_cons_of_mem), where f and g agree. Finally, because a ∈ a :: l (verified by simp), the hypothesis h gives f b a = g b a, rewriting the accumulator to g b a and completing the induction.
uses
List.foldl_cons,List.mem_cons_of_mem| cons a l ih => rw [List.foldl_cons, List.foldl_cons] rw [ih (f b a) (by intro b' a' ha'; exact h b' a' (List.mem_cons_of_mem a ha'))] rw [h b a (by simp)]The prefix state after s turns is expressed as a left fold over the sequence prefix.
Unfolding picking_prefix_state expands both sides into a left fold over seq.take s starting from the empty allocation state (fun _ => ∅, ∅), where each step applies picking_turn with the acting agent's ranking.
unfold picking_prefix_stateThe prefix states after s turns coincide for both ranking profiles.
We apply picking_prefix_state_eq_of_agree_foldl to the prefix seq.take s and the empty initial state. This reduces the equality of prefix states to showing that for any state st and any agent a occurring in the prefix, the single-turn transitions under rank and rank' coincide. Since the hypothesis h assumes rank a = rank' a for every agent in seq.take s, rewriting with this equality immediately matches both transition functions and concludes the proof.
uses
picking_prefix_state_eq_of_agree_foldlexact picking_prefix_state_eq_of_agree_foldl (seq.take s) (fun st a => picking_turn (List.ofFn ⇑(rank a)) a st) (fun st a => picking_turn (List.ofFn ⇑(rank' a)) a st) (fun _ => ∅, ∅) (by intro st a ha rw [h a ha])
List.foldl_cons- Left-folding an operation over a list with head a and tail l starting from accumulator b equals left-folding over l starting from f b a.
List.mem_cons_of_mem- An element belonging to a list also belongs to that list prepended with any element.
picking_prefix_state_eq_of_agree_foldl- Two left folds over the same list produce identical results from the same initial accumulator if their step functions agree on every element of the list for all accumulator values.
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.
lemma picking_prefix_state_eq_of_agree_foldl {α β : Type*} (l : List α) (f g : β → α → β) (b : β) (h : ∀ b a, a ∈ l → f b a = g b a) : l.foldl f b = l.foldl g b := by induction l generalizing b with | nil => rfl | cons a l ih => rw [List.foldl_cons, List.foldl_cons] rw [ih (f b a) (by intro b' a' ha'; exact h b' a' (List.mem_cons_of_mem a ha'))] rw [h b a (by simp)]/-- Prefix states agree when the bids agree on the agents acting in the first s turns. -/theorem picking_prefix_state_eq_of_agree {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank rank' : N → Fin m ≃ G) (s : ℕ) (h : ∀ a ∈ seq.take s, rank a = rank' a) : picking_prefix_state seq rank s = picking_prefix_state seq rank' s := by unfold picking_prefix_state exact picking_prefix_state_eq_of_agree_foldl (seq.take s) (fun st a => picking_turn (List.ofFn ⇑(rank a)) a st) (fun st a => picking_turn (List.ofFn ⇑(rank' a)) a st) (fun _ => ∅, ∅) (by intro st a ha rw [h a ha])