AFTD Auto-Formalizing Theoretical Domains

round_robin_divergence_turn_actor

theoremverified

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.

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

    lines 6–8

    uses List.take_add_one

      dsimp [picking_prefix_state]
      rw [List.take_add_one, hk]
      simp
  2. 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.

    lines 14–20

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

    lines 32–36

    uses List.getElem?_eq_getElem

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

    lines 37–41

    uses Function.update_of_ne

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

    lines 42–56

    uses round_robin_divergence_turn_actor_prefix_succ, le_rfl, round_robin_divergence_turn_actor_turn_snd_eq

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

    lines 57–58

        apply hne
        rw [h1, h2, hturn]
  7. 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.

    lines 59–60

      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.

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