AFTD Auto-Formalizing Theoretical Domains

ejr_adjacent_committees_exists

theoremverifiedformalization

For every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V satisfying EJR at sizes k and k+1, respectively.

Statement

theorem ejr_adjacent_committees_exists {n m : ℕ}
    (A : Fin n → Finset (Fin m)) (hn : 0 < n) (k : ℕ) (hk : k < m) :
    ∃ W V : Finset (Fin m), W ⊆ V ∧ is_ejr_committee A k W ∧
      is_ejr_committee A (k + 1) V
Formalizes
arXiv:2302.01989, Robust and Verifiable Proportionality Axioms for Multiwinner Voting, Proposition 8: EJR consequence of the published EJR+ nested-pair theorem; this proof uses a strengthened greedy cohesive argument instead of the priceability proof.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • ejr_greedy_cohesive_pair_auxFor every voter subset S and positive committee parameter K, a greedy cohesive core W has cost at most |S|K/n and satisfies every…
  • is_ejr_committeeA committee W with |W| = k satisfies EJR if for every ℓ ≥ 1 and every ℓ-cohesive group G some voter i ∈ G has |A_i ∩ W| ≥ ℓ.
  • is_ejr_cohesive_groupFor committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The proof applies an auxiliary lemma (ejr_greedy_cohesive_pair_aux) to find an initial committee W₀ with |W₀| ≤ k + 1 that satisfies EJR at size k + 1. If |W₀| ≤ k, we greedily extend W₀ to nested committees W ⊆ V of sizes k and k + 1; the EJR guarantee transfers upward because any group cohesive at size k is also cohesive at size k + 1. If |W₀| = k + 1, the auxiliary lemma provides a candidate c ∈ W₀ whose deletion satisfies EJR at size k, yielding the nested pair W₀ \ {c} ⊆ W₀.

  1. There exists an initial committee W₀ of size at most k + 1 satisfying EJR at committee size k + 1.

    We invoke the auxiliary lemma ejr_greedy_cohesive_pair_aux for target committee size k + 1 on the set of all voters. This yields a candidate set W₀ satisfying the budget constraint |W₀| * n ≤ n * (k + 1), an EJR representation guarantee at size k + 1, and a candidate-deletion guarantee if the budget is tight. Since n > 0, dividing by n shows that |W₀| ≤ k + 1.

    lines 5–9

    uses ejr_greedy_cohesive_pair_aux

      classical
      obtain ⟨W0, hbudget, hrep, hpair⟩ :=
        ejr_greedy_cohesive_pair_aux A (k + 1) hn (by omega) Finset.univ
      have hbudget' : W0.card * n ≤ n * (k + 1) := by simpa using hbudget
      have hW0 : W0.card ≤ k + 1 := by nlinarith
  2. In the case where |W₀| ≤ k, there exist nested committees W ⊆ V containing W₀ of sizes k and k + 1.

    Assuming |W₀| ≤ k, since k < m, there are at least k + 1 candidates total. By applying Finset.exists_superset_card_eq twice, we first extend W₀ to a committee W of size k, and then extend W to a committee V of size k + 1. We propose W and V as our witnesses, leaving their EJR properties to be verified.

    lines 10–16

    uses Finset.exists_superset_card_eq

      by_cases hsmall : W0.card ≤ k
      · obtain ⟨W, hWsub, hWcard⟩ :=
          Finset.exists_superset_card_eq hsmall (show k ≤ Fintype.card (Fin m) by simpa using hk.le)
        obtain ⟨V, hVsub, hVcard⟩ := Finset.exists_superset_card_eq
          (show W.card ≤ k + 1 by omega)
          (show k + 1 ≤ Fintype.card (Fin m) by simpa using hk)
        refine ⟨W, V, hVsub, ⟨hWcard, ?_⟩, ⟨hVcard, ?_⟩⟩
  3. W satisfies EJR at committee size k.

    Let G be a group cohesive at size k for some ℓ ≥ 1, so ℓ * n ≤ |G| * k. Since k ≤ k + 1, Nat.mul_le_mul_left and Nat.le_succ imply ℓ * n ≤ |G| * (k + 1), so G is also cohesive at size k + 1. By the representation guarantee of W₀, some voter i ∈ G approves at least ℓ candidates in W₀. Since W₀ ⊆ W, the intersection A i ∩ W₀ is contained in A i ∩ W (Finset.inter_subset_inter_left), so by Finset.card_le_card, voter i also approves at least ℓ candidates in W.

    lines 17–21

    uses Nat.mul_le_mul_left, Nat.le_succ, Finset.subset_univ, Finset.card_le_card, Finset.inter_subset_inter_left

        · intro ℓ hℓ G hG
          have hG' : is_ejr_cohesive_group A (k + 1) ℓ G :=
            ⟨hG.1.trans (Nat.mul_le_mul_left G.card (Nat.le_succ k)), hG.2⟩
          obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG'
          exact ⟨i, hi, hu.trans (Finset.card_le_card (Finset.inter_subset_inter_left hWsub))⟩
  4. V satisfies EJR at committee size k + 1.

    For any group G cohesive at size k + 1, the representation property of W₀ provides a voter i ∈ G approving at least ℓ candidates in W₀. Because W₀ ⊆ W ⊆ V, we have A i ∩ W₀ ⊆ A i ∩ V by Finset.inter_subset_inter_left, and Finset.card_le_card implies that voter i approves at least ℓ candidates in V.

    lines 22–25

    uses Finset.subset_univ, Finset.card_le_card, Finset.inter_subset_inter_left

        · intro ℓ hℓ G hG
          obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG
          exact ⟨i, hi, hu.trans (Finset.card_le_card
            (Finset.inter_subset_inter_left (hWsub.trans hVsub)))⟩
  5. In the case where |W₀| > k, we have |W₀| = k + 1, and deleting some candidate c ∈ W₀ gives nested committees W₀ \ {c} ⊆ W₀ of sizes k and k + 1.

    If |W₀| ≤ k does not hold, the upper bound |W₀| ≤ k + 1 forces |W₀| = k + 1. The budget equality |W₀| * n = n * (k + 1) is therefore met, and W₀ is nonempty by Finset.card_pos.mp. The candidate-removal property of ejr_greedy_cohesive_pair_aux then yields a candidate c ∈ W₀ whose removal satisfies EJR at size (k + 1) - 1 = k. We have W₀ \ {c} ⊆ W₀ by Finset.erase_subset, and its size is k by Finset.card_erase_of_mem.

    lines 26–33

    uses Nat.mul_comm, Finset.card_pos.mp, Finset.erase_subset, Finset.card_erase_of_mem

      · have hWcard : W0.card = k + 1 := by omega
        have hfull : W0.card * n = (Finset.univ : Finset (Fin n)).card * (k + 1) := by
          simp [hWcard, Nat.mul_comm]
        have hne : W0.Nonempty := Finset.card_pos.mp (by omega)
        obtain ⟨c, hc, hcpair⟩ := hpair hfull hne
        refine ⟨W0.erase c, W0, Finset.erase_subset _ _, ⟨?_, ?_⟩, ⟨hWcard, ?_⟩⟩
        · rw [Finset.card_erase_of_mem hc, hWcard]
          omega
  6. W₀ \ {c} satisfies EJR at committee size k.

    For any group G cohesive at size k, the candidate-removal property hcpair from the auxiliary lemma directly ensures that some voter in G approves at least ℓ candidates in W₀ \ {c}.

    lines 34–36

    uses Finset.subset_univ

        · intro ℓ hℓ G hG
          have := hcpair ℓ hℓ G (Finset.subset_univ _)
          simpa using this hG
  7. W₀ satisfies EJR at committee size k + 1.

    Any group cohesive at size k + 1 is represented in W₀ by the guarantee hrep from the auxiliary lemma.

    lines 37–38

    uses Finset.subset_univ

        · intro ℓ hℓ G hG
          exact hrep ℓ hℓ G (Finset.subset_univ _) hG
ejr_greedy_cohesive_pair_aux
For an approval profile with n > 0 voters and committee target K > 0, there exists a candidate set W with |W| * n ≤ |S| * K satisfying EJR on voter subset S at size K; if |W| * n = |S| * K and W is nonempty, there exists c ∈ W whose deletion satisfies EJR on S at size K - 1.
Finset.exists_superset_card_eq
A finite set of size at most n in a finite type of cardinality at least n can be extended to a superset of cardinality exactly n.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality.
Nat.le_succ
Every natural number is less than or equal to its successor.
Finset.subset_univ
Every finite set of a finite type is a subset of the universal finset.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Finset.inter_subset_inter_left
If t ⊆ u, then the intersection s ∩ t is a subset of s ∩ u.
Nat.mul_comm
Multiplication of natural numbers is commutative.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.erase_subset
Removing an element from a finite set produces a subset of the original set.
Finset.card_erase_of_mem
Removing an element that belongs to a finite set decreases its cardinality by 1.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem ejr_adjacent_committees_exists {n m : ℕ}    (A : Fin n → Finset (Fin m)) (hn : 0 < n) (k : ℕ) (hk : k < m) :    ∃ W V : Finset (Fin m), W ⊆ V ∧ is_ejr_committee A k W ∧      is_ejr_committee A (k + 1) V := by  classical  obtain ⟨W0, hbudget, hrep, hpair⟩ :=    ejr_greedy_cohesive_pair_aux A (k + 1) hn (by omega) Finset.univ  have hbudget' : W0.card * n ≤ n * (k + 1) := by simpa using hbudget  have hW0 : W0.card ≤ k + 1 := by nlinarith  by_cases hsmall : W0.card ≤ k  · obtain ⟨W, hWsub, hWcard⟩ :=      Finset.exists_superset_card_eq hsmall (show k ≤ Fintype.card (Fin m) by simpa using hk.le)    obtain ⟨V, hVsub, hVcard⟩ := Finset.exists_superset_card_eq      (show W.card ≤ k + 1 by omega)      (show k + 1 ≤ Fintype.card (Fin m) by simpa using hk)    refine ⟨W, V, hVsub, ⟨hWcard, ?_⟩, ⟨hVcard, ?_⟩⟩    · intro ℓ hℓ G hG      have hG' : is_ejr_cohesive_group A (k + 1) ℓ G :=        ⟨hG.1.trans (Nat.mul_le_mul_left G.card (Nat.le_succ k)), hG.2⟩      obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG'      exact ⟨i, hi, hu.trans (Finset.card_le_card (Finset.inter_subset_inter_left hWsub))⟩    · intro ℓ hℓ G hG      obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG      exact ⟨i, hi, hu.trans (Finset.card_le_card        (Finset.inter_subset_inter_left (hWsub.trans hVsub)))⟩  · have hWcard : W0.card = k + 1 := by omega    have hfull : W0.card * n = (Finset.univ : Finset (Fin n)).card * (k + 1) := by      simp [hWcard, Nat.mul_comm]    have hne : W0.Nonempty := Finset.card_pos.mp (by omega)    obtain ⟨c, hc, hcpair⟩ := hpair hfull hne    refine ⟨W0.erase c, W0, Finset.erase_subset _ _, ⟨?_, ?_⟩, ⟨hWcard, ?_⟩⟩    · rw [Finset.card_erase_of_mem hc, hWcard]      omega    · intro ℓ hℓ G hG      have := hcpair ℓ hℓ G (Finset.subset_univ _)      simpa using this hG    · intro ℓ hℓ G hG      exact hrep ℓ hℓ G (Finset.subset_univ _) hG
See it in the graphDiscuss this resultChallenge it