condorcet_winning_family_of_subset_potentials
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
- condorcet_ordering_score_le_subset_potentialFor any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining…
- condorcet_winning_family_of_ordering_certificatesIf every outsider selector on a finite committee family admits nonnegative integer weights such that every strict ranking satisfies claims…
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
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.
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.
uses
condorcet_winning_family_of_ordering_certificatesapply condorcet_winning_family_of_ordering_certificates m q SFor 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.
intro f hf obtain ⟨w, H, hstep, hbound⟩ := hcert f hf refine ⟨w, ?_⟩
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.
uses
Nat.mul_le_mul_left,condorcet_ordering_score_le_subset_potential,lt_of_le_of_ltintro σ 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
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.
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