picking_prefix_state_alloc_card_eq
After s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods have been allocated (in particular exactly s for s <= length seq).
Statement
theorem picking_prefix_state_alloc_card_eq {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (hseq : seq.length ≤ m) : (picking_prefix_state seq rank s).2.card = min s seq.length
- Source
- step towards round_robin_two_mul_add_one_deviation_certificate
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 7
- 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_state_succ_stepTurn 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…
- 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
The theorem is proved by induction on the number of turns s. The base case s = 0 is immediate because no turns have occurred and the allocated set is empty. In the inductive step s = t + 1, the proof splits the sequence prefix into the first t turns and the turn at index t: if the sequence has ended (t ≥ length), no turn occurs and the count is unchanged; if an agent picks (t < length ≤ m), fewer than m goods have been allocated so far, so by a helper lemma every turn strictly before exhaustion successfully allocates a new good, increasing the allocated count by 1 to min (t + 1) length.
If strictly fewer than m goods have been allocated, there exists at least one unallocated good.
Since the ranking r is an equivalence between Fin m and G, the total number of goods is |G| = m. If every good were already allocated, the universal finset of goods would be a subset of the allocated set st.2, giving m ≤ |st.2|, which contradicts st.2.card < m. Linear arithmetic finishes the contradiction.
uses
Fintype.card_congr,Finset.card_le_card,Finset.card_univhave hcardG : Fintype.card G = m := by simpa using (Fintype.card_congr r).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
When an unallocated good is found in the agent's preference order, executing the turn increases the number of allocated goods by 1.
The definition of `picking_turn` searches the agent's preference list for the first item not in the allocated set st.2. When such an item g' is found, it is inserted into st.2. Because g' ∉ st.2, the insertion increases the cardinality by exactly 1.
uses
List.find?_some,decide_eq_true_eq,Finset.card_insert_of_notMemdsimp [picking_turn] split · next g' hfind => have := List.find?_some hfind simp only [decide_eq_true_eq] at this rw [Finset.card_insert_of_notMem this]
A turn cannot leave the state unchanged: every agent must find an available good.
If the search returned none, every good in the preference list would already be allocated. But the preference list contains all m goods of G via the equivalence r. In particular, the unallocated good g found earlier would belong to st.2, contradicting that g is unallocated.
uses
List.find?_eq_none,List.mem_ofFn,decide_eq_true_eq,not_not· next hfind => exfalso rw [List.find?_eq_none] at hfind have hmem : g ∈ List.ofFn ⇑r := by rw [List.mem_ofFn] exact ⟨r.symm g, by simp⟩ have := hfind g hmem simp only [decide_eq_true_eq, not_not] at this exact hg thisBase case: after 0 turns, exactly min 0 (length seq) = 0 goods are allocated.
Taking a prefix of length 0 leaves the sequence empty, so the fold produces an empty allocated set with cardinality 0, which equals min 0 seq.length.
induction s with | zero => simp [picking_prefix_state]
The state after t + 1 turns decomposes into the state after t turns followed by the turn of the (t+1)-th agent.
Taking the first t + 1 elements of seq splits into taking the first t elements concatenated with the optional element at index t. The fold defining picking_prefix_state splits across this concatenation.
uses
List.take_add_one| 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]If the sequence has length at most t, no agent acts at step t + 1 and the allocated count remains min (t + 1) (length seq).
When index t is out of bounds (seq[t]? = none), seq.length ≤ t. The concatenation adds nothing, so the state is unchanged from step t. By the induction hypothesis, the count is min t seq.length = seq.length, which equals min (t + 1) seq.length.
uses
Option.toList_none,List.append_nil,List.getElem?_eq_getElemrcases h : seq[t]? with _ | a · rw [hstep, h, Option.toList_none, List.append_nil] change (picking_prefix_state seq rank t).2.card = _ rw [ih] have : seq.length ≤ t := by by_contra hc; push Not at hc rw [List.getElem?_eq_getElem hc] at h; simp at h omega
If an agent a acts at step t + 1, exactly one new good is allocated, bringing the total to min (t + 1) (length seq).
Since seq[t]? = some a, index t is within bounds, so t < seq.length ≤ m. By the induction hypothesis, exactly min t seq.length = t goods were allocated previously. Because t < m, the helper lemma picking_prefix_state_alloc_card_eq_turn applies: agent a takes an unallocated good, increasing the count by 1 to t + 1 = min (t + 1) seq.length.
uses
Option.toList_some,List.foldl_append,List.foldl_cons,List.foldl_nil,List.getElem?_eq_none,picking_prefix_state_alloc_card_eq_turn· rw [hstep, h, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil] have ht : t < seq.length := by by_contra hc; push Not at hc rw [List.getElem?_eq_none hc] at h; simp at h change (picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank t)).2.card = _ rw [picking_prefix_state_alloc_card_eq_turn (rank a) a _ (by rw [ih]; omega), ih] omega
Fintype.card_congr- An equivalence between two finite types implies they have the same cardinality.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the other's.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
List.find?_some- If searching a list for a predicate finds an element, that element satisfies the predicate.
decide_eq_true_eq- The boolean decision `decide p` is `true` if and only if the proposition `p` holds.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
List.find?_eq_none- A list search finds no element if and only if no element in the list satisfies the predicate.
List.mem_ofFn- An element is in the list generated by a function on `Fin n` if and only if it is in the function's image.
not_not- Double negation elimination: `¬¬a` is equivalent to `a`.
List.take_add_one- Taking `i + 1` elements from a list equals taking `i` elements concatenated with the optional `i`-th element converted to a list.
Option.toList_none- Converting `none` to a list yields the empty list.
List.append_nil- Appending the empty list to any list leaves it unchanged.
List.getElem?_eq_getElem- If an index is strictly less than the length of a list, looking up the element at that index yields `some` of that element.
Option.toList_some- Converting `some a` to a list yields the singleton list `[a]`.
List.foldl_append- Folding 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 accumulator unchanged.
List.getElem?_eq_none- Looking up an index greater than or equal to the list length yields `none`.
picking_prefix_state_alloc_card_eq_turn- Executing one picking turn for an agent whose preferences order all `m` goods increases the allocated set size by 1, provided strictly fewer than `m` goods were allocated.
- The definition of `picking_prefix_state` uses `List.take` and `List.foldl`. Splitting the prefix of length `t + 1` requires using `List.take_add_one` and case-splitting on `seq[t]?`, which handles the termination of the sequence when `s` exceeds its length.
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_alloc_card_eq_turn {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (r : Fin m ≃ G) (a : N) (st : (N → Finset G) × Finset G) (hst : st.2.card < m) : (picking_turn (List.ofFn ⇑r) a st).2.card = st.2.card + 1 := by have hcardG : Fintype.card G = m := by simpa using (Fintype.card_congr r).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 dsimp [picking_turn] split · next g' hfind => have := List.find?_some hfind simp only [decide_eq_true_eq] at this rw [Finset.card_insert_of_notMem this] · next hfind => exfalso rw [List.find?_eq_none] at hfind have hmem : g ∈ List.ofFn ⇑r := by rw [List.mem_ofFn] exact ⟨r.symm g, by simp⟩ have := hfind g hmem simp only [decide_eq_true_eq, not_not] at this exact hg this/-- After s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods are allocated. -/theorem picking_prefix_state_alloc_card_eq {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (hseq : seq.length ≤ m) : (picking_prefix_state seq rank s).2.card = min s seq.length := 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 = _ rw [ih] have : seq.length ≤ t := by by_contra hc; push Not at hc rw [List.getElem?_eq_getElem hc] at h; simp at h omega · rw [hstep, h, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil] have ht : t < seq.length := by by_contra hc; push Not at hc rw [List.getElem?_eq_none hc] at h; simp at h change (picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank t)).2.card = _ rw [picking_prefix_state_alloc_card_eq_turn (rank a) a _ (by rw [ih]; omega), ih] omega