Outer Diversity of Structured Domains

Piotr Faliszewski; Krzysztof Sornat; Stanisław Szufa; Tomasz Wąs

cs.GTFeb 17, 2026

Outer Diversity of Structured Domains

Authors: Piotr Faliszewski, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs

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

Abstract

An ordinal preference domain is a subset of preference orders that the voters are allowed to cast in an election. We introduce and study the notion of outer diversity of a domain and evaluate its value for a number of well-known structured domains, such as the single-peaked, single-crossing, group-separable, and Euclidean ones.

Figures & tables

		Complexity of Finding
Domain	Size	Closest Ranking from $D$
${\mathrm{GS}}({T})$	$\leq 2^{m-1}$	$O(m^{2})$
${\mathrm{GS/cat}}$	$2^{m-1}$	$O(m\log m)$
${\mathrm{GS/bal}}$	$2^{m-1}$	$O(m\log m)$
${\mathrm{SP}}$	$2^{m-1}$	$O(m^{2})$
${\mathrm{SP/DF}}$	$2^{m+1}-16$	$O(m^{4})$

Table 1: For each domain we give its size and the complexity of finding its closest member (in terms of swap distance) to a given input ranking. Running times marked with ∗ do not include the time needed for preprocessing.

Domain $D$	$\|D\|$	${\mathrm{ansd}}(D)$	${\mathrm{out}\hbox{-}\mathrm{div}}(D)$	dist- $1$	dist- $1$ / $\|D\|$
Vote+Its Rev.	2	0.384	0.232	14	7
GS/cat	128	0.194	0.613	704	5.5
GS/bal	128	0.257	0.486	384	3
SP	128	0.284	0.432	384	3
SP/DF	496	0.239	0.522	968	1.952
SPOC	512	0.196	0.608	1280	2.5

Table 2: Size, average normalized swap distance, outer diversity, and size of direct neighborhood (also normalized) of various domains, for the case of

\boldsymbol{8}

candidates. The standard deviation of outer diversity for domains that we need to sample (

\boldsymbol{{\mathrm{SC}}}

\boldsymbol{{\mathrm{1D\hbox{-}Int.}}}

\boldsymbol{{\mathrm{2D\hbox{-}Square}}}

\boldsymbol{{\mathrm{3D\hbox{-}Cube}}}

) is no larger than

\boldsymbol{0.005}

(for ten samples).

Panel of Figure 1 — Figure 1: Microscope plots of our domains, where each dot/cross represents a ranking from the domain, colored according to its normalized popularity (see Remark 5.1 ). Rankings with normalized popularity below $\boldsymbol{1}$ are marked with crosses, and the remaining ones with dots. Dots marking rankings with normalized popularity equal to exactly $\boldsymbol{1}$ have a black border.

Panel of Figure 2 — Figure 2: Outer diversity of several structured domains as a function of the number of candidates (on the left), or as a function of their size (on the right; including approximations of most diverse domains). For $\boldsymbol{{\mathrm{SPOC}}}$ and $\boldsymbol{{\mathrm{3D\hbox{-}Cube}}}$ , we omit outer diversity for $\boldsymbol{20}$ candidates, due to computation time.

Panel of Figure 3 — Figure 3: Outer diversity of several structured domains as a function of the number of candidates, compared to the outer diversity of (an approximation of) the most diverse domain of the same size.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: An illustration of the construction from the proof of Theorem 4.6 .

Figure 5: Comparison of the optimal diversity (red line) and the one achieved by simulated annealing (black line) for $6$ candidates.

Panel of Figure 6 — Figure 6: Histograms of votes at a given swap distance.

Social Choice Theory

Social choice theory studies how individual preferences can be combined into collective decisions, fair allocations, and representative outcomes.

See all 53 papers

Outer Diversity of Condorcet Domains
Sep 30, 2026Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak +3Social Choice Theory Majority Voting
AGH University, Poland · University of Geneva, Switzerland · University of Oxford, United Kingdom
Aggregating User Preferences while Ensuring Equity, Diversity, and Inclusion using Graph Summarization
Oct 5, 2026Adji Marieme Sita Cissé, Malek MouhoubGroup Fairness Rank Aggregation
Université Paris-Saclay, UVSQ, France · Department of Computer Science, University of Regina, Regina, SK, Canada
Nearly Group-Separable Elections
Sep 27, 2026Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski +3Social Choice Theory Parameterized Complexity
AGH University of Krakow, Poland · University of Warsaw, Poland · Charles University, Czechia +3

Sep 30, 2026J/K move · Enter open · S save

Outer Diversity of Condorcet Domains

Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat+2

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

Social Choice Theory Majority Voting

Open paper AskPDF arXiv

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.

Abstract

Social Choice Theory

Explore similar work

Outer Diversity of Condorcet Domains

Aggregating User Preferences while Ensuring Equity, Diversity, and Inclusion using Graph Summarization

Nearly Group-Separable Elections