AFTD Auto-Formalizing Theoretical Domains

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)
See it in the graphDiscuss this resultChallenge it