AFTD Auto-Formalizing Theoretical Domains

picking_prefix_state_succ_step

theoremverified

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

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.

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

    lines 4–5

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

    lines 6–14

    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 ≤ _
          omega
  3. If 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.

    lines 15–20

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

    lines 32–35

    uses List.take_add_one, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil

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

    lines 36–45

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

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

    lines 46–55

    uses List.find?_eq_none, List.mem_ofFn, decide_eq_true_eq, not_not

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

    lines 56–64

    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]
  8. 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).

    lines 65–74

    uses Function.update_of_ne, List.getElem_ofFn, decide_eq_true_eq, Bool.not_eq_true', decide_eq_false_iff_not, not_not

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

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