AFTD Auto-Formalizing Theoretical Domains

round_robin_two_mul_add_one_cover_pairs

theoremverified

Round-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and 2n, and let agent i's bundle be {b1, b2}. Then either some report of agent i alone gives it a bundle containing both a2 and a3, or two reports of agent i give bundles whose union contains a2, a3, b1 and b2.

Statement

theorem round_robin_two_mul_add_one_cover_pairs (n : ℕ) [NeZero n]
    (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0)
    (a1 a2 a3 b1 b2 : Fin (2 * n + 1))
    (ha1 : a1 = rank 0 ⟨0, by omega⟩)
    (hp2 : a2 ∉ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank n).2 ∧
      a2 ∈ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (n + 1)).2)
    (hp3 : a3 ∉ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (2 * n)).2 ∧
      a3 ∈ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (2 * n + 1)).2)
    (hB0 : picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 = {a1, a2, a3})
    (hBi : picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i = {b1, b2})
    (hdist : a1 ≠ a2 ∧ a1 ≠ a3 ∧ a2 ≠ a3) :
    (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1),
        ({a2, a3} : Finset (Fin (2 * n + 1))) ⊆
          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
            (Function.update rank i r) i) ∨
    (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1),
        ({a2, a3, b1, b2} : Finset (Fin (2 * n + 1))) ⊆
          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
            (Function.update rank i r₁) i ∪
          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
            (Function.update rank i r₂) i)
Source
step towards round_robin_two_mul_add_one_deviation_certificate
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • round_robin_two_mul_add_one_window_traceRound-Robin with n agents and 2n+1 goods: change only agent i's report to r. Then at every time s between i's first turn and i's second…
  • picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
  • round_robin_two_mul_add_one_outcome_structureRound-Robin with n agents and 2n+1 goods, any reports: there are goods a2, a3 (agent 0's picks at turns n and 2n) and b1, b2 (agent i's…
  • picking_prefix_state_succ_stepTurn s of a picking sequence with s < length seq and s < m: if the active agent is a, there is a good p, not allocated after s turns, such…
  • picking_prefix_state_alloc_card_eqAfter s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods have been allocated (in…
  • picking_prefix_state_alloc_monoThe set of allocated goods is monotone in the number of turns: if s <= t then the goods allocated after s turns are allocated after t turns.
  • round_robin_sequence_getElem?_eqThe t-th turn (for t < m) of the Round-Robin sequence of n agents is agent t mod n.
  • picking_prefix_state_update_of_not_mem_takeChanging agent i's ranking does not change the state of a picking sequence after the first t turns if agent i does not pick in those turns.
  • 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.
  • 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…
Used by 1

The proof, explained

To show agent i can either acquire {a2, a3} alone or cover {a2, a3, b1, b2} across two reports, we first consider a deviation ranking a2 first and a3 second. If a3 remains unallocated at agent i's second turn, agent i secures both a2 and a3 directly. Otherwise, because agent i's deviation changes the set of allocated goods by at most one item, agent i's original second pick q must still be available at its second turn. Agent i can then combine two deviations—one securing a2 and q, and another securing its original first pick p and a3—whose union covers all four contested goods.

  1. If two preference profiles differ only for agent i, agree at step s, and agent i does not pick at any step in [s, t), then the allocation states remain identical at step t (`rt3_cover_window_congr`).

    By induction on u from s to t. At each intermediate step, either no pick occurs or another agent a ≠ i picks; since all other agents have identical preference lists across both profiles, their selections and the resulting state updates coincide.

    lines 1–24

    uses Nat.le_induction, picking_prefix_two_named_first_dev_bundle_step_none, picking_prefix_two_named_first_dev_bundle_step

    private lemma rt3_cover_window_congr {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}
        (seq : List N) (rank₁ rank₂ : N → Fin m ≃ G) (i : N) (s t : ℕ) (hst : s ≤ t)
        (hstart : picking_prefix_state seq rank₁ s = picking_prefix_state seq rank₂ s)
        (hr : ∀ a, a ≠ i → rank₁ a = rank₂ a)
        (hno : ∀ u, s ≤ u → u < t → seq[u]? ≠ some i) :
        picking_prefix_state seq rank₁ t = picking_prefix_state seq rank₂ t := by
      have haux : ∀ u, s ≤ u → u ≤ t →
          picking_prefix_state seq rank₁ u = picking_prefix_state seq rank₂ u := by
        intro u hsu
        induction u,hsu using Nat.le_induction with
        | base => intro _; exact hstart
        | succ u hsu ih =>
          intro hut
          have he := ih (by omega)
          rcases hg : seq[u]? with _ | a
          · rw [picking_prefix_two_named_first_dev_bundle_step_none seq rank₁ u hg,
              picking_prefix_two_named_first_dev_bundle_step_none seq rank₂ u hg,he]
          · have hai : a ≠ i := by
              intro hai
              exact hno u hsu (by omega) (hg.trans (congrArg some hai))
            rw [picking_prefix_two_named_first_dev_bundle_step seq rank₁ u a hg,
              picking_prefix_two_named_first_dev_bundle_step seq rank₂ u a hg,he,hr a hai]
      exact haux t hst le_rfl
    
  2. If agent i's top-ranked good under a ranking is unallocated, agent i picks it on its turn (`rt3_cover_turn_first`).

    Unfolding the definition of a picking turn on a non-empty preference list: because the top-ranked element is not yet in the allocated set, linear search finds it immediately as the first available good and assigns it to agent i.

    lines 25–36

    uses List.ofFn_succ, List.find?_cons, decide_eq_true

    private lemma rt3_cover_turn_first {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}
        (r : Fin m ≃ G) (hm : 0 < m) (i : N) (st : (N → Finset G) × Finset G)
        (hfree : r ⟨0,hm⟩ ∉ st.2) :
        picking_turn (List.ofFn ⇑r) i st =
          (Function.update st.1 i (insert (r ⟨0,hm⟩) (st.1 i)),insert (r ⟨0,hm⟩) st.2) := by
      obtain ⟨k,rfl⟩ : ∃ k, m = k+1 := ⟨m-1,by omega⟩
      have h0 : (⟨0,hm⟩ : Fin (k+1)) = 0 := rfl
      rw [h0] at hfree ⊢
      rw [List.ofFn_succ]
      unfold picking_turn
      rw [List.find?_cons,decide_eq_true hfree]
    
  3. For any two distinct elements x ≠ y from a set of size m > 1, there exists a permutation mapping the first two positions to x and y (`rt3_cover_two_first`).

    First transpose index 0 with x, placing x at index 0. Then transpose the image of index 1 with y; since x ≠ y, this second transposition leaves index 0 unchanged while placing y at index 1.

    lines 37–51

    uses Equiv.swap_apply_left, Equiv.swap_apply_of_ne_of_ne

    private lemma rt3_cover_two_first (m : ℕ) (hm : 1 < m) (x y : Fin m) (hxy : x ≠ y) :
        ∃ r : Fin m ≃ Fin m, r ⟨0,by omega⟩ = x ∧ r ⟨1,hm⟩ = y := by
      let z : Fin m := ⟨0,by omega⟩
      let o : Fin m := ⟨1,hm⟩
      let e := Equiv.swap z x
      have hez : e z = x := Equiv.swap_apply_left _ _
      have hzo : z ≠ o := by intro h; have := congrArg Fin.val h; dsimp [z,o] at this; omega
      have heo : e o ≠ x := by
        intro he
        exact hzo (e.injective (he.trans hez.symm)).symm
      refine ⟨e.trans (Equiv.swap (e o) y),?_,?_⟩
      · change Equiv.swap (e o) y (e z) = x
        rw [hez,Equiv.swap_apply_of_ne_of_ne heo.symm hxy]
      · exact Equiv.swap_apply_left _ _
    
  4. A state update that adds a single good to agent i's bundle and to the global pool of allocated goods, leaving all other agents' bundles unchanged, equals the standard state transition (`rt3_cover_state_ext`).

    By extensionality of pairs and functions: the allocated set component matches directly, agent i's bundle matches the updated bundle, and every other agent's bundle is preserved.

    lines 52–63

    uses Prod.ext, Function.update_of_ne

    private lemma rt3_cover_state_ext {N G : Type*} [DecidableEq N] [DecidableEq G]
        (st st' : (N → Finset G) × Finset G) (i : N) (p : G)
        (hA : st'.2 = insert p st.2) (hB : st'.1 i = insert p (st.1 i))
        (hother : ∀ j, j ≠ i → st'.1 j = st.1 j) :
        st' = (Function.update st.1 i (insert p (st.1 i)),insert p st.2) := by
      apply Prod.ext
      · funext j
        by_cases hji : j = i
        · subst j; simpa using hB
        · simpa [Function.update_of_ne hji] using hother j hji
      · exact hA
    
  5. Any good acquired by agent i at an intermediate prefix step remains in agent i's bundle in the final outcome (`rt3_cover_mem_final`).

    By monotonicity of the picking sequence, an agent's bundle grows monotonically as additional turns are executed up to the full sequence length.

    lines 64–70

    uses picking_prefix_two_named_first_dev_bundle_mono, List.take_length

    private lemma rt3_cover_mem_final {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}
        (seq : List N) (rank : N → Fin m ≃ G) (i : N) (s : ℕ) (hs : s ≤ seq.length)
        (g : G) (hg : g ∈ (picking_prefix_state seq rank s).1 i) :
        g ∈ picking_sequence_outcome seq rank i := by
      have hh := (picking_prefix_two_named_first_dev_bundle_mono seq rank s seq.length hs).1 i hg
      simpa only [picking_prefix_state,List.take_length,picking_sequence_outcome] using hh
    
  6. Agent i's picking turns in the round-robin sequence are exactly turns i and n+i, with no picks by agent i in the window between them.

    Since i ≠ 0 and i < n, we have 0 < i < n. In a round-robin sequence of length 2n+1, agent t mod n picks at turn t. Thus agent i picks at turn i and turn n+i, while for any turn u strictly between i and n+i, u mod n ≠ i, so agent i does not pick.

    lines 71–117

    uses round_robin_sequence_getElem?_eq, round_robin_two_mul_add_one_window_trace_mod

    /-- The valuation-free cover for 2n+1 goods: either one deviation of agent i secures both of agent 0's remaining picks, or two deviations secure all four contested goods between them. -/
    theorem round_robin_two_mul_add_one_cover_pairs (n : ℕ) [NeZero n]
        (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0)
        (a1 a2 a3 b1 b2 : Fin (2 * n + 1))
        (ha1 : a1 = rank 0 ⟨0, by omega⟩)
        (hp2 : a2 ∉ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank n).2 ∧
          a2 ∈ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (n + 1)).2)
        (hp3 : a3 ∉ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (2 * n)).2 ∧
          a3 ∈ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (2 * n + 1)).2)
        (hB0 : picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 = {a1, a2, a3})
        (hBi : picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i = {b1, b2})
        (hdist : a1 ≠ a2 ∧ a1 ≠ a3 ∧ a2 ≠ a3) :
        (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1),
            ({a2, a3} : Finset (Fin (2 * n + 1))) ⊆
              picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
                (Function.update rank i r) i) ∨
        (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1),
            ({a2, a3, b1, b2} : Finset (Fin (2 * n + 1))) ⊆
              picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
                (Function.update rank i r₁) i ∪
              picking_sequence_outcome (round_robin_sequence n (2 * n + 1))
                (Function.update rank i r₂) i) := by
      classical
      have hn := NeZero.pos n
      have hil := i.isLt
      have hip : 0 < i.val := by
        have hz : i.val ≠ 0 := by
          intro h; apply hi; exact Fin.ext (by simpa using h)
        omega
      let seq := round_robin_sequence n (2*n+1)
      let st := fun (r : Fin n → Fin (2*n+1) ≃ Fin (2*n+1)) (s : ℕ) => picking_prefix_state seq r s
      let upd := fun (r : Fin (2*n+1) ≃ Fin (2*n+1)) => Function.update rank i r
      let out := fun (r : Fin (2*n+1) ≃ Fin (2*n+1)) => picking_sequence_outcome seq (upd r) i
      have hlen : seq.length = 2*n+1 := by simp [seq,round_robin_sequence]
      have ht1 : seq[i.val]? = some i := by
        rw [round_robin_sequence_getElem?_eq n (2*n+1) i.val (by omega)]
        congr 1
        exact Fin.ext (Nat.mod_eq_of_lt hil)
      have ht2 : seq[n+i.val]? = some i := by
        rw [round_robin_sequence_getElem?_eq n (2*n+1) (n+i.val) (by omega)]
        congr 1
        exact Fin.ext (by simp [Nat.mod_eq_of_lt hil])
      have hno : ∀ u, i.val+1 ≤ u → u < n+i.val → seq[u]? ≠ some i := by
        intro u hu1 hu2 he
        have hg := round_robin_sequence_getElem?_eq n (2*n+1) u (by omega)
        have hv : u%n = i.val := congrArg Fin.val (Option.some.inj (hg.symm.trans he))
        exact round_robin_two_mul_add_one_window_trace_mod n u i.val hil (by omega) (by omega) hv
  7. Deviations by agent i do not affect the state before turn i, and any two deviations that result in the same state after turn i also yield identical states at turn n+i.

    Before turn i, only agents 0, ..., i-1 have picked, so the state at step i is unaffected by agent i's report. If a deviation ranks an unallocated good x first, agent i acquires x at turn i. Since agent i does not pick between turns i+1 and n+i, applying `rt3_cover_window_congr` shows that identical states at step i+1 propagate to identical states at step n+i.

    lines 118–148

    uses picking_prefix_state_update_of_not_mem_take, rt3_cover_turn_first, rt3_cover_window_congr

      have hpre (r : Fin (2*n+1) ≃ Fin (2*n+1)) : st (upd r) i.val = st rank i.val := by
        apply picking_prefix_state_update_of_not_mem_take
        intro hm
        obtain ⟨t,ht,he⟩ := List.getElem_of_mem hm
        rw [List.length_take] at ht
        rw [List.getElem_take] at he
        have hg := round_robin_sequence_getElem?_eq n (2*n+1) t (by omega)
        change seq[t]? = some (⟨t%n,Nat.mod_lt _ hn⟩ : Fin n) at hg
        rw [List.getElem?_eq_getElem (show t < seq.length by omega),he,Option.some_inj] at hg
        have hv := congrArg Fin.val hg
        simp only at hv
        rw [Nat.mod_eq_of_lt (by omega)] at hv
        omega
      have first (r : Fin (2*n+1) ≃ Fin (2*n+1)) (x : Fin (2*n+1))
          (hx : x ∉ (st rank i.val).2) (hr : r ⟨0,by omega⟩ = x) :
          st (upd r) (i.val+1) =
            (Function.update (st rank i.val).1 i (insert x ((st rank i.val).1 i)),
              insert x (st rank i.val).2) := by
        have hs : st (upd r) (i.val+1) =
            picking_turn (List.ofFn ⇑((upd r) i)) i (st (upd r) i.val) :=
          picking_prefix_two_named_first_dev_bundle_step seq (upd r) i.val i ht1
        have hur : upd r i = r := Function.update_self i r rank
        rw [hs,hpre r,hur]
        change picking_turn (List.ofFn ⇑r) i (st rank i.val) = _
        simpa only [hr] using rt3_cover_turn_first r (by omega) i (st rank i.val) (by rw [hr]; exact hx)
      have together (r₁ r₂ : Fin (2*n+1) ≃ Fin (2*n+1))
          (he : st (upd r₁) (i.val+1) = st (upd r₂) (i.val+1)) :
          st (upd r₁) (n+i.val) = st (upd r₂) (n+i.val) := by
        apply rt3_cover_window_congr seq (upd r₁) (upd r₂) i (i.val+1) (n+i.val) (by omega) he
        · intro a ha; simp [upd,Function.update_of_ne ha]
        · exact hno
  8. Under the truthful report, agent i's picks at turns i and n+i are two distinct goods p and q, and its bundle {b1, b2} equals {p, q}.

    At each of its turns i and n+i, agent i picks an available good, say p and q respectively. Since p is already allocated when turn n+i begins, p ≠ q. Both belong to agent i's final bundle. Since the bundle has size at most 2, it is exactly the two-element set {p, q}.

    lines 149–174

    uses picking_prefix_state_succ_step, picking_prefix_state_alloc_mono, rt3_cover_mem_final, Finset.eq_of_subset_of_card_le, Finset.card_pair

      obtain ⟨p,hpfree,hAp,hBp,hotherp,_⟩ :=
        picking_prefix_state_succ_step seq rank i.val (by omega) (by omega) i ht1
      obtain ⟨q,hqfree,hAq,hBq,_,_⟩ :=
        picking_prefix_state_succ_step seq rank (n+i.val) (by omega) (by omega) i ht2
      have hpA : p ∈ (st rank (i.val+1)).2 := by rw [hAp]; simp
      have hpq : p ≠ q := by
        intro he
        exact hqfree (he ▸ picking_prefix_state_alloc_mono seq rank (show i.val+1 ≤ n+i.val by omega) hpA)
      have hpmem : p ∈ picking_sequence_outcome seq rank i := by
        apply rt3_cover_mem_final seq rank i (i.val+1) (by omega) p
        rw [hBp]; simp
      have hqmem : q ∈ picking_sequence_outcome seq rank i := by
        apply rt3_cover_mem_final seq rank i (n+i.val+1) (by omega) q
        rw [hBq]; simp
      have hcard : (picking_sequence_outcome seq rank i).card ≤ 2 := by
        rw [hBi]
        exact (Finset.card_insert_le _ _).trans (by simp)
      have hset : ({p,q} : Finset (Fin (2*n+1))) = picking_sequence_outcome seq rank i := by
        apply Finset.eq_of_subset_of_card_le
        · intro g hg
          simp only [Finset.mem_insert,Finset.mem_singleton] at hg
          rcases hg with rfl | rfl
          · exact hpmem
          · exact hqmem
        · rw [Finset.card_pair hpq]
          exact hcard
  9. The target goods a2 and a3 are free at turns i and n+i respectively, with q ≠ a3, p ≠ a3, and a2 ≠ q.

    Agent 0 picks a2 at turn n > i, so a2 is unallocated before turn i. Agent 0 picks a3 at turn 2n > n+i, so a3 is unallocated before turn n+i. Since p and q are allocated at or before turn n+i < 2n, neither can equal a3. Moreover, a2 is allocated at turn n+1 ≤ n+i, whereas q is only chosen at turn n+i, so a2 ≠ q.

    lines 175–190

    uses picking_prefix_state_alloc_mono

      have ha2free : a2 ∉ (st rank i.val).2 := by
        intro hh
        exact hp2.1 (picking_prefix_state_alloc_mono seq rank (show i.val ≤ n by omega) hh)
      have ha3free : a3 ∉ (st rank (n+i.val)).2 := by
        intro hh
        exact hp3.1 (picking_prefix_state_alloc_mono seq rank (show n+i.val ≤ 2*n by omega) hh)
      have hqy : q ≠ a3 := by
        intro he
        have hqA : q ∈ (st rank (n+i.val+1)).2 := by rw [hAq]; simp
        exact hp3.1 (he ▸ picking_prefix_state_alloc_mono seq rank (show n+i.val+1 ≤ 2*n by omega) hqA)
      have hpy : p ≠ a3 := by
        intro he
        exact hp3.1 (he ▸ picking_prefix_state_alloc_mono seq rank (show i.val+1 ≤ 2*n by omega) hpA)
      have ha2q : a2 ≠ q := by
        intro he
        exact hqfree (he ▸ picking_prefix_state_alloc_mono seq rank (show n+1 ≤ n+i.val by omega) hp2.2)
  10. If a3 remains unallocated at turn n+i under the deviation rxy ranking a2 first and a3 second, agent i obtains {a2, a3}.

    Agent i reports rxy, which places a2 first and a3 second. At turn i, a2 is free, so agent i picks a2. If a3 is still free at turn n+i, agent i picks a3 as its second choice, so its final bundle contains {a2, a3}, satisfying the first disjunct.

    lines 191–196

    uses rt3_cover_two_first, picking_prefix_two_named_first_dev_bundle

      obtain ⟨rxy,hrxy0,hrxy1⟩ := rt3_cover_two_first (2*n+1) (by omega) a2 a3 hdist.2.2
      by_cases hy : a3 ∉ (st (upd rxy) (n+i.val)).2
      · left
        exact ⟨rxy,picking_prefix_two_named_first_dev_bundle seq rank rxy i i.val (n+i.val)
          (by omega) (by omega) ht1 ht2 (by omega) a2 a3 ha2free hy hrxy0 hrxy1⟩
      · have hyA : a3 ∈ (st (upd rxy) (n+i.val)).2 := not_not.mp hy
  11. If a3 is allocated before turn n+i under rxy, then good q must remain unallocated at turn n+i under rxy.

    By the window trace theorem, agent i's deviation at turn i changes the set of allocated goods at turn n+i by at most 1 element: |Allocated(rxy) \ Allocated(truth)| ≤ 1. If a3 is allocated under rxy, it belongs to this set difference because it was unallocated under truth. Since q ≠ a3, q cannot also belong to the difference. Since q was unallocated under truth at turn n+i, it must remain unallocated under rxy.

    lines 197–203

    uses round_robin_two_mul_add_one_window_trace

        have hqD : q ∉ (st (upd rxy) (n+i.val)).2 := by
          intro hh
          have hc := (round_robin_two_mul_add_one_window_trace n rank i rxy (n+i.val)
            (by omega) (by omega)).1
          have he := Finset.card_le_one.mp hc a3 (Finset.mem_sdiff.mpr ⟨hyA,ha3free⟩)
            q (Finset.mem_sdiff.mpr ⟨hh,hqfree⟩)
          exact hqy he.symm
  12. Two deviations rxq (ranking a2 first, q second) and rpy (ranking p first, a3 second) secure bundles containing {a2, q} and {p, a3} respectively.

    Deviation rxq ranks a2 first, so by step 7 it induces the same state at turn n+i as rxy, where q is free; thus agent i picks a2 and q. Deviation rpy ranks p first, so it induces the same state at turn n+i as the truthful run, where a3 is free; thus agent i picks p and a3.

    lines 204–220

    uses rt3_cover_two_first, picking_prefix_two_named_first_dev_bundle, rt3_cover_window_congr, rt3_cover_state_ext

        obtain ⟨rxq,hrxq0,hrxq1⟩ := rt3_cover_two_first (2*n+1) (by omega) a2 q ha2q
        have hexy : st (upd rxq) (n+i.val) = st (upd rxy) (n+i.val) :=
          together rxq rxy ((first rxq a2 ha2free hrxq0).trans (first rxy a2 ha2free hrxy0).symm)
        have hxq : ({a2,q} : Finset (Fin (2*n+1))) ⊆ out rxq :=
          picking_prefix_two_named_first_dev_bundle seq rank rxq i i.val (n+i.val)
            (by omega) (by omega) ht1 ht2 (by omega) a2 q ha2free
            (by change q ∉ (st (upd rxq) (n+i.val)).2; rw [hexy]; exact hqD) hrxq0 hrxq1
        obtain ⟨rpy,hrpy0,hrpy1⟩ := rt3_cover_two_first (2*n+1) (by omega) p a3 hpy
        have heorig : st (upd rpy) (n+i.val) = st rank (n+i.val) := by
          apply rt3_cover_window_congr seq (upd rpy) rank i (i.val+1) (n+i.val) (by omega)
            ((first rpy p hpfree hrpy0).trans (rt3_cover_state_ext _ _ i p hAp hBp hotherp).symm)
          · intro a ha; simp [upd,Function.update_of_ne ha]
          · exact hno
        have hpyout : ({p,a3} : Finset (Fin (2*n+1))) ⊆ out rpy :=
          picking_prefix_two_named_first_dev_bundle seq rank rpy i i.val (n+i.val)
            (by omega) (by omega) ht1 ht2 (by omega) p a3 hpfree
            (by change a3 ∉ (st (upd rpy) (n+i.val)).2; rw [heorig]; exact ha3free) hrpy0 hrpy1
  13. The union of agent i's bundles under rxq and rpy contains {a2, a3, b1, b2}, completing the second disjunct.

    The union contains {a2, q} ∪ {p, a3} = {a2, a3, p, q}. Since agent i's truthful bundle {b1, b2} equals {p, q}, all four goods a2, a3, b1, b2 are covered by the two outcomes combined.

    lines 221–236

    uses Finset.mem_union_left, Finset.mem_union_right

        right
        refine ⟨rxq,rpy,?_⟩
        have hbase : picking_sequence_outcome seq rank i ⊆ out rxq ∪ out rpy := by
          rw [← hset]
          intro g hg
          simp only [Finset.mem_insert,Finset.mem_singleton] at hg
          rcases hg with rfl | rfl
          · exact Finset.mem_union_right _ (hpyout (by simp))
          · exact Finset.mem_union_left _ (hxq (by simp))
        intro g hg
        simp only [Finset.mem_insert,Finset.mem_singleton] at hg
        rcases hg with rfl | rfl | rfl | rfl
        · exact Finset.mem_union_left _ (hxq (by simp))
        · exact Finset.mem_union_right _ (hpyout (by simp))
        · exact hbase (by rw [hBi]; simp)
        · exact hbase (by rw [hBi]; simp)
decide_eq_true
A decidable proposition is true if and only if its boolean decision evaluates to true.
Equiv.swap_apply_left
A transposition swapping a and b maps a to b.
Equiv.swap_apply_of_ne_of_ne
A transposition swapping a and b leaves any element distinct from both a and b unchanged.
Finset.card_pair
A finite set with two distinct elements has cardinality 2.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Finset.mem_union_left
If an element belongs to s, it belongs to s ∪ t.
Finset.mem_union_right
If an element belongs to t, it belongs to s ∪ t.
Function.update_of_ne
Updating a function at point a' does not change its value at any distinct point a ≠ a'.
List.find?_cons
Linear search on a non-empty list checks the head element first; if it satisfies the predicate, it returns that element, otherwise continuing on the tail.
List.ofFn_succ
The list generated by a function on Fin (n+1) decomposes into the value at 0 followed by the list generated on the remaining indices.
List.take_length
Taking the first l.length elements of a list l returns l.
Nat.le_induction
Induction on natural numbers starting from a base index: if P(m) holds and P(n) implies P(n+1) for all n ≥ m, then P(n) holds for all n ≥ m.
picking_prefix_state_alloc_mono
The set of allocated goods grows monotonically as the sequence progresses.
picking_prefix_state_succ_step
At any scheduled turn before all goods are exhausted, the active agent selects a uniquely determined available good, adding it to its bundle and to the allocated set.
picking_prefix_state_update_of_not_mem_take
Updating an agent's ranking does not affect the prefix state up to any step before that agent's first scheduled turn.
picking_prefix_two_named_first_dev_bundle
If an agent ranks x first and y second, and x is free at the agent's first turn and y is free at its second turn, the agent's final bundle contains {x, y}.
picking_prefix_two_named_first_dev_bundle_mono
The bundles held by each agent and the set of allocated goods are monotonic with respect to the prefix step.
picking_prefix_two_named_first_dev_bundle_step
If an agent is scheduled to pick at step s, the prefix state at step s+1 is obtained by applying that agent's picking turn to the state at step s.
picking_prefix_two_named_first_dev_bundle_step_none
If no agent is scheduled at step s, the prefix state at step s+1 is identical to the state at step s.
Prod.ext
Two pairs are equal if and only if their first components are equal and their second components are equal.
round_robin_sequence_getElem?_eq
In a round-robin sequence with n agents, the agent picking at turn t is t mod n.
round_robin_two_mul_add_one_window_trace
A unilateral deviation by agent i at turn i changes the set of allocated goods at any turn up to i+n by at most one good.
round_robin_two_mul_add_one_window_trace_mod
In a round-robin schedule, for any turn s strictly between agent i's turns i and i+n, s mod n ≠ i.
rt3_cover_mem_final
Any good in an agent's bundle at an intermediate prefix step remains in that agent's bundle in the final outcome.
rt3_cover_state_ext
A state update that adds a single good to agent i's bundle and to the allocated set, leaving other agents' bundles unchanged, equals the standard state transition.
rt3_cover_turn_first
If an agent's top-ranked good under a ranking is unallocated, the agent picks that good on its turn.
rt3_cover_two_first
Given any two distinct elements in a finite set of size at least 2, there exists a permutation placing them at indices 0 and 1.
rt3_cover_window_congr
If two preference profiles differ only for agent i and agent i does not pick between steps s and t, identical states at step s lead to identical states at step t.

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

private lemma rt3_cover_window_congr {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}    (seq : List N) (rank₁ rank₂ : N → Fin m ≃ G) (i : N) (s t : ℕ) (hst : s ≤ t)    (hstart : picking_prefix_state seq rank₁ s = picking_prefix_state seq rank₂ s)    (hr : ∀ a, a ≠ i → rank₁ a = rank₂ a)    (hno : ∀ u, s ≤ u → u < t → seq[u]? ≠ some i) :    picking_prefix_state seq rank₁ t = picking_prefix_state seq rank₂ t := by  have haux : ∀ u, s ≤ u → u ≤ t →      picking_prefix_state seq rank₁ u = picking_prefix_state seq rank₂ u := by    intro u hsu    induction u,hsu using Nat.le_induction with    | base => intro _; exact hstart    | succ u hsu ih =>      intro hut      have he := ih (by omega)      rcases hg : seq[u]? with _ | a      · rw [picking_prefix_two_named_first_dev_bundle_step_none seq rank₁ u hg,          picking_prefix_two_named_first_dev_bundle_step_none seq rank₂ u hg,he]      · have hai : a ≠ i := by          intro hai          exact hno u hsu (by omega) (hg.trans (congrArg some hai))        rw [picking_prefix_two_named_first_dev_bundle_step seq rank₁ u a hg,          picking_prefix_two_named_first_dev_bundle_step seq rank₂ u a hg,he,hr a hai]  exact haux t hst le_rflprivate lemma rt3_cover_turn_first {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}    (r : Fin m ≃ G) (hm : 0 < m) (i : N) (st : (N → Finset G) × Finset G)    (hfree : r ⟨0,hm⟩ ∉ st.2) :    picking_turn (List.ofFn ⇑r) i st =      (Function.update st.1 i (insert (r ⟨0,hm⟩) (st.1 i)),insert (r ⟨0,hm⟩) st.2) := by  obtain ⟨k,rfl⟩ : ∃ k, m = k+1 := ⟨m-1,by omega⟩  have h0 : (⟨0,hm⟩ : Fin (k+1)) = 0 := rfl  rw [h0] at hfree ⊢  rw [List.ofFn_succ]  unfold picking_turn  rw [List.find?_cons,decide_eq_true hfree]private lemma rt3_cover_two_first (m : ℕ) (hm : 1 < m) (x y : Fin m) (hxy : x ≠ y) :    ∃ r : Fin m ≃ Fin m, r ⟨0,by omega⟩ = x ∧ r ⟨1,hm⟩ = y := by  let z : Fin m := ⟨0,by omega⟩  let o : Fin m := ⟨1,hm⟩  let e := Equiv.swap z x  have hez : e z = x := Equiv.swap_apply_left _ _  have hzo : z ≠ o := by intro h; have := congrArg Fin.val h; dsimp [z,o] at this; omega  have heo : e o ≠ x := by    intro he    exact hzo (e.injective (he.trans hez.symm)).symm  refine ⟨e.trans (Equiv.swap (e o) y),?_,?_⟩  · change Equiv.swap (e o) y (e z) = x    rw [hez,Equiv.swap_apply_of_ne_of_ne heo.symm hxy]  · exact Equiv.swap_apply_left _ _private lemma rt3_cover_state_ext {N G : Type*} [DecidableEq N] [DecidableEq G]    (st st' : (N → Finset G) × Finset G) (i : N) (p : G)    (hA : st'.2 = insert p st.2) (hB : st'.1 i = insert p (st.1 i))    (hother : ∀ j, j ≠ i → st'.1 j = st.1 j) :    st' = (Function.update st.1 i (insert p (st.1 i)),insert p st.2) := by  apply Prod.ext  · funext j    by_cases hji : j = i    · subst j; simpa using hB    · simpa [Function.update_of_ne hji] using hother j hji  · exact hAprivate lemma rt3_cover_mem_final {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}    (seq : List N) (rank : N → Fin m ≃ G) (i : N) (s : ℕ) (hs : s ≤ seq.length)    (g : G) (hg : g ∈ (picking_prefix_state seq rank s).1 i) :    g ∈ picking_sequence_outcome seq rank i := by  have hh := (picking_prefix_two_named_first_dev_bundle_mono seq rank s seq.length hs).1 i hg  simpa only [picking_prefix_state,List.take_length,picking_sequence_outcome] using hh/-- The valuation-free cover for 2n+1 goods: either one deviation of agent i secures both of agent 0's remaining picks, or two deviations secure all four contested goods between them. -/theorem round_robin_two_mul_add_one_cover_pairs (n : ℕ) [NeZero n]    (rank : Fin n → Fin (2 * n + 1) ≃ Fin (2 * n + 1)) (i : Fin n) (hi : i ≠ 0)    (a1 a2 a3 b1 b2 : Fin (2 * n + 1))    (ha1 : a1 = rank 0 ⟨0, by omega⟩)    (hp2 : a2 ∉ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank n).2 ∧      a2 ∈ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (n + 1)).2)    (hp3 : a3 ∉ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (2 * n)).2 ∧      a3 ∈ (picking_prefix_state (round_robin_sequence n (2 * n + 1)) rank (2 * n + 1)).2)    (hB0 : picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank 0 = {a1, a2, a3})    (hBi : picking_sequence_outcome (round_robin_sequence n (2 * n + 1)) rank i = {b1, b2})    (hdist : a1 ≠ a2 ∧ a1 ≠ a3 ∧ a2 ≠ a3) :    (∃ r : Fin (2 * n + 1) ≃ Fin (2 * n + 1),        ({a2, a3} : Finset (Fin (2 * n + 1))) ⊆          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))            (Function.update rank i r) i) ∨    (∃ r₁ r₂ : Fin (2 * n + 1) ≃ Fin (2 * n + 1),        ({a2, a3, b1, b2} : Finset (Fin (2 * n + 1))) ⊆          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))            (Function.update rank i r₁) i ∪          picking_sequence_outcome (round_robin_sequence n (2 * n + 1))            (Function.update rank i r₂) i) := by  classical  have hn := NeZero.pos n  have hil := i.isLt  have hip : 0 < i.val := by    have hz : i.val ≠ 0 := by      intro h; apply hi; exact Fin.ext (by simpa using h)    omega  let seq := round_robin_sequence n (2*n+1)  let st := fun (r : Fin n → Fin (2*n+1) ≃ Fin (2*n+1)) (s : ℕ) => picking_prefix_state seq r s  let upd := fun (r : Fin (2*n+1) ≃ Fin (2*n+1)) => Function.update rank i r  let out := fun (r : Fin (2*n+1) ≃ Fin (2*n+1)) => picking_sequence_outcome seq (upd r) i  have hlen : seq.length = 2*n+1 := by simp [seq,round_robin_sequence]  have ht1 : seq[i.val]? = some i := by    rw [round_robin_sequence_getElem?_eq n (2*n+1) i.val (by omega)]    congr 1    exact Fin.ext (Nat.mod_eq_of_lt hil)  have ht2 : seq[n+i.val]? = some i := by    rw [round_robin_sequence_getElem?_eq n (2*n+1) (n+i.val) (by omega)]    congr 1    exact Fin.ext (by simp [Nat.mod_eq_of_lt hil])  have hno : ∀ u, i.val+1 ≤ u → u < n+i.val → seq[u]? ≠ some i := by    intro u hu1 hu2 he    have hg := round_robin_sequence_getElem?_eq n (2*n+1) u (by omega)    have hv : u%n = i.val := congrArg Fin.val (Option.some.inj (hg.symm.trans he))    exact round_robin_two_mul_add_one_window_trace_mod n u i.val hil (by omega) (by omega) hv  have hpre (r : Fin (2*n+1) ≃ Fin (2*n+1)) : st (upd r) i.val = st rank i.val := by    apply picking_prefix_state_update_of_not_mem_take    intro hm    obtain ⟨t,ht,he⟩ := List.getElem_of_mem hm    rw [List.length_take] at ht    rw [List.getElem_take] at he    have hg := round_robin_sequence_getElem?_eq n (2*n+1) t (by omega)    change seq[t]? = some (⟨t%n,Nat.mod_lt _ hn⟩ : Fin n) at hg    rw [List.getElem?_eq_getElem (show t < seq.length by omega),he,Option.some_inj] at hg    have hv := congrArg Fin.val hg    simp only at hv    rw [Nat.mod_eq_of_lt (by omega)] at hv    omega  have first (r : Fin (2*n+1) ≃ Fin (2*n+1)) (x : Fin (2*n+1))      (hx : x ∉ (st rank i.val).2) (hr : r ⟨0,by omega⟩ = x) :      st (upd r) (i.val+1) =        (Function.update (st rank i.val).1 i (insert x ((st rank i.val).1 i)),          insert x (st rank i.val).2) := by    have hs : st (upd r) (i.val+1) =        picking_turn (List.ofFn ⇑((upd r) i)) i (st (upd r) i.val) :=      picking_prefix_two_named_first_dev_bundle_step seq (upd r) i.val i ht1    have hur : upd r i = r := Function.update_self i r rank    rw [hs,hpre r,hur]    change picking_turn (List.ofFn ⇑r) i (st rank i.val) = _    simpa only [hr] using rt3_cover_turn_first r (by omega) i (st rank i.val) (by rw [hr]; exact hx)  have together (r₁ r₂ : Fin (2*n+1) ≃ Fin (2*n+1))      (he : st (upd r₁) (i.val+1) = st (upd r₂) (i.val+1)) :      st (upd r₁) (n+i.val) = st (upd r₂) (n+i.val) := by    apply rt3_cover_window_congr seq (upd r₁) (upd r₂) i (i.val+1) (n+i.val) (by omega) he    · intro a ha; simp [upd,Function.update_of_ne ha]    · exact hno  obtain ⟨p,hpfree,hAp,hBp,hotherp,_⟩ :=    picking_prefix_state_succ_step seq rank i.val (by omega) (by omega) i ht1  obtain ⟨q,hqfree,hAq,hBq,_,_⟩ :=    picking_prefix_state_succ_step seq rank (n+i.val) (by omega) (by omega) i ht2  have hpA : p ∈ (st rank (i.val+1)).2 := by rw [hAp]; simp  have hpq : p ≠ q := by    intro he    exact hqfree (he ▸ picking_prefix_state_alloc_mono seq rank (show i.val+1 ≤ n+i.val by omega) hpA)  have hpmem : p ∈ picking_sequence_outcome seq rank i := by    apply rt3_cover_mem_final seq rank i (i.val+1) (by omega) p    rw [hBp]; simp  have hqmem : q ∈ picking_sequence_outcome seq rank i := by    apply rt3_cover_mem_final seq rank i (n+i.val+1) (by omega) q    rw [hBq]; simp  have hcard : (picking_sequence_outcome seq rank i).card ≤ 2 := by    rw [hBi]    exact (Finset.card_insert_le _ _).trans (by simp)  have hset : ({p,q} : Finset (Fin (2*n+1))) = picking_sequence_outcome seq rank i := by    apply Finset.eq_of_subset_of_card_le    · intro g hg      simp only [Finset.mem_insert,Finset.mem_singleton] at hg      rcases hg with rfl | rfl      · exact hpmem      · exact hqmem    · rw [Finset.card_pair hpq]      exact hcard  have ha2free : a2 ∉ (st rank i.val).2 := by    intro hh    exact hp2.1 (picking_prefix_state_alloc_mono seq rank (show i.val ≤ n by omega) hh)  have ha3free : a3 ∉ (st rank (n+i.val)).2 := by    intro hh    exact hp3.1 (picking_prefix_state_alloc_mono seq rank (show n+i.val ≤ 2*n by omega) hh)  have hqy : q ≠ a3 := by    intro he    have hqA : q ∈ (st rank (n+i.val+1)).2 := by rw [hAq]; simp    exact hp3.1 (he ▸ picking_prefix_state_alloc_mono seq rank (show n+i.val+1 ≤ 2*n by omega) hqA)  have hpy : p ≠ a3 := by    intro he    exact hp3.1 (he ▸ picking_prefix_state_alloc_mono seq rank (show i.val+1 ≤ 2*n by omega) hpA)  have ha2q : a2 ≠ q := by    intro he    exact hqfree (he ▸ picking_prefix_state_alloc_mono seq rank (show n+1 ≤ n+i.val by omega) hp2.2)  obtain ⟨rxy,hrxy0,hrxy1⟩ := rt3_cover_two_first (2*n+1) (by omega) a2 a3 hdist.2.2  by_cases hy : a3 ∉ (st (upd rxy) (n+i.val)).2  · left    exact ⟨rxy,picking_prefix_two_named_first_dev_bundle seq rank rxy i i.val (n+i.val)      (by omega) (by omega) ht1 ht2 (by omega) a2 a3 ha2free hy hrxy0 hrxy1⟩  · have hyA : a3 ∈ (st (upd rxy) (n+i.val)).2 := not_not.mp hy    have hqD : q ∉ (st (upd rxy) (n+i.val)).2 := by      intro hh      have hc := (round_robin_two_mul_add_one_window_trace n rank i rxy (n+i.val)        (by omega) (by omega)).1      have he := Finset.card_le_one.mp hc a3 (Finset.mem_sdiff.mpr ⟨hyA,ha3free⟩)        q (Finset.mem_sdiff.mpr ⟨hh,hqfree⟩)      exact hqy he.symm    obtain ⟨rxq,hrxq0,hrxq1⟩ := rt3_cover_two_first (2*n+1) (by omega) a2 q ha2q    have hexy : st (upd rxq) (n+i.val) = st (upd rxy) (n+i.val) :=      together rxq rxy ((first rxq a2 ha2free hrxq0).trans (first rxy a2 ha2free hrxy0).symm)    have hxq : ({a2,q} : Finset (Fin (2*n+1))) ⊆ out rxq :=      picking_prefix_two_named_first_dev_bundle seq rank rxq i i.val (n+i.val)        (by omega) (by omega) ht1 ht2 (by omega) a2 q ha2free        (by change q ∉ (st (upd rxq) (n+i.val)).2; rw [hexy]; exact hqD) hrxq0 hrxq1    obtain ⟨rpy,hrpy0,hrpy1⟩ := rt3_cover_two_first (2*n+1) (by omega) p a3 hpy    have heorig : st (upd rpy) (n+i.val) = st rank (n+i.val) := by      apply rt3_cover_window_congr seq (upd rpy) rank i (i.val+1) (n+i.val) (by omega)        ((first rpy p hpfree hrpy0).trans (rt3_cover_state_ext _ _ i p hAp hBp hotherp).symm)      · intro a ha; simp [upd,Function.update_of_ne ha]      · exact hno    have hpyout : ({p,a3} : Finset (Fin (2*n+1))) ⊆ out rpy :=      picking_prefix_two_named_first_dev_bundle seq rank rpy i i.val (n+i.val)        (by omega) (by omega) ht1 ht2 (by omega) p a3 hpfree        (by change a3 ∉ (st (upd rpy) (n+i.val)).2; rw [heorig]; exact ha3free) hrpy0 hrpy1    right    refine ⟨rxq,rpy,?_⟩    have hbase : picking_sequence_outcome seq rank i ⊆ out rxq ∪ out rpy := by      rw [← hset]      intro g hg      simp only [Finset.mem_insert,Finset.mem_singleton] at hg      rcases hg with rfl | rfl      · exact Finset.mem_union_right _ (hpyout (by simp))      · exact Finset.mem_union_left _ (hxq (by simp))    intro g hg    simp only [Finset.mem_insert,Finset.mem_singleton] at hg    rcases hg with rfl | rfl | rfl | rfl    · exact Finset.mem_union_left _ (hxq (by simp))    · exact Finset.mem_union_right _ (hpyout (by simp))    · exact hbase (by rw [hBi]; simp)    · exact hbase (by rw [hBi]; simp)
See it in the graphDiscuss this resultChallenge it