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
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.
/-- 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