cs.GTFeb 17, 2026
SaveOuter Diversity of Structured Domains
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 |
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 | dist- | dist- / | |||
| 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 candidates. The standard deviation of outer diversity for domains that we need to sample ( , , , ) is no larger than (for ten samples).
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 are marked with crosses, and the remaining ones with dots. Dots marking rankings with normalized popularity equal to exactly have a black border.
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 and , we omit outer diversity for candidates, due to computation time.
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
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 candidates.
Figure 6: Histograms of votes at a given swap distance.
More in this topic
Social Choice Theory
Social choice theory studies how individual preferences can be combined into collective decisions, fair allocations, and representative outcomes.
See all 53 papersA 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.
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 (), 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 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 () 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.
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.