round_robin_runs_coincide_bundle_eq
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.
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.
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
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.
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.2Symmetrically, 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`.
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.2When 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.
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 rflThe 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$.
uses
List.take_add_one,List.foldl_appendsimp only [picking_prefix_state] rw [List.take_add_one, hk] simp [List.foldl_append]
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.
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
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.
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) hstepThe 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`.
uses
le_rflexact key seq.length le_rflThe 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.
uses
round_robin_runs_coincide_bundle_eq_fold_eqhave 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
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.
uses
List.take_eq_self_iff,le_rflhave 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]
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.
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`.
- The source file establishes three helper lemmas directly before the main theorem: `round_robin_runs_coincide_bundle_eq_turn_alloc_eq` (a single turn's bundle update is determined by the item allocated), `round_robin_runs_coincide_bundle_eq_prefix_succ` (recursive step for prefix states), and `round_robin_runs_coincide_bundle_eq_fold_eq` (full prefix-state agreement by induction). The explanation presents these helper lemmas and the final theorem in the sequence they occur.
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.
/-- 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]