AFTD Auto-Formalizing Theoretical Domains

round_robin_runs_coincide_bundle_eq

theoremverified

If two Round-Robin executions have the same set of allocated items at each turn s <= m, then both executions produce identical final bundle allocations.

Statement

theorem round_robin_runs_coincide_bundle_eq (n m : ℕ) [NeZero n]
    (b b' : Fin n → Fin m ≃ Fin m)
    (h : ∀ s ≤ m, (picking_prefix_state (round_robin_sequence n m) b s).2 =
                 (picking_prefix_state (round_robin_sequence n m) b' s).2) :
    picking_sequence_outcome (round_robin_sequence n m) b =
    picking_sequence_outcome (round_robin_sequence n m) b'
Source
step towards round_robin_phi_lex_strict_increase
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • 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…
  • round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

The proof, explained

The theorem is proved by induction on the turn number $s \le m$ to show that the full allocation state (both the agents' bundles and the set of allocated items) is identical between the two Round-Robin executions at every step. In the inductive step, the state at turn $k+1$ is obtained by applying agent $a$'s picking turn to the state at turn $k$, where the states before the turn coincide by the induction hypothesis. Because the two runs allocate the same set of items at turn $k+1$, the item chosen by agent $a$ must be identical in both runs, meaning their bundle updates also coincide. Finally, since the sequence outcome is simply the bundle component of the state after all $m$ turns, the final bundle allocations of the two executions must be identical.

  1. If neither preference list has any remaining unallocated good, the bundle allocations are unchanged and therefore coincide.

    Unfolding the definition of `picking_turn` shows that each turn searches the agent's preference list for the first unallocated good. When neither search finds an available item, both executions leave the state unchanged, so their bundle allocations are trivially identical.

    lines 6–10

      unfold picking_turn at h ⊢
      cases hl : List.find? (fun g => decide (g ∉ st.2)) l with
      | none =>
        cases hl' : List.find? (fun g => decide (g ∉ st.2)) l' with
        | none => rfl
  2. It is impossible for preferences $l$ to find no available good while $l'$ finds an unallocated good $g'$.

    If $l$ finds `none` and $l'$ finds `some g'`, hypothesis $h$ states that the allocated sets agree, giving $st.2 = \operatorname{insert} g' st.2$, which means $g' \in st.2$ by `Finset.mem_insert_self`. However, `List.find?_some` ensures that $g' \notin st.2$, producing a contradiction.

    lines 11–17

    uses List.find?_some, Finset.mem_insert_self

        | some g' =>
          simp only [hl, hl'] at h
          have hg' : g' ∉ st.2 := by simpa using List.find?_some hl'
          exfalso
          apply hg'
          rw [h]
          exact Finset.mem_insert_self g' st.2
  3. Symmetrically, it is impossible for preferences $l$ to find an unallocated good $g$ while $l'$ finds no available good.

    If $l$ finds `some g` and $l'$ finds `none`, hypothesis $h$ yields $\operatorname{insert} g st.2 = st.2$. Thus $g \in st.2$ by `Finset.mem_insert_self`, contradicting $g \notin st.2$ from `List.find?_some`.

    lines 18–26

    uses List.find?_some, Finset.mem_insert_self

      | some g =>
        cases hl' : List.find? (fun g => decide (g ∉ st.2)) l' with
        | none =>
          simp only [hl, hl'] at h
          have hg : g ∉ st.2 := by simpa using List.find?_some hl
          exfalso
          apply hg
          rw [← h]
          exact Finset.mem_insert_self g st.2
  4. When both turns allocate goods $g$ and $g'$, they must choose the identical good ($g = g'$), so the bundle allocations match.

    Hypothesis $h$ implies $\operatorname{insert} g st.2 = \operatorname{insert} g' st.2$. Since $g \in \operatorname{insert} g' st.2$ by `Finset.mem_insert_self`, `Finset.mem_insert.mp` yields either $g = g'$ or $g \in st.2$. But $g \notin st.2$ by `List.find?_some`, forcing $g = g'$. Since both turns insert the same item into agent $a$'s bundle, the resulting bundle allocations are identical.

    lines 27–39

    uses List.find?_some, Finset.mem_insert_self, Finset.mem_insert.mp

        | some g' =>
          simp only [hl, hl'] at h ⊢
          have hg : g ∉ st.2 := by simpa using List.find?_some hl
          have hg' : g' ∉ st.2 := by simpa using List.find?_some hl'
          have hgg : g = g' := by
            have hmem : g ∈ insert g' st.2 := by
              rw [← h]
              exact Finset.mem_insert_self g st.2
            rcases Finset.mem_insert.mp hmem with h1 | h1
            · exact h1
            · exact absurd h1 hg
          subst hgg
          rfl
  5. The prefix state after $k + 1$ turns equals the result of agent $seq[k]$ taking a turn starting from the state after $k$ turns.

    Unfolding `picking_prefix_state`, the prefix of length $k + 1$ decomposes into the prefix of length $k$ followed by $seq[k]$ via `List.take_add_one`. Applying `List.foldl_append` expresses the fold over the concatenated list as executing one picking turn for agent $seq[k]$ from the prefix state at $k$.

    lines 47–49

    uses List.take_add_one, List.foldl_append

      simp only [picking_prefix_state]
      rw [List.take_add_one, hk]
      simp [List.foldl_append]
  6. To prove that the prefix states agree after $seq.\text{length}$ turns, it suffices to show they agree at every turn $s \le seq.\text{length}$ by induction on $s$, where the base case $s = 0$ holds trivially.

    We set up an induction on the turn counter $s$. At turn $0$, both prefix runs have taken $0$ turns and thus are in the initial state with empty bundles and no allocated items, which trivially match.

    lines 57–60

      have key : ∀ s ≤ seq.length, picking_prefix_state seq b s = picking_prefix_state seq b' s := by
        intro s hs
        induction s with
        | zero => rfl
  7. In the inductive step, if the two runs reach identical states after $k$ turns, they also reach identical states after $k + 1$ turns.

    Let $a = seq[k]$ be the active agent at turn $k$, whose existence is given by `List.getElem?_eq_getElem`. By `round_robin_runs_coincide_bundle_eq_prefix_succ`, the state after $k + 1$ turns is obtained by agent $a$ taking a turn from the state at $k$. By the induction hypothesis, the states at $k$ match. Since the allocated item sets agree at turn $k + 1$, `round_robin_runs_coincide_bundle_eq_turn_alloc_eq` implies the bundle allocations also agree. Finally, `Prod.ext` combines the equality of bundles and allocated items to conclude that the entire states are equal.

    lines 61–69

    uses List.getElem?_eq_getElem, round_robin_runs_coincide_bundle_eq_prefix_succ, round_robin_runs_coincide_bundle_eq_turn_alloc_eq, Prod.ext

        | succ k ih =>
          have hk : k < seq.length := by omega
          have ihk : picking_prefix_state seq b k = picking_prefix_state seq b' k := ih (by omega)
          obtain ⟨a, ha⟩ : ∃ a, seq[k]? = some a := ⟨_, List.getElem?_eq_getElem hk⟩
          have hstep := h (k+1) (by omega)
          rw [round_robin_runs_coincide_bundle_eq_prefix_succ seq b k a ha,
              round_robin_runs_coincide_bundle_eq_prefix_succ seq b' k a ha] at hstep ⊢
          rw [ihk] at hstep ⊢
          exact Prod.ext (round_robin_runs_coincide_bundle_eq_turn_alloc_eq _ a _ _ hstep) hstep
  8. The prefix states of the two executions are identical after $seq.\text{length}$ turns.

    Evaluating the proven inductive property at $s = seq.\text{length}$ with `le_rfl` concludes the lemma `round_robin_runs_coincide_bundle_eq_fold_eq`.

    line 70

    uses le_rfl

      exact key seq.length le_rfl
  9. The two Round-Robin executions reach the exact same state after all $m$ turns.

    The round-robin sequence has length $m$. By `round_robin_runs_coincide_bundle_eq_fold_eq`, because the allocated sets of items agree at every prefix turn $s \le m$, the complete prefix states after all $m$ turns are identical.

    lines 79–81

    uses round_robin_runs_coincide_bundle_eq_fold_eq

      have hlen : (round_robin_sequence n m).length = m := by
        simp [round_robin_sequence]
      have hkey := round_robin_runs_coincide_bundle_eq_fold_eq (round_robin_sequence n m) b b' (by omega) h
  10. The final outcome of a picking sequence is the bundle component of the prefix state after all turns.

    Unfolding `picking_sequence_outcome` and `picking_prefix_state`, taking all elements from the list yields the entire list by `List.take_eq_self_iff` and `le_rfl`. Thus, the outcome is definitionally the first component of the final prefix state.

    lines 82–87

    uses List.take_eq_self_iff, le_rfl

      have e : ∀ rank : Fin n → Fin m ≃ Fin m,
          picking_sequence_outcome (round_robin_sequence n m) rank
            = (picking_prefix_state (round_robin_sequence n m) rank (round_robin_sequence n m).length).1 := by
        intro rank
        simp only [picking_sequence_outcome, picking_prefix_state]
        rw [List.take_eq_self_iff _ |>.mpr le_rfl]
  11. Both Round-Robin executions produce identical final bundle allocations.

    Rewriting the outcomes of both runs as the bundle components of their respective final prefix states, the equality of the final states established in Step 9 immediately proves that the final bundle allocations coincide.

    line 88

      rw [e b, e b', hkey]
List.find?_some
If searching a list with `List.find? p` returns `some a`, then the element satisfies the predicate (`p a = true`).
Finset.mem_insert_self
An element `a` belongs to the set `insert a s`.
Finset.mem_insert.mp
If `a ∈ insert b s`, then either `a = b` or `a ∈ s`.
List.take_add_one
Taking `i + 1` elements from a list equals taking `i` elements concatenated with the singleton containing the `i`-th element (if it exists).
List.foldl_append
Folding a function over the concatenation of two lists `l ++ l'` is equivalent to folding over `l` and then folding over `l'` starting from the intermediate accumulator.
List.getElem?_eq_getElem
If an index `i` is strictly less than the length of list `l`, then indexing with `l[i]?` returns `some l[i]`.
round_robin_runs_coincide_bundle_eq_prefix_succ
The state of a picking sequence after `k + 1` turns equals the result of applying agent `seq[k]`'s picking turn to the state after `k` turns.
round_robin_runs_coincide_bundle_eq_turn_alloc_eq
If two picking turns starting from the same state end with the same set of allocated goods, the resulting bundle allocations are identical.
Prod.ext
Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
le_rfl
The inequality relation is reflexive: $a ≤ a$ for all $a$.
round_robin_runs_coincide_bundle_eq_fold_eq
If two runs of a picking sequence have identical allocated item sets after every prefix turn, then their full prefix states at the end of the sequence are identical.
List.take_eq_self_iff
Taking `n` elements from a list `x` returns `x` itself if and only if the length of `x` is at most `n`.

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

/-- If two picking turns starting from the same state allocate the same set of goods, they also give the same bundles. -/lemma round_robin_runs_coincide_bundle_eq_turn_alloc_eq {N G : Type*} [DecidableEq N] [DecidableEq G]    (st : (N → Finset G) × Finset G) (a : N) (l l' : List G)    (h : (picking_turn l a st).2 = (picking_turn l' a st).2) :    (picking_turn l a st).1 = (picking_turn l' a st).1 := by  unfold picking_turn at h ⊢  cases hl : List.find? (fun g => decide (g ∉ st.2)) l with  | none =>    cases hl' : List.find? (fun g => decide (g ∉ st.2)) l' with    | none => rfl    | some g' =>      simp only [hl, hl'] at h      have hg' : g' ∉ st.2 := by simpa using List.find?_some hl'      exfalso      apply hg'      rw [h]      exact Finset.mem_insert_self g' st.2  | some g =>    cases hl' : List.find? (fun g => decide (g ∉ st.2)) l' with    | none =>      simp only [hl, hl'] at h      have hg : g ∉ st.2 := by simpa using List.find?_some hl      exfalso      apply hg      rw [← h]      exact Finset.mem_insert_self g st.2    | some g' =>      simp only [hl, hl'] at h ⊢      have hg : g ∉ st.2 := by simpa using List.find?_some hl      have hg' : g' ∉ st.2 := by simpa using List.find?_some hl'      have hgg : g = g' := by        have hmem : g ∈ insert g' st.2 := by          rw [← h]          exact Finset.mem_insert_self g st.2        rcases Finset.mem_insert.mp hmem with h1 | h1        · exact h1        · exact absurd h1 hg      subst hgg      rfl/-- The prefix state after k+1 turns is the k-th turn applied to the state after k turns. -/lemma round_robin_runs_coincide_bundle_eq_prefix_succ {N G : Type*}    [DecidableEq N] [DecidableEq G]    {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (k : ℕ) (a : N) (hk : seq[k]? = some a) :    picking_prefix_state seq rank (k+1) =      picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank k) := by  simp only [picking_prefix_state]  rw [List.take_add_one, hk]  simp [List.foldl_append]/-- If the allocated sets of two picking-sequence runs agree after every prefix, the full prefix states agree. -/lemma round_robin_runs_coincide_bundle_eq_fold_eq {N G : Type*}    [DecidableEq N] [DecidableEq G] {m : ℕ}    (seq : List N) (b b' : N → Fin m ≃ G) (hseq : seq.length ≤ m)    (h : ∀ s ≤ m, (picking_prefix_state seq b s).2 = (picking_prefix_state seq b' s).2) :    picking_prefix_state seq b seq.length = picking_prefix_state seq b' seq.length := by  have key : ∀ s ≤ seq.length, picking_prefix_state seq b s = picking_prefix_state seq b' s := by    intro s hs    induction s with    | zero => rfl    | succ k ih =>      have hk : k < seq.length := by omega      have ihk : picking_prefix_state seq b k = picking_prefix_state seq b' k := ih (by omega)      obtain ⟨a, ha⟩ : ∃ a, seq[k]? = some a := ⟨_, List.getElem?_eq_getElem hk⟩      have hstep := h (k+1) (by omega)      rw [round_robin_runs_coincide_bundle_eq_prefix_succ seq b k a ha,          round_robin_runs_coincide_bundle_eq_prefix_succ seq b' k a ha] at hstep ⊢      rw [ihk] at hstep ⊢      exact Prod.ext (round_robin_runs_coincide_bundle_eq_turn_alloc_eq _ a _ _ hstep) hstep  exact key seq.length le_rfl/-- If two Round-Robin runs have identical allocated item sets at every step up to m, then every agent receives the exact same bundle in both runs. -/theorem round_robin_runs_coincide_bundle_eq (n m : ℕ) [NeZero n]    (b b' : Fin n → Fin m ≃ Fin m)    (h : ∀ s ≤ m, (picking_prefix_state (round_robin_sequence n m) b s).2 =                 (picking_prefix_state (round_robin_sequence n m) b' s).2) :    picking_sequence_outcome (round_robin_sequence n m) b =    picking_sequence_outcome (round_robin_sequence n m) b' := by  have hlen : (round_robin_sequence n m).length = m := by    simp [round_robin_sequence]  have hkey := round_robin_runs_coincide_bundle_eq_fold_eq (round_robin_sequence n m) b b' (by omega) h  have e : ∀ rank : Fin n → Fin m ≃ Fin m,      picking_sequence_outcome (round_robin_sequence n m) rank        = (picking_prefix_state (round_robin_sequence n m) rank (round_robin_sequence n m).length).1 := by    intro rank    simp only [picking_sequence_outcome, picking_prefix_state]    rw [List.take_eq_self_iff _ |>.mpr le_rfl]  rw [e b, e b', hkey]
See it in the graphDiscuss this resultChallenge it