AFTD Auto-Formalizing Theoretical Domains

picking_prefix_two_named_first_dev_bundle

theoremverified

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

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.

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

    lines 1–8

    uses List.take_add_one, Option.toList_some, List.foldl_append, List.foldl_cons, List.foldl_nil

    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]
    
  2. 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.

    lines 9–15

    uses List.take_add_one, Option.toList_none, List.append_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]
    
  3. 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.

    lines 16–27

    uses picking_sequence_outcome_update_mem_of_first_free_mem_turn_bundle, Finset.mem_insert_of_mem

    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 hg
    
  4. 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.

    lines 28–42

    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_mono

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

    lines 43–67

    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_ne

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

    lines 68–87

    uses List.ofFn_succ, decide_eq_false, not_not.mpr, decide_eq_true, List.find?_cons, Function.update_self, Finset.mem_insert_self

    theorem 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 _ _
    
  7. 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.

    lines 88–104

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

    lines 105–116

    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_getElem

      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]
  9. 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.

    lines 117–124

    uses picking_prefix_two_named_first_dev_bundle_mono, picking_prefix_state_update_of_not_mem_take, Function.update_self

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

    lines 125–131

    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_alloc

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

    lines 132–135

    uses picking_prefix_two_named_first_dev_bundle_step, picking_prefix_two_named_first_dev_bundle_turn_second

      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)
  12. 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.

    lines 136–145

    uses picking_prefix_two_named_first_dev_bundle_mono, Finset.mem_insert, Finset.mem_singleton

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

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

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