AFTD Auto-Formalizing Theoretical Domains

picking_prefix_state_card_diff_step_of_ne

theoremverified

Suppose 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 element each way, and that turn s is taken by an agent a other than i. Then after turn s+1 the allocated sets again differ in at most one element each way.

Statement

theorem picking_prefix_state_card_diff_step_of_ne {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G]
    {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G)
    (s : ℕ) (hseq : seq.length ≤ m) (hsl : s < seq.length) (hsm : s < m)
    (a : N) (ha : seq[s]? = some a) (hne : a ≠ i)
    (h1 : ((picking_prefix_state seq (Function.update rank i r) s).2 \
        (picking_prefix_state seq rank s).2).card ≤ 1)
    (h2 : ((picking_prefix_state seq rank s).2 \
        (picking_prefix_state seq (Function.update rank i r) s).2).card ≤ 1) :
    ((picking_prefix_state seq (Function.update rank i r) (s + 1)).2 \
        (picking_prefix_state seq rank (s + 1)).2).card ≤ 1 ∧
      ((picking_prefix_state seq rank (s + 1)).2 \
        (picking_prefix_state seq (Function.update rank i r) (s + 1)).2).card ≤ 1
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_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_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…
Used by 2

The proof, explained

To show that a turn taken by an agent a ≠ i preserves the property that the allocated sets differ by at most one element each way, we observe that agent a has the same preference ranking in both runs. By comparing the ranks of the items p and q chosen by agent a under the two profiles, we distinguish whether p was ranked higher than q, equal to q, or lower than q. When they are equal, the same item is added to both sets; when one is ranked higher, that item must already belong to the other allocated set, which allows an auxiliary lemma to bound both new set differences by 1.

  1. In the auxiliary lemma, the difference (insert p A) \ (insert q B) is a subset of A \ B, so its cardinality is at most 1.

    Any element z in (insert p A) \ (insert q B) must be in insert p A (so z = p or z ∈ A) and not in insert q B (so z ≠ q and z ∉ B). If z = p, this contradicts p ∈ B; hence z ∈ A and z ∉ B, placing z in A \ B. The cardinality bound follows from |A \ B| ≤ 1.

    lines 5–11

    uses le_trans, Finset.card_le_card, Finset.mem_sdiff, Finset.mem_insert, not_or

      constructor
      · refine le_trans (Finset.card_le_card ?_) h1
        intro z hz
        simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz ⊢
        rcases hz with ⟨rfl | hzA, hzq, hzB⟩
        · exact absurd hpB hzB
        · exact ⟨hzA, hzB⟩
  2. In the auxiliary lemma, (insert q B) \ (insert p A) is a subset of {q}, so its cardinality is at most 1.

    Any element z in (insert q B) \ (insert p A) satisfies (z = q or z ∈ B) with z ≠ p and z ∉ A. If z ≠ q, then z ∈ B \ A; but p also belongs to B \ A, and since |B \ A| ≤ 1, any two elements of B \ A must be equal, forcing z = p, which contradicts z ≠ p. Thus z must equal q, so the set difference is contained in {q} and has size at most 1.

    lines 12–21

    uses Finset.mem_sdiff, Finset.mem_insert, not_or, Finset.mem_singleton_self, Finset.mem_sdiff.mpr, Finset.card_le_one.mp, Finset.card_le_card

      · have hsub : insert q B \ insert p A ⊆ {q} := by
          intro z hz
          simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz
          rcases hz with ⟨rfl | hzB, hzp, hzA⟩
          · exact Finset.mem_singleton_self _
          · exfalso
            have hz' : z ∈ B \ A := Finset.mem_sdiff.mpr ⟨hzB, hzA⟩
            have hp' : p ∈ B \ A := Finset.mem_sdiff.mpr ⟨hpB, hpA⟩
            exact hzp (Finset.card_le_one.mp h2 z hz' p hp')
        exact (Finset.card_le_card hsub).trans (by simp)
  3. Under both profiles, the active agent a selects their top unallocated item according to the same ranking.

    Applying the step lemma to both runs shows that profile rank[i ↦ r] adds item p = (rank[i ↦ r] a) k to A, while profile rank adds item q = (rank a) k' to B, where all items ranked higher than k (respectively k') by agent a are already allocated. Since a ≠ i, agent a's ranking is identical under both profiles.

    lines 36–42

    uses picking_prefix_state_succ_step, Function.update_of_ne

      obtain ⟨p, hpA, hA', -, -, k, hk, hbk⟩ :=
        picking_prefix_state_succ_step seq (Function.update rank i r) s hsl hsm a ha
      obtain ⟨q, hqB, hB', -, -, k', hk', hbk'⟩ := picking_prefix_state_succ_step seq rank s hsl hsm a ha
      rw [Function.update_of_ne hne] at hk hbk
      rw [hA', hB']
      set A := (picking_prefix_state seq (Function.update rank i r) s).2
      set B := (picking_prefix_state seq rank s).2
  4. If k < k', then p ∈ B, and the auxiliary lemma shows both cardinalities remain at most 1.

    Because k < k', the item p = (rank a) k precedes q in agent a's ranking. Since q was the highest-ranked item of a not yet in B, all items preceding q are already in B, so p ∈ B. Since also p ∉ A, the auxiliary lemma applies directly to A, B, p, and q.

    lines 43–45

    uses lt_trichotomy, picking_prefix_state_card_diff_step_of_ne_aux

      rcases lt_trichotomy k k' with hlt | heq | hgt
      · have hpB : p ∈ B := by rw [← hk]; exact hbk' k hlt
        exact picking_prefix_state_card_diff_step_of_ne_aux A B p q hpA hpB h1 h2
  5. If k = k', then p = q, and both set differences remain of size at most 1.

    When k = k', agent a picks the same item in both runs, so p = q. Any element in (insert p A) \ (insert p B) cannot be p, hence it must belong to A \ B. Thus (insert p A) \ (insert p B) ⊆ A \ B, so its cardinality is at most |A \ B| ≤ 1. Symmetrically, (insert p B) \ (insert p A) ⊆ B \ A has size at most 1.

    lines 46–60

    uses le_trans, Finset.card_le_card, Finset.mem_sdiff, Finset.mem_insert, not_or

      · have hpq : p = q := by rw [← hk, ← hk', heq]
        subst hpq
        constructor
        · refine le_trans (Finset.card_le_card ?_) h1
          intro z hz
          simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz ⊢
          rcases hz with ⟨rfl | hzA, hzq, hzB⟩
          · exact absurd rfl hzq
          · exact ⟨hzA, hzB⟩
        · refine le_trans (Finset.card_le_card ?_) h2
          intro z hz
          simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz ⊢
          rcases hz with ⟨rfl | hzB, hzq, hzA⟩
          · exact absurd rfl hzq
          · exact ⟨hzB, hzA⟩
  6. If k' < k, then q ∈ A, and the auxiliary lemma with roles swapped shows both cardinalities remain at most 1.

    Symmetrically to the first case, since k' < k, the item q precedes p in agent a's ranking, so q ∈ A while q ∉ B. Applying the auxiliary lemma with the roles of A and B exchanged (and p and q exchanged) gives the desired bounds.

    lines 61–63

    uses picking_prefix_state_card_diff_step_of_ne_aux

      · have hqA : q ∈ A := by rw [← hk']; exact hbk k' hgt
        obtain ⟨c1, c2⟩ := picking_prefix_state_card_diff_step_of_ne_aux B A q p hqB hqA h2 h1
        exact ⟨c2, c1⟩
Finset.card_le_card
A subset has cardinality at most that of the superset.
Finset.card_le_one.mp
A set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.mem_sdiff
An element is in the difference s \ t if and only if it is in s and not in t.
Finset.mem_sdiff.mpr
If an element is in s and not in t, then it is in s \ t.
Finset.mem_insert
An element is in insert b s if and only if it equals b or is in s.
Finset.mem_singleton_self
An element belongs to its own singleton set.
le_trans
Transitivity of the preorder ≤.
not_or
De Morgan's law: not (p or q) is equivalent to (not p) and (not q).
Function.update_of_ne
Updating a function at a' does not change its value at a when a ≠ a'.
lt_trichotomy
For any two elements in a linear order, the first is less than, equal to, or greater than the second.
picking_prefix_state_succ_step
At step s of a picking sequence, the active agent adds their top available item to their bundle and to the allocated set.
picking_prefix_state_card_diff_step_of_ne_aux
If A and B differ by at most one element each way, p ∉ A, and p ∈ B, then insert p A and insert q B also differ by at most one element each way.

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_card_diff_step_of_ne_aux {G : Type*} [DecidableEq G]    (A B : Finset G) (p q : G) (hpA : p ∉ A) (hpB : p ∈ B)    (h1 : (A \ B).card ≤ 1) (h2 : (B \ A).card ≤ 1) :    (insert p A \ insert q B).card ≤ 1 ∧ (insert q B \ insert p A).card ≤ 1 := by  constructor  · refine le_trans (Finset.card_le_card ?_) h1    intro z hz    simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz ⊢    rcases hz with ⟨rfl | hzA, hzq, hzB⟩    · exact absurd hpB hzB    · exact ⟨hzA, hzB⟩  · have hsub : insert q B \ insert p A ⊆ {q} := by      intro z hz      simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz      rcases hz with ⟨rfl | hzB, hzp, hzA⟩      · exact Finset.mem_singleton_self _      · exfalso        have hz' : z ∈ B \ A := Finset.mem_sdiff.mpr ⟨hzB, hzA⟩        have hp' : p ∈ B \ A := Finset.mem_sdiff.mpr ⟨hpB, hpA⟩        exact hzp (Finset.card_le_one.mp h2 z hz' p hp')    exact (Finset.card_le_card hsub).trans (by simp)/-- One turn whose active agent is not the deviator preserves the invariant that the two allocated sets differ in at most one element on each side. -/theorem picking_prefix_state_card_diff_step_of_ne {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G]    {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G)    (s : ℕ) (hseq : seq.length ≤ m) (hsl : s < seq.length) (hsm : s < m)    (a : N) (ha : seq[s]? = some a) (hne : a ≠ i)    (h1 : ((picking_prefix_state seq (Function.update rank i r) s).2 \        (picking_prefix_state seq rank s).2).card ≤ 1)    (h2 : ((picking_prefix_state seq rank s).2 \        (picking_prefix_state seq (Function.update rank i r) s).2).card ≤ 1) :    ((picking_prefix_state seq (Function.update rank i r) (s + 1)).2 \        (picking_prefix_state seq rank (s + 1)).2).card ≤ 1 ∧      ((picking_prefix_state seq rank (s + 1)).2 \        (picking_prefix_state seq (Function.update rank i r) (s + 1)).2).card ≤ 1 := by  obtain ⟨p, hpA, hA', -, -, k, hk, hbk⟩ :=    picking_prefix_state_succ_step seq (Function.update rank i r) s hsl hsm a ha  obtain ⟨q, hqB, hB', -, -, k', hk', hbk'⟩ := picking_prefix_state_succ_step seq rank s hsl hsm a ha  rw [Function.update_of_ne hne] at hk hbk  rw [hA', hB']  set A := (picking_prefix_state seq (Function.update rank i r) s).2  set B := (picking_prefix_state seq rank s).2  rcases lt_trichotomy k k' with hlt | heq | hgt  · have hpB : p ∈ B := by rw [← hk]; exact hbk' k hlt    exact picking_prefix_state_card_diff_step_of_ne_aux A B p q hpA hpB h1 h2  · have hpq : p = q := by rw [← hk, ← hk', heq]    subst hpq    constructor    · refine le_trans (Finset.card_le_card ?_) h1      intro z hz      simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz ⊢      rcases hz with ⟨rfl | hzA, hzq, hzB⟩      · exact absurd rfl hzq      · exact ⟨hzA, hzB⟩    · refine le_trans (Finset.card_le_card ?_) h2      intro z hz      simp only [Finset.mem_sdiff, Finset.mem_insert, not_or] at hz ⊢      rcases hz with ⟨rfl | hzB, hzq, hzA⟩      · exact absurd rfl hzq      · exact ⟨hzB, hzA⟩  · have hqA : q ∈ A := by rw [← hk']; exact hbk k' hgt    obtain ⟨c1, c2⟩ := picking_prefix_state_card_diff_step_of_ne_aux B A q p hqB hqA h2 h1    exact ⟨c2, c1⟩
See it in the graphDiscuss this resultChallenge it