AFTD Auto-Formalizing Theoretical Domains

picking_sequence_outcome_update_mem_of_first_free

theoremverified

In a picking-sequence run, if agent i's first turn is turn t and the good g that i's new report r ranks first is still unallocated after the first t turns of the original run, then i gets g when it reports r (the others' reports unchanged).

Statement

theorem picking_sequence_outcome_update_mem_of_first_free {N G : Type*} [DecidableEq N]
    [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G)
    (t : ℕ) (hit : seq[t]? = some i) (hnot : i ∉ seq.take t) (hm : 0 < m)
    (hfree : r ⟨0, hm⟩ ∉ (picking_prefix_state seq rank t).2) :
    r ⟨0, hm⟩ ∈ picking_sequence_outcome seq (Function.update rank i r) i
Source
Step toward round_robin_two_mul_add_one_deviation_certificate (thread RT-3): the first case of the journal's turn analysis (agent i reporting a2 first gets a2).
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • 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…
  • picking_prefix_state_update_of_not_mem_takeChanging 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.
Used by 1

The proof, explained

The theorem proves that if agent i's first turn in a picking sequence occurs at step t, and the top-ranked good g = r(0) in i's updated report r is still unallocated after the first t turns, then i receives g in the final outcome under the updated report. The proof decomposes the sequence into the initial t turns, agent i's turn at step t, and the remaining suffix. Because i does not take part in the first t turns, updating i's report leaves the state after the first t turns unchanged, so g is still available when i's turn arrives. Agent i selects g at step t as their top available choice, and bundle monotonicity across subsequent turns ensures that i retains g through the end of the sequence.

  1. A single picking turn preserves all goods already allocated to any agent.

    Unfolding the definition of a picking turn (picking_turn), the state either changes if the acting agent a finds an unallocated good, or remains identical if no good is available. If an unallocated good g' is found, only agent a's bundle is updated by inserting g'. If a = i, agent i's bundle gains g', so the existing good g remains in the bundle by Finset.mem_insert_of_mem. If a ≠ i, agent i's bundle is untouched by Function.update_of_ne, so g is preserved. If no good is found, the bundle is unchanged. In all cases, g remains in agent i's bundle.

    lines 6–16

    uses Function.update_self, Finset.mem_insert_of_mem, Function.update_of_ne, Ne.symm

      dsimp [picking_turn]
      split
      · next g' hfind =>
        dsimp only
        by_cases hai : a = i
        · subst hai
          rw [Function.update_self]
          exact Finset.mem_insert_of_mem hg
        · rw [Function.update_of_ne (Ne.symm hai)]
          exact hg
      · exact hg
  2. Any sequence of picking turns preserves all goods already allocated to an agent.

    We proceed by induction on the list of turns (tail). In the base case (nil), no turns occur and the state is unchanged. In the inductive step (cons a as), agent a takes one turn, which preserves membership of g by picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle; the induction hypothesis then ensures that g remains in agent i's bundle through all remaining turns as.

    lines 23–27

    uses picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle

      induction tail generalizing st with
      | nil => exact hg
      | cons a as ih =>
        exact ih (picking_turn (f a) a st)
          (picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle (f a) a st i g hg)
  3. If an agent's top-ranked good is unallocated at the start of their turn, the agent receives it on that turn.

    Since the number of goods m is positive, write m = k + 1 via Nat.exists_eq_succ_of_ne_zero and identify the top index with 0. By List.ofFn_succ, the preference list begins with r(0). When searching for the first unallocated good, the condition decide (r 0 ∉ st.2) evaluates to true by decide_eq_true, so List.find?_cons immediately returns r(0). The turn updates agent i's bundle by inserting r(0) via Function.update_self, which contains r(0) by Finset.mem_insert_self.

    lines 34–43

    uses Nat.exists_eq_succ_of_ne_zero, List.ofFn_succ, decide_eq_true, List.find?_cons, Function.update_self, Finset.mem_insert_self

      obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hm.ne'
      have hr0 : (⟨0, hm⟩ : Fin (k + 1)) = 0 := rfl
      rw [hr0] at hfree ⊢
      rw [List.ofFn_succ]
      dsimp [picking_turn]
      have hdec : decide (r 0 ∉ st.2) = true := decide_eq_true hfree
      rw [List.find?_cons, hdec]
      dsimp only
      rw [Function.update_self]
      exact Finset.mem_insert_self (r 0) (st.1 i)
  4. The sequence decomposes into the prefix of length t, agent i's turn at index t, and the suffix after t + 1.

    Since seq[t]? = some i, the element at index t is i and t is within bounds by List.getElem?_eq_some_iff.mp, so List.cons_getElem_drop_succ.symm rewrites seq.drop t as i :: seq.drop (t + 1). Substituting this into the identity seq = seq.take t ++ seq.drop t (from List.take_append_drop) yields the desired decomposition of seq.

    lines 50–57

    uses List.getElem?_eq_some_iff.mp, List.cons_getElem_drop_succ.symm, List.take_append_drop

      set rank' := Function.update rank i r
      have h_drop : seq.drop t = i :: seq.drop (t + 1) := by
        obtain ⟨ht, h_get⟩ := List.getElem?_eq_some_iff.mp hit
        rw [← h_get]
        exact List.cons_getElem_drop_succ.symm
      have h_seq : seq = seq.take t ++ (i :: seq.drop (t + 1)) := by
        conv_lhs => rw [← List.take_append_drop t seq]
        rw [h_drop]
  5. The sequence outcome fold splits into the execution of the first t turns, followed by agent i's turn, followed by the remaining suffix.

    Unfolding picking_sequence_outcome and rewriting seq with the decomposition, List.foldl_append and List.foldl_cons split the execution into three phases: running the prefix of length t, executing agent i's turn on the resulting state, and running the suffix seq.drop (t + 1).

    lines 58–59

    uses List.foldl_append, List.foldl_cons

      dsimp [picking_sequence_outcome]
      rw [h_seq, List.foldl_append, List.foldl_cons]
  6. The state after the first t turns under the updated report profile equals the state under the original profile.

    Because agent i does not appear in the first t turns (hnot : i ∉ seq.take t), modifying agent i's report has no effect on the prefix execution: picking_prefix_state_update_of_not_mem_take shows that the state after the first t turns remains picking_prefix_state seq rank t.

    lines 60–64

    uses picking_prefix_state_update_of_not_mem_take

      have h_pref : (seq.take t).foldl (fun st a => picking_turn (List.ofFn ⇑(rank' a)) a st) (fun x => ∅, ∅)
          = picking_prefix_state seq rank t := by
        change picking_prefix_state seq rank' t = picking_prefix_state seq rank t
        exact picking_prefix_state_update_of_not_mem_take seq rank i r t hnot
      rw [h_pref]
  7. Agent i receives the good r(0) on turn t under the updated report profile.

    Under the updated profile, agent i's report is r by Function.update_self. At turn t, the current state is the prefix state, where r(0) is unallocated by hypothesis hfree. Applying picking_sequence_outcome_update_mem_of_first_free_turn_first_free, agent i picks and receives r(0) on this turn.

    lines 65–68

    uses Function.update_self, picking_sequence_outcome_update_mem_of_first_free_turn_first_free

      have h_rank'i : rank' i = r := Function.update_self i r rank
      rw [h_rank'i]
      have h_in : r ⟨0, hm⟩ ∈ (picking_turn (List.ofFn ⇑r) i (picking_prefix_state seq rank t)).1 i :=
        picking_sequence_outcome_update_mem_of_first_free_turn_first_free r hm i (picking_prefix_state seq rank t) hfree
  8. The good r(0) remains in agent i's bundle in the final outcome of the picking sequence.

    Having acquired r(0) at turn t, picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundle guarantees that r(0) remains in agent i's bundle throughout all subsequent turns in seq.drop (t + 1), completing the proof.

    lines 69–70

    uses picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundle

      exact picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundle
        (fun a => List.ofFn ⇑(rank' a)) (seq.drop (t + 1)) _ i _ h_in
Function.update_self
Evaluating an updated function f[a ↦ v] at the updated point a yields the new value v.
Finset.mem_insert_of_mem
If an element already belongs to a finite set s, it remains in the set after inserting any element b.
Function.update_of_ne
Updating a function at a point a' does not affect its value at any distinct point a ≠ a'.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle
If good g is in agent i's bundle before a picking turn, it remains in i's bundle after that turn.
Nat.exists_eq_succ_of_ne_zero
Every non-zero natural number is the successor of some natural number.
List.ofFn_succ
A list generated from a function on Fin(n + 1) starts with the value at index 0 followed by the remaining elements.
decide_eq_true
If a decidable proposition p is true, decide p evaluates to the boolean true.
List.find?_cons
Searching for an element satisfying predicate p in a :: as returns a if p(a) holds, and otherwise continues searching in as.
Finset.mem_insert_self
An element a belongs to the set obtained by inserting a into any finite set s.
List.getElem?_eq_some_iff.mp
If the element of list l at index t exists and equals x, then t is within bounds and l[t] = x.
List.cons_getElem_drop_succ.symm
Dropping t elements from list l equals the element at index t followed by dropping t + 1 elements from l.
List.take_append_drop
Concatenating the first t elements of a list with the suffix obtained by dropping t elements recovers the original list.
List.foldl_append
Folding a function over the concatenation of two lists l ++ l' is equivalent to folding over l and then folding over l' from the intermediate accumulator.
List.foldl_cons
Folding a function over a :: l updates the accumulator with a and then folds over l.
picking_prefix_state_update_of_not_mem_take
If agent i does not appear in the first t turns of a sequence, updating i's ranking does not alter the state after the first t turns.
picking_sequence_outcome_update_mem_of_first_free_turn_first_free
If an agent's top-ranked good is not yet allocated when their turn arrives, the agent acquires it on that turn.
picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundle
If a good is in an agent's bundle, it remains in that bundle after any sequence of picking turns.

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_sequence_outcome_update_mem_of_first_free_mem_turn_bundle    {N G : Type*} [DecidableEq N] [DecidableEq G]    (l : List G) (a : N) (st : (N → Finset G) × Finset G) (i : N) (g : G)    (hg : g ∈ st.1 i) :    g ∈ (picking_turn l a st).1 i := by  dsimp [picking_turn]  split  · next g' hfind =>    dsimp only    by_cases hai : a = i    · subst hai      rw [Function.update_self]      exact Finset.mem_insert_of_mem hg    · rw [Function.update_of_ne (Ne.symm hai)]      exact hg  · exact hgtheorem picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundle    {N G : Type*} [DecidableEq N] [DecidableEq G]    (f : N → List G) (tail : List N) (st : (N → Finset G) × Finset G) (i : N) (g : G)    (hg : g ∈ st.1 i) :    g ∈ (tail.foldl (fun s a => picking_turn (f a) a s) st).1 i := by  induction tail generalizing st with  | nil => exact hg  | cons a as ih =>    exact ih (picking_turn (f a) a st)      (picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle (f a) a st i g hg)theorem picking_sequence_outcome_update_mem_of_first_free_turn_first_free    {N G : Type*} [DecidableEq N] [DecidableEq G]    {m : ℕ} (r : Fin m ≃ G) (hm : 0 < m) (i : N) (st : (N → Finset G) × Finset G)    (hfree : r ⟨0, hm⟩ ∉ st.2) :    r ⟨0, hm⟩ ∈ (picking_turn (List.ofFn (r : Fin m → G)) i st).1 i := by  obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hm.ne'  have hr0 : (⟨0, hm⟩ : Fin (k + 1)) = 0 := rfl  rw [hr0] at hfree ⊢  rw [List.ofFn_succ]  dsimp [picking_turn]  have hdec : decide (r 0 ∉ st.2) = true := decide_eq_true hfree  rw [List.find?_cons, hdec]  dsimp only  rw [Function.update_self]  exact Finset.mem_insert_self (r 0) (st.1 i)theorem picking_sequence_outcome_update_mem_of_first_free {N G : Type*} [DecidableEq N]    [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G)    (t : ℕ) (hit : seq[t]? = some i) (hnot : i ∉ seq.take t) (hm : 0 < m)    (hfree : r ⟨0, hm⟩ ∉ (picking_prefix_state seq rank t).2) :    r ⟨0, hm⟩ ∈ picking_sequence_outcome seq (Function.update rank i r) i := by  set rank' := Function.update rank i r  have h_drop : seq.drop t = i :: seq.drop (t + 1) := by    obtain ⟨ht, h_get⟩ := List.getElem?_eq_some_iff.mp hit    rw [← h_get]    exact List.cons_getElem_drop_succ.symm  have h_seq : seq = seq.take t ++ (i :: seq.drop (t + 1)) := by    conv_lhs => rw [← List.take_append_drop t seq]    rw [h_drop]  dsimp [picking_sequence_outcome]  rw [h_seq, List.foldl_append, List.foldl_cons]  have h_pref : (seq.take t).foldl (fun st a => picking_turn (List.ofFn ⇑(rank' a)) a st) (fun x => ∅, ∅)      = picking_prefix_state seq rank t := by    change picking_prefix_state seq rank' t = picking_prefix_state seq rank t    exact picking_prefix_state_update_of_not_mem_take seq rank i r t hnot  rw [h_pref]  have h_rank'i : rank' i = r := Function.update_self i r rank  rw [h_rank'i]  have h_in : r ⟨0, hm⟩ ∈ (picking_turn (List.ofFn ⇑r) i (picking_prefix_state seq rank t)).1 i :=    picking_sequence_outcome_update_mem_of_first_free_turn_first_free r hm i (picking_prefix_state seq rank t) hfree  exact picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundle    (fun a => List.ofFn ⇑(rank' a)) (seq.drop (t + 1)) _ i _ h_in
See it in the graphDiscuss this resultChallenge it