AFTD Auto-Formalizing Theoretical Domains

picking_prefix_state_allocated_card_le

theoremverified

After s turns of a picking sequence at most s items have been allocated: every picking_turn inserts at most one item into the allocated set.

Statement

theorem picking_prefix_state_allocated_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
Source
step towards round_robin_item_preserving_swaps_polynomial_convergence
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1
  • picking_phi_entry_leFor the Round-Robin sequence of n agents and m goods, the 0-based rank phi_s of the item selected at turn s is at most s (the paper's 1 <=…

The proof, explained

The theorem is established by first proving a general lemma by induction on the sequence of turns: folding picking_turn over any list of turns increases the number of allocated items by at most the length of the list. In the inductive step, a single turn either allocates an agent's most-preferred available item or leaves the state unchanged, in either case adding at most one item to the allocated set. The main theorem then specializes this lemma to the prefix of the first s turns starting from empty allocations, concluding because the prefix contains at most s turns.

  1. For an empty list of turns, the number of allocated items is at most the initial number of allocated items.

    We proceed by induction on the list L of turns, generalizing the initial state st. When L = [], the fold does nothing and the list length is 0, so the inequality st.2.card ≤ st.2.card + 0 holds immediately by simplification.

    lines 4–6

      induction L generalizing st with
      | nil =>
        simp
  2. In the inductive step for a :: as, the final number of allocated items is bounded by the number of allocated items after turn a plus the length of as.

    Simplifying with List.foldl_cons and List.length_cons rewrites the fold over a :: as as executing turn a first and then folding over the tail as. The induction hypothesis ih applied to the intermediate state picking_turn (f a) a st bounds the final allocated count by the count after turn a plus as.length.

    lines 7–9

    uses List.foldl_cons, List.length_cons

      | cons a as ih =>
        simp only [List.foldl_cons, List.length_cons]
        have hstep := ih (picking_turn (f a) a st)
  3. A single picking turn adds at most one item to the allocated set, completing the inductive step.

    Unfolding picking_turn and splitting on whether agent a finds an unallocated preferred item: if an item is found, it is inserted into the allocated set, increasing cardinality by at most 1 by Finset.card_insert_le; if no item is available, the state is unchanged, satisfying the bound by Nat.le_add_right. Combining this single-turn bound (hone) with the induction hypothesis (hstep) via linear arithmetic (linarith) proves that folding over a :: as increases the allocated set by at most (a :: as).length.

    lines 10–15

    uses Finset.card_insert_le, Nat.le_add_right

        have hone : (picking_turn (f a) a st).2.card ≤ st.2.card + 1 := by
          unfold picking_turn
          split
          · exact Finset.card_insert_le _ _
          · exact Nat.le_add_right _ _
        linarith
  4. After the first s turns starting from empty allocations, the number of allocated items is at most the length of the prefix of turns.

    Unfolding picking_prefix_state, the state is defined by folding picking_turn over the prefix List.take s seq starting from the initial state where no items are allocated. Applying picking_prefix_state_allocated_card_le_foldl bounds the allocated count by ∅.card + (List.take s seq).length. Simplifying with Finset.card_empty and Nat.zero_add leaves (List.take s seq).length.

    lines 21–23

    uses picking_prefix_state_allocated_card_le_foldl, Finset.card_empty, Nat.zero_add

      unfold picking_prefix_state
      have h := picking_prefix_state_allocated_card_le_foldl (fun a => List.ofFn ⇑(rank a)) (List.take s seq) (fun _ => ∅, ∅)
      simp only [Finset.card_empty, Nat.zero_add] at h
  5. At most s items have been allocated after s turns.

    The length of the prefix List.take s seq is at most s by List.length_take_le. Combining this with the previous bound via transitivity proves that at most s items are allocated.

    lines 24–25

    uses List.length_take_le

      have hlen : (List.take s seq).length ≤ s := List.length_take_le s seq
      exact h.trans hlen
List.foldl_cons
Folding a function over a non-empty list `a :: l` starting from `b` equals folding over `l` starting from the result of the function on `b` and `a`.
List.length_cons
The length of a non-empty list `a :: as` is one more than the length of `as`.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Nat.le_add_right
Any natural number n is at most n + k.
picking_prefix_state_allocated_card_le_foldl
Executing picking turns for a list of agents L via foldl increases the allocated set's cardinality by at most the length of L.
Finset.card_empty
The empty finite set has cardinality 0.
Nat.zero_add
Adding 0 to n equals n.
List.length_take_le
Taking at most i elements from a list yields a list of length at most i.

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_allocated_card_le_foldl {N G : Type*} [DecidableEq N] [DecidableEq G]    (f : N → List G) (L : List N) (st : (N → Finset G) × Finset G) :    (L.foldl (fun s a => picking_turn (f a) a s) st).2.card ≤ st.2.card + L.length := by  induction L generalizing st with  | nil =>    simp  | cons a as ih =>    simp only [List.foldl_cons, List.length_cons]    have hstep := ih (picking_turn (f a) a st)    have hone : (picking_turn (f a) a st).2.card ≤ st.2.card + 1 := by      unfold picking_turn      split      · exact Finset.card_insert_le _ _      · exact Nat.le_add_right _ _    linarith/-- After s turns at most s items have been allocated. -/theorem picking_prefix_state_allocated_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  unfold picking_prefix_state  have h := picking_prefix_state_allocated_card_le_foldl (fun a => List.ofFn ⇑(rank a)) (List.take s seq) (fun _ => ∅, ∅)  simp only [Finset.card_empty, Nat.zero_add] at h  have hlen : (List.take s seq).length ≤ s := List.length_take_le s seq  exact h.trans hlen
See it in the graphDiscuss this resultChallenge it