AFTD Auto-Formalizing Theoretical Domains

picking_prefix_state_alloc_card_eq

theoremverified

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

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.

  1. 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.

    lines 5–12

    uses Fintype.card_congr, Finset.card_le_card, Finset.card_univ

      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
  2. 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.

    lines 13–18

    uses List.find?_some, decide_eq_true_eq, Finset.card_insert_of_notMem

      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]
  3. 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.

    lines 19–27

    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 this
  4. Base 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.

    lines 33–34

      induction s with
      | zero => simp [picking_prefix_state]
  5. 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.

    lines 35–39

    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]
  6. 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.

    lines 40–47

    uses Option.toList_none, List.append_nil, List.getElem?_eq_getElem

        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
  7. 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.

    lines 48–54

    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.

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_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
See it in the graphDiscuss this resultChallenge it