Outer Diversity of Condorcet Domains

Piotr Faliszewski; Jan Jabrocki; Mateusz Słuszniak; Krzysztof Sornat; Stanisław Szufa; Tomasz Wąs

cs.GTSep 30, 2026

Outer Diversity of Condorcet Domains

Authors: Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs

Organizations: AGH University, Poland · University of Geneva, Switzerland · University of Oxford, United Kingdom

Abstract

A Condorcet domain is a set of rankings over a given candidate set, such that every election that consists only of (an odd number of) votes from the domain has a transitive majority relation. We study outer diversity of Condorcet domains, i.e., a measure that quantifies expected swap distance from a random vote to a closest one in the domain. We numerically analyze outer diversity for maximal Condorcet domains with few candidates, and then we establish its asymptotic behavior for several special domains, mostly obtaining theoretical results.

Figures & tables

Panel of Figure 1 — Figure 1 : Analysis of all of the maximal Condorcet domains for six candidates.

Panel of Figure 2 — Figure 2 : Outer diversity of ${\mathrm{GS}}$ , ${\mathrm{SP/T}}$ and ${\mathrm{SC}}$ domains, depending on the number of candidates.

Figure 3 : Outer diversity of

{\mathrm{SP}}

{\mathrm{SP/star}}

{\mathrm{GS/cat}}

{\mathrm{GS/bal}}

, and

{\mathrm{SC}}

for large numbers of candidates. Note that the

x

axis is scaled logarithmically. Shaded areas show two standard deviations for sampling-based computations.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4 : Analysis of all of the maximal Condorcet domains for seven candidates.

Panel of Figure 5 — Figure 5 : Candidate distributions within circular and square subareas using a sample size of $500,000$ points.

Panel of Figure 6 — Figure 6 : Heatmaps of mean outer diversity as a function of the number of candidates in 2D Euclidean domains, compared across circular and square subareas. The Beta distribution parameters are shown on a logarithmic scale. The $95\%$ confidence interval indicates a margin of error of at most $0.00262$ , with only two exceptions reaching $0.00928$ and $0.00817$ for the square subarea at $\alpha=\beta=0.1$ with 4 and 3 candidates, respectively. The number of generated samples per candidate count is $6000$ , $4000$ , $2000$ , $1000$ , $500$ , and $200$ for $3,4,5,6,7$ , and $8$ candidates, respectively.

Figure 7 : $100,000$ 2D Euclidean domains with candidates generated uniformly at random within a square subarea. Each domain is represented as a single dot, where the x-axis corresponds to the number of votes within the domain and the y-axis represents its outer diversity. This subset illustrates a representative sample, not all possible domains.

Figure 8 : Microscope visualizations of Condorcet domains on 6 candidates. For each domain size (number of distinct votes), we show the domain with the largest outer-diversity. Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate.

Figure 9 : Microscope visualizations of Condorcet domains on 6 candidates. For each domain size (number of distinct votes), we show the domain with the smallest outer-diversity. Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate.

Figure 10 : Microscope visualizations of various SP/T domains with up to 9 candidates, and up to 1000 votes. For each domain size (number of distinct votes), we show the domain with maximum (top) and minimum (bottom) outer-diversity. Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate.

Figure 11 : Microscope visualizations of domains satisfying never-middle condition, that are not $GS$ . Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate.

Figure 12 : Microscope visualizations of ${\mathrm{GS}}$ domains. Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate.

Explore similar work

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections
Apr 21, 2026Itai Zilberstein, Ratip Emin Berker, George Li +1Elections Majority Voting
Carnegie Mellon University Pittsburgh, USA
Nearly Group-Separable Elections
Sep 27, 2026Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski +3Elections Maximum Independent Set
AGH University of Krakow, Poland · University of Warsaw, Poland · Charles University, Czechia +3
Voting Method Synthesis on an Infinite Domain: A Possibility Theorem for Positive Involvement
Aug 9, 2026Wesley H. HollidaySatisfiability Majority Voting
University of California, Berkeley

Apr 21, 2026, cs.GTJ/K move · Enter open · S save

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections

Itai Zilberstein, Ratip Emin Berker, George Li, Ruben Martins

Carnegie Mellon University Pittsburgh, USA

Elections Majority Voting Upper Bounds Maximum Independent Set Candidate Mixed-Integer Programming

Open paper AskPDF arXiv

In an election where

n

voters rank

m

candidates, a Condorcet winning set is a committee of

k

candidates such that for any outside candidate, a majority of voters prefer some committee member. Condorcet's paradox shows that some elections admit no Condorcet winning sets with a single candidate (i.e.,

k=1

), and the same can be shown for

k=2

. On the other hand, recent work proves that a set of size

k=5

exists for every election. This leaves an important theoretical gap between the best known lower bound

(k\geq 3)

and upper bound

(k \leq 5)

for the number of candidates needed to guarantee existence. We aim to close the gap between the existence guarantees and impossibility results for Condorcet winning sets. We explore an automated reasoning approach to tighten these bounds. We design a mixed-integer linear program (MILP) to search for elections that would serve as counter-examples to conjectured bounds. We employ a number of optimizations, such as symmetry breaking, subsampling, and constraint generation, to enhance the search and model effectively infinite electorates. Furthermore, we analyze the dual of the linear programming relaxation as a path towards obtaining a new upper bound. Despite extensive search on moderate-sized elections, we fail to find any election requiring a committee larger than size 3. Motivated by our experimental results in this direction, we simplify the dual linear program and formulate a conjecture which, if true, implies that a winning set of size 4 always exists. Our automated reasoning results provide strong empirical evidence that the Condorcet dimension of any election may be smaller than currently known upper bounds, at least for small instances. We offer a general-purpose framework for searching elections in ranked voting and a new, concrete analytical path via duality toward proving that smaller committees suffice.

Abstract

Explore similar work

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections

Nearly Group-Separable Elections

Voting Method Synthesis on an Infinite Domain: A Possibility Theorem for Positive Involvement