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
- droop_monroe_violates_droop_pjr_plus_of_not_dvdWithout the assumption that k + 1 divides n, the Droop Monroe rule can output a committee violating Droop-PJR+: with n = 4 voters, k = 2…
- droop_monroe_tie_violates_droop_ejr_plus_fjrWith ties, the Droop Monroe rule can output a committee violating Droop-EJR+ and Droop-FJR even when k + 1 divides n: n = 3, k = 2,…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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