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

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 30, 2026

Outer Diversity of Condorcet Domains

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.
Oct 5, 2026

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

Aggregating the preferences of diverse user groups into a collective outcome raises fundamental challenges of equity, diversity, and inclusion (EDI): classical aggregation rules such as Borda and Condorcet have no mechanism to prevent results from systematically favoring majority groups, collapsing onto homogeneous items, or under-representing minorities. We address this problem through EDI-constrained graph summarization. User preferences are modeled as a weighted attributed bipartite graph, and a greedy coarsening algorithm iteratively merges user nodes while enforcing three structural EDI criteria: an equity gap constraint (ΔEΔE), an intra-list diversity constraint (ILD), and a group inclusion constraint. Rather than correcting fairness after aggregation, our method embeds EDI preservation directly into the graph structure. We evaluate across five datasets spanning four domains: MovieLens 100k and 1M, libimseti.cz, Rate My Professors, and OpenAlex (2018-2023). Our method, AURORA, achieves the largest and most consistent diversity gains over classical voting rules, and on MovieLens 100k at k=20k = 20 it simultaneously improves all three EDI criteria over both Borda and Condorcet. On Rate My Professors, it combines high diversity (ILD = 0.808) with the highest female item representation (60%), at a moderate equity cost, and it achieves the lowest equity gap (ΔE=0.031ΔE = 0.031) on OpenAlex, where Borda-based methods recommend zero female authors. On libimseti.cz, the only dataset where the sensitive attribute is present on both sides of the bipartite graph, our method does not reduce the equity gap, a limitation we connect to prior findings that demographic parity is not always an appropriate target. These results demonstrate that embedding EDI constraints into aggregation structure yields more robust fairness-diversity trade-offs than post-hoc approaches.
Sep 27, 2026

Nearly Group-Separable Elections

We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.