AFTD Auto-Formalizing Theoretical Domains

sum_plackett_luce_prob

lemmaverified

With positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.

Statement

lemma sum_plackett_luce_prob (w : ℕ → ℝ) :
    ∀ n (S : Finset ℕ), S.card = n → (∀ b ∈ S, 0 < w b) →
      ∑ l ∈ rankings_of S, plackett_luce_prob w l = 1
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 5
  • 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.
  • rankings_of_emptyThe empty set has exactly one ranking, the empty list.
  • sum_rankings_of_nonemptyFor nonempty S, a sum over rankings of S splits as a sum over the top alternative a and the rankings of S minus a.
  • plackett_luce_prob_consIf 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.
Used by 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 sum_plackett_luce_prob (w : ℕ → ℝ) :    ∀ n (S : Finset ℕ), S.card = n → (∀ b ∈ S, 0 < w b) →      ∑ l ∈ rankings_of S, plackett_luce_prob w l = 1 := by  intro n  induction n with  | zero =>    intro S hS _    rw [Finset.card_eq_zero.1 hS, rankings_of_empty, Finset.sum_singleton, plackett_luce_prob]  | succ n ih =>    intro S hS hw    have hne : S.Nonempty := Finset.card_pos.1 (by omega)    have hW : 0 < ∑ b ∈ S, w b := Finset.sum_pos hw hne    rw [sum_rankings_of_nonempty S hne]    calc ∑ a ∈ S, ∑ t ∈ rankings_of (S.erase a), plackett_luce_prob w (a :: t)        = ∑ a ∈ S, w a / (∑ b ∈ S, w b) := by          refine Finset.sum_congr rfl fun a ha => ?_          rw [Finset.sum_congr rfl fun t ht => plackett_luce_prob_cons w S a ha t ht,            ← Finset.mul_sum,            ih (S.erase a) (by rw [Finset.card_erase_of_mem ha]; omega)              (fun b hb => hw b (Finset.mem_of_mem_erase hb)), mul_one]      _ = 1 := by rw [← Finset.sum_div, div_self hW.ne']
See it in the graphDiscuss this resultChallenge it