AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_family_of_subset_potentials

theoremverified

If every outside-challenger selector for a finite committee family has nonnegative integer weights and a subset potential satisfying the local first-candidate removal inequalities, with twice the full-set potential strictly less than the total weight, then every positive finite electorate has a winning committee in the family. Universal certificate existence remains an explicit hypothesis.

Statement

theorem condorcet_winning_family_of_subset_potentials
    (m q : ℕ) (S : Fin q → Finset (Fin m))
    (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) →
      ∃ (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ),
        (∀ A : Finset (Fin m), ∀ a ∈ A,
          (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + H (A.erase a) ≤ H A) ∧
        2 * H univ < ∑ i, w i) :
    ∀ (n : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)),
      ∃ i, is_condorcet_winning_set P (S i)
Source
IN-339 supporting step for the OP-19 campaign. Strict definition: Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . Related selector formulation: arXiv:2604.19851v2. These are verification and coalition-closure helpers; no new dimension bound or research advance is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof reduces the existence of a Condorcet winning committee to constructing ordering certificates via `condorcet_winning_family_of_ordering_certificates`. For each outside challenger selector, the hypothesis supplies weights and a subset potential whose value on the full set bounds the ordering score of any voter ranking. Multiplying this bound by two and chaining it with the hypothesis that twice the full-set potential is strictly less than the total weight produces the required ordering certificate.

  1. It suffices to show that every outside challenger selector admits weights satisfying the Condorcet ordering certificate condition.

    By applying `condorcet_winning_family_of_ordering_certificates`, the theorem reduces to finding, for every challenger function f mapping each committee to an external alternative, a weight vector w such that twice the ordering score is strictly less than the total weight for every voter preference ordering.

    line 15

    uses condorcet_winning_family_of_ordering_certificates

      apply condorcet_winning_family_of_ordering_certificates m q S
  2. For an arbitrary outside challenger selector f, the weights w provided by the subset potential hypothesis serve as the candidate certificate weights.

    Given an outside selector f such that f(i) ∉ S(i) for all i, the hypothesis hcert yields weights w and a subset potential H satisfying the local first-candidate removal step inequality and the bound 2 * H(univ) < ∑ i, w(i). We choose these weights w for the ordering certificate.

    lines 16–18

      intro f hf
      obtain ⟨w, H, hstep, hbound⟩ := hcert f hf
      refine ⟨w, ?_⟩
  3. For every voter preference ordering σ, twice the ordering score of f under w is strictly less than the total weight ∑ i, w(i).

    For any preference order σ, the lemma `condorcet_ordering_score_le_subset_potential` bounds the ordering score ∑_{i, ∀ c ∈ S(i), σ(f(i)) < σ(c)} w(i) by the potential of the full set, H(univ). Multiplying this inequality by 2 via `Nat.mul_le_mul_left` gives 2 * (score) ≤ 2 * H(univ). Chaining this with the boundary hypothesis 2 * H(univ) < ∑ i, w(i) via transitivity (`lt_of_le_of_lt`) completes the proof.

    lines 19–21

    uses Nat.mul_le_mul_left, condorcet_ordering_score_le_subset_potential, lt_of_le_of_lt

      intro σ
      exact lt_of_le_of_lt (Nat.mul_le_mul_left 2
        (condorcet_ordering_score_le_subset_potential m q S f w H hstep σ)) hbound
condorcet_winning_family_of_ordering_certificates
If every outside challenger selector admits weights such that twice the ordering score is strictly less than the total weight for all voter rankings, then every positive finite electorate has a Condorcet winning committee in the family.
condorcet_ordering_score_le_subset_potential
For any outside selector, weights, and potential function satisfying the local subset removal inequalities, the ordering score under any permutation is at most the potential of the full set of alternatives.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers on the left by a constant preserves the inequality.
lt_of_le_of_lt
In a preorder, if a ≤ b and b < c, then a < c.

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

open Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_winning_family_of_subset_potentials    (m q : ℕ) (S : Fin q → Finset (Fin m))    (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) →      ∃ (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ),        (∀ A : Finset (Fin m), ∀ a ∈ A,          (∑ i, if f i = a ∧ S i ⊆ A.erase a then w i else 0) + H (A.erase a) ≤ H A) ∧        2 * H univ < ∑ i, w i) :    ∀ (n : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)),      ∃ i, is_condorcet_winning_set P (S i) := by  apply condorcet_winning_family_of_ordering_certificates m q S  intro f hf  obtain ⟨w, H, hstep, hbound⟩ := hcert f hf  refine ⟨w, ?_⟩  intro σ  exact lt_of_le_of_lt (Nat.mul_le_mul_left 2    (condorcet_ordering_score_le_subset_potential m q S f w H hstep σ)) hbound
See it in the graphDiscuss this resultChallenge it