AFTD Auto-Formalizing Theoretical Domains

picking_prefix_state_eq_of_agree

theoremverified

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.

  1. 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.

    lines 5–6

      induction l generalizing b with
      | nil => rfl
  2. 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.

    lines 7–10

    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)]
  3. 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.

    line 17

      unfold picking_prefix_state
  4. The 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.

    lines 18–23

    uses picking_prefix_state_eq_of_agree_foldl

      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])
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

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