AFTD Auto-Formalizing Theoretical Domains

monroe_exchange

theoremverified

Exchange 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 score is at least score(π) + min(|π⁻¹(c)|, |S|) - |π⁻¹(c) \ S|.

Statement

theorem monroe_exchange {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m))
    (π : Fin n → Fin m) (hv : is_hare_valid_assignment k W π) (c c' : Fin m) (hc : c ∈ W)
    (hc' : c' ∉ W) (S : Finset (Fin n)) (hSa : ∀ i ∈ S, c' ∈ A i)
    (hun : ∀ i ∈ S, π i ∉ A i) :
    ∃ π', is_hare_valid_assignment k (insert c' (W.erase c)) π' ∧
      monroe_score A π + min (Finset.univ.filter fun i => π i = c).card S.card ≤
        monroe_score A π' + ((Finset.univ.filter fun i => π i = c).filter fun i => i ∉ S).card
Source
step towards hare_monroe_satisfies_droop_jr (Monroe and Droop-JR, open case of Justified Representation: From Hare to Droop, arXiv:2508.00811)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_hare_valid_assignmentA Hare-valid Monroe assignment (arXiv:2508.00811, Def. 16): W has k members, π sends every voter into W, and every c ∈ W receives between…
  • monroe_scoreThe Monroe score of an assignment π: the number of voters i with π(i) ∈ A_i.
  • monroe_load_comp_permPrecomposing an assignment with a permutation of the voters does not change how many voters each candidate receives.
  • assignment_exchangeGeneric exchange step: for an assignment π of voters to β, a set S of voters each satisfied by c′ but not by π, and the renaming c ↦ c′…
Used by 1
  • hare_monroe_satisfies_droop_jrEvery committee selected by the (Hare) Monroe rule satisfies Droop-JR, for all n and k. This answers the open question of Justified…

Lean source view module on GitHub

/-- The exchange step: swapping `c ∈ W` for a candidate `c' ∉ W` approved by everyone in `S` (and with no member of `S` satisfied by `π`) gives a valid assignment whose score is at least `score π + min(|π⁻¹(c)|, |S|) - |π⁻¹(c) \ S|`. -/theorem monroe_exchange {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m))    (π : Fin n → Fin m) (hv : is_hare_valid_assignment k W π) (c c' : Fin m) (hc : c ∈ W)    (hc' : c' ∉ W) (S : Finset (Fin n)) (hSa : ∀ i ∈ S, c' ∈ A i)    (hun : ∀ i ∈ S, π i ∉ A i) :    ∃ π', is_hare_valid_assignment k (insert c' (W.erase c)) π' ∧      monroe_score A π + min (Finset.univ.filter fun i => π i = c).card S.card ≤        monroe_score A π' + ((Finset.univ.filter fun i => π i = c).filter fun i => i ∉ S).card := by  obtain ⟨σ, hσ⟩ := assignment_exchange (fun i b => b ∈ A i) π c c' S hSa hun  obtain ⟨hW, hmap, hload⟩ := hv  let ρ : Fin m → Fin m := fun x => if x = c then c' else x  have hπc' : ∀ v, π v ≠ c' := fun v h => hc' (h ▸ hmap v)  refine ⟨fun v => ρ (π (σ v)), ⟨?_, ?_, ?_⟩, hσ⟩  · have : c' ∉ W.erase c := fun h => hc' (Finset.mem_of_mem_erase h)    rw [Finset.card_insert_of_notMem this, Finset.card_erase_of_mem hc, hW]    have : 0 < k := hW ▸ Finset.card_pos.2 ⟨c, hc⟩    omega  · intro v    simp only [ρ]    split_ifs with h    · exact Finset.mem_insert_self _ _    · exact Finset.mem_insert_of_mem (Finset.mem_erase.2 ⟨h, hmap _⟩)  · intro d hd    have key : ∃ e ∈ W, (Finset.univ.filter fun v => ρ (π (σ v)) = d) =        (Finset.univ.filter fun v => π (σ v) = e) := by      rcases Finset.mem_insert.1 hd with rfl | hd      · refine ⟨c, hc, Finset.filter_congr fun v _ => ?_⟩        simp only [ρ]        split_ifs with h        · simp [h]        · simp [h, hπc']      · obtain ⟨hdc, hdW⟩ := Finset.mem_erase.1 hd        refine ⟨d, hdW, Finset.filter_congr fun v _ => ?_⟩        simp only [ρ]        split_ifs with h        · constructor          · intro h'; exact absurd (h' ▸ hdW) hc'          · intro h'; exact absurd (h.symm.trans h') (Ne.symm hdc)        · rfl    obtain ⟨e, he, heq⟩ := key    rw [heq, monroe_load_comp_perm]    exact hload e he
See it in the graphDiscuss this resultChallenge it