round_robin_sequence_count_le_two_of_ne_zero
In the Round-Robin sequence of n agents and 2n + 1 goods, every agent other than agent 0 picks at most twice.
Statement
theorem round_robin_sequence_count_le_two_of_ne_zero (n : ℕ) [NeZero n] (j : Fin n) (hj : j ≠ 0) :
(round_robin_sequence n (2 * n + 1)).count j ≤ 2- Source
- Step for round_robin_pne_ef1_of_card_le_two_mul_add_one (thread RT-3).
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
- Used by 1
- round_robin_pne_ef1_of_card_le_two_mul_add_oneWith n agents and at most 2n + 1 goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1. For three…
The proof, explained
We partition the length-(2n + 1) Round-Robin sequence into three segments: the first n elements, the next n elements, and the single remaining element. The first two segments each consist of n distinct agents, so agent j can appear at most once in each. The last item is allocated to agent (2n) % n = 0, which cannot be j since j ≠ 0, so j appears 0 times in the tail, yielding at most 1 + 1 + 0 = 2 picks in total.
Define the sequence `seq` and record its length and indexing formula.
We let `seq` denote `round_robin_sequence n (2 * n + 1)`. By `rr_l1_seq_length`, its total length is 2n + 1, and by `rr_l1_seq_getElem`, the agent at index t has numerical value t % n.
uses
rr_l1_seq_length,rr_l1_seq_getElemset seq := round_robin_sequence n (2 * n + 1) with hseq have hlen : seq.length = 2 * n + 1 := rr_l1_seq_length n _ have ex : ∀ (t : ℕ) (ht : t < seq.length), (seq[t]).val = t % n := fun t ht => rr_l1_seq_getElem n _ t ht
Decompose the count of j in `seq` into the sum of its counts in three subsegments.
Using `List.take_append_drop` twice, `seq` is decomposed into the prefix of length n (`seq.take n`), the next n elements (`(seq.drop n).take n`), and the remaining tail (`seq.drop (n + n)`). By `List.count_append`, the count of j in `seq` equals the sum of its counts in these three disjoint sublists.
uses
List.take_append_drop,List.count_append,List.drop_droprw [← List.take_append_drop n seq, List.count_append, ← List.take_append_drop n (seq.drop n), List.count_append, List.drop_drop]Agent j appears at most once in the first segment: `(seq.take n).count j ≤ 1`.
By `rr_l1_count_take_le_one`, any prefix of length at most n in a round-robin sequence contains each agent at most once. Applying this with k = n (using `le_rfl`) yields the bound for the first n items.
uses
rr_l1_count_take_le_one,le_rflhave h1 := rr_l1_count_take_le_one n (2 * n + 1) n le_rfl j rw [← hseq] at h1
Agent j appears at most once in the second segment: `((seq.drop n).take n).count j ≤ 1`.
By `List.nodup_iff_count_le_one.mp`, it suffices to show that this segment contains no duplicate elements (`Nodup`), which by `List.nodup_iff_injective_getElem` is equivalent to the injectivity of its indexing function. For any indices x, y < n where the elements agree, their values are (n + x) % n and (n + y) % n. Because x, y < n, these reduce by `Nat.add_mod_left` and `Nat.mod_eq_of_lt` to x and y, proving x = y and hence injectivity.
uses
List.nodup_iff_count_le_one.mp,List.nodup_iff_injective_getElem,List.length_take,List.length_drop,congrArg,List.getElem_take,List.getElem_drop,Nat.add_mod_left,Nat.mod_eq_of_lt,Fin.exthave h2 : ((seq.drop n).take n).count j ≤ 1 := by apply List.nodup_iff_count_le_one.mp rw [List.nodup_iff_injective_getElem] intro ⟨x, hx⟩ ⟨y, hy⟩ hxy simp only [List.length_take, List.length_drop, hlen] at hx hy have h1 := congrArg Fin.val hxy simp only [List.getElem_take, List.getElem_drop, ex] at h1 have e1 : (n + x) % n = x := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have e2 : (n + y) % n = y := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] rw [e1, e2] at h1 exact Fin.ext h1
Agent j does not appear in the final tail: `(seq.drop (n + n)).count j = 0`.
By `List.count_eq_zero.mpr`, it suffices to show that j does not belong to `seq.drop (n + n)`. The tail has length (2n + 1) - 2n = 1, so any index t within it must be 0. The element at index 0 has value (2n + 0) % n = 0, which would imply j = 0, contradicting the hypothesis that j ≠ 0.
uses
List.count_eq_zero.mpr,List.mem_iff_getElem.mp,List.length_drop,congrArg,List.getElem_drop,Fin.exthave h3 : (seq.drop (n + n)).count j = 0 := by apply List.count_eq_zero.mpr intro hmem obtain ⟨t, ht, hte⟩ := List.mem_iff_getElem.mp hmem simp only [List.length_drop, hlen] at ht have h1 := congrArg Fin.val hte simp only [List.getElem_drop, ex] at h1 have : (n + n + t) % n = 0 := by have ht0 : t = 0 := by omega subst ht0; simp rw [this] at h1 exact hj (Fin.ext h1.symm)
The total count of j in the round-robin sequence is at most 2. automation
Linear integer arithmetic (`omega`) combines the bounds from the three segments: at most 1 from the first, at most 1 from the second, and 0 from the tail, showing 1 + 1 + 0 ≤ 2.
omega
congrArg- Applying a function to equal arguments yields equal results: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
le_rfl- The reflexive property of inequality: a ≤ a.
List.count_append- The count of an element in the concatenation of two lists is the sum of its counts in each list.
List.count_eq_zero.mpr- If an element does not belong to a list, its count in that list is 0.
List.drop_drop- Dropping i elements from a list already dropped by j elements is equivalent to dropping j + i elements: drop i (drop j l) = drop (j + i) l.
List.getElem_drop- The j-th element of drop i xs is xs[i + j].
List.getElem_take- The i-th element of take j xs is xs[i].
List.length_drop- The length of drop i l is length(l) - i.
List.length_take- The length of take i l is min(i, length(l)).
List.mem_iff_getElem.mp- If an element belongs to a list, it appears at some index i < length(l).
List.nodup_iff_injective_getElem- A list has no duplicate elements (Nodup) if and only if its indexing function i ↦ l[i] is injective.
List.nodup_iff_count_le_one.mp- If a list has no duplicate elements (Nodup), then every element appears at most once in the list.
List.take_append_drop- A list can be reconstructed by appending its drop to its prefix: take i l ++ drop i l = l.
Nat.add_mod_left- For natural numbers x and z, (x + z) % x = z % x.
Nat.mod_eq_of_lt- If a < b for natural numbers, then a % b = a.
rr_l1_count_take_le_one- In a round-robin sequence of n agents, any prefix of length k ≤ n contains each agent at most once.
rr_l1_seq_getElem- The numerical value of the t-th element in round_robin_sequence n m is t % n.
rr_l1_seq_length- The length of round_robin_sequence n m is m.
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_sequence_count_le_two_of_ne_zero (n : ℕ) [NeZero n] (j : Fin n) (hj : j ≠ 0) : (round_robin_sequence n (2 * n + 1)).count j ≤ 2 := by set seq := round_robin_sequence n (2 * n + 1) with hseq have hlen : seq.length = 2 * n + 1 := rr_l1_seq_length n _ have ex : ∀ (t : ℕ) (ht : t < seq.length), (seq[t]).val = t % n := fun t ht => rr_l1_seq_getElem n _ t ht rw [← List.take_append_drop n seq, List.count_append, ← List.take_append_drop n (seq.drop n), List.count_append, List.drop_drop] have h1 := rr_l1_count_take_le_one n (2 * n + 1) n le_rfl j rw [← hseq] at h1 have h2 : ((seq.drop n).take n).count j ≤ 1 := by apply List.nodup_iff_count_le_one.mp rw [List.nodup_iff_injective_getElem] intro ⟨x, hx⟩ ⟨y, hy⟩ hxy simp only [List.length_take, List.length_drop, hlen] at hx hy have h1 := congrArg Fin.val hxy simp only [List.getElem_take, List.getElem_drop, ex] at h1 have e1 : (n + x) % n = x := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have e2 : (n + y) % n = y := by rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] rw [e1, e2] at h1 exact Fin.ext h1 have h3 : (seq.drop (n + n)).count j = 0 := by apply List.count_eq_zero.mpr intro hmem obtain ⟨t, ht, hte⟩ := List.mem_iff_getElem.mp hmem simp only [List.length_drop, hlen] at ht have h1 := congrArg Fin.val hte simp only [List.getElem_drop, ex] at h1 have : (n + n + t) % n = 0 := by have ht0 : t = 0 := by omega subst ht0; simp rw [this] at h1 exact hj (Fin.ext h1.symm) omega