picking_prefix_state_succ_step
Turn s of a picking sequence with s < length seq and s < m: if the active agent is a, there is a good p, not allocated after s turns, such that after s+1 turns the allocated set is insert p (allocated after s), the bundle of a grows by exactly p, every other bundle is unchanged, and every good ranked before p by a is already allocated.
Statement
theorem picking_prefix_state_succ_step {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (hsl : s < seq.length) (hsm : s < m) (a : N) (ha : seq[s]? = some a) : ∃ p : G, p ∉ (picking_prefix_state seq rank s).2 ∧ (picking_prefix_state seq rank (s + 1)).2 = insert p (picking_prefix_state seq rank s).2 ∧ (picking_prefix_state seq rank (s + 1)).1 a = insert p ((picking_prefix_state seq rank s).1 a) ∧ (∀ b : N, b ≠ a → (picking_prefix_state seq rank (s + 1)).1 b = (picking_prefix_state seq rank s).1 b) ∧ (∃ k : Fin m, (rank a) k = p ∧ ∀ j : Fin m, j < k → (rank a) j ∈ (picking_prefix_state seq rank s).2)
- Source
- step towards round_robin_two_mul_add_one_deviation_certificate
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- picking_prefix_state_alloc_card_eqAfter s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods have been allocated (in…
- 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 6
- picking_prefix_state_card_diff_step_of_neSuppose two runs of a picking sequence (differing only in agent i's ranking) have allocated sets at time s that differ in at most one…
- 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…
- round_robin_two_mul_add_one_deviation_certificateRound-Robin with n agents and 2n+1 goods, any reports, agent i ≠ 0: for some good g of agent 0's bundle B_0 (its first pick a1), either…
- round_robin_two_mul_add_one_outcome_structureRound-Robin with n agents and 2n+1 goods, any reports: there are goods a2, a3 (agent 0's picks at turns n and 2n) and b1, b2 (agent i's…
- round_robin_two_mul_add_one_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
- round_robin_two_mul_add_one_window_traceRound-Robin with n agents and 2n+1 goods: change only agent i's report to r. Then at every time s between i's first turn and i's second…
The proof, explained
At turn s < m with active agent a, the number of goods allocated so far is at most s, so at least one of the m goods remains unallocated. Because agent a's ranking is a bijection from Fin m to the goods, searching a's ranking list must successfully find the first good p that is not yet allocated. In this turn, p is added to agent a's bundle and to the set of allocated goods, other agents' bundles remain unchanged, and every good ranked before p by agent a is already allocated.
At turn 0, the number of allocated goods is at most 0.
We proceed by induction on s. In the base case s = 0, no turns have occurred, so by definition of picking_prefix_state the allocated set is empty and its cardinality is 0 ≤ 0.
induction s with | zero => simp [picking_prefix_state]
If turn t has no active agent, the allocated set size remains at most t + 1.
We rewrite the state at t + 1 using List.take_add_one. When seq[t]? = none, the active sequence prefix has no new agent (Option.toList_none, List.append_nil), so the state is unchanged from turn t. By the induction hypothesis, its size is at most t ≤ t + 1.
uses
List.take_add_one,Option.toList_none,List.append_nil| succ t ih => have hstep : picking_prefix_state seq rank (t + 1) = (seq.take t ++ seq[t]?.toList).foldl (fun st a => picking_turn (List.ofFn ⇑(rank a)) a st) (fun _ => ∅, ∅) := by unfold picking_prefix_state; rw [List.take_add_one] rcases h : seq[t]? with _ | a · rw [hstep, h, Option.toList_none, List.append_nil] change (picking_prefix_state seq rank t).2.card ≤ _ omegaIf agent a acts at turn t, at most one good is added, so the allocated set size is at most t + 1.
When seq[t]? = some a, folding over the prefix decomposes into the state at turn t followed by picking_turn for agent a (Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil). The turn either finds an unallocated good and inserts it (increasing cardinality by at most 1 by Finset.card_insert_le) or leaves the state unchanged. In either case, the new cardinality is at most t + 1 by linear arithmetic.
uses
Option.toList_some,List.foldl_append,List.foldl_cons,List.foldl_nil,Finset.card_insert_le· rw [hstep, h, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil] change (picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank t)).2.card ≤ _ dsimp [picking_turn] split · exact (Finset.card_insert_le _ _).trans (by omega) · omega
The state after s + 1 turns is obtained by applying one picking_turn for agent a to the state after s turns.
Unfolding picking_prefix_state, the prefix of length s + 1 decomposes into the prefix of length s followed by [a] since seq[s]? = some a (List.take_add_one, Option.toList_some). Decomposing foldl over concatenation and a singleton list (List.foldl_append, List.foldl_cons, List.foldl_nil) expresses the new state directly as picking_turn for agent a applied to the state at turn s.
uses
List.take_add_one,Option.toList_some,List.foldl_append,List.foldl_cons,List.foldl_nilhave hstep : picking_prefix_state seq rank (s + 1) = picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank s) := by unfold picking_prefix_state rw [List.take_add_one, ha, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil]
There exists at least one good g not yet allocated after s turns.
By picking_prefix_state_succ_step_card_le, the number of allocated goods after s turns is at most s. Since agent a's ranking is a bijection Fin m ≃ G, the total number of goods is m (Fintype.card_congr). If all goods were allocated, the universal set of goods would be a subset of the allocated set (Finset.card_le_card, Finset.card_univ), which would force m ≤ s, contradicting the hypothesis s < m.
uses
picking_prefix_state_succ_step_card_le,Fintype.card_congr,Finset.card_le_card,Finset.card_univhave hcs := picking_prefix_state_succ_step_card_le seq rank s set st := picking_prefix_state seq rank s with hst have hcardG : Fintype.card G = m := by simpa using (Fintype.card_congr (rank a)).symm obtain ⟨g, hg⟩ : ∃ g : G, g ∉ st.2 := by by_contra hc push Not at hc have : (Finset.univ : Finset G) ⊆ st.2 := fun x _ => hc x have := Finset.card_le_card this rw [Finset.card_univ, hcardG] at this omega
Agent a's search in their ranking list for an unallocated good finds some good p.
We inspect the result of List.find? on agent a's ranking list. If the search returned none, then by List.find?_eq_none every good in the ranking would already be allocated. But the unallocated good g is in the ranking list by surjectivity (List.mem_ofFn), yielding g ∈ st.2, a contradiction. Hence the search must return some good p.
uses
List.find?_eq_none,List.mem_ofFn,decide_eq_true_eq,not_notrw [hstep] rcases hfind : (List.ofFn ⇑(rank a)).find? (fun g => decide (g ∉ st.2)) with _ | p · exfalso rw [List.find?_eq_none] at hfind have hmem : g ∈ List.ofFn ⇑(rank a) := by rw [List.mem_ofFn] exact ⟨(rank a).symm g, by simp⟩ have := hfind g hmem simp only [decide_eq_true_eq, not_not] at this exact hg this
The chosen good p is unallocated, appears at some index i < m with all prior goods allocated, and the state updates by allocating p to agent a.
By List.find?_eq_some_iff_getElem, p is not allocated (decide_eq_true_eq), occurs at index i in the ranking list of length m (List.length_ofFn), and every good at an earlier index was already allocated. Unfolding picking_turn with this find? result shows that the state updates by inserting p into agent a's bundle and into the allocated set, leaving other bundles untouched.
uses
List.find?_eq_some_iff_getElem,decide_eq_true_eq,List.length_ofFn· have hf := hfind rw [List.find?_eq_some_iff_getElem] at hf obtain ⟨hp, i, hi, hip, hbefore⟩ := hf simp only [decide_eq_true_eq] at hp rw [List.length_ofFn] at hi have hpt : picking_turn (List.ofFn ⇑(rank a)) a st = (Function.update st.1 a (insert p (st.1 a)), insert p st.2) := by unfold picking_turn; rw [hfind] rw [hpt]
The good p satisfies all five requirements of the step.
We provide p as the witness. It is unallocated, and the allocated set is updated by inserting p. Agent a's bundle grows by p, while any other agent b ≠ a has an unchanged bundle by Function.update_of_ne. Finally, setting index k = ⟨i, hi⟩ : Fin m, we have (rank a) k = p by List.getElem_ofFn, and for every index j < k, the earlier-checked condition ensures that (rank a) j is already allocated (Bool.not_eq_true', decide_eq_false_iff_not, not_not).
uses
Function.update_of_ne,List.getElem_ofFn,decide_eq_true_eq,Bool.not_eq_true',decide_eq_false_iff_not,not_notrefine ⟨p, hp, rfl, ?_, ?_, ⟨i, hi⟩, ?_, ?_⟩ · simp · intro b hb simp [Function.update_of_ne hb] · rw [← hip]; simp · intro j hj have := hbefore j.val (by exact_mod_cast hj) simp only [List.getElem_ofFn, decide_eq_true_eq, Bool.not_eq_true', decide_eq_false_iff_not, not_not] at this simpa using this
List.take_add_one- Taking the first i + 1 elements of a list equals taking the first i elements followed by the i-th element (as a singleton list, or empty if out of bounds).
Option.toList_none- Converting none of an option type to a list yields the empty list.
List.append_nil- Appending the empty list to any list leaves it unchanged.
Option.toList_some- Converting some a to a list yields the singleton list [a].
List.foldl_append- Folding a function over the concatenation of two lists equals folding over the first list and then folding over the second.
List.foldl_cons- Folding over a :: l applies the step function to the accumulator and a, then folds over l.
List.foldl_nil- Folding over the empty list returns the starting accumulator.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
picking_prefix_state_succ_step_card_le- After s turns of a picking sequence, the number of allocated goods is at most s.
Fintype.card_congr- Equivalent finite types have the same cardinality.
Finset.card_le_card- A subset of a finite set has cardinality less than or equal to the superset.
Finset.card_univ- The cardinality of the universal finite set of a type equals the cardinality of the type.
List.find?_eq_none- A predicate search in a list returns none if and only if no element in the list satisfies the predicate.
List.mem_ofFn- An element belongs to List.ofFn f if and only if it is in the range of f.
decide_eq_true_eq- The decidable boolean decide p is true if and only if the proposition p holds.
not_not- Double negation elimination: ¬¬a is equivalent to a.
List.find?_eq_some_iff_getElem- Searching a list with find? returns some b if and only if b satisfies the predicate, appears at some index i, and no element before index i satisfies the predicate.
List.length_ofFn- The length of the list formed by List.ofFn f on Fin n is n.
Function.update_of_ne- Updating a function at a' leaves its value at any distinct point b ≠ a' unchanged.
List.getElem_ofFn- The i-th element of List.ofFn f is f evaluated at index i.
Bool.not_eq_true'- The boolean negation !b is true if and only if b is false.
decide_eq_false_iff_not- The decidable boolean decide p is false if and only if proposition p is false.
- The source includes both the auxiliary lemma picking_prefix_state_succ_step_card_le (bounding the number of allocated goods at each step) and the main theorem picking_prefix_state_succ_step.
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_prefix_state_succ_step_card_le {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : (picking_prefix_state seq rank s).2.card ≤ s := by induction s with | zero => simp [picking_prefix_state] | succ t ih => have hstep : picking_prefix_state seq rank (t + 1) = (seq.take t ++ seq[t]?.toList).foldl (fun st a => picking_turn (List.ofFn ⇑(rank a)) a st) (fun _ => ∅, ∅) := by unfold picking_prefix_state; rw [List.take_add_one] rcases h : seq[t]? with _ | a · rw [hstep, h, Option.toList_none, List.append_nil] change (picking_prefix_state seq rank t).2.card ≤ _ omega · rw [hstep, h, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil] change (picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank t)).2.card ≤ _ dsimp [picking_turn] split · exact (Finset.card_insert_le _ _).trans (by omega) · omega/-- One turn of a picking sequence allocates exactly one good, namely the first good of the active agent's ranking that is not yet allocated. -/theorem picking_prefix_state_succ_step {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (hsl : s < seq.length) (hsm : s < m) (a : N) (ha : seq[s]? = some a) : ∃ p : G, p ∉ (picking_prefix_state seq rank s).2 ∧ (picking_prefix_state seq rank (s + 1)).2 = insert p (picking_prefix_state seq rank s).2 ∧ (picking_prefix_state seq rank (s + 1)).1 a = insert p ((picking_prefix_state seq rank s).1 a) ∧ (∀ b : N, b ≠ a → (picking_prefix_state seq rank (s + 1)).1 b = (picking_prefix_state seq rank s).1 b) ∧ (∃ k : Fin m, (rank a) k = p ∧ ∀ j : Fin m, j < k → (rank a) j ∈ (picking_prefix_state seq rank s).2) := by have hstep : picking_prefix_state seq rank (s + 1) = picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank s) := by unfold picking_prefix_state rw [List.take_add_one, ha, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil] have hcs := picking_prefix_state_succ_step_card_le seq rank s set st := picking_prefix_state seq rank s with hst have hcardG : Fintype.card G = m := by simpa using (Fintype.card_congr (rank a)).symm obtain ⟨g, hg⟩ : ∃ g : G, g ∉ st.2 := by by_contra hc push Not at hc have : (Finset.univ : Finset G) ⊆ st.2 := fun x _ => hc x have := Finset.card_le_card this rw [Finset.card_univ, hcardG] at this omega rw [hstep] rcases hfind : (List.ofFn ⇑(rank a)).find? (fun g => decide (g ∉ st.2)) with _ | p · exfalso rw [List.find?_eq_none] at hfind have hmem : g ∈ List.ofFn ⇑(rank a) := by rw [List.mem_ofFn] exact ⟨(rank a).symm g, by simp⟩ have := hfind g hmem simp only [decide_eq_true_eq, not_not] at this exact hg this · have hf := hfind rw [List.find?_eq_some_iff_getElem] at hf obtain ⟨hp, i, hi, hip, hbefore⟩ := hf simp only [decide_eq_true_eq] at hp rw [List.length_ofFn] at hi have hpt : picking_turn (List.ofFn ⇑(rank a)) a st = (Function.update st.1 a (insert p (st.1 a)), insert p st.2) := by unfold picking_turn; rw [hfind] rw [hpt] refine ⟨p, hp, rfl, ?_, ?_, ⟨i, hi⟩, ?_, ?_⟩ · simp · intro b hb simp [Function.update_of_ne hb] · rw [← hip]; simp · intro j hj have := hbefore j.val (by exact_mod_cast hj) simp only [List.getElem_ofFn, decide_eq_true_eq, Bool.not_eq_true', decide_eq_false_iff_not, not_not] at this simpa using this