is_droop_valid_assignment
def
A 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 gets between ⌊n/(k+1)⌋ and ⌈n/(k+1)⌉ voters and the dummy exactly ⌊n/(k+1)⌋.
Statement
def is_droop_valid_assignment {n m : ℕ} (k : ℕ) (W : Finset (Fin m)) (π : Fin n → Option (Fin m)) : Prop
- Defined in
- Justified Representation: From Hare to Droop, arXiv:2508.00811, Def. 16 (valid Monroe assignment, Droop quota with a dummy candidate)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Used by 7
- droop_monroe_exchangeExchange step for Droop assignments: swapping c₀ ∈ W for c ∉ W approved by all of S (no member of S satisfied) gives a Droop-valid…
- is_droop_monroe_committeeW is a winning committee of the Droop Monroe rule: some Droop-valid assignment for W scores at least as much as every Droop-valid…
- droop_monroe_score_leA Droop-valid assignment scores at most n - ⌊n/(k+1)⌋, since the dummy voters are unsatisfied.
- 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,…
- droop_valid_assignment_real_voters_cardFor any Droop-valid Monroe assignment π of n voters to committee size k, the number of voters assigned to a real candidate (not none) is…
- droop_monroe_unsatisfied_groupLemma 2 of arXiv:2508.00811: if (k+1) divides n and π is an optimal Droop-valid assignment for W, no group of more than n/(k+1) voters,…
Lean source view module on GitHub
/-- A Droop-valid Monroe assignment (arXiv:2508.00811, Def. 16): `W` has `k` members, `π` sends each voter to a member of `W` or to the dummy `none`, every `c ∈ W` gets between `⌊n/(k+1)⌋` and `⌈n/(k+1)⌉` voters, and the dummy gets exactly `⌊n/(k+1)⌋`. -/ def is_droop_valid_assignment {n m : ℕ} (k : ℕ) (W : Finset (Fin m)) (π : Fin n → Option (Fin m)) : Prop := W.card = k ∧ (∀ i c, π i = some c → c ∈ W) ∧ (∀ c ∈ W, n / (k + 1) ≤ (Finset.univ.filter fun i => π i = some c).card ∧ (Finset.univ.filter fun i => π i = some c).card ≤ (n + k) / (k + 1)) ∧ (Finset.univ.filter fun i => π i = none).card = n / (k + 1)