AFTD Auto-Formalizing Theoretical Domains

plackett_luce_entropy_eq

lemmaverified

Chain rule: the Plackett-Luce entropy on S equals the entropy of the first choice plus the expected Plackett-Luce entropy of the remaining alternatives.

Statement

lemma plackett_luce_entropy_eq (w : ℕ → ℝ) (S : Finset ℕ) (hS : S.Nonempty)
    (hw : ∀ b ∈ S, 0 < w b) :
    plackett_luce_entropy w S =
      ∑ a ∈ S, Real.negMulLog (w a / ∑ b ∈ S, w b) +
        ∑ a ∈ S, w a / (∑ b ∈ S, w b) * plackett_luce_entropy w (S.erase a)
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 4
  • plackett_luce_entropyShannon entropy (natural logarithm) of the Plackett-Luce distribution over the rankings of S.
  • 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.
  • sum_plackett_luce_probWith positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.
Used by 1
  • plackett_luce_entropy_geometric_leFor geometric weights phi^a with 0 < phi < 1, the Plackett-Luce entropy on any set of n alternatives is at most C(phi) * n with C(phi) =…

Lean source view module on GitHub

/-- Chain rule (grouping by the top-ranked alternative). -/lemma plackett_luce_entropy_eq (w : ℕ → ℝ) (S : Finset ℕ) (hS : S.Nonempty)    (hw : ∀ b ∈ S, 0 < w b) :    plackett_luce_entropy w S =      ∑ a ∈ S, Real.negMulLog (w a / ∑ b ∈ S, w b) +        ∑ a ∈ S, w a / (∑ b ∈ S, w b) * plackett_luce_entropy w (S.erase a) := by  unfold plackett_luce_entropy  rw [sum_rankings_of_nonempty S hS, ← Finset.sum_add_distrib]  refine Finset.sum_congr rfl fun a ha => ?_  have h1 := sum_plackett_luce_prob w _ (S.erase a) rfl (fun b hb => hw b (Finset.mem_of_mem_erase hb))  rw [Finset.sum_congr rfl fun t ht => by rw [plackett_luce_prob_cons w S a ha t ht, Real.negMulLog_mul],    Finset.sum_add_distrib, ← Finset.sum_mul, h1, one_mul, ← Finset.mul_sum]
See it in the graphDiscuss this resultChallenge it