picking_sequence_outcome_update_mem_of_first_free
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
- picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
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.
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.
uses
Function.update_self,Finset.mem_insert_of_mem,Function.update_of_ne,Ne.symmdsimp [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
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.
uses
picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundleinduction 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)
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.
uses
Nat.exists_eq_succ_of_ne_zero,List.ofFn_succ,decide_eq_true,List.find?_cons,Function.update_self,Finset.mem_insert_selfobtain ⟨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)
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.
uses
List.getElem?_eq_some_iff.mp,List.cons_getElem_drop_succ.symm,List.take_append_dropset 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]
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).
uses
List.foldl_append,List.foldl_consdsimp [picking_sequence_outcome] rw [h_seq, List.foldl_append, List.foldl_cons]
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.
uses
picking_prefix_state_update_of_not_mem_takehave 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]
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.
uses
Function.update_self,picking_sequence_outcome_update_mem_of_first_free_turn_first_freehave 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
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.
uses
picking_sequence_outcome_update_mem_of_first_free_mem_foldl_turn_bundleexact 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
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_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