temporal_droop_fjr_not_imp_bfjr
theoremverifiedoriginal
Droop-FJR does not imply BFJR in temporal voting, even when no voter approves every candidate in a round. Four voters, six rounds, two candidates: the outcome choosing candidate 1 in every round provides Droop-FJR, but S = {0, 1} is (2, 1)-BFJR-cohesive and gets satisfaction 0. This answers the question left open in arXiv:2505.22513, App. A.3.
Statement
theorem temporal_droop_fjr_not_imp_bfjr :
∃ a : Fin 4 → Fin 6 → Finset (Fin 2), ∃ o : Fin 6 → Fin 2,
(∀ i r, a i r ≠ Finset.univ) ∧ is_temporal_droop_fjr a o ∧ ¬ is_temporal_bfjr a o- Related work
- answers the question of arXiv:2505.22513, App. A.3 (BFJR implies Droop-FJR; does the converse hold, possibly under extra assumptions?) negatively, even when no voter approves every candidate in a round
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- temporal_satSatisfaction of voter i in a temporal election from outcome o restricted to rounds R: the number of rounds r in R with o(r) approved by i…
- is_temporal_droop_fjrDroop-FJR for temporal elections (arXiv:2505.22513, Def. A.6): for every nonempty group S and set of rounds T there is R ⊆ T of size…
- temporal_embed_satSatisfaction of voter i from a set Y of (candidate, round) pairs: the number of pairs (c, r) in Y with c approved by i in round r.
- is_bfjr_cohesive(α, β)-BFJR-cohesiveness (arXiv:2505.22513, Def. A.5) in the embedding of a temporal election: for every feasible X, either some Y with…
- is_temporal_bfjrBFJR for a temporal outcome o (arXiv:2505.22513, Def. A.5): every (α, β)-BFJR-cohesive group has a member with satisfaction at least β…
- tfjr_ballotBallots of the Droop-FJR vs BFJR counterexample: voter 0 approves candidate 0 in rounds 0-2, voter 1 approves candidate 0 in rounds 3-5,…
- tfjr_countIn the counterexample, every nonempty group either contains voter 2 or 3, or has a member who approves nothing in at least ⌈(|T|+1)|S|/4⌉…
- tfjr_avoidAny two rounds out of six miss some round among 0-2 and some round among 3-5 (checked by decide).
- tfjr_droop_le⌈(t+1)s/n⌉ - 1 ≤ t whenever s ≤ n.
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.
/-- Droop-FJR does not imply BFJR in temporal voting, even when no voter approves every candidate in a round. Four voters, six rounds, two candidates: the outcome choosing candidate 1 in every round provides Droop-FJR, but S = {0, 1} is (2, 1)-BFJR-cohesive and gets satisfaction 0. This answers the question left open in arXiv:2505.22513, App. A.3. -/theorem temporal_droop_fjr_not_imp_bfjr : ∃ a : Fin 4 → Fin 6 → Finset (Fin 2), ∃ o : Fin 6 → Fin 2, (∀ i r, a i r ≠ Finset.univ) ∧ is_temporal_droop_fjr a o ∧ ¬ is_temporal_bfjr a o := by refine ⟨tfjr_ballot, fun _ => 1, by decide, ?_, ?_⟩ · intro S hS T rcases tfjr_count S T hS with ⟨i, hi, hi2⟩ | ⟨j, hj, hcard⟩ · obtain ⟨R, hRT, hR⟩ := Finset.exists_subset_card_eq (tfjr_droop_le T.card S.card 4 (by simpa using Finset.card_le_univ S)) refine ⟨R, hRT, hR, fun o' => ⟨i, hi, i, hi, ?_⟩⟩ have h6 : ∀ i : Fin 4, 2 ≤ i.val → temporal_sat tfjr_ballot i (fun _ => 1) Finset.univ = 6 := by decide rw [h6 i hi2] calc temporal_sat tfjr_ballot i o' R ≤ R.card := Finset.card_filter_le _ _ _ ≤ (Finset.univ : Finset (Fin 6)).card := Finset.card_le_univ R _ = 6 := by simp · obtain ⟨R, hRT, hR⟩ := Finset.exists_subset_card_eq hcard refine ⟨R, hRT.trans (Finset.filter_subset _ _), hR, fun o' => ⟨j, hj, j, hj, ?_⟩⟩ have : temporal_sat tfjr_ballot j o' R = 0 := by unfold temporal_sat rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro r hr have := (Finset.mem_filter.1 (hRT hr)).2 rw [this]; exact Finset.notMem_empty _ rw [this]; exact Nat.zero_le _ · intro h have hcoh : is_bfjr_cohesive tfjr_ballot {0, 1} 2 1 := by intro X hX by_cases hbig : 2 * 4 < ({0, 1} : Finset (Fin 4)).card * (X.card + 2) · exact Or.inr hbig left have h2 : ({0, 1} : Finset (Fin 4)).card = 2 := by decide rw [h2] at hbig have hX2 : (X.image Prod.snd).card ≤ 2 := by have := Finset.card_image_le (s := X) (f := Prod.snd); omega obtain ⟨r₁, r₂, h1, h2, h1D, h2D⟩ := tfjr_avoid _ hX2 have hne : r₁ ≠ r₂ := by intro h; rw [h] at h1; omega refine ⟨{(0, r₁), (0, r₂)}, ?_, ?_, ?_⟩ · rw [Finset.card_pair]; intro h; exact hne (Prod.ext_iff.1 h).2 · intro i hi unfold temporal_embed_sat apply Finset.card_pos.2 rcases Finset.mem_insert.1 hi with rfl | hi · refine ⟨(0, r₁), ?_⟩ simp [tfjr_ballot, h1] · rw [Finset.mem_singleton] at hi; subst hi refine ⟨(0, r₂), ?_⟩ have : ¬ r₂.val < 3 := by omega simp [tfjr_ballot, h2] · intro p hp q hq hpq have hY : ∀ y ∈ ({(0, r₁), (0, r₂)} : Finset (Fin 2 × Fin 6)), y.2 ∉ X.image Prod.snd := by intro y hy rcases Finset.mem_insert.1 hy with rfl | hy · exact h1D · rw [Finset.mem_singleton] at hy; subst hy; exact h2D rcases Finset.mem_union.1 hp with hp | hp <;> rcases Finset.mem_union.1 hq with hq | hq · exact hX p hp q hq hpq · exact absurd (hpq ▸ Finset.mem_image_of_mem Prod.snd hp) (hY q hq) · exact absurd (hpq.symm ▸ Finset.mem_image_of_mem Prod.snd hq) (hY p hp) · simp only [Finset.mem_insert, Finset.mem_singleton] at hp hq rcases hp with rfl | rfl <;> rcases hq with rfl | rfl <;> rfl obtain ⟨i, hi, hsat⟩ := h {0, 1} 2 1 hcoh revert i decide