AFTD Auto-Formalizing Theoretical Domains

picking_phi_entry_le

theoremverified

For the Round-Robin sequence of n agents and m goods, the 0-based rank phi_s of the item selected at turn s is at most s (the paper's 1 <= phi_s <= s, one-based).

Statement

theorem picking_phi_entry_le (n : ℕ) [NeZero n] (m : ℕ) (rank : Fin n → Fin m ≃ Fin m) (s : ℕ) :
    picking_phi_entry (round_robin_sequence n m) rank s ≤ s
Source
step towards round_robin_item_preserving_swaps_polynomial_convergence
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • picking_phi_entryThe coordinate phi_s of the potential of arXiv:2610.23040 (proof of Thm 3.13): at turn s the acting agent takes the highest-ranked item…
  • picking_prefix_state_allocated_card_leAfter s turns of a picking sequence at most s items have been allocated: every picking_turn inserts at most one item into the allocated set.
  • round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
  • 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…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

The proof, explained

At turn $s$, agent $a$ selects their most preferred item among those that have not yet been allocated. By a counting argument, at most $s$ items have been allocated in the first $s$ turns, so agent $a$'s top $s + 1$ preferred items cannot all be already allocated. Applying an auxiliary lemma on list search (`picking_phi_entry_le_find_mem_take`), the first unallocated item found by linear search must lie within this initial prefix of length $s + 1$. Therefore, its index in the preference list—its 0-based rank—is at most $s$.

  1. In the helper lemma `picking_phi_entry_le_find_mem_take`, the base case where $l$ is empty holds vacuously.

    We proceed by induction on the list $l$. When $l = []$, its prefix of length $k$ is empty, so no witness $x$ can exist, closing the base case.

    lines 6–8

      intro l
      induction l with
      | nil => intro k h; obtain ⟨x, hx, -⟩ := h; simp at hx
  2. In the inductive step $l = a :: as$, the case where prefix length $k = 0$ holds vacuously.

    We case split on $k$. When $k = 0$, the prefix `(a :: as).take 0` is empty, so again no satisfying witness can exist.

    lines 9–12

      | cons a as ih =>
        intro k h
        cases k with
        | zero => obtain ⟨x, hx, -⟩ := h; simp at hx
  3. When $k = k' + 1$ and the head element $a$ satisfies $p$, the head $a$ is the desired witness.

    We rewrite the prefix as $a :: as.\text{take } k'$. If $p(a) = \text{true}$, then `(a :: as).find? p` immediately evaluates to `some a`. Since $a$ is the head of the prefix, it is an element of that prefix.

    lines 13–16

    uses List.take_succ_cons, List.find?_cons

        | succ k' =>
          rw [List.take_succ_cons] at h ⊢
          by_cases hpa : p a = true
          · exact ⟨a, by rw [List.find?_cons, hpa], by simp⟩
  4. When $k = k' + 1$ and $p(a) = \text{false}$, the witness lies in the tail, and the inductive hypothesis finishes the helper lemma.

    Since $p(a) = \text{false}$ and the witness $x$ satisfies $p(x) = \text{true}$, $x$ cannot be $a$, so $x \in as.\text{take } k'$. Applying the inductive hypothesis to $as$ gives an element $g \in as.\text{take } k'$ returned by `as.find? p`. Because $p(a) = \text{false}$, `(a :: as).find? p` also returns $g$, which belongs to the prefix $a :: as.\text{take } k'$.

    lines 17–24

    uses List.mem_cons.mp, List.find?_cons

          · have hpa' : p a = false := by simpa using hpa
            obtain ⟨x, hx, hpx⟩ := h
            have hx' : x ∈ as.take k' := by
              rcases List.mem_cons.mp hx with h | h
              · subst h; rw [hpa'] at hpx; exact absurd hpx (by simp)
              · exact h
            obtain ⟨g, hg, hmem⟩ := ih k' ⟨x, hx', hpx⟩
            exact ⟨g, by rw [List.find?_cons, hpa']; exact hg, by simp [hmem]⟩
  5. In `picking_phi_entry_le`, if turn $s$ is out of bounds, the claim holds trivially.

    We unfold the definition of `picking_phi_entry` and case split on whether turn $s$ falls within the Round-Robin sequence. If $s$ is out of bounds, `seq[s]?` is `none` and the definition evaluates to $0 \le s$, which holds by linear arithmetic.

    lines 29–31

      unfold picking_phi_entry
      split
      · omega
  6. When turn $s$ selects agent $a$, the preference list of $a$ has length $m$ with no duplicates, and $s < m$.

    The Round-Robin sequence has length $m$, so the existence of an agent $a$ at turn $s$ implies $s < m$. Agent $a$'s preference list `List.ofFn (rank a)` has length $m$ and contains no duplicate elements because the preference ranking $\text{rank } a$ is a bijection, hence injective.

    lines 32–39

    uses List.length_ofFn, List.getElem?_eq_some_iff.mp, List.nodup_ofFn

      · rename_i a ha
        have hrr : (round_robin_sequence n m).length = m := by simp [round_robin_sequence]
        have hLlen : (List.ofFn ⇑(rank a)).length = m := List.length_ofFn
        have hslen : s < m := by
          have := (List.getElem?_eq_some_iff.mp ha).1
          omega
        have hLnodup : (List.ofFn ⇑(rank a)).Nodup := by
          rw [List.nodup_ofFn]; exact (rank a).injective
  7. The top $s + 1$ preferred goods of agent $a$ contain at least one good that has not yet been allocated.

    We argue by contradiction: suppose every good in the prefix of length $s + 1$ of agent $a$'s preference list were already allocated before turn $s$. Then this prefix set would be a subset of the allocated goods set. Because the preference list has no duplicates and $s < m$, this prefix set contains exactly $s + 1$ distinct goods. However, by `picking_prefix_state_allocated_card_le`, at most $s$ goods have been allocated in the first $s$ turns. By `Finset.card_le_card`, a set of size $s + 1$ cannot be a subset of a set of size at most $s$, yielding a contradiction.

    lines 40–56

    uses List.mem_toFinset, List.toFinset_card_of_nodup, List.take_sublist, List.length_take, picking_prefix_state_allocated_card_le, Finset.card_le_card

        have hwit : ∃ x ∈ (List.ofFn ⇑(rank a)).take (s + 1),
            (fun g => decide (g ∉ (picking_prefix_state (round_robin_sequence n m) rank s).2)) x = true := by
          by_contra h
          push Not at h
          have hsubset : ((List.ofFn ⇑(rank a)).take (s + 1)).toFinset ⊆
              (picking_prefix_state (round_robin_sequence n m) rank s).2 := by
            intro x hx
            rw [List.mem_toFinset] at hx
            have hx' := h x hx
            simpa using hx'
          have hcard : ((List.ofFn ⇑(rank a)).take (s + 1)).toFinset.card = s + 1 := by
            rw [List.toFinset_card_of_nodup ((List.take_sublist (s+1) _).nodup hLnodup),
              List.length_take, hLlen]
            omega
          have h2 := picking_prefix_state_allocated_card_le (round_robin_sequence n m) rank s
          have h3 := Finset.card_le_card hsubset
          omega
  8. The good $g$ chosen by agent $a$ at turn $s$ belongs to the prefix of length $s + 1$ of agent $a$'s preference list.

    Applying `picking_phi_entry_le_find_mem_take` with the unallocated good found in the previous step, `List.find?` returns an unallocated good $g$ that belongs to the prefix of length $s + 1$ of agent $a$'s preference list. Rewriting with this evaluation simplifies the definition of `picking_phi_entry` to the rank of $g$.

    lines 57–59

    uses picking_phi_entry_le_find_mem_take

        obtain ⟨g, hfind, hmem⟩ := picking_phi_entry_le_find_mem_take _ _ _ hwit
        rw [hfind]
        simp only
  9. The 0-based rank of the chosen good $g$ is at most $s$.

    Since $g$ belongs to the prefix of length $s + 1$, it is located at some index $i < \min(s + 1, m) \le s + 1$. By definition of `List.ofFn`, the $i$-th entry of the preference list is $(\text{rank } a)(i)$, so applying the inverse ranking $(\text{rank } a)^{-1}$ to $g$ yields index $i$. Since $i < s + 1$, we conclude $i \le s$ by linear arithmetic.

    lines 60–70

    uses List.mem_iff_getElem.mp, List.length_take, List.getElem_take, List.getElem_ofFn, Equiv.symm_apply_apply

        obtain ⟨i, hi, hig⟩ := List.mem_iff_getElem.mp hmem
        rw [List.length_take, hLlen] at hi
        have him : i < m := by omega
        rw [List.getElem_take] at hig
        rw [List.getElem_ofFn] at hig
        have hval : (rank a).symm g = ⟨i, him⟩ := by
          rw [← hig]
          exact Equiv.symm_apply_apply (rank a) ⟨i, him⟩
        rw [hval]
        show i ≤ s
        omega
List.take_succ_cons
Taking $k + 1$ elements from $a :: as$ yields $a$ followed by taking $k$ elements from $as$.
List.find?_cons
Finding the first element satisfying $p$ in $a :: as$ returns $a$ if $p(a) = \text{true}$, and otherwise searches $as$.
List.mem_cons.mp
If an element belongs to $a :: as$, it is either equal to $a$ or belongs to $as$.
List.length_ofFn
The length of a list generated by `List.ofFn f` on $\text{Fin } n$ is $n$.
List.getElem?_eq_some_iff.mp
If getting the element at index $s$ of a list succeeds, then $s$ is strictly less than the length of the list.
List.nodup_ofFn
A list constructed from a function on $\text{Fin } n$ contains no duplicates if and only if the function is injective.
List.mem_toFinset
An element belongs to `l.toFinset` if and only if it belongs to the list $l$.
List.toFinset_card_of_nodup
If a list has no duplicate elements, the cardinality of its set of elements equals the length of the list.
List.take_sublist
The prefix `l.take k` is a sublist of $l$.
List.length_take
The length of `l.take k` is $\min(k, l.\text{length})$.
picking_prefix_state_allocated_card_le
The number of goods allocated after $s$ turns of the picking sequence is at most $s$.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the superset.
picking_phi_entry_le_find_mem_take
If a prefix `l.take k` contains an element satisfying a Boolean predicate $p$, then `l.find? p` finds an element belonging to that same prefix.
List.mem_iff_getElem.mp
If an element is in a list, it appears at some index strictly less than the length of the list.
List.getElem_take
Accessing the $i$-th element of a prefix `xs.take j` yields the $i$-th element of $xs$.
List.getElem_ofFn
The $i$-th element of `List.ofFn f` is $f(i)$.
Equiv.symm_apply_apply
Applying the inverse of an equivalence to $e(x)$ yields $x$.

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

/-- If some element of the prefix `l.take k` satisfies the Boolean predicate `p`, then `l.find? p`returns an element lying in that same prefix. -/lemma picking_phi_entry_le_find_mem_take {α : Type*} (p : α → Bool) :    ∀ (l : List α) (k : ℕ), (∃ x ∈ l.take k, p x = true) →      ∃ g, l.find? p = some g ∧ g ∈ l.take k := by  intro l  induction l with  | nil => intro k h; obtain ⟨x, hx, -⟩ := h; simp at hx  | cons a as ih =>    intro k h    cases k with    | zero => obtain ⟨x, hx, -⟩ := h; simp at hx    | succ k' =>      rw [List.take_succ_cons] at h ⊢      by_cases hpa : p a = true      · exact ⟨a, by rw [List.find?_cons, hpa], by simp⟩      · have hpa' : p a = false := by simpa using hpa        obtain ⟨x, hx, hpx⟩ := h        have hx' : x ∈ as.take k' := by          rcases List.mem_cons.mp hx with h | h          · subst h; rw [hpa'] at hpx; exact absurd hpx (by simp)          · exact h        obtain ⟨g, hg, hmem⟩ := ih k' ⟨x, hx', hpx⟩        exact ⟨g, by rw [List.find?_cons, hpa']; exact hg, by simp [hmem]⟩/-- At turn s of Round Robin the selected item's 0-based rank is at most s. -/theorem picking_phi_entry_le (n : ℕ) [NeZero n] (m : ℕ) (rank : Fin n → Fin m ≃ Fin m) (s : ℕ) :    picking_phi_entry (round_robin_sequence n m) rank s ≤ s := by  unfold picking_phi_entry  split  · omega  · rename_i a ha    have hrr : (round_robin_sequence n m).length = m := by simp [round_robin_sequence]    have hLlen : (List.ofFn ⇑(rank a)).length = m := List.length_ofFn    have hslen : s < m := by      have := (List.getElem?_eq_some_iff.mp ha).1      omega    have hLnodup : (List.ofFn ⇑(rank a)).Nodup := by      rw [List.nodup_ofFn]; exact (rank a).injective    have hwit : ∃ x ∈ (List.ofFn ⇑(rank a)).take (s + 1),        (fun g => decide (g ∉ (picking_prefix_state (round_robin_sequence n m) rank s).2)) x = true := by      by_contra h      push Not at h      have hsubset : ((List.ofFn ⇑(rank a)).take (s + 1)).toFinset ⊆          (picking_prefix_state (round_robin_sequence n m) rank s).2 := by        intro x hx        rw [List.mem_toFinset] at hx        have hx' := h x hx        simpa using hx'      have hcard : ((List.ofFn ⇑(rank a)).take (s + 1)).toFinset.card = s + 1 := by        rw [List.toFinset_card_of_nodup ((List.take_sublist (s+1) _).nodup hLnodup),          List.length_take, hLlen]        omega      have h2 := picking_prefix_state_allocated_card_le (round_robin_sequence n m) rank s      have h3 := Finset.card_le_card hsubset      omega    obtain ⟨g, hfind, hmem⟩ := picking_phi_entry_le_find_mem_take _ _ _ hwit    rw [hfind]    simp only    obtain ⟨i, hi, hig⟩ := List.mem_iff_getElem.mp hmem    rw [List.length_take, hLlen] at hi    have him : i < m := by omega    rw [List.getElem_take] at hig    rw [List.getElem_ofFn] at hig    have hval : (rank a).symm g = ⟨i, him⟩ := by      rw [← hig]      exact Equiv.symm_apply_apply (rank a) ⟨i, him⟩    rw [hval]    show i ≤ s    omega
See it in the graphDiscuss this resultChallenge it