AFTD Auto-Formalizing Theoretical Domains

droop_monroe_score_le

theoremverified

A Droop-valid assignment scores at most n - ⌊n/(k+1)⌋, since the dummy voters are unsatisfied.

Statement

theorem droop_monroe_score_le {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m))
    (π : Fin n → Option (Fin m)) (hv : is_droop_valid_assignment k W π) :
    droop_monroe_score A π + n / (k + 1) ≤ n
Source
step towards droop_monroe_tie_violates_droop_ejr_plus_fjr (tie example for Justified Representation: From Hare to Droop, arXiv:2508.00811, Table 1)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_droop_valid_assignmentA Droop-valid Monroe assignment (arXiv:2508.00811, Def. 16): |W| = k, each voter goes to a member of W or to the dummy (none), each c ∈ W…
  • droop_monroe_scoreMonroe score of a Droop assignment: the number of voters sent to a non-dummy candidate they approve.
Used by 2

Lean source view module on GitHub

/-- A Droop-valid assignment never scores more than `n - ⌊n/(k+1)⌋`: the dummy's voters are unsatisfied. -/theorem droop_monroe_score_le {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m))    (π : Fin n → Option (Fin m)) (hv : is_droop_valid_assignment k W π) :    droop_monroe_score A π + n / (k + 1) ≤ n := by  have hsub : (Finset.univ.filter fun i => ∃ c, π i = some c ∧ c ∈ A i) ⊆      Finset.univ.filter fun i => ¬ π i = none := by    intro i hi    obtain ⟨c, hc, _⟩ := (Finset.mem_filter.1 hi).2    simp [hc]  have h1 := Finset.card_le_card hsub  have h2 := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin n)))    (p := fun i => π i = none)  rw [hv.2.2.2] at h2  simp only [Finset.card_univ, Fintype.card_fin] at h2  unfold droop_monroe_score  omega
See it in the graphDiscuss this resultChallenge it