AFTD Auto-Formalizing Theoretical Domains

round_robin_two_mul_add_one_window_trace

theoremverified

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
Used by 2

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.

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

    lines 1–6

    uses Nat.lt_or_ge, Nat.mod_eq_of_lt, Nat.mod_eq_sub_mod

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

    lines 7–32

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

    lines 33–35

    uses Nat.le_induction

      intro s hs1 hs2
      induction s, hs1 using Nat.le_induction with
      | base => rw [h0]; simp
  4. 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.

    lines 36–47

    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 ih2
  5. In 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.

    lines 48–68

    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.

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