is_condorcet_winning_set
def
With 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 voters rank a above every member of S (equivalently, a strict majority prefers some member of S to a).
Statement
def is_condorcet_winning_set {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) : Prop
- Defined in
- Condorcet winning sets (Social Choice and Welfare 44(3):493-517, 2015), definition of Condorcet winning sets and Condorcet dimension
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Used by 29
- condorcet_dimension_le_two_of_le_threeEvery election with at most three candidates and at least one voter has a Condorcet winning set of at most two candidates.
- condorcet_winning_family_of_subset_potentialsIf every outside-challenger selector for a finite committee family has nonnegative integer weights and a subset potential satisfying the…
- condorcet_dimension_le_three_iff_oriented_acyclic_weight_separationThe unchanged universal strict three-candidate election conjecture is equivalent to the strict acyclic-weight-separation assertion…
- condorcet_winning_set_of_top_choicesFor any election with at least one candidate, the set of top-choice candidates of any subset of voters V0 is a Condorcet winning set…
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- condorcet_winning_of_pairwise_dominatedIf every candidate outside S is pairwise strictly majority-defeated by some candidate in S, then S is a Condorcet winning set.
- condorcet_dimension_le_three_of_le_fiveEvery election with at most 5 candidates (and at least 1 voter) has a Condorcet winning set of at most 3 candidates.
- condorcet_mutual_bad_outsiders_partitionIf two challenger claims are incompatible because each challenger lies in the other committee, and each has at least half the voter…
- condorcet_acyclic_half_cover_of_no_winning_kFor any n and k, a finite n-voter election with no strict Condorcet winning set of size at most k yields a finite relation with outside…
- condorcet_dimension_le_four_of_odd_threeIf every finite strict-ranking election with a positive odd number of voters has a strict Condorcet winning set of size at most three,…
- condorcet_dimension_le_three_iff_acyclic_cover_closed_walkThe universal strict Condorcet bound three is equivalent to the following statement: on every finite S3 directed relation, every positive…
- condorcet_winning_set_of_sum_min_rank_ltIf 2 * (sum of min ranks of S) < n, then S is a Condorcet winning set.
- condorcet_equal_coalition_root_sinkIn a positive finite electorate, let a family of challenger claims all have exactly the same voter coalition as one claim with at least…
- condorcet_ordering_certificate_excludes_common_obstructionFor any finite family of challenger claims with nonnegative integer weights, if in every strict ranking their total satisfied weight is…
- condorcet_six_balanced_has_winning_three_setOpen sub-problem: every six-candidate election with at least one voter in which every three-candidate set contains the top choice of at…
- condorcet_dimension_le_three_of_voters_le_fiveEvery election with at most 5 voters (and at least 1 voter) has a Condorcet winning set of at most 3 candidates: selecting the top-choice…
- condorcet_winning_set_of_bottom_three_majorityIf S is a set of exactly three candidates and every candidate a outside S is ranked below all but at most two candidates by a strict…
- condorcet_potential_break_of_fixed_electorate_boundAssume every finite election with exactly n voters has a strict Condorcet winning committee of size at most k. Then on any finite relation…
- condorcet_acyclic_cover_no_winning_kFor any voter count n and committee bound k, a finite relation having outside common predecessors for all sets of at most k vertices,…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- condorcet_dimension_le_three_of_le_fourEvery election with at most four candidates (and at least one voter) has a Condorcet winning set of at most three candidates: drop a…
- is_condorcet_winning_set_nonemptyIn an election with at least one voter and at least one candidate, every Condorcet winning set is nonempty.
- is_condorcet_winning_set_monoCondorcet winning sets are upward closed: if S is a Condorcet winning set and S is a subset of T, then T is also a Condorcet winning set.
- condorcet_failure_k_iff_acyclic_half_coverFor fixed voter count n and committee bound k, some finite n-voter election has no strict Condorcet winning committee of size at most k if…
- condorcet_winning_set_of_top_choice_majorityAny candidate set S whose complement contains the top choice of strictly fewer than n/2 voters (i.e. S contains the top choices of a…
- condorcet_winning_set_univThe set of all candidates is a Condorcet winning set.
- condorcet_dimension_le_three_iff_acyclic_cover_potential_breakThe original universal strict Condorcet winning-set bound of three is equivalent to this assertion: for every finite relation with an…
- 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…
- condorcet_winning_family_of_subset_potentials_oddFix a relation R on the candidates. Suppose every outside-challenger selector whose roots are R-related to all committee members has…
Lean source view module on GitHub
/-- A Condorcet winning set in the election where voter `v` ranks candidate `c` at position `P v c` (position 0 is the top): for every candidate `a` outside `S`, strictly fewer than half of the voters rank `a` above every member of `S`. -/ def is_condorcet_winning_set {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) : Prop := ∀ a, a ∉ S → 2 * (Finset.univ.filter fun v => ∀ b ∈ S, P v a < P v b).card < n