round_robin_two_mul_add_one_window_trace
Round-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 turn (i <= s <= i + n), the goods allocated by the deviated run and by the original run differ in at most one element each way.
Statement
theorem round_robin_two_mul_add_one_window_trace (n : ℕ) [NeZero n]
(rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n)
(r : Fin (2 * n + 1) ≃ Fin (2 * n + 1)) :
∀ s, i.val ≤ s → s ≤ i.val + n →
((picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) s).2 \
(picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank s).2).card ≤ 1 ∧
((picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank s).2 \
(picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) s).2).card ≤ 1- Source
- step towards round_robin_two_mul_add_one_deviation_certificate
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- picking_prefix_state_card_diff_step_of_neSuppose 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…
- 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…
- round_robin_sequence_getElem?_eqThe t-th turn (for t < m) of the Round-Robin sequence of n agents is agent t mod n.
- picking_prefix_state_update_of_not_mem_takeChanging agent i's ranking does not change the state of a picking sequence after the first t turns if agent i does not pick in those turns.
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- 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_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
The proof, explained
The theorem is proved by induction on the step s starting from agent i's first turn at s = i. Before turn i, agent i has never picked, so the original and deviated runs have identical allocation states, giving a trivial base case at s = i. At agent i's first turn (s = i), each run allocates at most one item to agent i while sharing the identical prior history, so the allocated sets at step i + 1 differ by at most one item each way. For all intermediate turns s between i and i + n, modular arithmetic ensures the active agent is never agent i, so inductive preservation (picking_prefix_state_card_diff_step_of_ne) guarantees that the discrepancy between the allocated sets never increases.
For any step s strictly between agent i's first and second turns (i < s < i + n), the active agent s % n is not agent i.
We split into cases on whether s < n or s ≥ n. If s < n, then s % n = s, which is strictly greater than i and hence cannot equal i. If s ≥ n, then s < i + n < 2n implies s - n < i < n, so s % n = (s - n) % n = s - n < i, which again cannot equal i.
uses
Nat.lt_or_ge,Nat.mod_eq_of_lt,Nat.mod_eq_sub_modtheorem round_robin_two_mul_add_one_window_trace_mod (n s : ℕ) (i : ℕ) (hi : i < n) (h1 : i < s) (h2 : s < i + n) : s % n ≠ i := by rcases Nat.lt_or_ge s n with hs | hs · rw [Nat.mod_eq_of_lt hs]; omega · rw [Nat.mod_eq_sub_mod hs, Nat.mod_eq_of_lt (by omega)]; omega
Before agent i's first turn at step i, the original and deviated runs have identical allocation states.
The round-robin sequence has length 2n + 1, and agent i satisfies i < n. By picking_prefix_state_update_of_not_mem_take, changing only agent i's ranking has no effect on the allocation state up to step i provided agent i does not appear in the first i turns. Any agent picking at step t < i has index t % n = t ≠ i because t < i < n. Hence agent i has not picked yet, and the two runs coincide at step i.
uses
picking_prefix_state_update_of_not_mem_take,List.mem_iff_getElem,List.length_take,List.getElem_take,round_robin_sequence_getElem?_eq,List.getElem?_eq_getElem,Option.some_inj,congrArg,Fin.val,Nat.mod_eq_of_lt/-- Over the window between agent i's two Round-Robin turns, the original and the deviated run have allocated sets differing in at most one element on each side. -/ theorem round_robin_two_mul_add_one_window_trace (n : ℕ) [NeZero n] (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (r : Fin (2 * n + 1) ≃ Fin (2 * n + 1)) : ∀ s, i.val ≤ s → s ≤ i.val + n → ((picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) s).2 \ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank s).2).card ≤ 1 ∧ ((picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank s).2 \ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) s).2).card ≤ 1 := by have hlen : (round_robin_sequence n (2 * n + 1)).length = 2 * n + 1 := by simp [round_robin_sequence] have hi := i.isLt have h0 : picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) i.val = picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank i.val := by apply picking_prefix_state_update_of_not_mem_take intro hmem rw [List.mem_iff_getElem] at hmem obtain ⟨t, ht, he⟩ := hmem rw [List.length_take] at ht rw [List.getElem_take] at he have hget := round_robin_sequence_getElem?_eq n (2 * n + 1) t (by omega) rw [List.getElem?_eq_getElem (by omega), he, Option.some_inj] at hget have := congrArg Fin.val hget simp only at this rw [Nat.mod_eq_of_lt (by omega)] at this omega
At the base case s = i, the set differences between the allocated goods of the two runs have cardinality at most 1 in both directions.
We proceed by induction on s ≥ i using Nat.le_induction. At s = i, the allocated sets in both runs are identical, so their set differences are empty with cardinality 0 ≤ 1.
uses
Nat.le_inductionintro s hs1 hs2 induction s, hs1 using Nat.le_induction with | base => rw [h0]; simp
In the inductive step, if i < s < i + n, the allocated sets after step s + 1 continue to differ by at most one element each way.
By the induction hypothesis, the difference bound holds at step s. The agent picking at step s is s % n. Since i < s < i + n, round_robin_two_mul_add_one_window_trace_mod ensures that this active agent is not agent i. Since that agent's ranking is unchanged, picking_prefix_state_card_diff_step_of_ne guarantees that taking this turn preserves the invariant that the allocated sets differ by at most one element each way.
uses
round_robin_sequence_getElem?_eq,picking_prefix_state_card_diff_step_of_ne,congrArg,Fin.val,round_robin_two_mul_add_one_window_trace_mod| succ s hs ih => obtain ⟨ih1, ih2⟩ := ih (by omega) have hsl : s < (round_robin_sequence n (2 * n + 1)).length := by omega have ha := round_robin_sequence_getElem?_eq n (2 * n + 1) s (by omega) rcases hs.lt_or_eq with hlt | heq · exact picking_prefix_state_card_diff_step_of_ne _ rank i r s (by omega) hsl (by omega) _ ha (by intro hc have := congrArg Fin.val hc simp only at this exact round_robin_two_mul_add_one_window_trace_mod n s i.val hi hlt (by omega) this) ih1 ih2In the inductive step, if s = i (agent i's first turn), the allocated sets after step i + 1 differ by at most one element each way.
When s = i, the active agent is i % n = i. In each run, picking_prefix_state_succ_step shows that agent i chooses some good (say p in the deviated run and q in the original run), adding it to the identical prior set S(i). The difference (S(i) ∪ {p}) \ (S(i) ∪ {q}) is contained in the singleton {p}, so by Finset.card_le_card its cardinality is at most 1. Symmetrically, (S(i) ∪ {q}) \ (S(i) ∪ {p}) ⊆ {q} has cardinality at most 1.
uses
Nat.mod_lt,NeZero.pos,Nat.mod_eq_of_lt,picking_prefix_state_succ_step,Finset.card_le_card,Finset.mem_sdiff,Finset.mem_insert,Or.inr· subst heq have hai : (⟨i.val % n, Nat.mod_lt _ (NeZero.pos n)⟩ : Fin n) = i := by ext; simp [Nat.mod_eq_of_lt hi] rw [hai] at ha obtain ⟨p, -, hA', -⟩ := picking_prefix_state_succ_step _ (Function.update rank i r) i.val hsl (by omega) i ha obtain ⟨q, -, hB', -⟩ := picking_prefix_state_succ_step _ rank i.val hsl (by omega) i ha rw [hA', hB', h0] constructor · refine (Finset.card_le_card (t := {p}) ?_).trans (by simp) intro z hz simp only [Finset.mem_sdiff, Finset.mem_insert] at hz rcases hz with ⟨rfl | hz, hn⟩ · simp · exact absurd (Or.inr hz) hn · refine (Finset.card_le_card (t := {q}) ?_).trans (by simp) intro z hz simp only [Finset.mem_sdiff, Finset.mem_insert] at hz rcases hz with ⟨rfl | hz, hn⟩ · simp · exact absurd (Or.inr hz) hn
Nat.lt_or_ge- For any two natural numbers n and m, either n < m or n ≥ m.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
Nat.mod_eq_sub_mod- If a ≥ b, then a % b = (a - b) % b.
picking_prefix_state_update_of_not_mem_take- Modifying agent i's ranking does not alter the prefix allocation state after t steps if agent i does not appear in the first t elements of the picking sequence.
List.mem_iff_getElem- An element belongs to a list if and only if it occurs at some valid index in the list.
List.length_take- The length of the prefix take i l of a list l is min(i, l.length).
List.getElem_take- The element at index i of the prefix take j xs is the element xs[i].
round_robin_sequence_getElem?_eq- The t-th agent in a round-robin sequence of n agents is the agent with index t % n.
List.getElem?_eq_getElem- For any in-bounds index i < l.length, the optional lookup l[i]? evaluates to some l[i].
Option.some_inj- Equality of some a and some b is equivalent to equality of a and b.
congrArg- If two inputs are equal, applying any function to them yields equal outputs.
Fin.val- Extracts the underlying natural number value from an element of Fin n.
Nat.le_induction- Induction principle for natural numbers starting at a base value m ≤ n.
picking_prefix_state_card_diff_step_of_ne- When an agent other than i takes a turn in two runs differing only in agent i's ranking, if the allocated sets differed by at most 1 item before the turn, they differ by at most 1 item after the turn.
round_robin_two_mul_add_one_window_trace_mod- If i < n and i < s < i + n, then s % n ≠ i.
Nat.mod_lt- For any positive divisor y, x % y < y.
NeZero.pos- A non-zero natural number is strictly positive.
picking_prefix_state_succ_step- When an agent takes a turn, they choose a previously unallocated item p, increasing the allocated set by {p}.
Finset.card_le_card- If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and not to t.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Or.inr- If proposition B holds, then A ∨ B holds.
- The fact that agent i does not pick before step i is immediate informally because the first n turns are 0, 1, ..., n-1 in order; in Lean, this requires unpacking the list lookup, the take prefix, and proving t % n = t for t < i < n.
- The set-theoretic step showing that (S ∪ {p}) \ (S ∪ {q}) ⊆ {p} is verified formally via case analysis on membership with Finset.mem_sdiff and Finset.mem_insert.
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 round_robin_two_mul_add_one_window_trace_mod (n s : ℕ) (i : ℕ) (hi : i < n) (h1 : i < s) (h2 : s < i + n) : s % n ≠ i := by rcases Nat.lt_or_ge s n with hs | hs · rw [Nat.mod_eq_of_lt hs]; omega · rw [Nat.mod_eq_sub_mod hs, Nat.mod_eq_of_lt (by omega)]; omega/-- Over the window between agent i's two Round-Robin turns, the original and the deviated run have allocated sets differing in at most one element on each side. -/theorem round_robin_two_mul_add_one_window_trace (n : ℕ) [NeZero n] (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (r : Fin (2 * n + 1) ≃ Fin (2 * n + 1)) : ∀ s, i.val ≤ s → s ≤ i.val + n → ((picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) s).2 \ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank s).2).card ≤ 1 ∧ ((picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank s).2 \ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) s).2).card ≤ 1 := by have hlen : (round_robin_sequence n (2 * n + 1)).length = 2 * n + 1 := by simp [round_robin_sequence] have hi := i.isLt have h0 : picking_prefix_state (round_robin_sequence n (2 * n + 1)) (Function.update rank i r) i.val = picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank i.val := by apply picking_prefix_state_update_of_not_mem_take intro hmem rw [List.mem_iff_getElem] at hmem obtain ⟨t, ht, he⟩ := hmem rw [List.length_take] at ht rw [List.getElem_take] at he have hget := round_robin_sequence_getElem?_eq n (2 * n + 1) t (by omega) rw [List.getElem?_eq_getElem (by omega), he, Option.some_inj] at hget have := congrArg Fin.val hget simp only at this rw [Nat.mod_eq_of_lt (by omega)] at this omega intro s hs1 hs2 induction s, hs1 using Nat.le_induction with | base => rw [h0]; simp | succ s hs ih => obtain ⟨ih1, ih2⟩ := ih (by omega) have hsl : s < (round_robin_sequence n (2 * n + 1)).length := by omega have ha := round_robin_sequence_getElem?_eq n (2 * n + 1) s (by omega) rcases hs.lt_or_eq with hlt | heq · exact picking_prefix_state_card_diff_step_of_ne _ rank i r s (by omega) hsl (by omega) _ ha (by intro hc have := congrArg Fin.val hc simp only at this exact round_robin_two_mul_add_one_window_trace_mod n s i.val hi hlt (by omega) this) ih1 ih2 · subst heq have hai : (⟨i.val % n, Nat.mod_lt _ (NeZero.pos n)⟩ : Fin n) = i := by ext; simp [Nat.mod_eq_of_lt hi] rw [hai] at ha obtain ⟨p, -, hA', -⟩ := picking_prefix_state_succ_step _ (Function.update rank i r) i.val hsl (by omega) i ha obtain ⟨q, -, hB', -⟩ := picking_prefix_state_succ_step _ rank i.val hsl (by omega) i ha rw [hA', hB', h0] constructor · refine (Finset.card_le_card (t := {p}) ?_).trans (by simp) intro z hz simp only [Finset.mem_sdiff, Finset.mem_insert] at hz rcases hz with ⟨rfl | hz, hn⟩ · simp · exact absurd (Or.inr hz) hn · refine (Finset.card_le_card (t := {q}) ?_).trans (by simp) intro z hz simp only [Finset.mem_sdiff, Finset.mem_insert] at hz rcases hz with ⟨rfl | hz, hn⟩ · simp · exact absurd (Or.inr hz) hn