AFTD Auto-Formalizing Theoretical Domains

iterated_round_robin_item_preserving_swaps_zero_of_card_le

theoremverified

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.

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

    lines 4–11

    uses Fin.mk.injEq, lt_of_lt_of_le, Nat.mod_eq_of_lt

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

    lines 12–15

    uses List.nodup_ofFn.mpr, List.nodup_iff_count_le_one.mp

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

    lines 21–25

    uses List.foldl_cons, List.count_cons

      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)
  4. 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.

    lines 26–40

    uses Function.update_self, beq_self_eq_true, ite_true, Finset.card_insert_le, Function.update_of_ne, Ne.symm, beq_false_of_ne

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

    lines 50–55

    uses Nat.pos_of_ne_zero

      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
  6. 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].

    lines 56–68

    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_le

      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)
  7. 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}.

    lines 69–77

    uses Finset.mem_singleton, Finset.card_le_one.mp

      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⟩
  8. 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.

    lines 78–79

    uses lt_irrefl

      rw [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

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