AFTD Auto-Formalizing Theoretical Domains

independent_rank_trajectories_single_good

theoremverifiedoriginal

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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…

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.

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

    lines 6–9

    uses picking_sequence_outcome, picking_turn

      by_cases h : i = a
      · subst h
        simp [picking_sequence_outcome, picking_turn]
      · simp [picking_sequence_outcome, picking_turn, h]
  2. 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.

    lines 16–19

    uses Finset.univ_unique, Finset.filter_singleton, Fintype.card_unique

      rw [Finset.univ_unique, Finset.filter_singleton]
      by_cases h : P default
      · simp [h, Fintype.card_unique]
      · simp [h, Fintype.card_unique]
  3. 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].

    line 31

    uses List.length_eq_one_iff.mp

      obtain ⟨a, rfl⟩ := List.length_eq_one_iff.mp hlen
  4. 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.

    line 32

    uses independent_rank_trajectories_single_good_trajectory

      simp only [independent_rank_trajectories_single_good_trajectory]
  5. 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.

    line 33

    uses independent_rank_trajectories_single_good_card_filter_unique_div

      simp only [independent_rank_trajectories_single_good_card_filter_unique_div]
  6. 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.

    lines 34–35

    uses Finset.prod_boole

      rw [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.

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

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