iterated_round_robin_item_preserving_swaps_zero_of_card_le
When the number of goods m is at most the number of agents n, for any initial preference profile pref : Fin n → Fin m ≃ Fin m and non-negative additive valuations v : Fin n → Fin m → ℝ (with v i g ≥ 0 for all i, g) strictly consistent with pref (with v i (pref i l) < v i (pref i k) whenever k < l), any execution f : ℕ → (Fin n → Fin m ≃ Fin m) starting at f 0 = pref of T steps of iterated Round Robin under item-preserving swap bids (irr_step) must have length T = 0.
Statement
theorem iterated_round_robin_item_preserving_swaps_zero_of_card_le (n m : ℕ) [NeZero n] (hm : m ≤ n)
(pref : Fin n → Fin m ≃ Fin m) (v : Fin n → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g)
(hcons : ∀ (i : Fin n) (k l : Fin m), k < l → v i (pref i l) < v i (pref i k))
(f : ℕ → (Fin n → Fin m ≃ Fin m)) (hf0 : f 0 = pref) (T : ℕ)
(hf : ∀ t < T, irr_step v (round_robin_sequence n m)
(is_item_preserving_swap_bid (round_robin_sequence n m)) (f t) (f (t + 1))) :
T = 0- Source
- scout/2610-23040-on-the-convergence-of-iterated-round-robin.md:309
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- irr_stepOne step of iterated picking sequences restricted to admissible bids adm: some agent i that has a strictly profitable admissible…
- is_item_preserving_swap_bidBid r of agent i is obtained from b i by an item-preserving swap: a swap of the goods in positions k < l that demotes the good g = b i k,…
- ranking_swapThe ranking obtained from r by exchanging the goods in positions k and l.
- picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
- picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
Given:
- natural numbers $n, m$ with $n \ne 0$ and $m \le n$;
- a preference profile $\text{pref} : \text{Fin } n \to (\text{Fin } m \simeq \text{Fin } m)$ assigning to each agent $i$ a ranking (permutation) of items;
- a valuation function $v : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$;
- an assumption that all valuations are non-negative ($v(i, g) \ge 0$ for all $i, g$);
- an assumption that valuations strictly decrease with rank in $\text{pref}$ (for every agent $i$ and indices $k < l$ in $\text{Fin } m$, $v(i, \text{pref}(i)(l)) < v(i, \text{pref}(i)(k))$);
- a sequence of bid profiles $f : \mathbb{N} \to (\text{Fin } n \to (\text{Fin } m \simeq \text{Fin } m))$ starting at truthful preferences ($f(0) = \text{pref}$);
- and a natural number $T$ such that for all $t < T$, the step from $f(t)$ to $f(t+1)$ is an iterated round-robin step (irr_step) with valuation $v$, picking sequence round_robin_sequence n m, and admissible bids given by item-preserving swaps (is_item_preserving_swap_bid);
the theorem asserts that $T = 0$ (i.e., no such step can take place).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
When the number of goods m is at most the number of agents n, the round-robin sequence gives every agent at most one picking turn. Consequently, each agent receives at most one good overall. For an item-preserving swap bid to be admissible, the swapped good must still be obtained by the agent, forcing both the truthful and manipulated bundles to be identical singletons; thus, the agent's valuation cannot strictly increase, ruling out any manipulation step and forcing T = 0.
The round-robin agent index map t ↦ t % n from Fin m to Fin n is injective when m ≤ n.
Let x, y ∈ Fin m have the same image in Fin n, so x.val % n = y.val % n. Since x.val < m ≤ n and y.val < m ≤ n, both values are strictly less than n. Thus x.val % n = x.val and y.val % n = y.val, which implies x.val = y.val, so x = y.
uses
Fin.mk.injEq,lt_of_lt_of_le,Nat.mod_eq_of_lthave hinj : Function.Injective (fun (t : Fin m) => (⟨t.val % n, Nat.mod_lt _ (NeZero.pos n)⟩ : Fin n)) := by intro x y hxy simp only [Fin.mk.injEq] at hxy have hx : x.val < n := lt_of_lt_of_le x.isLt hm have hy : y.val < n := lt_of_lt_of_le y.isLt hm rw [Nat.mod_eq_of_lt hx, Nat.mod_eq_of_lt hy] at hxy ext exact hxy
The round-robin sequence has no duplicate entries, so each agent appears at most once.
By definition, the round-robin sequence is formed by evaluating the index map across Fin m using List.ofFn. Because the index map was proved injective, List.nodup_ofFn implies the sequence has no duplicates. A list without duplicates contains any element at most once.
uses
List.nodup_ofFn.mpr,List.nodup_iff_count_le_one.mphave hnodup : (round_robin_sequence n m).Nodup := by unfold round_robin_sequence exact List.nodup_ofFn.mpr hinj exact List.nodup_iff_count_le_one.mp hnodup a
Base case and induction step setup: the allocated bundle cardinality bound holds for the empty list and reduces to a single-step turn bound.
We proceed by induction on the picking sequence list l. When l is empty, the outcome bundle equals the initial bundle, and the count of a in l is 0, satisfying the bound trivially. For a non-empty sequence h :: t, List.foldl_cons and List.count_cons allow us to apply the induction hypothesis to the remaining sequence t after updating the state via picking_turn.
uses
List.foldl_cons,List.count_consinduction l generalizing st with | nil => simp | cons h t ih => simp only [List.foldl_cons, List.count_cons] have ih_st := ih (picking_turn (L h) h st)
A single picking turn increases the cardinality of the current chooser's bundle by at most 1, and leaves all other agents' bundles unchanged.
Unfolding picking_turn, either an available item g is picked or no item is picked. If an item is picked and the chooser h equals a, agent a's bundle has g inserted, increasing its cardinality by at most 1 (by Finset.card_insert_le). If h ≠ a, agent a's bundle is untouched. Combining this single-step inequality with the induction hypothesis via linear arithmetic (omega) completes the inductive proof.
uses
Function.update_self,beq_self_eq_true,ite_true,Finset.card_insert_le,Function.update_of_ne,Ne.symm,beq_false_of_nehave hstep : ((picking_turn (L h) h st).1 a).card ≤ (st.1 a).card + if (h == a) = true then 1 else 0 := by unfold picking_turn split · next g hfind => dsimp only by_cases ha : h = a · subst ha rw [Function.update_self] simp only [beq_self_eq_true, ite_true] exact Finset.card_insert_le _ _ · rw [Function.update_of_ne (Ne.symm ha)] have : (h == a) = false := beq_false_of_ne ha simp [this] · simp omega
Assuming T ≠ 0, there exists a strictly beneficial item-preserving swap bid at the initial step t = 0.
Assume for contradiction that T ≠ 0. Then T > 0, so the first step t = 0 must be an iterated Round Robin step. By definition of irr_step, there is an agent i with an admissible item-preserving swap bid r—swapping goods at ranks k < l—that strictly increases agent i's valuation from the truthful outcome.
uses
Nat.pos_of_ne_zeroby_contra hT have hT0 : 0 < T := Nat.pos_of_ne_zero hT have hstep := hf 0 hT0 obtain ⟨i, ⟨r, hadm, hlt⟩, -⟩ := hstep obtain ⟨k, l, hkl, hr, hg1, hg2⟩ := hadm set seq := round_robin_sequence n m
Agent i receives at most one good in total, both under truthful preferences f 0 and under the swapped bid.
Because m ≤ n, agent i appears at most once in the round-robin sequence. Applying the cardinality lemma for sequence outcomes starting from the empty allocation shows that the number of goods allocated to i is bounded by 0 + seq.count i ≤ 1, both for f 0 and for the modified profile (f 0)[i ↦ r].
uses
iterated_round_robin_item_preserving_swaps_zero_of_card_le_seq_count_le_one,iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_lehave hcount : seq.count i ≤ 1 := iterated_round_robin_item_preserving_swaps_zero_of_card_le_seq_count_le_one n m hm i have h0 : (((fun _ : Fin n => (∅ : Finset (Fin m))), (∅ : Finset (Fin m))).1 i).card = 0 := by simp have hcard1 : (picking_sequence_outcome seq (f 0) i).card ≤ 1 := by have hcard := iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_le (fun a => List.ofFn (f 0 a)) seq i (fun _ => ∅, ∅) rw [h0] at hcard exact hcard.trans (by omega) have hcard2 : (picking_sequence_outcome seq (Function.update (f 0) i r) i).card ≤ 1 := by have hcard := iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_le (fun a => List.ofFn (Function.update (f 0) i r a)) seq i (fun _ => ∅, ∅) rw [h0] at hcard exact hcard.trans (by omega)
Agent i's outcome bundle is the singleton {g} under both preference profiles, where g = f 0 i k.
By the definition of an item-preserving swap bid, the item g = f 0 i k is allocated to i in both the truthful outcome and the manipulated outcome. Since both outcome bundles contain g and have cardinality at most 1 (using Finset.card_le_one), each bundle must be exactly the singleton set {g}.
uses
Finset.mem_singleton,Finset.card_le_one.mpset g := (f 0 i) k have eA : picking_sequence_outcome seq (f 0) i = {g} := by ext x simp only [Finset.mem_singleton] exact ⟨fun hx => Finset.card_le_one.mp hcard1 x hx g hg1, fun hx => hx ▸ hg1⟩ have eB : picking_sequence_outcome seq (Function.update (f 0) i r) i = {g} := by ext x simp only [Finset.mem_singleton] exact ⟨fun hx => Finset.card_le_one.mp hcard2 x hx g hg2, fun hx => hx ▸ hg2⟩
The strict utility improvement assumption yields a contradiction, proving T = 0.
Replacing both outcome bundles with {g} in the strict inequality from the step assumption gives ∑_{x ∈ {g}} v i x < ∑_{x ∈ {g}} v i x. By irreflexivity of strict inequality (lt_irrefl), this is impossible, establishing T = 0.
uses
lt_irreflrw [eA, eB] at hlt exact lt_irrefl _ hlt
Fin.mk.injEq- Two elements of Fin n are equal if and only if their underlying natural values are equal.
lt_of_lt_of_le- Transitivity of strict inequality and non-strict inequality: if a < b and b ≤ c, then a < c.
Nat.mod_eq_of_lt- If a < b, then the remainder a % b is simply a.
List.nodup_ofFn.mpr- A list constructed with List.ofFn has no duplicates if the indexing function is injective.
List.nodup_iff_count_le_one.mp- A list has no duplicate elements if and only if every element occurs at most once in the list.
List.foldl_cons- Folding over a prepended list satisfies foldl f b (a :: l) = foldl f (f b a) l.
List.count_cons- The count of an element in a :: l equals its count in l plus 1 if the head matches, and 0 otherwise.
Function.update_self- Updating a function f at point a with value v evaluates at a to v.
beq_self_eq_true- Boolean equality of an element with itself evaluates to true.
ite_true- If True then a else b evaluates to a.
Finset.card_insert_le- The cardinality of insert a s is at most s.card + 1.
Function.update_of_ne- Updating a function at a' does not change its value at a if a ≠ a'.
Ne.symm- Symmetry of inequality: a ≠ b implies b ≠ a.
beq_false_of_ne- Boolean equality (a == b) is false when a ≠ b.
Nat.pos_of_ne_zero- If a natural number is non-zero, then it is strictly positive.
iterated_round_robin_item_preserving_swaps_zero_of_card_le_seq_count_le_one- In a round-robin sequence with m goods and n agents where m ≤ n, each agent appears at most once.
iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_le- In any picking sequence, the number of items allocated to an agent is at most their initial bundle size plus the number of times they appear in the sequence.
Finset.mem_singleton- An element x belongs to the singleton set {a} if and only if x = a.
Finset.card_le_one.mp- If a finite set has cardinality at most 1, any two elements in it are equal.
lt_irrefl- Strict inequality is irreflexive: a < a is false for any element a.
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 iterated_round_robin_item_preserving_swaps_zero_of_card_le_seq_count_le_one (n m : ℕ) [NeZero n] (hm : m ≤ n) (a : Fin n) : (round_robin_sequence n m).count a ≤ 1 := by have hinj : Function.Injective (fun (t : Fin m) => (⟨t.val % n, Nat.mod_lt _ (NeZero.pos n)⟩ : Fin n)) := by intro x y hxy simp only [Fin.mk.injEq] at hxy have hx : x.val < n := lt_of_lt_of_le x.isLt hm have hy : y.val < n := lt_of_lt_of_le y.isLt hm rw [Nat.mod_eq_of_lt hx, Nat.mod_eq_of_lt hy] at hxy ext exact hxy have hnodup : (round_robin_sequence n m).Nodup := by unfold round_robin_sequence exact List.nodup_ofFn.mpr hinj exact List.nodup_iff_count_le_one.mp hnodup atheorem iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_le {N G : Type*} [DecidableEq N] [DecidableEq G] (L : N → List G) (l : List N) (a : N) (st : (N → Finset G) × Finset G) : ((List.foldl (fun st a => picking_turn (L a) a st) st l).1 a).card ≤ (st.1 a).card + l.count a := by induction l generalizing st with | nil => simp | cons h t ih => simp only [List.foldl_cons, List.count_cons] have ih_st := ih (picking_turn (L h) h st) have hstep : ((picking_turn (L h) h st).1 a).card ≤ (st.1 a).card + if (h == a) = true then 1 else 0 := by unfold picking_turn split · next g hfind => dsimp only by_cases ha : h = a · subst ha rw [Function.update_self] simp only [beq_self_eq_true, ite_true] exact Finset.card_insert_le _ _ · rw [Function.update_of_ne (Ne.symm ha)] have : (h == a) = false := beq_false_of_ne ha simp [this] · simp omega/-- When m ≤ n, iterated Round Robin under item-preserving swaps terminates immediately with 0 manipulations. -/theorem iterated_round_robin_item_preserving_swaps_zero_of_card_le (n m : ℕ) [NeZero n] (hm : m ≤ n) (pref : Fin n → Fin m ≃ Fin m) (v : Fin n → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g) (hcons : ∀ (i : Fin n) (k l : Fin m), k < l → v i (pref i l) < v i (pref i k)) (f : ℕ → (Fin n → Fin m ≃ Fin m)) (hf0 : f 0 = pref) (T : ℕ) (hf : ∀ t < T, irr_step v (round_robin_sequence n m) (is_item_preserving_swap_bid (round_robin_sequence n m)) (f t) (f (t + 1))) : T = 0 := by by_contra hT have hT0 : 0 < T := Nat.pos_of_ne_zero hT have hstep := hf 0 hT0 obtain ⟨i, ⟨r, hadm, hlt⟩, -⟩ := hstep obtain ⟨k, l, hkl, hr, hg1, hg2⟩ := hadm set seq := round_robin_sequence n m have hcount : seq.count i ≤ 1 := iterated_round_robin_item_preserving_swaps_zero_of_card_le_seq_count_le_one n m hm i have h0 : (((fun _ : Fin n => (∅ : Finset (Fin m))), (∅ : Finset (Fin m))).1 i).card = 0 := by simp have hcard1 : (picking_sequence_outcome seq (f 0) i).card ≤ 1 := by have hcard := iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_le (fun a => List.ofFn (f 0 a)) seq i (fun _ => ∅, ∅) rw [h0] at hcard exact hcard.trans (by omega) have hcard2 : (picking_sequence_outcome seq (Function.update (f 0) i r) i).card ≤ 1 := by have hcard := iterated_round_robin_item_preserving_swaps_zero_of_card_le_card_foldl_le (fun a => List.ofFn (Function.update (f 0) i r a)) seq i (fun _ => ∅, ∅) rw [h0] at hcard exact hcard.trans (by omega) set g := (f 0 i) k have eA : picking_sequence_outcome seq (f 0) i = {g} := by ext x simp only [Finset.mem_singleton] exact ⟨fun hx => Finset.card_le_one.mp hcard1 x hx g hg1, fun hx => hx ▸ hg1⟩ have eB : picking_sequence_outcome seq (Function.update (f 0) i r) i = {g} := by ext x simp only [Finset.mem_singleton] exact ⟨fun hx => Finset.card_le_one.mp hcard2 x hx g hg2, fun hx => hx ▸ hg2⟩ rw [eA, eB] at hlt exact lt_irrefl _ hlt