AFTD Auto-Formalizing Theoretical Domains

plackett_luce_prob_cons

lemmaverified

If a is in S and t ranks S minus a, the Plackett-Luce probability of a followed by t is w(a)/w(S) times that of t.

Statement

lemma plackett_luce_prob_cons (w : ℕ → ℝ) (S : Finset ℕ) (a : ℕ) (ha : a ∈ S) (t : List ℕ)
    (ht : t ∈ rankings_of (S.erase a)) :
    plackett_luce_prob w (a :: t) = w a / (∑ b ∈ S, w b) * plackett_luce_prob w t
Source
step towards plackett_luce_geometric_entropy_linear (Preference Elicitation as Average-Case Sorting, AAAI 2021, Sec. 5 conjecture (entropy O(m) for every phi in (0,1)))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • plackett_luce_probPlackett-Luce probability of a ranking (best first): the product over positions of the weight of the alternative placed there divided by…
  • rankings_ofThe rankings of a finite set S of alternatives: all orderings of S as duplicate-free lists.
  • map_sum_of_mem_rankings_ofThe total weight of the entries of a ranking of S is the total weight of S.
Used by 2
  • sum_plackett_luce_probWith positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.
  • plackett_luce_entropy_eqChain rule: the Plackett-Luce entropy on S equals the entropy of the first choice plus the expected Plackett-Luce entropy of the remaining…

Lean source view module on GitHub

lemma plackett_luce_prob_cons (w : ℕ → ℝ) (S : Finset ℕ) (a : ℕ) (ha : a ∈ S) (t : List ℕ)    (ht : t ∈ rankings_of (S.erase a)) :    plackett_luce_prob w (a :: t) = w a / (∑ b ∈ S, w b) * plackett_luce_prob w t := by  rw [plackett_luce_prob, map_sum_of_mem_rankings_of w _ t ht, Finset.add_sum_erase S w ha]
See it in the graphDiscuss this resultChallenge it