picking_phi_entry_le
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$.
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.
intro l induction l with | nil => intro k h; obtain ⟨x, hx, -⟩ := h; simp at hx
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.
| cons a as ih => intro k h cases k with | zero => obtain ⟨x, hx, -⟩ := h; simp at hxWhen $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.
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⟩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'$.
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]⟩
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.
unfold picking_phi_entry split · omega
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.
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).injectiveThe 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.
uses
List.mem_toFinset,List.toFinset_card_of_nodup,List.take_sublist,List.length_take,picking_prefix_state_allocated_card_le,Finset.card_le_cardhave 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
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$.
uses
picking_phi_entry_le_find_mem_takeobtain ⟨g, hfind, hmem⟩ := picking_phi_entry_le_find_mem_take _ _ _ hwit rw [hfind] simp only
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.
uses
List.mem_iff_getElem.mp,List.length_take,List.getElem_take,List.getElem_ofFn,Equiv.symm_apply_applyobtain ⟨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$.
- The formalization precedes the main theorem with a helper lemma, `picking_phi_entry_le_find_mem_take`, proving that `List.find?` returns an element from a prefix whenever that prefix contains at least one satisfying element. In mathematical prose, this is an immediate property of first-match search.
- Indices and ranks are 0-based in Lean: agent turns range from $0$ to $m - 1$, and item ranks range from $0$ to $m - 1$. The theorem's conclusion $\text{rank} \le s$ corresponds to the paper's 1-based inequality $1 \le \phi_s \le s + 1$.
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.
/-- 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