assignment_exchange
theoremverified
Generic 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′ after a suitable permutation σ of the voters, the number of satisfied voters grows by at least min(|π⁻¹(c)|, |S|) - |π⁻¹(c) \ S|.
Statement
theorem assignment_exchange {n : ℕ} {β : Type*} [DecidableEq β] (g : Fin n → β → Prop) [∀ i b, Decidable (g i b)] (π : Fin n → β) (c c' : β) (S : Finset (Fin n)) (hSa : ∀ i ∈ S, g i c') (hun : ∀ i ∈ S, ¬ g i (π i)) : ∃ σ : Equiv.Perm (Fin n), (Finset.univ.filter fun i => g i (π i)).card + min (Finset.univ.filter fun i => π i = c).card S.card ≤ (Finset.univ.filter fun i => g i (if π (σ i) = c then c' else π (σ i))).card + ((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 1
- monroe_perm_swap_finsetsFor disjoint finite sets P, Q of equal size there is a permutation sending P into Q, Q into P, and fixing everything else.
- Used by 2
- 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…
- 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…
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 generic exchange step behind the Monroe arguments. Let `π` assign voters to `β`, let every member of `S` be satisfied by `c'` (`g i c'`) but not by `π`, and rename `c` to `c'` after a suitable permutation `σ` of the voters. Then the number of satisfied voters grows by at least `min(|π⁻¹(c)|, |S|) - |π⁻¹(c) \ S|`. -/theorem assignment_exchange {n : ℕ} {β : Type*} [DecidableEq β] (g : Fin n → β → Prop) [∀ i b, Decidable (g i b)] (π : Fin n → β) (c c' : β) (S : Finset (Fin n)) (hSa : ∀ i ∈ S, g i c') (hun : ∀ i ∈ S, ¬ g i (π i)) : ∃ σ : Equiv.Perm (Fin n), (Finset.univ.filter fun i => g i (π i)).card + min (Finset.univ.filter fun i => π i = c).card S.card ≤ (Finset.univ.filter fun i => g i (if π (σ i) = c then c' else π (σ i))).card + ((Finset.univ.filter fun i => π i = c).filter fun i => i ∉ S).card := by set R := Finset.univ.filter fun i => π i = c with hR set P := R.filter fun i => i ∉ S with hP set Q := S.filter fun i => π i ≠ c with hQ set T := R.filter fun i => i ∈ S with hT obtain ⟨P', hP'P, hP'c⟩ := Finset.exists_subset_card_eq (min_le_left P.card Q.card) obtain ⟨Q', hQ'Q, hQ'c⟩ := Finset.exists_subset_card_eq (min_le_right P.card Q.card) have memP : ∀ v, v ∈ P ↔ π v = c ∧ v ∉ S := by intro v; simp [hP, hR] have memQ : ∀ v, v ∈ Q ↔ v ∈ S ∧ π v ≠ c := by intro v; simp [hQ] have memT : ∀ v, v ∈ T ↔ π v = c ∧ v ∈ S := by intro v; simp [hT, hR] have hdisj : Disjoint P' Q' := by rw [Finset.disjoint_left] intro v h1 h2 exact ((memP v).1 (hP'P h1)).2 ((memQ v).1 (hQ'Q h2)).1 obtain ⟨σ, h1, h2, h3⟩ := monroe_perm_swap_finsets P' Q' hdisj (hP'c.trans hQ'c.symm) let ρ : β → β := fun x => if x = c then c' else x refine ⟨σ, ?_⟩ show (Finset.univ.filter fun i => g i (π i)).card + min R.card S.card ≤ (Finset.univ.filter fun i => g i (ρ (π (σ i)))).card + P.card have pt : ∀ v, (if g v (π v) then 1 else 0) + (if v ∈ Q' ∪ T then 1 else 0) ≤ (if g v (ρ (π (σ v))) then 1 else 0) + (if v ∈ P then 1 else 0) := by intro v by_cases hvQ' : v ∈ Q' · have hvQ := (memQ v).1 (hQ'Q hvQ') have hσ : π (σ v) = c := ((memP _).1 (hP'P (h2 v hvQ'))).1 have : ρ (π (σ v)) = c' := by simp [ρ, hσ] simp [this, hSa v hvQ.1, hun v hvQ.1, hvQ', (memP v).not.2 (by tauto)] · by_cases hvT : v ∈ T · have hvT' := (memT v).1 hvT have hσ : σ v = v := h3 v (fun h => ((memP v).1 (hP'P h)).2 hvT'.2) hvQ' have : ρ (π (σ v)) = c' := by simp [ρ, hσ, hvT'.1] simp [this, hSa v hvT'.2, hun v hvT'.2, hvT, (memP v).not.2 (by tauto)] · by_cases hvP : v ∈ P · simp only [hvP, Finset.mem_union, hvQ', hvT, or_self, if_true, if_false] split_ifs <;> omega · have hσ : σ v = v := h3 v (fun h => hvP (hP'P h)) hvQ' have hπ : π v ≠ c := by intro h by_cases hs : v ∈ S · exact hvT ((memT v).2 ⟨h, hs⟩) · exact hvP ((memP v).2 ⟨h, hs⟩) have : ρ (π (σ v)) = π v := by simp [ρ, hσ, hπ] simp [this, hvQ', hvT, hvP] have hsum := Finset.sum_le_sum (fun v (_ : v ∈ (Finset.univ : Finset (Fin n))) => pt v) rw [Finset.sum_add_distrib, Finset.sum_add_distrib] at hsum simp only [Finset.sum_boole, Nat.cast_id, Finset.filter_mem_eq_inter, Finset.univ_inter] at hsum have hQT : (Q' ∪ T).card = Q'.card + T.card := by apply Finset.card_union_of_disjoint rw [Finset.disjoint_left] intro v hv1 hv2 exact ((memQ v).1 (hQ'Q hv1)).2 ((memT v).1 hv2).1 have hRc : R.card = T.card + P.card := by rw [hT, hP]; exact (Finset.card_filter_add_card_filter_not _).symm have hSc : S.card = T.card + Q.card := by have : T.card = (S.filter fun i => π i = c).card := by apply Finset.card_bij (fun v _ => v) · intro v hv; have := (memT v).1 hv; simp [this.1, this.2] · intro _ _ _ _ h; exact h · intro v hv; simp only [Finset.mem_filter] at hv exact ⟨v, (memT v).2 ⟨hv.2, hv.1⟩, rfl⟩ rw [this, hQ]; exact (Finset.card_filter_add_card_filter_not _).symm rw [hQT] at hsum have : min R.card S.card = T.card + min P.card Q.card := by rw [hRc, hSc]; omega rw [this] omega