picking_prefix_state_card_diff_step_of_ne
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
- 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_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
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.
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.
uses
le_trans,Finset.card_le_card,Finset.mem_sdiff,Finset.mem_insert,not_orconstructor · 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⟩
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.
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)
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.
uses
picking_prefix_state_succ_step,Function.update_of_neobtain ⟨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
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.
uses
lt_trichotomy,picking_prefix_state_card_diff_step_of_ne_auxrcases 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
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.
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⟩
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.
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
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_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⟩