independent_rank_trajectories_single_good
For n ≥ 2 agents and m = 1 good, under any length-1 picking sequence, the agents' received rank vectors are mutually independent under uniformly random rankings.
Statement
theorem independent_rank_trajectories_single_good (n : ℕ) (hn : 2 ≤ n) (seq : List (Fin n)) (hlen : seq.length = 1) (s : Fin n → List (Fin 1)) : (((Finset.univ : Finset (Fin n → Fin 1 ≃ Fin 1)).filter (fun r => ∀ i, ((picking_sequence_outcome seq r i).image (r i).symm).sort (· ≤ ·) = s i)).card : ℚ) / (Fintype.card (Fin n → Fin 1 ≃ Fin 1) : ℚ) = ∏ i : Fin n, (((Finset.univ : Finset (Fin n → Fin 1 ≃ Fin 1)).filter (fun r => ((picking_sequence_outcome seq r i).image (r i).symm).sort (· ≤ ·) = s i)).card : ℚ) / (Fintype.card (Fin n → Fin 1 ≃ Fin 1) : ℚ)
- Related work
- OP-1532
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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…
- LinearOrder.toTotalPreorderEvery
Read back from the Lean
For any natural number $n \ge 2$, any picking sequence seq of agents in Fin n of length 1, and any function s : Fin n → List (Fin 1):
The fraction of ranking profiles $r : \text{Fin } n \to (\text{Fin } 1 \simeq \text{Fin } 1)$ for which, for every agent $i \in \text{Fin } n$, the sorted list of the ranks of items allocated to agent $i$ by picking_sequence_outcome equals $s(i)$ (out of all possible ranking profiles)
equals
the product over all agents $i \in \text{Fin } n$ of the fraction of ranking profiles $r$ for which the sorted list of the ranks of items allocated to agent $i$ equals $s(i)$ (out of all possible ranking profiles).
All counts and quotients are computed in the rational numbers $\mathbb{Q}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
With only one good and a single picking turn, the picking sequence consists of a single scheduled agent a. That agent deterministically receives the only good (achieving rank 0), while every other agent receives nothing, regardless of the ranking profile. Furthermore, the space of ranking profiles on a single good is a singleton, so both the joint probability and all marginal probabilities degenerate to boolean indicators (1 or 0). Mutual independence then holds because a product of boolean indicators ∏ᵢ 1_{P(i)} equals 1 if and only if P(i) holds for all agents i.
Under a picking sequence [a] with one good, agent i receives rank trajectory [0] if i = a and [] if i ≠ a.
By case analysis on whether i = a: if i = a, agent a picks on the only turn and receives the single available good (which has rank 0), producing trajectory [0]; if i ≠ a, agent i is never scheduled and receives no goods, giving the empty trajectory []. Both cases simplify by unfolding picking_sequence_outcome and picking_turn.
uses
picking_sequence_outcome,picking_turnby_cases h : i = a · subst h simp [picking_sequence_outcome, picking_turn] · simp [picking_sequence_outcome, picking_turn, h]
On any finite singleton type, the normalized cardinality of a filtered subset is 1 if default satisfies the predicate and 0 otherwise.
The universal set of a unique type is {default} by Finset.univ_unique, and filtering it gives {default} or ∅ by Finset.filter_singleton. By case analysis on whether P default holds, the cardinality is 1 or 0, while the full type has cardinality 1 by Fintype.card_unique.
uses
Finset.univ_unique,Finset.filter_singleton,Fintype.card_uniquerw [Finset.univ_unique, Finset.filter_singleton] by_cases h : P default · simp [h, Fintype.card_unique] · simp [h, Fintype.card_unique]
The picking sequence seq has the form [a] for some agent a.
Since seq has length 1, List.length_eq_one_iff.mp extracts the unique scheduled agent a such that seq = [a].
uses
List.length_eq_one_iff.mpobtain ⟨a, rfl⟩ := List.length_eq_one_iff.mp hlen
Each agent's rank trajectory simplifies to [0] if i = a and [] if i ≠ a.
Rewriting with independent_rank_trajectories_single_good_trajectory replaces each agent's sorted rank trajectory with the deterministic outcome determined by whether the agent is scheduled.
uses
independent_rank_trajectories_single_good_trajectorysimp only [independent_rank_trajectories_single_good_trajectory]The joint and marginal probabilities simplify to boolean indicators of whether the target trajectories match the deterministic outcomes.
The profile type Fin n → Fin 1 ≃ Fin 1 is a singleton because there is only one permutation of a 1-element set. Applying independent_rank_trajectories_single_good_card_filter_unique_div evaluates each normalized cardinality to 1 or 0 depending on whether the trajectory condition holds for the unique ranking profile.
uses
independent_rank_trajectories_single_good_card_filter_unique_divsimp only [independent_rank_trajectories_single_good_card_filter_unique_div]The product of marginal indicators equals the joint indicator, establishing mutual independence.
Finset.prod_boole turns the product of booleans into an indicator that the condition holds for all agents in Finset.univ. Finally, simp simplifies the quantification over Finset.univ to universal quantification over Fin n, matching the left-hand side.
uses
Finset.prod_boolerw [Finset.prod_boole] simp
Finset.univ_unique- In any finite type with a unique element, the universal set consists solely of the default element.
Finset.filter_singleton- Filtering a singleton set {a} by predicate p yields {a} if p(a) holds, and ∅ otherwise.
Fintype.card_unique- Any finite type with a unique element has cardinality 1.
List.length_eq_one_iff.mp- A list has length 1 if and only if it consists of a single element [a].
independent_rank_trajectories_single_good_trajectory- Under a length-1 picking sequence [a] with one good, agent i's received rank trajectory is [0] if i = a and empty [] if i ≠ a, regardless of rankings.
independent_rank_trajectories_single_good_card_filter_unique_div- On a finite singleton type, the proportion of elements satisfying predicate P is 1 if P default holds, and 0 otherwise.
Finset.prod_boole- A product of boolean indicators over a finite set equals 1 if the condition holds for every element in the set, and 0 otherwise.
picking_sequence_outcome- Computes the set of goods allocated to each agent by folding picking turns along a picking sequence.
picking_turn- Performs one agent's turn by allocating their highest-ranked remaining good if one is available.
- The hypothesis hn : 2 ≤ n is not used anywhere in the proof; the result holds for any number of agents.
- Because there is only one permutation of Fin 1, the type of ranking profiles Fin n → Fin 1 ≃ Fin 1 is a singleton. Consequently, the uniform distribution is a Dirac mass on the unique ranking profile, and all event probabilities are boolean indicators (0 or 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.
/-- With one good, a length-one picking sequence gives the good only to its sole scheduled agent. -/private lemma independent_rank_trajectories_single_good_trajectory (n : ℕ) (a i : Fin n) (r : Fin n → Fin 1 ≃ Fin 1) : ((picking_sequence_outcome [a] r i).image (r i).symm).sort (· ≤ ·) = (if i = a then [0] else []) := by by_cases h : i = a · subst h simp [picking_sequence_outcome, picking_turn] · simp [picking_sequence_outcome, picking_turn, h]/-- Normalizing the cardinality of a filter over a singleton type gives the indicator of its predicate. -/private lemma independent_rank_trajectories_single_good_card_filter_unique_div (α : Type*) [Fintype α] [Unique α] (P : α → Prop) [DecidablePred P] : (((Finset.univ : Finset α).filter P).card : ℚ) / (Fintype.card α : ℚ) = if P default then 1 else 0 := by rw [Finset.univ_unique, Finset.filter_singleton] by_cases h : P default · simp [h, Fintype.card_unique] · simp [h, Fintype.card_unique]/-- For any number of agents n ≥ 2 and m = 1 good, the agents' received rank vectors are mutually independent under a length-1 picking sequence. -/theorem independent_rank_trajectories_single_good (n : ℕ) (hn : 2 ≤ n) (seq : List (Fin n)) (hlen : seq.length = 1) (s : Fin n → List (Fin 1)) : (((Finset.univ : Finset (Fin n → Fin 1 ≃ Fin 1)).filter (fun r => ∀ i, ((picking_sequence_outcome seq r i).image (r i).symm).sort (· ≤ ·) = s i)).card : ℚ) / (Fintype.card (Fin n → Fin 1 ≃ Fin 1) : ℚ) = ∏ i : Fin n, (((Finset.univ : Finset (Fin n → Fin 1 ≃ Fin 1)).filter (fun r => ((picking_sequence_outcome seq r i).image (r i).symm).sort (· ≤ ·) = s i)).card : ℚ) / (Fintype.card (Fin n → Fin 1 ≃ Fin 1) : ℚ) := by obtain ⟨a, rfl⟩ := List.length_eq_one_iff.mp hlen simp only [independent_rank_trajectories_single_good_trajectory] simp only [independent_rank_trajectories_single_good_card_filter_unique_div] rw [Finset.prod_boole] simp