AFTD Auto-Formalizing Theoretical Domains

picking_prefix_state_update_of_not_mem_take

theoremverified

Changing agent i's ranking does not change the state of a picking sequence after the first t turns if agent i does not pick in those turns.

Statement

theorem picking_prefix_state_update_of_not_mem_take {N G : Type*} [DecidableEq N] [DecidableEq G]
    {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G) (t : ℕ)
    (h : i ∉ seq.take t) :
    picking_prefix_state seq (Function.update rank i r) t = picking_prefix_state seq rank t
Source
step for round_robin_two_mul_add_one_deviation_certificate (research thread RT-3)
Verified
21 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…
Used by 4

The proof, explained

The prefix state after t turns is computed as a left fold over the first t agents in the sequence. Since agent i is assumed not to appear in this prefix, every agent who picks during these turns is distinct from i. Consequently, modifying agent i's ranking does not affect any turn's ranking, and the equality of the overall folded state follows by extensionality of foldl (`List.foldl_ext`).

  1. It suffices to show that for any state and any agent appearing in the prefix of the sequence, the picking transition function is the same under both ranking functions.

    By definition, `picking_prefix_state` is computed by folding `picking_turn` across the prefix `seq.take t` starting from the empty allocation state. By `List.foldl_ext`, two folds produce identical outcomes if their step functions agree for every element in the list and every accumulator state. Introducing an arbitrary state `st`, an agent `a`, and the membership assumption `ha : a ∈ seq.take t` leaves this step-wise equality as the goal.

    lines 5–7

    uses List.foldl_ext

      unfold picking_prefix_state
      apply List.foldl_ext
      intro st a ha
  2. The agent a is not equal to i.

    Suppose, for contradiction, that a = i. Then the assumption that a is in the prefix (`ha`) means i ∈ seq.take t, which directly contradicts the hypothesis h that i does not appear in seq.take t.

    lines 8–10

      have hne : a ≠ i := by
        rintro rfl
        exact h ha
  3. The picking transition at agent a with the updated ranking is identical to the transition with the original ranking.

    Since a ≠ i, updating rank at i does not change its evaluation at a (`Function.update_of_ne`). Rewriting with this identity substitutes `rank a` for `Function.update rank i r a`, making both sides of the equation identical and completing the proof.

    line 11

    uses Function.update_of_ne

      rw [Function.update_of_ne hne]
List.foldl_ext
Two left folds over the same list starting from the same accumulator yield the same result if their step functions produce identical outputs on every element in the list.
Function.update_of_ne
Updating a function at a point a' does not change its value at any distinct input a ≠ a'.

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

theorem picking_prefix_state_update_of_not_mem_take {N G : Type*} [DecidableEq N] [DecidableEq G]    {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G) (t : ℕ)    (h : i ∉ seq.take t) :    picking_prefix_state seq (Function.update rank i r) t = picking_prefix_state seq rank t := by  unfold picking_prefix_state  apply List.foldl_ext  intro st a ha  have hne : a ≠ i := by    rintro rfl    exact h ha  rw [Function.update_of_ne hne]
See it in the graphDiscuss this resultChallenge it