round_robin_two_mul_add_one_cover_pairs
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
- round_robin_two_mul_add_one_deviation_certificateRound-Robin with n agents and 2n+1 goods, any reports, agent i ≠ 0: for some good g of agent 0's bundle B_0 (its first pick a1), either…
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.
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.
uses
Nat.le_induction,picking_prefix_two_named_first_dev_bundle_step_none,picking_prefix_two_named_first_dev_bundle_stepprivate 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
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.
uses
List.ofFn_succ,List.find?_cons,decide_eq_trueprivate 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]
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.
uses
Equiv.swap_apply_left,Equiv.swap_apply_of_ne_of_neprivate 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 _ _
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.
uses
Prod.ext,Function.update_of_neprivate 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
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.
uses
picking_prefix_two_named_first_dev_bundle_mono,List.take_lengthprivate 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
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.
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
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.
uses
picking_prefix_state_update_of_not_mem_take,rt3_cover_turn_first,rt3_cover_window_congrhave 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
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}.
uses
picking_prefix_state_succ_step,picking_prefix_state_alloc_mono,rt3_cover_mem_final,Finset.eq_of_subset_of_card_le,Finset.card_pairobtain ⟨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
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.
uses
picking_prefix_state_alloc_monohave 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)
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.
uses
rt3_cover_two_first,picking_prefix_two_named_first_dev_bundleobtain ⟨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
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.
uses
round_robin_two_mul_add_one_window_tracehave 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
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.
uses
rt3_cover_two_first,picking_prefix_two_named_first_dev_bundle,rt3_cover_window_congr,rt3_cover_state_extobtain ⟨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
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.
uses
Finset.mem_union_left,Finset.mem_union_rightright 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.
- The theorem signature contains a small inline tactic (`by omega` on line 75) ensuring that the number of goods 2n+1 is positive.
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.
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)