AFTD Auto-Formalizing Theoretical Domains

is_hare_valid_assignment

def

A Hare-valid Monroe assignment (arXiv:2508.00811, Def. 16): W has k members, π sends every voter into W, and every c ∈ W receives between ⌊n/k⌋ and ⌈n/k⌉ voters.

Statement

def is_hare_valid_assignment {n m : ℕ} (k : ℕ) (W : Finset (Fin m)) (π : Fin n → Fin m) : Prop
Defined in
Justified Representation: From Hare to Droop, arXiv:2508.00811, Def. 16 (valid Monroe assignment, Hare quota)
Verified
06 Oct 2026
Axioms
none listed
Used by 3
  • is_hare_monroe_committeeW is a winning committee of the (Hare) Monroe rule: some Hare-valid assignment for W has Monroe score at least that of every Hare-valid…
  • monroe_exchangeExchange step: replacing c ∈ W by c ∉ W approved by all of S (no member of S being satisfied by π) yields a Hare-valid assignment whose…
  • monroe_exists_heavyCounting step: if (W, π) is Hare-valid and |S| > n/(k+1), then some c ∈ W satisfies |π⁻¹(c)| < min(|π⁻¹(c)|, |S|) + |π⁻¹(c) ∩ S|.

Lean source view module on GitHub

/-- A Hare-valid Monroe assignment (arXiv:2508.00811, Def. 16): `W` has `k` members, `π` sends every voter into `W`, and every `c ∈ W` gets between `⌊n/k⌋` and `⌈n/k⌉` voters. -/
def is_hare_valid_assignment {n m : ℕ} (k : ℕ) (W : Finset (Fin m)) (π : Fin n → Fin m) : Prop :=
  W.card = k ∧ (∀ i, π i ∈ W) ∧
    ∀ c ∈ W, n / k ≤ (Finset.univ.filter fun i => π i = c).card ∧
      (Finset.univ.filter fun i => π i = c).card ≤ (n + k - 1) / k
See it in the graphDiscuss this resultChallenge it