round_robin_divergence_turn_actor
If only agent i deviates and the executions have identical allocated sets up to turn t but diverge at turn t + 1, then the agent acting at turn t must be agent i.
Statement
theorem round_robin_divergence_turn_actor (n m : ℕ) [NeZero n]
(b b' : Fin n → Fin m ≃ Fin m) (i : Fin n)
(hupd : b' = Function.update b i (b' i))
(t : ℕ) (ht : t < m)
(heq : ∀ s ≤ t, (picking_prefix_state (round_robin_sequence n m) b s).2 =
(picking_prefix_state (round_robin_sequence n m) b' s).2)
(hne : (picking_prefix_state (round_robin_sequence n m) b (t + 1)).2 ≠
(picking_prefix_state (round_robin_sequence n m) b' (t + 1)).2) :
(round_robin_sequence n m)[t]? = some i- Source
- step towards round_robin_phi_lex_strict_increase
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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 contradiction. Since only agent i changes their preference ranking, any other agent a ≠ i has identical rankings in both executions. If the agent acting at turn t were some a ≠ i, then because both runs have identical allocated items up to turn t, agent a would face the exact same available items and make the exact same choice, meaning the allocated sets would still match at turn t + 1. This contradicts the hypothesis that the allocated sets diverge at turn t + 1, so the active agent at turn t must be agent i.
The allocation state after k + 1 turns equals the result of executing agent a's turn on the state after k turns, where a is the agent at index k in the sequence.
Unfolding the definition of picking_prefix_state reveals that it folds picking_turn over the prefix of length k + 1. Rewriting this prefix as the prefix of length k followed by [a] via List.take_add_one and the hypothesis hk, the fold simplifies to applying picking_turn for agent a to the prefix state at turn k.
uses
List.take_add_onedsimp [picking_prefix_state] rw [List.take_add_one, hk] simp
If two states have identical sets of allocated items, they still have identical sets of allocated items after any agent executes a picking turn with preference list l.
Unfolding picking_turn shows that an agent examines their preference list l and picks the first item not in the allocated set (st.2). Because st.2 = st'.2, the unallocated items are identical in both states, so both states either pick the exact same item g or both find no available item. In either case, the updated sets of allocated items remain identical.
unfold picking_turn have hpred : (fun g => decide (g ∉ st.2)) = (fun g => decide (g ∉ st'.2)) := by rw [hst] rw [hpred] split · simp [hst] · exact hst
The round-robin sequence has length m, so at any turn t < m there is a well-defined scheduled agent a = (round_robin_sequence n m)[t].
Simplifying the definition of round_robin_sequence establishes that its length is m. Because t < m, linear arithmetic confirms t is within the list bounds, and List.getElem?_eq_getElem shows that the optional lookup at index t yields some a.
uses
List.getElem?_eq_getElemhave hlen : (round_robin_sequence n m).length = m := by simp [round_robin_sequence] have ht' : t < (round_robin_sequence n m).length := by omega set a := (round_robin_sequence n m)[t] have ha : (round_robin_sequence n m)[t]? = some a := List.getElem?_eq_getElem ht'
Assuming for contradiction that the acting agent a at turn t is not i, agent a has identical preferences under both profiles b and b'.
We assume for contradiction that a ≠ i. Because b' is obtained by updating b only at agent i, Function.update_of_ne confirms that b'(a) = b(a).
uses
Function.update_of_nehave heqi : a = i := by by_contra hne_ai have hba : b' a = b a := by rw [hupd] exact Function.update_of_ne hne_ai (b' i) b
If a ≠ i, the set of items allocated after turn t + 1 must be identical under b and b'.
By the prefix transition lemma round_robin_divergence_turn_actor_prefix_succ, the state at turn t + 1 is the result of agent a acting on the state at turn t with list b(a) (respectively, b'(a)). By the hypothesis heq, the sets of allocated items at turn t coincide. Since b'(a) = b(a), the preservation lemma round_robin_divergence_turn_actor_turn_snd_eq implies that the sets of allocated items after turn t + 1 must also coincide.
uses
round_robin_divergence_turn_actor_prefix_succ,le_rfl,round_robin_divergence_turn_actor_turn_snd_eqhave h1 : picking_prefix_state (round_robin_sequence n m) b (t + 1) = picking_turn (List.ofFn ⇑(b a)) a (picking_prefix_state (round_robin_sequence n m) b t) := round_robin_divergence_turn_actor_prefix_succ (round_robin_sequence n m) b t a ha have h2 : picking_prefix_state (round_robin_sequence n m) b' (t + 1) = picking_turn (List.ofFn ⇑(b' a)) a (picking_prefix_state (round_robin_sequence n m) b' t) := round_robin_divergence_turn_actor_prefix_succ (round_robin_sequence n m) b' t a ha have hst : (picking_prefix_state (round_robin_sequence n m) b t).2 = (picking_prefix_state (round_robin_sequence n m) b' t).2 := heq t le_rfl have hturn : (picking_turn (List.ofFn ⇑(b a)) a (picking_prefix_state (round_robin_sequence n m) b t)).2 = (picking_turn (List.ofFn ⇑(b' a)) a (picking_prefix_state (round_robin_sequence n m) b' t)).2 := by rw [hba] exact round_robin_divergence_turn_actor_turn_snd_eq a (List.ofFn ⇑(b a)) (picking_prefix_state (round_robin_sequence n m) b t) (picking_prefix_state (round_robin_sequence n m) b' t) hst
The assumption a ≠ i leads to a contradiction, proving a = i.
The equality of the allocated item sets at turn t + 1 directly contradicts the hypothesis hne that the allocated item sets diverge at turn t + 1. Hence, the assumption a ≠ i is refuted, leaving a = i.
apply hne rw [h1, h2, hturn]
The scheduled agent at turn t in the round-robin sequence is agent i.
Substituting a = i into the established fact that (round_robin_sequence n m)[t]? = some a yields (round_robin_sequence n m)[t]? = some i.
rw [heqi] at ha exact ha
List.take_add_one- Taking the first i + 1 elements of a list l is equal to taking the first i elements concatenated with the singleton list containing the (i + 1)-th element (or empty if the index is out of bounds).
List.getElem?_eq_getElem- For an index i strictly less than the length of list l, the optional lookup l[i]? evaluates to some l[i].
Function.update_of_ne- Evaluating a function updated at an input a' at any distinct input a ≠ a' returns the original value f(a).
round_robin_divergence_turn_actor_prefix_succ- The allocation state after k + 1 turns is obtained by applying agent a's picking turn to the state after k turns, where a is the agent at index k in the sequence.
le_rfl- The less-than-or-equal relation is reflexive (a ≤ a for all a).
round_robin_divergence_turn_actor_turn_snd_eq- If two allocation states have the same set of allocated items (their second components coincide), then applying a picking turn for agent a with preference list l results in states whose sets of allocated items still coincide.
- The source begins by establishing two helper lemmas: round_robin_divergence_turn_actor_prefix_succ decomposes the (k + 1)-step prefix state into a single turn applied to the k-step prefix state, and round_robin_divergence_turn_actor_turn_snd_eq proves that the set of allocated items after an agent's turn depends only on the set of already allocated items, not on how those items were distributed among agents.
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_divergence_turn_actor_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 dsimp [picking_prefix_state] rw [List.take_add_one, hk] simptheorem round_robin_divergence_turn_actor_turn_snd_eq {N G : Type*} [DecidableEq N] [DecidableEq G] (a : N) (l : List G) (st st' : (N → Finset G) × Finset G) (hst : st.2 = st'.2) : (picking_turn l a st).2 = (picking_turn l a st').2 := by unfold picking_turn have hpred : (fun g => decide (g ∉ st.2)) = (fun g => decide (g ∉ st'.2)) := by rw [hst] rw [hpred] split · simp [hst] · exact hst/-- When only agent i changes their bid, the earliest turn t < m where the allocated item set diverges between the two runs must be a turn where agent i acts. -/theorem round_robin_divergence_turn_actor (n m : ℕ) [NeZero n] (b b' : Fin n → Fin m ≃ Fin m) (i : Fin n) (hupd : b' = Function.update b i (b' i)) (t : ℕ) (ht : t < m) (heq : ∀ s ≤ t, (picking_prefix_state (round_robin_sequence n m) b s).2 = (picking_prefix_state (round_robin_sequence n m) b' s).2) (hne : (picking_prefix_state (round_robin_sequence n m) b (t + 1)).2 ≠ (picking_prefix_state (round_robin_sequence n m) b' (t + 1)).2) : (round_robin_sequence n m)[t]? = some i := by have hlen : (round_robin_sequence n m).length = m := by simp [round_robin_sequence] have ht' : t < (round_robin_sequence n m).length := by omega set a := (round_robin_sequence n m)[t] have ha : (round_robin_sequence n m)[t]? = some a := List.getElem?_eq_getElem ht' have heqi : a = i := by by_contra hne_ai have hba : b' a = b a := by rw [hupd] exact Function.update_of_ne hne_ai (b' i) b have h1 : picking_prefix_state (round_robin_sequence n m) b (t + 1) = picking_turn (List.ofFn ⇑(b a)) a (picking_prefix_state (round_robin_sequence n m) b t) := round_robin_divergence_turn_actor_prefix_succ (round_robin_sequence n m) b t a ha have h2 : picking_prefix_state (round_robin_sequence n m) b' (t + 1) = picking_turn (List.ofFn ⇑(b' a)) a (picking_prefix_state (round_robin_sequence n m) b' t) := round_robin_divergence_turn_actor_prefix_succ (round_robin_sequence n m) b' t a ha have hst : (picking_prefix_state (round_robin_sequence n m) b t).2 = (picking_prefix_state (round_robin_sequence n m) b' t).2 := heq t le_rfl have hturn : (picking_turn (List.ofFn ⇑(b a)) a (picking_prefix_state (round_robin_sequence n m) b t)).2 = (picking_turn (List.ofFn ⇑(b' a)) a (picking_prefix_state (round_robin_sequence n m) b' t)).2 := by rw [hba] exact round_robin_divergence_turn_actor_turn_snd_eq a (List.ofFn ⇑(b a)) (picking_prefix_state (round_robin_sequence n m) b t) (picking_prefix_state (round_robin_sequence n m) b' t) hst apply hne rw [h1, h2, hturn] rw [heqi] at ha exact ha