picking_prefix_two_named_first_dev_bundle
In 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 at t1 in the original run and y is unallocated at t2 in the run where i reports r (r ranks x first, y second). Then that run gives agent i both x and y.
Statement
theorem picking_prefix_two_named_first_dev_bundle {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (r : Fin m ≃ G) (i : N) (t₁ t₂ : ℕ) (hm : 1 < m) (hseq : seq.length ≤ m) (h₁ : seq[t₁]? = some i) (h₂ : seq[t₂]? = some i) (hlt : t₁ < t₂) (x y : G) (hx : x ∉ (picking_prefix_state seq rank t₁).2) (hy : y ∉ (picking_prefix_state seq (Function.update rank i r) t₂).2) (h0 : r ⟨0, by omega⟩ = x) (h1 : r ⟨1, hm⟩ = y) : ({x, y} : Finset G) ⊆ picking_sequence_outcome seq (Function.update rank i r) i
- Source
- step towards round_robin_two_mul_add_one_deviation_certificate
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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.
- picking_sequence_outcome_update_mem_of_first_freeIn a picking-sequence run, if agent i's first turn is turn t and the good g that i's new report r ranks first is still unallocated after…
- 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_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_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…
- 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…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 2
- 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…
- round_robin_two_mul_add_one_cover_pairsRound-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…
The proof, explained
To show that agent i receives both items x and y under a deviation where i reports preference r ranking x first and y second, the proof traces agent i's first turn t₀ ≤ t₁ and its subsequent turn t₂. Because agent i does not act before turn t₀, the state up to t₀ is identical to the original run where x was unallocated, so agent i claims x at turn t₀. By turn t₂, item x is already held by agent i while item y remains unallocated, causing agent i to claim its second choice y at turn t₂. Monotonicity of prefix state transitions guarantees that items acquired by agent i remain in its bundle through the end of the sequence.
The prefix state at step s + 1 equals the result of agent a taking a turn from the state at step s, provided a is scheduled at step s.
Unfolding the definition of picking_prefix_state, the prefix of length s + 1 decomposes into the prefix of length s concatenated with [a] via List.take_add_one and Option.toList_some. Splitting the fold over this concatenation using List.foldl_append evaluates the first s turns and then processes the single turn for agent a via List.foldl_cons and List.foldl_nil.
uses
List.take_add_one,Option.toList_some,List.foldl_append,List.foldl_cons,List.foldl_niltheorem picking_prefix_two_named_first_dev_bundle_step {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (a : N) (h : seq[s]? = some a) : picking_prefix_state seq rank (s + 1) = picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank s) := by unfold picking_prefix_state rw [List.take_add_one, h, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil]
The prefix state at step s + 1 is identical to the state at step s whenever step s is past the end of the sequence.
When seq[s]? = none, taking s + 1 elements yields the same list as taking s elements because appending the empty list (Option.toList_none) leaves the taken prefix unchanged via List.append_nil.
uses
List.take_add_one,Option.toList_none,List.append_niltheorem picking_prefix_two_named_first_dev_bundle_step_none {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (h : seq[s]? = none) : picking_prefix_state seq rank (s + 1) = picking_prefix_state seq rank s := by unfold picking_prefix_state rw [List.take_add_one, h, Option.toList_none, List.append_nil]
In a single picking turn, each agent's bundle and the total set of allocated goods are non-decreasing under subset inclusion.
For individual bundles, picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle guarantees that previously allocated items are retained. For the set of allocated goods, if an item is picked it is inserted into the set (preserving prior items by Finset.mem_insert_of_mem), and if no free item is available the allocated set is unchanged.
uses
picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle,Finset.mem_insert_of_memtheorem picking_prefix_two_named_first_dev_bundle_turn_mono {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (a : N) (st : (N → Finset G) × Finset G) : (∀ j, st.1 j ⊆ (picking_turn l a st).1 j) ∧ st.2 ⊆ (picking_turn l a st).2 := by constructor · intro j g hg exact picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle l a st j g hg · intro g hg dsimp [picking_turn] split · exact Finset.mem_insert_of_mem hg · exact hg
Prefix states are monotonic over time: for s ≤ t, each agent's bundle and the total set of allocated goods at step s are subsets of those at step t.
By induction on t ≥ s using Nat.le_induction, the base case t = s is reflexivity (subset_refl). For the step from t to t + 1, if no agent is scheduled the state is unchanged by picking_prefix_two_named_first_dev_bundle_step_none; if an agent is scheduled, the state advances by a single turn via picking_prefix_two_named_first_dev_bundle_step, and single-turn monotonicity (picking_prefix_two_named_first_dev_bundle_turn_mono) together with the induction hypothesis completes the step.
uses
Nat.le_induction,subset_refl,picking_prefix_two_named_first_dev_bundle_step_none,picking_prefix_two_named_first_dev_bundle_step,picking_prefix_two_named_first_dev_bundle_turn_monotheorem picking_prefix_two_named_first_dev_bundle_mono {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s t : ℕ) (hst : s ≤ t) : (∀ j, (picking_prefix_state seq rank s).1 j ⊆ (picking_prefix_state seq rank t).1 j) ∧ (picking_prefix_state seq rank s).2 ⊆ (picking_prefix_state seq rank t).2 := by induction t, hst using Nat.le_induction with | base => exact ⟨fun _ => subset_refl _, subset_refl _⟩ | succ t _ ih => rcases h : seq[t]? with _ | a · rw [picking_prefix_two_named_first_dev_bundle_step_none seq rank t h] exact ih · rw [picking_prefix_two_named_first_dev_bundle_step seq rank t a h] obtain ⟨h1, h2⟩ := picking_prefix_two_named_first_dev_bundle_turn_mono (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank t) exact ⟨fun j => (ih.1 j).trans (h1 j), ih.2.trans h2⟩
At any step s, every good in any agent j's bundle belongs to the total set of allocated goods.
By induction on s: at step 0 all bundles are empty. In the inductive step, if no agent acts the state is unchanged. If an agent a acts and picks item g', then for agent j = a, any item in j's bundle is either g' (in the allocated set by Finset.mem_insert_self) or was already in j's bundle (in the allocated set by the induction hypothesis and Finset.mem_insert_of_mem). If j ≠ a, j's bundle is unchanged by Function.update_of_ne, so all its items were already allocated.
uses
picking_prefix_two_named_first_dev_bundle_step_none,picking_prefix_two_named_first_dev_bundle_step,Function.update_self,Finset.mem_insert,Finset.mem_insert_self,Finset.mem_insert_of_mem,Function.update_of_netheorem picking_prefix_two_named_first_dev_bundle_sub_alloc {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (j : N) : (picking_prefix_state seq rank s).1 j ⊆ (picking_prefix_state seq rank s).2 := by induction s with | zero => simp [picking_prefix_state] | succ t ih => rcases h : seq[t]? with _ | a · rw [picking_prefix_two_named_first_dev_bundle_step_none seq rank t h] exact ih · rw [picking_prefix_two_named_first_dev_bundle_step seq rank t a h] intro g hg dsimp [picking_turn] at hg ⊢ split at hg · next g' _ => dsimp only at hg ⊢ by_cases hja : j = a · subst hja rw [Function.update_self, Finset.mem_insert] at hg rcases hg with rfl | hg · exact Finset.mem_insert_self _ _ · exact Finset.mem_insert_of_mem (ih hg) · rw [Function.update_of_ne hja] at hg exact Finset.mem_insert_of_mem (ih hg) · exact ih hg
If an agent acts with ranking r when r(0) is already allocated and r(1) is free, the agent receives r(1).
Representing the number of goods as m = k + 2, the agent's priority list begins with r(0) followed by r(1) via List.ofFn_succ. The picking turn sequentially searches for the first unallocated item: since r(0) is already allocated, the search skips it by decide_eq_false and List.find?_cons; since r(1) is unallocated, the search selects it by decide_eq_true. Thus r(1) is inserted into the agent's bundle by Finset.mem_insert_self.
uses
List.ofFn_succ,decide_eq_false,not_not.mpr,decide_eq_true,List.find?_cons,Function.update_self,Finset.mem_insert_selftheorem picking_prefix_two_named_first_dev_bundle_turn_second {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (r : Fin m ≃ G) (hm : 1 < m) (i : N) (st : (N → Finset G) × Finset G) (h0 : r ⟨0, by omega⟩ ∈ st.2) (h1 : r ⟨1, hm⟩ ∉ st.2) : r ⟨1, hm⟩ ∈ (picking_turn (List.ofFn (r : Fin m → G)) i st).1 i := by obtain ⟨k, rfl⟩ : ∃ k, m = k + 2 := ⟨m - 2, by omega⟩ have e0 : (⟨0, by omega⟩ : Fin (k + 2)) = 0 := rfl have e1 : (⟨1, hm⟩ : Fin (k + 2)) = 1 := rfl rw [e0] at h0 rw [e1] at h1 ⊢ rw [List.ofFn_succ, List.ofFn_succ] dsimp [picking_turn] have hd0 : decide (r 0 ∉ st.2) = false := decide_eq_false (not_not.mpr h0) have hd1 : decide (r 1 ∉ st.2) = true := decide_eq_true h1 rw [List.find?_cons, hd0] dsimp only rw [List.find?_cons, hd1] dsimp only rw [Function.update_self] exact Finset.mem_insert_self _ _
The final outcome of the picking sequence equals the state after running all steps, and turn t₂ occurs within the sequence bounds.
By List.take_length, taking the prefix of length seq.length yields the entire sequence, identifying picking_sequence_outcome with the allocation component of the state at seq.length. Since agent i is scheduled at turn t₂, List.getElem?_eq_some_iff.mp confirms that t₂ < seq.length.
uses
List.take_length,List.getElem?_eq_some_iff.mp/-- If agent i reports x first and y second, x is still free at its first turn and y is still free at its second turn, then i's bundle in that run contains both x and y. -/ theorem picking_prefix_two_named_first_dev_bundle {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (r : Fin m ≃ G) (i : N) (t₁ t₂ : ℕ) (hm : 1 < m) (hseq : seq.length ≤ m) (h₁ : seq[t₁]? = some i) (h₂ : seq[t₂]? = some i) (hlt : t₁ < t₂) (x y : G) (hx : x ∉ (picking_prefix_state seq rank t₁).2) (hy : y ∉ (picking_prefix_state seq (Function.update rank i r) t₂).2) (h0 : r ⟨0, by omega⟩ = x) (h1 : r ⟨1, hm⟩ = y) : ({x, y} : Finset G) ⊆ picking_sequence_outcome seq (Function.update rank i r) i := by classical set rank' := Function.update rank i r with hrank' -- the outcome is the state after all turns have hout : picking_sequence_outcome seq rank' = (picking_prefix_state seq rank' seq.length).1 := by unfold picking_sequence_outcome picking_prefix_state rw [List.take_length] have ht2 : t₂ < seq.length := (List.getElem?_eq_some_iff.mp h₂).1 -- i's first turn
Let t₀ be the first turn at which agent i is scheduled in the sequence; then t₀ ≤ t₁ and agent i does not appear in the prefix before t₀.
Using Nat.find on the non-empty set of turns where agent i acts, t₀ is the minimal such turn (Nat.find_spec). Because i acts at turn t₁, minimality implies t₀ ≤ t₁ by Nat.find_min'. Any appearance of i in the prefix of length t₀ would correspond to an index k < t₀ by List.getElem_of_mem and List.length_take, contradicting the minimality of t₀ via Nat.find_min.
uses
Nat.find_spec,Nat.find_min',List.getElem_of_mem,List.length_take,lt_of_lt_of_le,min_le_left,Nat.find_min,List.getElem_take,List.getElem?_eq_getElemhave hex : ∃ t, seq[t]? = some i := ⟨t₁, h₁⟩ let t₀ := Nat.find hex have ht₀ : seq[t₀]? = some i := Nat.find_spec hex have ht₀le : t₀ ≤ t₁ := Nat.find_min' hex h₁ have hnot : i ∉ seq.take t₀ := by intro hmem obtain ⟨k, hk, hki⟩ := List.getElem_of_mem hmem rw [List.length_take] at hk have hk' : k < t₀ := lt_of_lt_of_le hk (min_le_left _ _) apply Nat.find_min hex hk' rw [List.getElem_take] at hki rw [List.getElem?_eq_getElem (by omega), hki]
Item x is unallocated at turn t₀ in the original run, and the prefix state at turn t₀ under the deviated profile rank' is identical to that under rank.
Since x is free at turn t₁ and t₀ ≤ t₁, monotonicity (picking_prefix_two_named_first_dev_bundle_mono) implies that x is also unallocated at turn t₀. Moreover, because agent i does not act in the sequence prior to turn t₀, changing i's reported ranking to r does not alter the state up to t₀ by picking_prefix_state_update_of_not_mem_take. In addition, rank' i = r by Function.update_self.
uses
picking_prefix_two_named_first_dev_bundle_mono,picking_prefix_state_update_of_not_mem_take,Function.update_selfhave hfree : r ⟨0, by omega⟩ ∉ (picking_prefix_state seq rank t₀).2 := by rw [h0] intro hc exact hx ((picking_prefix_two_named_first_dev_bundle_mono seq rank t₀ t₁ ht₀le).2 hc) -- x is in i's bundle right after turn t₀ of the deviated run have hpre : picking_prefix_state seq rank' t₀ = picking_prefix_state seq rank t₀ := picking_prefix_state_update_of_not_mem_take seq rank i r t₀ hnot have hri : rank' i = r := Function.update_self i r rank
Agent i receives item x at turn t₀ under rank', and x remains in i's bundle and is allocated at turn t₂.
At turn t₀, the state advances by picking_prefix_two_named_first_dev_bundle_step. Because rank' i = r has r(0) = x and x is unallocated, picking_sequence_outcome_update_mem_of_first_free_turn_first_free ensures that i receives x, so x enters i's bundle at step t₀ + 1. Since t₀ ≤ t₁ < t₂, monotonicity (picking_prefix_two_named_first_dev_bundle_mono) guarantees that x remains in i's bundle at turn t₂, which also implies that x is in the allocated set at t₂ by picking_prefix_two_named_first_dev_bundle_sub_alloc.
uses
picking_prefix_two_named_first_dev_bundle_step,picking_sequence_outcome_update_mem_of_first_free_turn_first_free,picking_prefix_two_named_first_dev_bundle_mono,picking_prefix_two_named_first_dev_bundle_sub_allochave hx1 : x ∈ (picking_prefix_state seq rank' (t₀ + 1)).1 i := by rw [picking_prefix_two_named_first_dev_bundle_step seq rank' t₀ i ht₀, hpre, hri, ← h0] exact picking_sequence_outcome_update_mem_of_first_free_turn_first_free r (by omega) i _ hfree have hx2 : x ∈ (picking_prefix_state seq rank' t₂).1 i := (picking_prefix_two_named_first_dev_bundle_mono seq rank' (t₀ + 1) t₂ (by omega)).1 i hx1 have hxa : x ∈ (picking_prefix_state seq rank' t₂).2 := picking_prefix_two_named_first_dev_bundle_sub_alloc seq rank' t₂ i hx2
Agent i receives item y at turn t₂ under rank'.
At turn t₂, agent i acts again under profile rank'. Its top choice r(0) = x is already allocated, but its second choice r(1) = y is unallocated by hypothesis. By picking_prefix_two_named_first_dev_bundle_turn_second, agent i takes y on this turn, so y belongs to i's bundle at step t₂ + 1.
uses
picking_prefix_two_named_first_dev_bundle_step,picking_prefix_two_named_first_dev_bundle_turn_secondhave hy1 : y ∈ (picking_prefix_state seq rank' (t₂ + 1)).1 i := by rw [picking_prefix_two_named_first_dev_bundle_step seq rank' t₂ i h₂, hri, ← h1] exact picking_prefix_two_named_first_dev_bundle_turn_second r hm i _ (by rw [h0]; exact hxa) (by rw [h1]; exact hy)
Both x and y belong to agent i's bundle in the final outcome, so {x, y} ⊆ picking_sequence_outcome seq rank' i.
Monotonicity of prefix states to the end of the sequence (seq.length) ensures that x (acquired at t₀ + 1) and y (acquired at t₂ + 1) both remain in agent i's bundle in the final state. Decomposing membership in {x, y} via Finset.mem_insert and Finset.mem_singleton confirms that both elements are in i's final outcome.
uses
picking_prefix_two_named_first_dev_bundle_mono,Finset.mem_insert,Finset.mem_singletonhave hmono := (picking_prefix_two_named_first_dev_bundle_mono seq rank' (t₂ + 1) seq.length (by omega)).1 i have hmono0 := (picking_prefix_two_named_first_dev_bundle_mono seq rank' (t₀ + 1) seq.length (by omega)).1 i rw [hout] intro g hg rw [Finset.mem_insert, Finset.mem_singleton] at hg rcases hg with rfl | rfl · exact hmono0 hx1 · exact hmono hy1
List.take_add_one- Taking i + 1 elements from a list equals taking i elements concatenated with the i-th element (if it exists) as a list.
Option.toList_some- The list associated with an Option of the form some a is the singleton list [a].
Option.toList_none- The list associated with none is the empty list.
List.foldl_append- Folding over a concatenated list l ++ l' equals folding over l, and then folding over l' starting from that intermediate accumulator.
List.foldl_cons- Folding over a cons list a :: l equals folding over l starting from f b a.
List.foldl_nil- Folding over an empty list leaves the accumulator unchanged.
List.append_nil- Appending the empty list to any list leaves the list unchanged.
picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle- In a single picking turn, any item already in an agent's allocated bundle remains in that bundle.
Finset.mem_insert_of_mem- If an element belongs to a finite set, it also belongs to the set with an element inserted.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or was already in s.
Finset.mem_insert_self- An element belongs to the set obtained by inserting it into any finite set.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
Nat.le_induction- Induction principle for natural numbers starting from a base index m.
subset_refl- The subset relation is reflexive: every set is a subset of itself.
Function.update_self- Evaluating a function updated at point a with value v at the point a yields v.
Function.update_of_ne- Evaluating a function updated at a' at a distinct point a leaves the value unchanged.
List.ofFn_succ- The list generated from a function on Fin (n + 1) starts with f(0) followed by the list of subsequent values.
decide_eq_false- If a proposition is false, its decidable boolean representation is false.
not_not.mpr- A true proposition implies its double negation.
decide_eq_true- If a proposition is true, its decidable boolean representation is true.
List.find?_cons- Searching for the first element satisfying a predicate in a cons list checks the head and recurses on the tail if the predicate is false.
List.take_length- Taking l.length elements from a list l returns the entire list l.
List.getElem?_eq_some_iff.mp- If looking up index i in a list succeeds, then i is strictly less than the length of the list.
Nat.find_spec- The minimal natural number satisfying a predicate satisfies the predicate.
Nat.find_min'- The minimal natural number satisfying a predicate is at most any other witness.
Nat.find_min- No natural number strictly smaller than the minimal witness satisfies the predicate.
List.getElem_of_mem- Any element belonging to a list appears at some valid index in the list.
List.length_take- The length of taking i elements from a list is the minimum of i and the length of the list.
lt_of_lt_of_le- Strict inequality and non-strict inequality are transitive: a < b and b ≤ c implies a < c.
min_le_left- The minimum of two values is at most the first value.
List.getElem_take- The i-th element of a prefix of a list equals the i-th element of the original list.
List.getElem?_eq_getElem- Indexing an element within bounds via getElem? yields some containing that element.
picking_prefix_two_named_first_dev_bundle_step- If agent a is scheduled at turn s, the prefix state at s + 1 is obtained by executing agent a's turn from the state at s.
picking_prefix_two_named_first_dev_bundle_step_none- If turn s is beyond the sequence, the prefix state at s + 1 is identical to the state at s.
picking_prefix_two_named_first_dev_bundle_turn_mono- In any single turn, each agent's bundle and the total set of allocated goods are non-decreasing.
picking_prefix_two_named_first_dev_bundle_mono- For s ≤ t, all agents' bundles and the set of allocated goods at step s are subsets of those at step t.
picking_prefix_two_named_first_dev_bundle_sub_alloc- At any step, every good held in an agent's bundle belongs to the total set of allocated goods.
picking_prefix_two_named_first_dev_bundle_turn_second- If an agent acts with ranking r when r(0) is allocated and r(1) is free, the agent receives r(1).
picking_prefix_state_update_of_not_mem_take- If an agent does not act in the first t turns, changing that agent's reported ranking does not affect the state at step t.
picking_sequence_outcome_update_mem_of_first_free_turn_first_free- If an agent acts with ranking r and r(0) is unallocated, the agent receives r(0).
- Linear arithmetic conditions (such as 0 < m and index constraints) within type annotations and step justifications are discharged automatically via omega.
- The proof identifies agent i's very first turn t₀ via Nat.find, which may occur strictly before t₁, ensuring that the state prior to t₀ is completely unaffected by agent i's deviation.
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 picking_prefix_two_named_first_dev_bundle_step {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (a : N) (h : seq[s]? = some a) : picking_prefix_state seq rank (s + 1) = picking_turn (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank s) := by unfold picking_prefix_state rw [List.take_add_one, h, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil]theorem picking_prefix_two_named_first_dev_bundle_step_none {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (h : seq[s]? = none) : picking_prefix_state seq rank (s + 1) = picking_prefix_state seq rank s := by unfold picking_prefix_state rw [List.take_add_one, h, Option.toList_none, List.append_nil]theorem picking_prefix_two_named_first_dev_bundle_turn_mono {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (a : N) (st : (N → Finset G) × Finset G) : (∀ j, st.1 j ⊆ (picking_turn l a st).1 j) ∧ st.2 ⊆ (picking_turn l a st).2 := by constructor · intro j g hg exact picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle l a st j g hg · intro g hg dsimp [picking_turn] split · exact Finset.mem_insert_of_mem hg · exact hgtheorem picking_prefix_two_named_first_dev_bundle_mono {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s t : ℕ) (hst : s ≤ t) : (∀ j, (picking_prefix_state seq rank s).1 j ⊆ (picking_prefix_state seq rank t).1 j) ∧ (picking_prefix_state seq rank s).2 ⊆ (picking_prefix_state seq rank t).2 := by induction t, hst using Nat.le_induction with | base => exact ⟨fun _ => subset_refl _, subset_refl _⟩ | succ t _ ih => rcases h : seq[t]? with _ | a · rw [picking_prefix_two_named_first_dev_bundle_step_none seq rank t h] exact ih · rw [picking_prefix_two_named_first_dev_bundle_step seq rank t a h] obtain ⟨h1, h2⟩ := picking_prefix_two_named_first_dev_bundle_turn_mono (List.ofFn ⇑(rank a)) a (picking_prefix_state seq rank t) exact ⟨fun j => (ih.1 j).trans (h1 j), ih.2.trans h2⟩theorem picking_prefix_two_named_first_dev_bundle_sub_alloc {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) (j : N) : (picking_prefix_state seq rank s).1 j ⊆ (picking_prefix_state seq rank s).2 := by induction s with | zero => simp [picking_prefix_state] | succ t ih => rcases h : seq[t]? with _ | a · rw [picking_prefix_two_named_first_dev_bundle_step_none seq rank t h] exact ih · rw [picking_prefix_two_named_first_dev_bundle_step seq rank t a h] intro g hg dsimp [picking_turn] at hg ⊢ split at hg · next g' _ => dsimp only at hg ⊢ by_cases hja : j = a · subst hja rw [Function.update_self, Finset.mem_insert] at hg rcases hg with rfl | hg · exact Finset.mem_insert_self _ _ · exact Finset.mem_insert_of_mem (ih hg) · rw [Function.update_of_ne hja] at hg exact Finset.mem_insert_of_mem (ih hg) · exact ih hgtheorem picking_prefix_two_named_first_dev_bundle_turn_second {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (r : Fin m ≃ G) (hm : 1 < m) (i : N) (st : (N → Finset G) × Finset G) (h0 : r ⟨0, by omega⟩ ∈ st.2) (h1 : r ⟨1, hm⟩ ∉ st.2) : r ⟨1, hm⟩ ∈ (picking_turn (List.ofFn (r : Fin m → G)) i st).1 i := by obtain ⟨k, rfl⟩ : ∃ k, m = k + 2 := ⟨m - 2, by omega⟩ have e0 : (⟨0, by omega⟩ : Fin (k + 2)) = 0 := rfl have e1 : (⟨1, hm⟩ : Fin (k + 2)) = 1 := rfl rw [e0] at h0 rw [e1] at h1 ⊢ rw [List.ofFn_succ, List.ofFn_succ] dsimp [picking_turn] have hd0 : decide (r 0 ∉ st.2) = false := decide_eq_false (not_not.mpr h0) have hd1 : decide (r 1 ∉ st.2) = true := decide_eq_true h1 rw [List.find?_cons, hd0] dsimp only rw [List.find?_cons, hd1] dsimp only rw [Function.update_self] exact Finset.mem_insert_self _ _/-- If agent i reports x first and y second, x is still free at its first turn and y is still free at its second turn, then i's bundle in that run contains both x and y. -/theorem picking_prefix_two_named_first_dev_bundle {N G : Type*} [DecidableEq N] [DecidableEq G] [Fintype G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (r : Fin m ≃ G) (i : N) (t₁ t₂ : ℕ) (hm : 1 < m) (hseq : seq.length ≤ m) (h₁ : seq[t₁]? = some i) (h₂ : seq[t₂]? = some i) (hlt : t₁ < t₂) (x y : G) (hx : x ∉ (picking_prefix_state seq rank t₁).2) (hy : y ∉ (picking_prefix_state seq (Function.update rank i r) t₂).2) (h0 : r ⟨0, by omega⟩ = x) (h1 : r ⟨1, hm⟩ = y) : ({x, y} : Finset G) ⊆ picking_sequence_outcome seq (Function.update rank i r) i := by classical set rank' := Function.update rank i r with hrank' -- the outcome is the state after all turns have hout : picking_sequence_outcome seq rank' = (picking_prefix_state seq rank' seq.length).1 := by unfold picking_sequence_outcome picking_prefix_state rw [List.take_length] have ht2 : t₂ < seq.length := (List.getElem?_eq_some_iff.mp h₂).1 -- i's first turn have hex : ∃ t, seq[t]? = some i := ⟨t₁, h₁⟩ let t₀ := Nat.find hex have ht₀ : seq[t₀]? = some i := Nat.find_spec hex have ht₀le : t₀ ≤ t₁ := Nat.find_min' hex h₁ have hnot : i ∉ seq.take t₀ := by intro hmem obtain ⟨k, hk, hki⟩ := List.getElem_of_mem hmem rw [List.length_take] at hk have hk' : k < t₀ := lt_of_lt_of_le hk (min_le_left _ _) apply Nat.find_min hex hk' rw [List.getElem_take] at hki rw [List.getElem?_eq_getElem (by omega), hki] have hfree : r ⟨0, by omega⟩ ∉ (picking_prefix_state seq rank t₀).2 := by rw [h0] intro hc exact hx ((picking_prefix_two_named_first_dev_bundle_mono seq rank t₀ t₁ ht₀le).2 hc) -- x is in i's bundle right after turn t₀ of the deviated run have hpre : picking_prefix_state seq rank' t₀ = picking_prefix_state seq rank t₀ := picking_prefix_state_update_of_not_mem_take seq rank i r t₀ hnot have hri : rank' i = r := Function.update_self i r rank have hx1 : x ∈ (picking_prefix_state seq rank' (t₀ + 1)).1 i := by rw [picking_prefix_two_named_first_dev_bundle_step seq rank' t₀ i ht₀, hpre, hri, ← h0] exact picking_sequence_outcome_update_mem_of_first_free_turn_first_free r (by omega) i _ hfree have hx2 : x ∈ (picking_prefix_state seq rank' t₂).1 i := (picking_prefix_two_named_first_dev_bundle_mono seq rank' (t₀ + 1) t₂ (by omega)).1 i hx1 have hxa : x ∈ (picking_prefix_state seq rank' t₂).2 := picking_prefix_two_named_first_dev_bundle_sub_alloc seq rank' t₂ i hx2 have hy1 : y ∈ (picking_prefix_state seq rank' (t₂ + 1)).1 i := by rw [picking_prefix_two_named_first_dev_bundle_step seq rank' t₂ i h₂, hri, ← h1] exact picking_prefix_two_named_first_dev_bundle_turn_second r hm i _ (by rw [h0]; exact hxa) (by rw [h1]; exact hy) have hmono := (picking_prefix_two_named_first_dev_bundle_mono seq rank' (t₂ + 1) seq.length (by omega)).1 i have hmono0 := (picking_prefix_two_named_first_dev_bundle_mono seq rank' (t₀ + 1) seq.length (by omega)).1 i rw [hout] intro g hg rw [Finset.mem_insert, Finset.mem_singleton] at hg rcases hg with rfl | rfl · exact hmono0 hx1 · exact hmono hy1