Paper deep dive
Outer Diversity of Condorcet Domains
Piotr Faliszewski, Jan Jabrocki, Mateusz Słuszniak, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/2/2026, 9:35:21 AM
Summary
This paper investigates the 'outer diversity' of Condorcet domains, a metric quantifying the expected swap distance from a random vote to the closest vote within the domain. The authors numerically analyze this metric for maximal Condorcet domains with few candidates (specifically 6 candidates) and establish asymptotic behaviors for special domains like single-peaked on a tree, group-separable, and single-crossing domains. Key findings include a strong correlation between outer diversity and the number of satisfied 'never-middle' conditions, and the discovery that single-peaked domains on trees can achieve outer diversity comparable to the general domain in the limit.
Entities (10)
Relation Signals (6)
Piotr Faliszewski → affiliatedwith → AGH University
confidence 95% · Piotr Faliszewski , faliszew@agh.edu.pl, AGH University, Poland
Single-Peaked on a Tree → istypeof → Weak Condorcet Domain
confidence 95% · domains single-peaked on a tree... are weak Condorcet.
Outer Diversity → measures → Swap Distance
confidence 95% · outer diversity... quantifies expected swap distance from a random vote to a closest one in the domain.
Group-Separable → satisfies → Never-Middle Condition
confidence 95% · group-separable domains satisfy never-middle conditions only.
Outer Diversity → correlateswith → Never-Middle Condition
confidence 90% · the number of satisfied never-middle conditions is strongly correlated with the domains’ outer-diversity
Condorcet Domain → requires → Never-Middle Condition
confidence 90% · A domain is Condorcet if and only if, for every triple of candidates, it satisfies at least one of the never conditions... never-middle
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.00720v1
- Canonical: https://arxiv.org/abs/2610.00720v1
Trouble viewing inline? Open PDF directly →
Full Text
112,489 characters extracted from source content.
Expand or collapse full text
Outer Diversity of Condorcet Domains Piotr Faliszewski Jan Jabrocki Mateusz Słuszniak Krzysztof Sornat Stanisław Szufa Tomasz Wąs 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. Code: https://github.com/Project-AGREE/Outer-Diversity-Condorcet/ 00footnotetext: Authors’ Information: Piotr Faliszewski , faliszew@agh.edu.pl, AGH University, Poland; Jan Jabrocki, jjabrocki@student.agh.edu.pl, AGH University, Poland; Mateusz Słuszniak, msluszniak1@gmail.com, AGH University, Poland; Krzysztof Sornat , sornat@agh.edu.pl, AGH University, Poland; Stanisław Szufa , s.szufa@gmail.com, University of Geneva, Switzerland; Tomasz Wąs , tomasz.was@cs.ox.ac.uk, University of Oxford, United Kingdom. 1 Introduction We study outer diversity of Condorcet domains for ordinal elections, focusing on both the values for specific domains and on algorithms for computing them. Below we explain these notions intuitively and explain why seeking outer diversity of Condorcet domains is interesting. In the setting of ordinal preferences, each vote is a ranking of candidates—from the most to the least appealing one—and a preference domain is a set of votes that are allowed in a considered election. For example, the general domain contains all possible rankings, the single-peaked domain contains those that arise when the candidates form a single-dimensional spectrum [Black, 1958],11 1 E.g., this domains captures political preferences, when the candidates are ordered on the left-to-right scale. and the group-separable domain captures preferences over candidates with hierarchically-organized features [Inada, 1964; Inada, 1969] (the feature-based interpretation is presented, e.g., by Faliszewski et al. [2022]). A Condorcet domain guarantees that the majority relation of an election with an odd number of votes from such a domain is transitive: If a majority of voters prefers candidate a to candidate b, and a (possibly different) majority of voters prefers b to c, then there is also a majority of voters that prefers a to c. For example, single-peaked and group-separable domains are Condorcet (see the book of Puppe and Slinko [2026] and the surveys of Elkind et al. [2022] and Monjardet [2009] for a discussion of various such domains). Outer diversity, introduced by Faliszewski et al. [2026b], quantifies the expected distance from a random vote to the closest one in the domain (see Section 2 for formal definitions) and, hence, measures how well a given domain covers the general one. Condorcet domains are among the most classic objects studied within social choice theory. Indeed, the single-peaked domain was already introduced by Black [1958] and was quickly generalized by Arrow [1963]. Sen [1966] provided an exact characterization of Condorcet domains using so-called never conditions: A domain is Condorcet if and only if for each triple of candidates a, b, and c it either satisfies a never-top, a never-middle, or a never-bottom condition: The former requires that there is candidate x∈a,b,cx∈\a,b,c\ such that no vote in the domain ranks x on top when restricted to a,b,c\a,b,c\, and the other two conditions are defined analogously. For example, Black’s and Arrow’s single-peaked domains satisfy never-bottom conditions, peak-pit domains of Danilov et al. [2012] satisfy combinations of never-top and never-bottom conditions (and, hence, peak-pit domains include the single-peaked ones, but also many others). On the other hand, group-separable domains satisfy never-middle conditions only. Generally, the never conditions satisfied by a given domain have a strong influence on its properties, but the nature of this influence is only partially understood. We are interested in outer diversity of Condorcet domains because it extends this understanding. Diversity analysis is also interesting because it gives a new perspective on the long-studied problem of finding large Condorcet domains [Fishburn, 1996; Galambos and Reiner, 2008; Danilov et al., 2012; Karpov and Slinko, 2023; Puppe and Slinko, 2024]. Such domains are sought after because they are interesting mathematically, but also because, intuitively, the larger a domain is, the more freedom it gives the voters to express their views (while ensuring transitivity of the majority relation). Yet, as shown by Faliszewski et al. [2026b], having many votes does not need to translate to high outer diversity value: The largest Condorcet domain with 88 candidates, computed by Leedham-Green et al. [2024], has 224 votes but is notably less diverse than some group-separable ones, with only 128 votes. As outer diversity quantifies voters’ ability to express their views more directly than domain cardinality, we propose to seek Condorcet domains for which outer diversity is highest. Further, diversity analysis of Condorcet domains is currently receiving increased attention. For example, Karpov et al. [2024] and Ammann and Puppe [2025] measured diversity using various richness properties, such as the number of different tuples of candidates that can be ranked among top positions, and Faliszewski et al. [2026a] introduced inner diversity, which measures how tightly packed are the votes in a given domain. The advantage of outer diversity over these measures is that it provides a single, easy to interpret number (inner diversity provides vectors of numbers, which are not easy to compare, and it is not clear which richness-based notions to use). For a general theory of diversity, we point to the work of Nehring and Puppe [2002]. Contributions. First, we consider all Condorcet domains with six candidates, as enumerated by Akello-Egwel et al. [2025], and we analyze their properties, connecting these properties to the never conditions that they satisfy. Based on these findings, we pursue asymptotic behavior of outer diversity of several special domains. While doing so, we improve some of the results of Faliszewski et al. [2026b]. For example, they computed outer diversity of their domains for up to 2020 candidates, whereas we consider up to 100100 candidates (albeit we do not consider all the domains that they do), they showed a lower bound on outer diversity of the group-separable/caterpillar domain and we give an exact formula for its value, and they provided approximation, sampling-based algorithms for computing outer diversity for their domains, whereas we give some exact algorithms. Additionally, we also consider domains single-peaked on a tree [Demange, 1982; Peters et al., 2022], which are weak Condorcet. Any election with an odd number of votes from such a domain is guaranteed to have a Condorcet winner, i.e., a candidate that is preferred to every other one by a majority of voters. We find that, in the limit, such domains can be as outer-diverse as the general one. All omitted proofs can be found in Appendix A. 2 Preliminaries Given a set of candidates C=c1,…,cmC=\c_1,…,c_m\, a vote (or, a preference order, or a preference ranking) is a total order over C, ranking the candidates from the most to the least desirable one. For two candidates a,b∈Ca,b∈ C, we write v:a≻bv a b to indicate that a is preferred over b in vote v (i.e., v ranks a higher than b). An election E=(C,V)E=(C,V) is a pair, where C is a set of candidates and V is a collection of voters, each with a single vote. For an election E=(C,V)E=(C,V), we say that candidate a∈Ca∈ C is majority-preferred to candidate b∈Cb∈ C, denoted aMEba M_Eb, if a strict majority of voters in V prefer a over b. We refer to MEM_E as the majority relation of E. We are particularly interested in elections for which MEM_E is an order, and we call such elections transitive. A candidate c∈Cc∈ C is a Condorcet winner if for every other candidate d∈Cd∈ C we have cMEdc M_Ed. Naturally, an election either has a unique Condorcet winner or does not have one at all. Every transitive election has a Condorcet winner, but there are also nontransitive ones with Condorcet winners. 2.1 Domains A domain over candidate set C is any subset of votes over C. In particular, we write ℒ(C)L(C) to denote the general domain that contains all votes over C. By a domain’s size, we mean the number of votes that it contains. Given a domain D, we say that an election E is a D-election if every voter has a vote that belongs to D. We say that D is a Condorcet domain if every D-election with an odd number of voters is transitive. A Condorcet domain D is maximal if for every vote v (over the same candidate set) not present in D, D∪vD∪\v\ is not a Condorcet domain. D is a weak Condorcet domain if every D-election with an odd number of voters has a Condorcet winner. For a detailed survey on Condorcet domains, we point to the book of Puppe and Slinko [2026], as well as to the surveys of Elkind et al. [2022] and Monjardet [2009]. Condorcet domains are characterized using so-called never conditions. For a triple a,b,c⊆C\a,b,c\ C we say that x∈a,b,cx∈\a,b,c\ is never-top (resp. never-middle, never-bottom) in D with respect to a,b,c\a,b,c\ if no vote in D ranks x first (resp. second, last) among a,b,c\a,b,c\. A domain is a Condorcet domain if and only if, for every triple of candidates, it satisfies at least one of the never conditions [Sen, 1966]. Next we describe the domains and families of domains that we focus on. Peak-Pit. A domain D is a peak-pit domain if it is a Condorcet domain that for every triple of candidates either satisfies a never-top or a never-bottom condition [Danilov et al., 2012]. While peak-pit domains are one of the major classes of Condorcet domains, so far they only received very limited attention from computational social choice. For example, the complexity of deciding if a given set of never-top and never-bottom conditions yields a nonempty domain is not known (Puppe and Slinko [2026] conjecture that it is NPNP-complete). A Fishburn domain is a peak-pit domain that for a given ordering of candidates, c1⊳c2⊳⋯⊳cmc_1 c_2 ·s c_m, requires that among every three candidates ci,cj,ckc_i,c_j,c_k, with i<j<ki<j<k, cjc_j is never-top, if j is odd, and cjc_j is never-bottom, if j is even [Fishburn, 1996]. Fishburn domains are among the largest Condorcet domains (albeit, in general, they are known to not be the largest ones [Leedham-Green et al., 2024]). As opposed to peak-pit domains, the family of single-peaked domains has received very detailed attention in (computational) social choice and includes some of the best known domains [Elkind et al., 2022]. However, not all domains in this family are Condorcet or even weak Condorcet. Formally, let G be an undirected, connected graph with vertex set C. Following Faliszewski et al. [2026b], we refer to such graphs as SP-graphs (or SP-trees, when G is a tree). A vote v∈ℒ(C)v∈L(C) is single-peaked on G if for each t∈[m]t∈[m] the t top-ranked candidates in v form a connected component within G. A domain D is single-peaked on a graph, denoted SP/GSP/G, if there is an SP-graph G such that D consists exactly of votes single-peaked on G. The particular G we have in mind will either be clear from the context or irrelevant for the discussion. We consider the following SP/GSP/G domains: Single Peaked (SP). The classic single-peaked domain (SPSP), introduced by Black [1958], is defined over a path and, w.l.o.g., we use path c1⊳c2⊳⋯⊳cmc_1 c_2 ·s c_m. This path is called the societal axis. SP is a Condorcet domain: Indeed, for every three candidates ci,cj,ckc_i,c_j,c_k, with i<j<ki<j<k, we see that cjc_j is never-bottom. SPSP is sometimes referred to as Black’s single-peakedness. We are also interested in Arrow’s single peaked domains (Arrow’s SP domains, for short) that generalize Black’s SP by requiring that every triple of candidates satisfies some never-bottom condition, but not restricting these conditions to be defined by the axis [Arrow, 1963].22 2 The reader may wonder about domains defined by never-top conditions only. These are so-called single-dipped domains and are obtained by reversing all the votes in the Arrow’s single peaked ones. Because of this symmetry, they are not interesting in our study as, by necessity, their outer diversity is the same as that of their dual Arrow’s SPSP domains. Note that Arrow’s SP domains are not SP/GSP/G domains. SP/T. If an SP-graph is a tree, then we refer to it as an SPSP-tree and to the domain as single-peaked on a tree (SP/TSP/T). These domains were introduced by Demange [1982]. A specific SP/TSP/T that we will consider is based on a star graph with m leaves—we call such domain SP/starmSP/star_m. SP/TSP/T are weak Condorcet domains, but not Condorcet ones. Algorithmic study of SP/TSP/T domains was provided by Peters et al. [2022]. If G is an SP-graph with a cycle, then the SP/GSP/G domain that it yields is not even weak Condorcet. The family of single-crossing domains was introduced by Mirrlees [1971] and Roberts [1977]: Single Crossing (SC). A domain D is single-crossing if it is possible to order its votes as v1⊳v2⊳⋯⊳vnv_1 v_2 ·s v_n, so that for each two candidates ci,cj∈Cc_i,c_j∈ C, votes where cic_i is preferred to cjc_j form either a prefix or a suffix of this order. SC domains are Condorcet and, indeed, they form a subclass of the peak-pit domains. We note that there are many nonisomorphic single-crossing domains [Faliszewski et al., 2025]. In particular, Szufa et al. [2025] suggested an algorithm for sampling such domains, albeit their algorithm does not ensure uniform distribution. Whenever we refer to single-crossing domains, either it will be clear which specific SCSC domain we mean, or it will not be relevant. Next we consider group-separable domains. While these domains were introduced by Inada [1964]; Inada [1969], we use their definition based on trees, provided by Karpov [2019]. Let T be a rooted, ordered, binary tree where each leaf is labeled with a unique candidate from C. We refer to such trees as GS-trees. A frontier of a GS-tree T is the ranking of candidates obtained by reading them off from the leaves, from left to right. We say that a vote v∈ℒ(C)v∈L(C) is compatible with T if v is a frontier of some tree obtained from T by, possibly, reversing the order of some of its nodes’ children: Group-Separable (GS). A domain D is group-separable (GSGS) if there is a GS-tree T such that D consists exactly of the votes compatible with T. GSGS domains are Condorcet and satisfy never-middle condition, but not all domains defined by never-middle conditions are GSGS. GS/cat and GS/bal. A GS-tree is a caterpillar if every internal node has at most one nonleaf child. A GS/caterpillar domain (GS/catGS/cat) is a GSGS domain defined by a caterpillar tree. Similarly, a GS-tree is balanced if for each two leaves their distance from the root differs at most by one, and GS/balanced (GS/balGS/bal) is a GSGS domain defined by a balanced tree. Note that if we ignore leaf labels, then for a given number of candidates, there is a unique caterpillar tree, but possibly many balanced ones, leading to nonisomorphic domains. It is well-known that for a size-m candidate set, Black’s SPSP, as well as all GSGS domains, contain exactly 2m−12^m-1 votes. The same holds for Arrow’s SPSP domains [Slinko, 2019]. 2.2 Outer Diversity Given two votes u,vu,v over candidate set C, their swap distance, known also as Kendall tau distance, denoted swap(u,v)swap(u,v), is the smallest number of swaps of adjacent candidates needed to transform one into the other. The average normalized swap distance of a domain D is defined as: ansd(D)=∑u∈ℒ(C)swap(D,u)m!⋅(m2),ansd(D)= _u (C)swap(D,u)m!· m2, i.e., the expected swap distance between a vote selected uniformly at random from ℒ(C)L(C) and its nearest member of D, normalized by the maximum possible swap distance. The outer diversity of a domain D⊆ℒ(C)D (C) is out-div(D)=1−2⋅ansd(D)out -div(D)=1-2·ansd(D). Outer diversity assumes values between 00 and 11, where 00 is the lowest possible diversity, achieved, e.g., by each singleton domain v\v\, and 11 is the maximum diversity, achieved by ℒ(C)L(C). Outer diversity was introduced by Faliszewski et al. [2026b]. In particular, they gave a general brute-force algorithm for computing its value for domains specified by listing their votes (running in time O(m⋅m!)O(m· m!), where m is the number of candidates; we use this algorithm as a default), as well as sampling-based algorithms. For the latter, the idea is to sample votes from ℒ(C)L(C) and compute their closest members from the considered domain: They provided polynomial-time algorithms for computing a closest SPSP, SCSC, and GSGS vote for a given one (for SPSP, see also the work of Faliszewski et al. [2014]), and a non-polynomial algorithm for SP/TSP/T. They computed outer diversity values for a few special domains for up to 2020 candidates, gave lower bound of 1/2 12 for GS/catGS/cat, and obtained a few other results less directly relevant to our work. 3 Outer Diversity of Domains With a Few Candidates We begin our analysis with an extensive study of Condorcet domains with a few candidates. In this case it is possible to enumerate all nonisomorphic maximal Condorcet domains and we use such an enumeration for 66 candidates, provided by Akello-Egwel et al. [2025] (they generated domains with up to 7 candidates, and we show results for a sample of these domains in Appendix B; the overall conclusions are the same.) Additionally, we also discuss single-crossing domains (which typically are not maximal Condorcet domains) and SP/TSP/T domains.33 3 We ran the experiments presented in the main body of the paper on personal computers. The computatoin required a few dozen hours. 3.1 Maximal Condorcet Domains As established by Akello-Egwel et al. [2025], for the case of 66 candidates there are 256 895256\,895 nonisomorphic maximal Condorcet domains. Among them there are 9 9399\,939 peak-pit domains, of which 4040 are Arrow’s SP domains—including the classic Black’s single-peaked domain—and another 4040 are single-dipped domains. There are also 1212 domains defined by never-middle conditions only, of which 66 are group-separable (two of which have the same outer diversity). In Figure 1(a) we plot all these domains as dots, where the x coordinate gives the number of votes in the domain and the y coordinate gives its outer diversity. Different families of domains are depicted with different colors. As there are 256 895256\,895 domains, many points are occluded by others. For example, many peak-pit domains are drawn “on top of” other domains. We proceed by analyzing the results for particular families of domains. (a) Every maximal nonisomorphic Condorcet domain with six candidates is placed as a dot, with its x coordinate giving the domain’s size, and its y coordinate giving its outer diversity. If a domain belongs to a certain class of domains, such as peak-pit, then its dot is colored accordingly; otherwise it is gray. We additionally include a sample of 200 single-crossing domains. (b) Outer diversity of maximal nonisomorphic Condorcet domains depending on the number of satisfied never-bottom (x-axis) and never-middle (y-axis) conditions. The size of each square reflects the number of domains satisfying given numbers of conditions, and the horizontal color gradient presents the distribution of outer diversity values for these domains. Figure 1: Analysis of all of the maximal Condorcet domains for six candidates. We note that maximal Condorcet domains with even numbers of votes tend to achieve more varied and larger outer diversity values than those with odd numbers. Next, for a given number of votes, peak-pit domains tend to assume lower outer diversity values than domains that include never-middle conditions. Indeed, domains defined entirely by never-middle conditions have some of the highest outer-diversity values overall (including the highest one, assumed by GS/catGS/cat). We explore this in Figure 1(b). Specifically, for each pair b,mb,m of integers, we let D6(b,m)D_6(b,m) be the subset of our domains that satisfy exactly b never-bottom and m never-middle conditions (they also typically satisfy 20−b−m20-b-m never-top conditions, but a small number of domains satisfies more than 2020 never conditions in total). For each D6(b,m)D_6(b,m), we plot a square centered over point (b,m)(b,m), whose side’s length is proportional to 1+log|D6(b,m)|1+ |D_6(b,m)|. The color of the square gradually shifts from left to right, proportionally to the outer diversities of the domains in D6(b,m)D_6(b,m), sorted in the non-decreasing order. Altogether, it is visible that the number of satisfied never-middle conditions is strongly correlated with the domains’ outer-diversity (with PCC = 0.7140.714) and negatively correlated with the number of domains (with PCC = −0.565-0.565). One possible explanation of lower diversity of peak-pit domains is that—at least for up to 77 candidates—these are exactly the connected domains, i.e., domains where for each two of their votes u and v, one can transform u into v by swapping adjacent candidates only, without ever leaving the domain [Akello-Egwel et al., 2025]. This means that, as compared to other domains of the same size, they are confined to a smaller area of the space. On the other hand, Faliszewski et al. [2026b] have shown that GS/catGS/cat is very uniformly spread out through the space of all possible votes and, in this sense, is strongly disconnected. Finding 3.1. The outer diversity of maximal nonisomorphic Condorcet domains with six candidates is strongly correlated with the number of satisfied never-middle conditions (PCC = 0.7140.714). Interestingly, for many pairs (b,m)(b,m) we observe outlier domains in D6(b,m)D_6(b,m) with very low outer diversity values (see, e.g., vertical blue stripe on the left part of squares for m∈10,11m∈\10,11\ in Figure 1(b)). Typically these domains consist of very few votes. However, while low cardinality must imply low outer diversity (see the work of Faliszewski et al. [2026b] and the next section), generally the correlation between cardinality and outer diversity of a domain is fairly weak (PCC=0.3450.345). For example, the Fishburn domain, which is the largest maximal Condorcet domains for six candidates (with 45 votes), has outer diversity of 0.5380.538 (the average over all maximal Condorcet domains for six candidates is 0.4950.495, with standard deviation 0.0210.021, and GS/catGS/cat has outer diversity 0.6490.649). Let us now consider single-peaked domains. For the case of 66 candidates, Black’s SP domain is the most diverse Arrow’s SP domain (the same holds for m=7m=7). It would be very interesting to prove this formally, or to verify computationally for larger numbers of candidates, but currently it is not clear how to efficiently generate Arrow’s SP domains. Finding 3.2. Black’s SP has the highest outer diversity among Arrow’s SP domains for 6 candidates. (a) Outer diversity of GSGS domains. Colors give the heights of the trees that generate the domains. GS/catGS/cat and GS/balGS/bal have highest and lowest outer diversity, respectively. (b) Outer diversity of SCSC domains (light and dark purple dots; see text) and SP/TSP/T domains (blue-to-red dots; colors give diameters of the trees generating the domains). 2402400.7780.778nnout-div out -div 1321320.6710.671 1121120.6440.644 0072720.5820.582 0060600.5730.573 0032320.5050.505 (c) Nonisomorphic trees for SP/TSP/T domains with 66 candidates. For each tree we provide the number of votes (n) in the domain it generates and its outer diversity (out-divout -div). Figure 2: Outer diversity of GSGS, SP/TSP/T and SCSC domains, depending on the number of candidates. Next, let us consider group-separable domains. As they achieve some of the largest outer diversity values among maximal Condorcet domains with six candidates, in Figure 2(a) we also explore how their outer diversity depends on the number of candidates and the heights of the trees used to generate them. Specifically, for each m∈3,…,16m∈\3,…,16\ we generated all nonisomorphic GS-trees with m nodes and computed the outer diversities of their corresponding domains. In Figure 2(a) we depict them as orange/purple dots (their x coordinates correspond to the number of candidates, perturbed a bit for clarity, and their y coordinates give their outer diversity values). We see that the taller a given tree, the larger is the outer diversity value of a given domain. Finding 3.3. For each number of candidates in 3,…,16\3,…,16\, GS/catGS/cat has the highest outer diversity and GS/balGS/bal has the lowest one among GSGS domains. There is a strong correlation between the height of the domain’s tree and its outer diversity (for each m∈4,…,16m∈\4,…,16\, PCC ≥0.896≥ 0.896; for m=3m=3 there is only one domain). It is also interesting to consider the domains that satisfy never-middle conditions only, but that are not group-separable. As we see in Figure 1(a), for six candidates they have fewer votes than the GS ones and their outer diversity values are a bit lower. In Appendix D we have a closer look at them and find that they are structurally quite similar to the GS ones. 3.2 Single-Crossing Domains A single-crossing domain is maximal if it is not possible to extend it without making it non-single-crossing.44 4 Note that being a maximal single-crossing domain typically does not mean being a maximal Condorcet domain. It is well-known that each maximal single-crossing domain consists of 1+(m2)1+ m2 votes, which can be arranged in a line, where each two consecutive votes differ by ordering of two adjacent candidates. For this size, single-crossing domains have fairly low outer diversity. However, as opposed to many other classes of peak-pit domains, we can sample single-crossing domains uniformly at random and, hence, evaluate how their outer diversity changes for somewhat larger candidate sets. Unfortunately, our sampling algorithm runs in exponential time. Theorem 3.4. There exists a sampling procedure that, after O(m⋅m!)O(m· m!) preprocessing, samples a single-crossing domain over m candidates uniformly at random in O(m3)O(m^3) time. Using this sampler, for each m∈3,…,9m∈\3,…,9\ we sampled 10001000 single-crossing domains uniformly at random, without repetition. Additionally, we sampled 10001000 such domains using the polynomial-time algorithm of Szufa et al. [2025] (which does not achieve uniform distribution). For m∈3,4,5m∈\3,4,5\ there are fewer than 10001000 maximal single-crossing domains and for this case we generated all such domains. We restricted attention to up to 99 candidates due to speed of exact computation of outer diversity. For each of the domains we computed its outer diversity. We show the results in Figure 2(b): Each light purple diamond corresponds to a domain sampled using our algorithm and each dark purple diamond corresponds to one sampled using the algorithm of Szufa et al. [2025] (the diamonds for 33 and 44 candidates are much larger as there are very few maximal single-crossing domains in this case, while remaining ones are very small, looking rather like small dots than diamonds, but there are very many of them). We make two observations: Outer diversity of single-crossing domains seems to quickly diminish, and outer diversity of domains sampled using both algorithms seems to follow essentially the same distribution (Kolmogorov-Smirnov test gives D≈0D≈ 0 and p-value ≈1≈ 1). This is reassuring as for larger domain sizes using the uniform algorithm is infeasible. Finding 3.5. For up to 99 candidates, the distributions of outer diversity of maximal single-crossing domains sampled uniformly at random and using the algorithm of Szufa et al. [2025] are near-identical. 3.3 Single-Peakedness on a Tree We conclude this section by considering the family of SP/TSP/T domains, known to be weak Condorcet (the only SP/TSP/T Condorcet domain is Black’s SPSP). In Figure 2(b) we show outer diversity values of these domains for all nonisomorphic SP trees with m∈3,…,9m∈\3,…,9\ candidates. Not surprisingly, the smaller is the diameter of the underlying tree, the higher is the outer diversity of the domain it generates. Indeed, the highest outer diversity is achieved by a star graph (where we have one central node and each other node is connected to it). Finding 3.6. For m∈3,…,9m∈\3,…,9\, outer diversities of SP/TSP/T domains are negatively correlated with the diameter of their underlying trees (PCC monotonically goes from −1-1 for 44 candidates to −0.931-0.931 for 99 candidates). SP/TSP/T domain based on a star graph has the highest outer diversity. In Figure 2(c) we plot the six nonisomorphic SP trees for the case of six candidates, as well as provide the cardinality of the domains they generate and their outer diversity values. It is interesting how, except for Black’s SP (depicted on the bottom), all these domains have significantly more votes than even the largest Condorcet domains. Hence the nature of weak Condorcet domains is quite different from that of Condorcet ones and understanding them better is an interesting research challenge. 4 Asymptotic Behavior of Outer Diversity Figure 3: Outer diversity of SPSP, SP/starSP/star, GS/catGS/cat, GS/balGS/bal, and SCSC for large numbers of candidates. Note that the x axis is scaled logarithmically. Shaded areas show two standard deviations for sampling-based computations. In Figure 3, we plot outer diversity values for SCSC, SPSP, SP/starSP/star, GS/catGS/cat, and GS/balGS/bal, as functions of the number m of candidates, for m up to 100100; our main goal is to analyze these values asymptotically. We selected these domains because each of them is in some way extreme. Indeed, in Section 3 we saw that for six candidates, SP/starSP/star, GS/catGS/cat and SPSP have the highest outer diversity among, respectively, SP/TSP/T domains, all Condorcet domains, and Arrow’s SP domains, whereas GS/balGS/bal has the lowest outer diversity among GSGS domains. SCSC domains serve as representatives of Condorcet domains with low outer diversity that we can sample. Further, they are commonly studied in computational social choice (as are SPSP and GSGS domains). To obtain Figure 3, for SPSP and SCSC we used the approximate sampling algorithm provided by Faliszewski et al. [2026b], whereas for GS/catGS/cat, GS/balGS/bal, and SP/starSP/star we used our own, exact algorithms (see Theorems 4.6, 4.3 and 4.10). Inspecting Figure 3, we see that outer diversity of SP/starSP/star and GS/catGS/cat seem to approach 11 and 1/2 12, respectively, whereas outer diversity of SCSC, SPSP, and GS/balGS/bal might be approaching 00. In this section we confirm these limit values theoretically (except for SPSP, for which we do not yet have sufficiently good theoretical understanding), describe our exact algorithms, and provide some additional results We first consider the case of SCSC. Faliszewski et al. [2026b] have shown that for every family of domains, with one domain for each number of candidates, whose sizes are bounded by a constant, the outer diversity of these domains tends to 00 as the number of candidates increases. We extend this result to domains of polynomial size. Since every SCSC domain over m candidates contains at most O(m2)O(m^2) votes, this means that outer diversity of SCSC domains tends to 00.55 5 Interestingly, this also applies to so-called Euclidean domains of a fixed dimension. In such domains each candidate and each voter is represented as a point in ℝdR^d, where d is some constant. A voter ranks the candidates with respect to their nondecreasing distance from his or her point. Each such domain contains O(m2d)O(m^2d) votes. Theorem 4.1. Let us fix a polynomial P(m)P(m) and let D2D_2, D3D_3, … be a sequence of domains, where each DmD_m contains at most P(m)P(m) rankings over m candidates. Then limm→∞out-div(Dm)=0 _m→∞out -div(D_m)=0. Corollary 4.2. For every m∈ℕm , let SCmSC_m be a single-crossing domain over m candidates. Then limm→∞out-div(SCm)=0 _m→∞out -div(SC_m)=0. Next, we move to the case of GSGS. In Theorem 4.3, we show how to efficiently compute the outer diversity of any GSGS domain specified by a binary tree. The algorithm aggregates votes according to the positions of one child block at each node, computes the corresponding local contribution, and combines it with the contributions of the two subtrees in a bottom-up way. Theorem 4.3. For any domain GS(T)GS(T) over m candidates, where T is a given binary tree, there exists an O(m4)O(m^4)-time algorithm that computes out-div(GS(T))out -div(GS(T)). Proof sketch of Theorem 4.3. We defer the full formal proof to the appendix and describe here the main idea. To compute out-div(GS(T))out -div(GS(T)), where T is labeled with candidate set C and |C|=m|C|=m, it is enough to compute the sum of swap distances from all votes from ℒ(C)L(C) to the domain GS(T)GS(T). We first consider the distance from a fixed vote u∈ℒ(C)u∈L(C) to GS(T)GS(T). We argue that this distance decomposes over the nodes of the tree. For an internal node x, the local cost of u at x is the cost of arranging the two child blocks in one of the two admissible orders, while the remaining cost is paid independently inside the two subtrees. In Lemma A.1 we show that, if the left child of x contains t candidates, then this local cost depends only on the sum of the positions occupied in u by these t candidates. Thus, when summing over all votes, we do not need to consider all m!m! votes separately: we can group together votes with the same value of this position sum. By grouping votes in this way, Lemma A.2 gives an aggregated local contribution F(x)F(x) for each node x. To compute these aggregated contributions, we use a dynamic-programming table A(m,t,s)A(m,t,s). The value A(m,t,s)A(m,t,s) counts the number of sets of t positions among 1,…,m\1,…,m\ whose indices sum to s. For each such set of positions, the candidates inside the two child blocks can be permuted independently. Hence A(m,t,s)A(m,t,s) lets us count how many votes have each type, and therefore compute the value F(x)F(x) without iterating over all votes. Once all local contributions are known, we process the tree bottom-up. At every internal node, the total value for the subtree is obtained by adding the local contribution F(x)F(x) and appropriately scaled contributions of the two children. This recurrence is presented in Lemma A.3. Finally, the table A has O(m4)O(m^4) states, since the sum parameter is bounded by O(m2)O(m^2). All remaining computations, including the computation of all values F(x)F(x) and the bottom-up computation of the subtree values, are dominated by this dynamic program. Hence out-div(GS(T))out -div(GS(T)) can be computed in time O(m4)O(m^4). ∎ It turns out that there is a simple modification of the above algorithm so that instead of computing outer diversity of a GSGS domain specified by a given binary tree T, it computes the tree that leads to either the highest or the lowest outer diversity (see Theorem 4.5). The idea is to choose the optimal split at the root. If the two subtrees have sizes a and m−am-a, then the contribution of the root depends only on this split, while the two subtrees can be optimized independently. Thus, we compute optimal trees of sizes 1,2,…,m1,2,…,m in increasing order: for each size, we try all possible splits at the root and combine the best already-computed subtrees. The same dynamic program can be used for both maximizing and minimizing the outer diversity. Using this algorithm, we extend Finding 3.3: Finding 4.4. GS/catGS/cat and GS/balGS/bal have, respectively, the highest and the lowest outer diversity among GSGS domains with up to 100100 candidates. Theorem 4.5. Let mT_m denote the family of all binary trees with m leaves. There exists an O(m4)O(m^4)-time algorithm that finds a tree in argmaxT∈mout-div(GS(T)) _T _mout -div(GS(T)). Moreover, the same approach can be used to find a tree in argminT∈mout-div(GS(T)) _T _mout -div(GS(T)). Further, using the approach from Theorem 4.3, we also obtain an exact, closed formula for outer diversity of GS/catGS/cat. Namely, we apply the algorithm to the caterpillar tree, which yields a recurrence that we solve explicitly. On the one hand, using this formula, we can compute outer diversity of GS/catGS/cat in O(m)O(m) time, much faster than using Theorem 4.3, and, on the other hand, we see that in the limit it approaches 1/2 12. This extends the result of Faliszewski et al. [2026b], who established that 1/2 12 is a lower bound on the outer diversity of GS/catGS/cat. To be formally correct, we use GS/catmGS/cat_m to denote the GS/catGS/cat domain over m candidates (we use the same convention for GS/balGS/bal, SPSP, and SP/starSP/star). Theorem 4.6. For every m≥2m≥ 2, it holds that out-div(GS/catm)=12+1m−1−1(m−1)m⋅(Hm−12H⌊m/2⌋), out -div(GS/cat_m)= 12+ 1m-1- 1(m-1)m· (H_m- 12H_ m/2 ), where Hm=∑i=1m1/iH_m= _i=1^m1/i is the m-th harmonic number. Corollary 4.7. It holds that limm→∞out-div(GS/catm)=12 _m→∞out -div(GS/cat_m)= 12. The case of GS/balGS/bal is more complicated and there does not seem to be an easy way of applying Theorem 4.3 to obtain an exact formula for outer diversity. Nonetheless, a somewhat involved proof leads to an asymptotic formula and the limit value. Theorem 4.8. For a GS/balGS/bal domain over m candidates we have out-div(GS/bal)=O(1/m)out -div(GS/bal)=O(1/ m). Corollary 4.9. It holds that limm→∞out-div(GS/balm)=0 _m→∞out -div(GS/bal_m)=0. In Figure 3, we see that for sufficiently many candidates, outer diversity of SPSP is lower than that of GS/balGS/bal. This reinforces our belief that limm→∞out-div(SPm)=0 _m→∞out -div(SP_m)=0, albeit a proof is still missing. Another interesting consequence of Corollaries 4.7 and 4.9 is that if GS/catGS/cat indeed has the highest outer diversity among Condorcet domains with a given number of candidates, then as we considered larger and larger candidate sets, Condorcet domains would achieve outer diversity values between 00 and 1/2 12. In fact, we would even expect outer diversity values to be placed densely in between 00 and 1/2 12. To see this, consider, e.g., GSGS domains based on a tree where some fraction of candidates forms a balanced tree, with one leaf replaced by a caterpillar tree over the remaining candidates. Such domains would have outer diversity values between 00 and 1/2 12. We conclude this section by considering SP/starSP/star, our representative of SP/TSP/T domains (and, more broadly, a representative of weak Condorcet domains). This domain is very close to the general one. Indeed, if c is the candidate placed in the center of the star graph, then SP/starSP/star includes all votes that rank c either first or second. Consequently, we have the following results. Theorem 4.10. It holds that out-div(SP/starm)=1−2/m+4/m2out -div(SP/star_m)=1-2/m+4/m^2. Corollary 4.11. It holds that limm→∞out-div(SP/starm)=1 _m→∞out -div(SP/star_m)=1. While these results are not surprising on their own, they are quite interesting in the context of the preceding discussion: For weak Condorcet domains, the range of outer diversity values is from 00 to 11. Using an analogous meta-argument as for the case of GSGS, but for star graphs with one leaf replaced by a path, we expect these values to be placed densely in this interval. 5 Conclusions Our main conclusion is that outer diversity provides valuable insights into the nature of Condorcet domains. In particular, there seems to be a strong correlation between the number of never-middle conditions satisfied by a domain and its outer diversity. On the other hand, domain size is only weakly correlated with outer diversity. Our results strongly suggest that the group-separable/caterpillar domain has the highest outer diversity value among Condorcet domains. Somewhat weaker arguments suggest that Black’s single-peaked domain has the highest outer diversity value among Arrow’s single-peaked ones. Finally, we observed some radical differences between Condorcet and weak Condorcet domains. For example, there are weak Condorcet domains whose outer diversity approaches 11—namely the SP on a star graph domain—whereas we do not believe that Condorcet domains with such high values exist (albeit we did not establish this formally). Acknowledgments Tomasz Wąs was supported by UK Engineering and Physical Sciences Research Council (EPSRC) under grant EP/X038548/1. Piotr Faliszewski and Krzysztof Sornat were supported by NCN project AGREE (UMO-2025/58/A/ST6/00371). During its early stages, this project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854). References Akello-Egwel et al. [2025] D. Akello-Egwel, C. Leedham-Green, A. Litterick, K. Markström, and S. Riis. Condorcet domains on at most seven alternatives. Mathematical Social Sciences, 133:23–33, 2025. Ammann and Puppe [2025] M. Ammann and C. Puppe. Preference diversity. Review of Economic Design, 2025. Online First. Arrow [1963] K. Arrow. Social Choice and Individual Values. John Wiley and Sons, 1963. Originally published in 1951. Black [1958] D. Black. The Theory of Committees and Elections. Cambridge University Press, 1958. Danilov et al. [2012] V. Danilov, A. Karzanov, and G Koshevoy. Condorcet domains of tiling type. Discrete Applied Mathematics, 160(7–8):933–940, 2012. Demange [1982] G. Demange. Single-peaked orders on a tree. Mathematical Social Sciences, 3(4):389–396, 1982. Elkind et al. [2022] E. Elkind, M. Lackner, and D. Peters. Preference restrictions in computational social choice: A survey. Technical Report arXiv.2205.09092 [cs.GT], arXiv.org, 2022. Faliszewski et al. [2014] P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra. The complexity of manipulative attacks in nearly single-peaked electorates. Artificial Intelligence, 207:69–99, 2014. Faliszewski et al. [2022] P. Faliszewski, A. Karpov, and S. Obraztsova. The complexity of election problems with group-separable preferences. Autonomous Agents and Multi-Agent Systems, 36(1):18, 2022. Faliszewski et al. [2025] P. Faliszewski, P. Skowron, A. Slinko, K. Sornat, S. Szufa, and N. Talmon. How similar are two elections? Journal of Computer and System Sciences, 150:103632, 2025. Faliszewski et al. [2026a] P. Faliszewski, K. Sornat, S. Szufa, and T. Wąs. Diversity of structured domains via k-Kemeny scores. In Proceedings of AAAI-2026, 2026a. Faliszewski et al. [2026b] P. Faliszewski, K. Sornat, S. Szufa, and T. Wąs. Outer diversity of structured domains. In Proceedings of AAMAS-2026, 2026b. See arXiv:2602.15708 [cs.GT]. Fishburn [1996] P. Fishburn. Acyclic sets of linear orders. Social Choice and Welfare, 14:113–124, 1996. Galambos and Reiner [2008] A. Galambos and V. Reiner. Acyclic sets of linear orders via the bruhat orders. Social Choice and Welfare, 30(2):245–264, 2008. Inada [1964] K. Inada. A note on the simple majority decision rule. Econometrica, 32(32):525–531, 1964. Inada [1969] K. Inada. The simple majority decision rule. Econometrica, 37(3):490–506, 1969. Karpov [2019] A. Karpov. On the number of group-separable preference profiles. Group Decision and Negotiation, 28(3):501–517, 2019. Karpov and Slinko [2023] A. Karpov and A. Slinko. Constructing large peak-pit Condorcet domains. Theory and Decision, 94:97–120, 2023. Karpov et al. [2024] A. Karpov, K. Markström, S. Riis, and B. Zhou. Local diversity of Condorcet domains. Technical Report arXiv:2401.11912 [econ.TH], arXiv.org, May 2024. Leedham-Green et al. [2024] C. Leedham-Green, K. Markström, and S. Riis. The largest Condorcet domain on 8 alternatives. Social Choice and Welfare, 62(1):109–116, 2024. Mirrlees [1971] J. Mirrlees. An exploration in the theory of optimal income taxation. Review of Economic Studies, 38:175–208, 1971. Monjardet [2009] B. Monjardet. Acyclic domains of linear orders: A survey. In S. Brams, W. Gehrlein, and F. Roberts, editors, The Mathematics of Preference, Choice and Order: Essays in Honor of Peter C. Fishburn, pages 139–160. Springer Berlin Heidelberg, 2009. Nehring and Puppe [2002] K. Nehring and C. Puppe. A theory of diversity. Econometrica, 70(3):1155–1198, 2002. Peters et al. [2022] D. Peters, L. Yu, H. Chan, and E. Elkind. Preferences single-peaked on a tree: Multiwinner elections and structural results. Journal of Artificial Intelligence Research, 73:231–276, 2022. Puppe and Slinko [2024] C. Puppe and A. Slinko. Maximal Condorcet domains. A further progress report. Games and Economic Behavior, 145:426–450, 2024. Puppe and Slinko [2026] C. Puppe and A. Slinko. Condorcet Domains: The Mathematics of Coherent Collective Decision-Making. Studies in Choice and Welfare. Springer, 2026. URL https://books.google.pl/books?id=NUe20QEACAAJ. Roberts [1977] K. Roberts. Voting over income tax schedules. Journal of Public Economics, 8(3):329–340, 1977. Sen [1966] A. Sen. A possibility theorem on majority decisions. Econometrica, 34(2):491–499, 1966. Slinko [2019] A. Slinko. Condorcet domains satisfying Arrow’s single-peakedness. Journal of Mathematical Economics, 84:166–175, 2019. Szufa et al. [2025] S. Szufa, N. Boehmer, R. Bredereck, P. Faliszewski, R. Niedermeier, P. Skowron, A. Slinko, and N. Talmon. Drawing a map of elections. Artificial Intelligence, 343:104332, 2025. Appendix A Missing Proofs A.1 Proof of Theorem 3.4 Consider candidate set C=c1,…,cmC=\c_1,…,c_m\. First, we construct a swap graph, where each node is associated with a vote: Starting from vote u:c1≻c2≻⋯≻cmu c_1 c_2 ·s c_m, we generate all votes that can be obtained by swapping pairs of adjacent candidates cj,cj+1c_j,c_j+1, where cjc_j is ranked before cj+1c_j+1. This produces a directed acyclic graph (DAG) whose nodes are votes and whose edges correspond to such swaps (directed toward the vote with larger swap distance from u). This DAG has exactly m!m! nodes and O(m⋅m!)O(m· m!) edges. A single-crossing domain corresponds to a maximal chain in this DAG. For each node v in this DAG, we compute the number of maximal chains starting at v, denoted f(v)f(v). If v is the (unique) sink, then f(v)=1f(v)=1. Otherwise, f(v)=∑wf(w)f(v)= _wf(w), where the sum ranges over the direct successors of v. Since each node has at most m−1m-1 successors and there are m!m! nodes, this phase runs in O(m⋅m!)O(m· m!) time. Finally, to sample a domain, we start from the top node, vote u, and at each step select a direct successor w with probability f(w)/f(v)f(w)/f(v), then continue from w until the sink is reached. The resulting path has length (m2) m2, and each step considers at most m−1m-1 successors, so sampling runs in O(m3)O(m^3) time. Sampling proportionally to the counts ensures that every maximal chain, i.e., single-crossing domain, is reached with equal probability. A.2 Proof of Theorem 4.1 Fix an arbitrary polynomial P(m)P(m) and the sequence of domains D2D_2, D3D_3, …, where each DmD_m contains at most P(m)P(m) rankings over m candidates C. Let k be the largest power in P(m)P(m), then |Dm|=Θ(mk)|D_m|= (m^k). We assume that k>0k>0 and |Dm|>2|D_m|>2, as the case of k=0k=0, i.e., constant number of votes in a domain, was already considered in [Faliszewski et al., 2026b]. Let us also denote dmax=(m2)d_ = m2, for convenience. Let πm:ℒ(C)→Dm _m:L(C)→ D_m be a function that assigns every vote u∈ℒ(C)u (C) a vote from the domain DmD_m in a way that minimizes the swap distance, i.e., swap(u,πm(u))=minv∈Dmswap(u,v).swap(u, _m(u))= _v∈ D_mswap(u,v). Then, we can write ansdansd of DmD_m in terms of votes from ℒ(C)L(C) assigned to each vote in DmD_m, i.e., ansd(Dm)=∑u∈ℒ(C)minv∈Dmswap(u,v)m!⋅dmax=∑v∈Dm∑u∈πm−1(v)swap(u,v)m!⋅dmax.ansd(D_m)= _u (C) _v∈ D_mswap(u,v)m!· d_ = _v∈ D_m _u∈π^-1_m(v)swap(u,v)m!· d_ . Let Mm,0,Mm,1,…,Mm,dmaxM_m,0,M_m,1,…,M_m,d_ be so called Mahonian numbers where each Mm,iM_m,i counts the number of votes in ℒ(C)L(C) that are at swap distance i from a fixed vote v.66 6 See, e.g., https://oeis.org/A008302. For a number t∈ℕt , let ℓ(t) (t) be a maximum integer such that ∑i=0ℓ(t)Mm,i≤t _i=0 (t)M_m,i≤ t. Also, let F(t)F(t) be the minimum sum of swap distances from a set of t pairwise distinct votes to a fixed vote v, i.e., F(t)=∑i=0ℓ(t)i⋅Mm,i+(t−∑i=0ℓ(t)Mm,i)⋅(ℓ(t)+1).F(t)= _i=0 (t)i· M_m,i+ (t- _i=0 (t)M_m,i )·( (t)+1). Then, since all votes in πm−1(v)π^-1_m(v) for each v∈Dmv∈ D_m are pairwise distinct, we get that ansd(Dm)≥∑v∈DmF(|πm−1(v)|)m!⋅dmax.ansd(D_m)≥ _v∈ D_mF(|π^-1_m(v)|)m!· d_ . Observe that the value of the above term is minimized, if the sets πm−1(v)π^-1_m(v) for different votes v∈Dmv∈ D_m have as similar sizes as possible, i.e., each vote from the domain DmD_m is assigned an (almost) equal number of votes from ℒ(C)L(C). Hence, we can provide its lower bound by exchanging F(|πm−1(v)|)F(|π^-1_m(v)|) for F(⌊m!/|Dm|⌋)F( m!/|D_m| ), which yields ansd(Dm) ansd(D_m) ≥∑v∈DmF(⌊m!/|Dm|⌋)m!⋅dmax ≥ _v∈ D_mF( m!/|D_m| )m!· d_ =|Dm|m!⋅⌊m!|Dm|⌋⋅1dmax⋅F(⌊m!/|Dm|⌋)⌊m!/|Dm|⌋ = |D_m|m!· m!|D_m| · 1d_ · F( m!/|D_m| ) m!/|D_m| ≥|Dm|m!⋅(m!|Dm|−1)⋅1dmax⋅F(⌊m!/|Dm|⌋)⌊m!/|Dm|⌋ ≥ |D_m|m!· ( m!|D_m|-1 )· 1d_ · F( m!/|D_m| ) m!/|D_m| =(1−Θ(mk)m!)⋅1dmax⋅F(⌊m!/|Dm|⌋)⌊m!/|Dm|⌋. = (1- (m^k)m! )· 1d_ · F( m!/|D_m| ) m!/|D_m| . (1) Now, let V be an arbitrary set of ⌊m!/|Dm|⌋ m!/|D_m| closest votes from ℒ(C)L(C) to a given fixed vote v. Also, let x be a vote chosen uniformly at random from ℒ(C)L(C). Then, observe that we can express F(⌊m!/|Dm|⌋)/⌊m!/|Dm|⌋F( m!/|D_m| )/ m!/|D_m| in terms of expected swap distance between x and v conditioned on the fact that x belongs to V, i.e., F(⌊m!/|Dm|⌋)⌊m!/|Dm|⌋=(swap(x,v)|x∈V). F( m!/|D_m| ) m!/|D_m| =E(swap(x,v)|x∈ V). Next, let us denote ℓm≔ℓ(⌊m!/|Dm|⌋) _m ( m!/|D_m| ) and observe that (swap(x,v)|x∈V)≥(swap(x,v)|swap(x,v)≤ℓm),E(swap(x,v)|x∈ V) (swap(x,v)|swap(x,v)≤ _m), as the set x∈ℒ(C):swap(x,v)≤ℓm\x (C):swap(x,v)≤ _m\ is a subset of V, and the expected value can only decrease as we remove the votes from V with the highest swap distance to v. Combining this with Inequality (1), we obtain ansd(Dm)≥(1−Θ(mk)m!)⋅1dmax⋅(swap(x,v)|swap(x,v)≤ℓm).ansd(D_m)≥ (1- (m^k)m! )· 1d_ ·E(swap(x,v)|swap(x,v)≤ _m). (2) In order to bound the expected conditional distance, we will first look at the asymptotics of ℓm _m. To this end, we will use the Lehmer code and the Hoeffding’s inequality. First, however, let us show that ℓm<dmax/2. _m<d_ /2. (3) Assume otherwise, i.e., ℓm≥dmax/2 _m≥ d_ /2. We use that fact that the Mahonian numbers are symmetric, i.e., Mm,i=Mm,dmax−iM_m,i=M_m,d_ -i for each i∈0,1,…,dmaxi∈\0,1,…,d_ \. This implies that ∑i=0ℓmMm,i≥12∑i=0dmaxMm,i=m!2. _i=0 _mM_m,i≥ 12 _i=0^d_ M_m,i= m!2. On the other hand, from the definition of ℓm _m, ∑i=0ℓmMm,i≤⌊m!|Dm|⌋≤m!|Dm|. _i=0 _mM_m,i≤ m!|D_m| ≤ m!|D_m|. Combining both inequalities together, we get that |Dm|≤2|D_m|≤ 2, which contradicts our assumption. Thus, Inequality (3) holds. Now, let us denote the linear order in vote v by v:c1≻c2≻⋯≻cmv:c_1 c_2 … c_m. The Lehmer code of vote x∈ℒ(C)x (C) with respect to the reference vote v is a sequence (σ(x,v,1),σ(x,v,2),…,σ(x,v,m))(σ(x,v,1),σ(x,v,2),…,σ(x,v,m)) in which σ(x,v,i)σ(x,v,i) denotes the number of candidates ranked by v below cic_i which x ranks above cic_i, i.e., σ(x,v,i)=|cj∈C:ci≻vcj∧cj≻xci|.σ(x,v,i)=|\c_j∈ C:c_i _vc_j c_j _xc_i\|. The Lehmer code has three properties that are important for us. First, it holds that the sum of Lehmer codes is equal to the swap distance, i.e., swap(x,v)=∑i=1mσ(x,v,i).swap(x,v)= _i=1^mσ(x,v,i). Second, for every i∈[m]i∈[m], it holds that σ(x,v,i)∈0,1,…,m−iσ(x,v,i)∈\0,1,…,m-i\. Third, every sequence (s1,s2,…,sm)(s_1,s_2,…,s_m) such that si∈0,1,…,m−is_i∈\0,1,…,m-i\ uniquely determines vote x such that (σ(x,v,i))i∈[m]=(si)i∈[m](σ(x,v,i))_i∈[m]=(s_i)_i∈[m]. Thus, in order to pick x from ℒ(C)L(C) uniformly at random we can alternatively pick its Lehmer code uniformly at random. In other words, we can express a random variable swap(x,v)swap(x,v) as a sum of m independent random variables σ(x,v,1),…,σ(x,v,m)σ(x,v,1),…,σ(x,v,m), where for each i∈[m]i∈[m] we have that σ(x,v,i)σ(x,v,i) follows a uniform distribution from the set 0,1,…,m−i\0,1,…,m-i\. This allows us to use the Hoeffding’s inequality, which in general says (in its lower tail version) that for independent random variables X1,…,XnX_1,…,X_n such that each XiX_i takes values from [ai,bi][a_i,b_i] and t≥0t≥ 0 it holds that ℙ(∑i∈[n](Xi)−(∑i∈[n]Xi)≤−t)≤exp(−2t2∑i∈[n](bi−ai)2). ( _i∈[n](X_i)-E ( _i∈[n]X_i )≤-t )≤ (- 2t^2 _i∈[n](b_i-a_i)^2 ). By applying it to our setting and taking t=(swap(x,v))−(ℓm+1)=dmax/2−(ℓm+1)t=E(swap(x,v))-( _m+1)=d_ /2-( _m+1), for which we have t≥0t≥ 0 by Inequality (3), we obtain ℙ(swap(x,v)−dmax/2≤(ℓm+1)−dmax/2)≤exp(−2(ℓm+1−dmax/2)2∑i∈[m](m−i)2). (swap(x,v)-d_ /2≤( _m+1)-d_ /2 )≤ (- 2( _m+1-d_ /2)^2 _i∈[m](m-i)^2 ). Clearly, ℙ(swap(x,v)−dmax/2≤(ℓm+1)−dmax/2)=ℙ(swap(x,v)≤ℓm+1),P (swap(x,v)-d_ /2≤( _m+1)-d_ /2 )=P(swap(x,v)≤ _m+1), thus we get ℙ(swap(x,v)≤ℓm+1)≤exp(−2(dmax/2−(ℓm+1))2∑i∈[m](m−i)2). (swap(x,v)≤ _m+1 )≤ (- 2(d_ /2-( _m+1))^2 _i∈[m](m-i)^2 ). On the other hand, observe that ℙ(swap(x,v)≤ℓm+1)=1m!∑i=0ℓm+1Mm,i≥1m!⋅m!|Dm|=1|Dm|=Θ(m−k),P (swap(x,v)≤ _m+1 )= 1m! _i=0 _m+1M_m,i≥ 1m!· m!|D_m|= 1|D_m|= (m^-k), (4) where the inequality comes from the fact that by definition ℓm _m is the largest natural number such that ∑i=0ℓmMm,i≤⌊m!/|Dm|⌋ _i=0 _mM_m,i≤ m!/|D_m| , hence if we extend the sum to ℓm+1 _m+1 it will exceed m!/|Dm|m!/|D_m|, as Mm,i>1M_m,i>1 for i>0i>0. Thus, we get Θ(m−k)≤ℙ(swap(x,v)≤ℓm+1)≤exp(−2(dmax/2−(ℓm+1))2∑i∈[m](m−i)2). (m^-k) (swap(x,v)≤ _m+1 )≤ (- 2(d_ /2-( _m+1))^2 _i∈[m](m-i)^2 ). On each side of the above inequality let us take the natural logarithm and multiply by −1-1, then we obtain Θ(klog(m))≥2(dmax/2−(ℓm+1))2∑i∈[m](m−i)2. (k (m))≥ 2(d_ /2-( _m+1))^2 _i∈[m](m-i)^2. Since k is a constant, we can remove it from the Θ notation, as well as constant 22 from the right hand side. Then, Θ(log(m))⋅∑i∈[m](m−i)2≥(dmax/2−(ℓm+1))2. ( (m))· _i∈[m](m-i)^2≥(d_ /2-( _m+1))^2. By the fact that ∑i∈[m](m−i)2=(m−1)m(2m−1)/6 _i∈[m](m-i)^2=(m-1)m(2m-1)/6, we get Θ(m3log(m))≥(dmax/2−(ℓm+1))2. (m^3 (m))≥(d_ /2-( _m+1))^2. Since we know that dmax/2−(ℓm+1)≥0d_ /2-( _m+1)≥ 0 (by Inequality (3)), we can take the square root to obtain Θ(m3/2log(m))≥dmax/2−(ℓm+1). (m^3/2 (m) )≥ d_ /2-( _m+1). And from this we obtain the asymptotic bound on ℓm _m that is ℓm≥dmax/2−O(m3/2log(m)). _m≥ d_ /2-O (m^3/2 (m) ). (5) Now, observe that we could repeat our reasoning for an arbitrary sequence of domains DmκD^κ_m of size |Dmκ|=mκ|D^κ_m|=m^κ and obtain bounds analogous to (4) and (5) for different ℓκ≔ℓ(⌊m!/|D|⌋) ^κ ( m!/|D| ). Let k′∈ℕk be a smallest integer such that k′≥2k ≥ 2k and ℓ′≔ℓk′<ℓm ^k < _m, and k′∈ℕk be a smallest integer such that k′≥2k′k ≥ 2k and ℓ′≔ℓk′<ℓ′ ^k < , Then, ℓ′≥dmax/2−O(m3/2log(m))andℙ(swap(x,v)≤ℓ′+1)≥Θ(m−k′). ≥ d_ /2-O (m^3/2 (m) ) and (swap(x,v)≤ +1 )≥ (m^-k ). Finally, observe that by definition of ℓ(t) (t), we obtain ℙ(swap(x,v)≤ℓ′)=1m!∑i=0ℓ′Mm,i≤1m!⋅⌊m!|Dmk′|⌋≤1|Dmk′|=Θ(m−k′).P (swap(x,v)≤ )= 1m! _i=0 M_m,i≤ 1m!· m!|D^k _m| ≤ 1|D^k _m|= (m^-k ). Then, from Inequality (2) we obtain ansd(Dm) ansd(D_m) ≥1dmax⋅(swap(x,v)|swap(x,v)≤ℓm)(1−Θ(mk)m!) ≥ 1d_ ·E(swap(x,v)|swap(x,v)≤ _m) (1- (m^k)m! ) ≥ℓ′+1dmaxℙ(swap(x,v)≥ℓ′+1|swap(x,v)≤ℓm)(1−Θ(mk)m!) ≥ +1d_ P(swap(x,v)≥ +1|swap(x,v)≤ _m) (1- (m^k)m! ) ≥ℓ′+1dmaxℙ(swap(x,v)≥ℓ′+1|swap(x,v)≤ℓ′+1)(1−Θ(mk)m!) ≥ +1d_ P(swap(x,v)≥ +1|swap(x,v)≤ +1) (1- (m^k)m! ) =ℓ′+1dmax(1−ℙ(swap(x,v)≤ℓ′+1|swap(x,v)≤ℓ′+1))(1−Θ(mk)m!) = +1d_ (1-P(swap(x,v)≤ +1|swap(x,v)≤ +1) ) (1- (m^k)m! ) =ℓ′+1dmax(1−ℙ(swap(x,v)≤ℓ′+1)ℙ(swap(x,v)≤ℓ′+1))(1−Θ(mk)m!) = +1d_ (1- P(swap(x,v)≤ +1)P(swap(x,v)≤ +1) ) (1- (m^k)m! ) ≥dmax/2−O(m3/2log(m))dmax(1−Θ(m−k′)Θ(m−k′))(1−Θ(mk)m!) ≥ d_ /2-O (m^3/2 (m) )d_ (1- (m^-k ) (m^-k ) ) (1- (m^k)m! ) =12(1−O(log(m)/m))(1−Θ(m−(k′−k′)))(1−Θ(mk)m!). = 12 (1-O ( (m)/m ) ) (1- (m^-(k -k ) ) ) (1- (m^k)m! ). Therefore, limm→∞ansd(Dm)≥12. _m→∞ansd(D_m)≥ 12. Since ansdansd can never be greater than half, we get that limm→∞ansd(Dm)=12, _m→∞ansd(D_m)= 12, which concludes the proof. A.3 Proof of Theorem 4.3 Let C=c1,c2,…,cmC=\c_1,c_2,…,c_m\ be the set of candidates and let TxT_x denote the subtree rooted at a node x of T. For each node x, let CxC_x be the set of candidates labeling the leaves of TxT_x. Let us define S(x)≔∑u∈ℒ(Cx)swap(u,GS(Tx))S(x) _u∈L(C_x)swap(u,GS(T_x)). From the definitions of ansd(⋅)ansd(·) and out-div(⋅)out -div(·), and since Cρ=C_ρ=C for the root ρ of T, we have: out-div(GS(T))=1−2⋅∑u∈ℒ(C)swap(u,GS(T))(m2)⋅m!=1−2⋅S(ρ)(m2)⋅m!. out -div(GS(T))=1- 2· _u∈L(C)swap(u,GS(T)) m2· m!=1- 2· S(ρ) m2· m!. (6) Therefore, in order to prove the theorem statement it suffices to compute S(ρ)S(ρ) in time O(m4)O(m^4). We start with an auxiliary dynamic programming table. Let us define a function A(m,t,s)A(m,t,s) which represents how many subsets of t positions from the set of positions 1,2,3,…,m\1,2,3,…,m\ achieve the sum of indices equal to s. Formally, A(m,t,s)≔|X⊆1,2,…,m:|X|=t,∑x∈Xx=s|.A(m,t,s) |\X \1,2,…,m\:|X|=t, _x∈ Xx=s\|. We can obtain this number using a basic recurrence formula based on the fact that either we use a subset of positions from 1,2,…,m−1\1,2,…,m-1\ or we add m to a subset of t−1t-1 positions; hence: A(m,t,s)=A(m−1,t,s)+A(m−1,t−1,s−m)A(m,t,s)=A(m-1,t,s)+A(m-1,t-1,s-m). Additionally we define boundary conditions: A(m,0,0)=1A(m,0,0)=1 for every m≥0m≥ 0 (since the empty set satisfies the condition), and A(m,t,s)=0A(m,t,s)=0 whenever m<0m<0, or t<0t<0, or s<0s<0. Let us now consider an arbitrary internal node x of T. Let ℓ and r be the left and right child of x, respectively. Let mx=|Cx|m_x=|C_x| and t=|Cℓ|t=|C_ |. For two disjoint sets of candidates X,Y⊆CxX,Y C_x and a vote u∈ℒ(Cx)u∈L(C_x), we write X≻uYX _uY if every candidate from X is ranked above every candidate from Y in u. We define a domain Dx≔u∈ℒ(Cx):Cℓ≻uCr or Cr≻uCℓD_x \u∈L(C_x):C_ _uC_r or C_r _uC_ \, i.e., DxD_x consists of all votes u such that either u ranks all candidates from CℓC_ before any candidate from CrC_r or u ranks all candidates from CrC_r before any candidate from CℓC_ . Since x is the root of TxT_x, every vote u∈GS(Tx)u∈GS(T_x) satisfies either Cℓ≻uCrC_ _uC_r or Cr≻uCℓC_r _uC_ . Hence, GS(Tx)⊆DxGS(T_x) D_x. For every vote u∈ℒ(Cx)u∈L(C_x), let sx(u)≔∑i=1tpis_x(u) _i=1^tp_i, where 1≤p1<p2<⋯<pt≤mx1≤ p_1<p_2<·s<p_t≤ m_x are the positions occupied in u by the candidates from CℓC_ . The following lemma (Lemma A.1) gives a closed formula for swap(u,Dx)swap(u,D_x), which we call the local cost of u at node x. Lemma A.1. For every u∈ℒ(Cx)u∈L(C_x), we have swap(u,Dx)=minsx(u)−t(t+1)2,t⋅(mx−t)+t(t+1)2−sx(u).swap(u,D_x)= \s_x(u)- t(t+1)2, t·(m_x-t)+ t(t+1)2-s_x(u) \. Proof of Lemma A.1. We fix u∈ℒ(Cx)u∈L(C_x). Let 1≤p1<p2<⋯<pt≤mx1≤ p_1<p_2<·s<p_t≤ m_x be the positions occupied in u by the candidates from CℓC_ . We observe that the minimum number of adjacent swaps required to transform u so that the candidates from CℓC_ occupy the first t positions equals ∑i=1t(pi−i)=sx(u)−t(t+1)2≕α _i=1^t(p_i-i)=s_x(u)- t(t+1)2 α. Indeed, this quantity is exactly the number of pairs (a,b)(a,b) such that a∉Cℓa∉ C_ , b∈Cℓb∈ C_ , and u:a≻bu a b (a is ranked higher than b in u). For the candidate from CℓC_ occupying position pip_i, there are exactly pi−ip_i-i such candidates above it, since among the first pi−1p_i-1 positions exactly i−1i-1 are occupied by candidates from CℓC_ . Each adjacent swap changes the number of such pairs by at most one, and the target arrangement is obtained exactly when no such pair remains. Hence the above quantity is the minimum number of adjacent swaps. Similarly, the minimum number of adjacent swaps required to transform u so that the candidates from CℓC_ occupy the last t positions equals ∑i=1t((mx−t+i)−pi)=t⋅(mx−t)+t(t+1)2−sx(u)≕β _i=1^t ((m_x-t+i)-p_i )=t·(m_x-t)+ t(t+1)2-s_x(u) β. Every transformation of u into a vote from DxD_x must make the candidates from CℓC_ occupy either the first t positions or the last t positions. Hence swap(u,Dx)≥minα,βswap(u,D_x)≥ \α,β\. This minimum is also enough to transform u into a vote from DxD_x, so swap(u,Dx)≤minα,βswap(u,D_x)≤ \α,β\. This finishes the proof of Lemma A.1. ∎ Let F(x)F(x) denote the sum of the local costs of all votes from ℒ(Cx)L(C_x) at node x, i.e., F(x)≔∑u∈ℒ(Cx)swap(u,Dx)F(x) _u∈L(C_x)swap(u,D_x). The following lemma (Lemma A.2) shows that we can compute F(x)F(x) more efficiently than by summing swap(u,Dx)swap(u,D_x) over all votes from ℒ(Cx)L(C_x) one by one. Instead, we group together all votes for which the candidates from CℓC_ occupy sets of positions with the same sum s, and count how many such votes there are. We define fx(s)≔mins−t(t+1)2,t⋅(mx−t)+t(t+1)2−sf_x(s) \s- t(t+1)2, t·(m_x-t)+ t(t+1)2-s\. Lemma A.2. We have F(x)=∑sfx(s)⋅A(mx,t,s)⋅t!⋅(mx−t)!F(x)= _sf_x(s)· A(m_x,t,s)· t!·(m_x-t)!. Proof of Lemma A.2. For a fixed value of s, there are exactly A(mx,t,s)A(m_x,t,s) sets of t positions in 1,2,…,mx\1,2,…,m_x\ whose indices sum to s. For each such set of positions, the candidates from CℓC_ can be arranged within these positions in t!t! ways, and the candidates from CrC_r can be arranged in the remaining mx−tm_x-t positions in (mx−t)!(m_x-t)! ways. Hence, the number of votes u∈ℒ(Cx)u∈L(C_x) for which the candidates from CℓC_ occupy a set of positions whose indices sum to s is equal to A(mx,t,s)⋅t!⋅(mx−t)!A(m_x,t,s)· t!·(m_x-t)!. By Lemma A.1, for each such vote u, swap(u,Dx)=fx(s)swap(u,D_x)=f_x(s). Summing over all values of s, we obtain F(x)=∑sfx(s)⋅A(mx,t,s)⋅t!⋅(mx−t)!F(x)= _sf_x(s)· A(m_x,t,s)· t!·(m_x-t)!. Note that only values of s in the range t(t+1)2≤s≤mxt−t(t−1)2 t(t+1)2≤ s≤ m_xt- t(t-1)2 contribute nonzero terms. This finishes the proof of Lemma A.2. ∎ For a vote u∈ℒ(Cx)u∈L(C_x) and a set X⊆CxX C_x, let u|Xu|_X denote the restriction of u to X, i.e., the unique vote in ℒ(X)L(X) such that, a≻u|Xb⇔a≻uba _u|_Xb a _ub for every a,b∈Xa,b∈ X. The following lemma gives a recurrence formula for computing S(x)S(x). Lemma A.3. Let x be a node of T. If x is a leaf, then S(x)=0S(x)=0. If x is an internal node with children ℓ and r, then S(x)=F(x)+(mxt)⋅(mx−t)!⋅S(ℓ)+(mxmx−t)⋅t!⋅S(r).S(x)=F(x)+ m_xt·(m_x-t)!· S( )+ m_xm_x-t· t!· S(r). Proof of Lemma A.3. If x is a leaf, then |Cx|=1|C_x|=1, hence ℒ(Cx)L(C_x) consists of a single vote, which already belongs to GS(Tx)GS(T_x). Therefore, S(x)=0S(x)=0. Assume now that x is an internal node with children ℓ and r. Fix a vote u∈ℒ(Cx)u∈L(C_x). Transforming u into a vote from GS(Tx)GS(T_x) is equivalent to performing three independent tasks: 1. arranging the two blocks CℓC_ and CrC_r so as to obtain a vote from DxD_x, 2. transforming u|Cℓu|_C_ into a vote from GS(Tℓ)GS(T_ ), 3. transforming u|Cru|_C_r into a vote from GS(Tr)GS(T_r). Indeed, every vote from GS(Tx)GS(T_x) satisfies these three conditions. Since the corresponding swaps concern disjoint pairs of candidates, their costs add up. Conversely, once we choose one of the two admissible orders of the blocks and arbitrary votes from GS(Tℓ)GS(T_ ) and GS(Tr)GS(T_r), they uniquely determine a vote from GS(Tx)GS(T_x). Therefore, swap(u,GS(Tx))=swap(u,Dx)+swap(u|Cℓ,GS(Tℓ))+swap(u|Cr,GS(Tr)). swap(u,GS(T_x))=swap(u,D_x)+swap(u|_C_ ,GS(T_ ))+swap(u|_C_r,GS(T_r)). (7) This allows us to calculate S(x)=∑u∈ℒ(Cx)swap(u,GS(Tx))S(x)= _u∈L(C_x)swap(u,GS(T_x)) by splitting swap(u,GS(Tx))swap(u,GS(T_x)) into 3 parts. The first part is ∑u∈ℒ(Cx)swap(u,Dx)=F(x) _u∈L(C_x)swap(u,D_x)=F(x) by the definition of F(x)F(x). For the second part, we group together all votes u∈ℒ(Cx)u∈L(C_x) that induce the same restriction u|Cℓu|_C_ . For every fixed vote w∈ℒ(Cℓ)w∈L(C_ ), the value swap(w,GS(Tℓ))swap(w,GS(T_ )) appears once for each vote u∈ℒ(Cx)u∈L(C_x) such that u|Cℓ=wu|_C_ =w. The number of such votes is exactly (mxt)⋅(mx−t)! m_xt·(m_x-t)!: we choose the t positions occupied by the candidates from CℓC_ , and then we place the candidates from CrC_r arbitrarily on the remaining positions. Therefore, using the definition of S(ℓ)S( ), we obtain ∑u∈ℒ(Cx)swap(u|Cℓ,GS(Tℓ)) _u∈L(C_x)swap(u|_C_ ,GS(T_ )) =(mxt)⋅(mx−t)!⋅∑w∈ℒ(Cℓ)swap(w,GS(Tℓ)). = m_xt·(m_x-t)!· _w∈L(C_ )swap(w,GS(T_ )). =(mxt)⋅(mx−t)!⋅S(ℓ). = m_xt·(m_x-t)!· S( ). Symmetrically, in the third part, we group together all votes u∈ℒ(Cx)u∈L(C_x) that induce the same restriction u|Cru|_C_r. By an analogous analysis, we obtain ∑u∈ℒ(Cx)swap(u|Cr,GS(Tr))=(mxmx−t)⋅t!⋅S(r) _u∈L(C_x)swap(u|_C_r,GS(T_r))= m_xm_x-t· t!· S(r). Combining the three contributions gives the required recurrence. ∎ It remains to estimate the running time. The values A(m,t,s)A(m,t,s) can be computed by dynamic programming (using the given recurrence). For each fixed m, the parameter t ranges from 00 to m, while the parameter s ranges up to O(m2)O(m^2), since it is the sum of t distinct numbers from 1,2,…,m\1,2,…,m\. Thus, the number of states of the table A is O(m4)O(m^4), and each state is computed in constant time from the recurrence. After precomputing factorials and binomial coefficients in O(m2)O(m^2) time, each value F(x)F(x) can be computed from Lemma A.2 by summing over all relevant values of s. Since the range of s has size O(mx2)O(m_x^2), this takes O(mx2)O(m_x^2) time for a fixed node x. Therefore, all values F(x)F(x) can be computed in O(m3)O(m^3) time in total. Finally, once all values F(x)F(x) are known, the values S(x)S(x) for all nodes x of the tree can be computed in linear time by processing the nodes bottom-up and applying Lemma A.3. Therefore, S(ρ)S(ρ) can be computed in time O(m4)O(m^4), and consequently out-div(GS(T))out -div(GS(T)) can also be computed in time O(m4)O(m^4). A.4 Proof of Theorem 4.5 For a tree T whose leaves are labeled by candidates from C, we write S(T)S(T) for the total swap distance from all votes in ℒ(C)L(C) to the domain GS(T)GS(T), that is, S(T)≔∑u∈ℒ(C)swap(u,GS(T)). S(T) _u∈L(C)swap(u,GS(T)). This is the same quantity as S(ρ)S(ρ) in the proof of Theorem 4.3, where ρ is the root of T. By (6), for every fixed m, maximizing out-div(GS(T))out -div(GS(T)) over mT_m is equivalent to minimizing S(T)S(T), and minimizing out-div(GS(T))out -div(GS(T)) is equivalent to maximizing S(T)S(T). We first describe how to minimize S(T)S(T) for a fixed number m of leaves. For that we define Mmin(a)≔minT∈aS(T). M_ (a) _T _aS(T). (8) In particular, any tree T∈mT _m achieving Mmin(m)M_ (m) minimizes S(T)S(T), and therefore maximizes out-div(GS(T))out -div(GS(T)). Fix a binary tree T and an internal node x of T. By Lemma A.3, once the sizes of the two subtrees of x are fixed, the local contribution of x to S(T)S(T) is independent of the shapes of these subtrees. More precisely, by Lemma A.2, this local contribution depends only on the number a of leaves below x and on the number of leaves t in the left subtree of x. Hence, for a∈2,3,…,ma∈\2,3,…,m\ and t∈1,2,…,a−1t∈\1,2,…,a-1\, we define F(a,t)F(a,t) as the value F(x)F(x) from Lemma A.2 at any node x with mx=am_x=a and |Cℓ|=t|C_ |=t. For a∈2,3,…,ma∈\2,3,…,m\ and t∈1,2,…,a−1t∈\1,2,…,a-1\, we define Mmin(a,t)≔F(a,t)+(at)⋅(a−t)!⋅Mmin(t)+(a−t)⋅t!⋅Mmin(a−t). M_ (a,t) F(a,t)+ at·(a-t)!· M_ (t)+ aa-t· t!· M_ (a-t). (9) In other words, Mmin(a,t)M_ (a,t) is the value of S(T)S(T) for a tree T whose root split has sizes t and a−ta-t, and whose two subtrees achieve Mmin(t)M_ (t) and Mmin(a−t)M_ (a-t), respectively. The next lemma shows that Mmin(a)M_ (a) is obtained by minimizing Mmin(a,t)M_ (a,t) over all possible root splits t. This recurrence will be used by the dynamic program. Lemma A.4. We have Mmin(1)=0M_ (1)=0 and, for every a≥2a≥ 2, Mmin(a)=min1≤t≤a−1Mmin(a,t). M_ (a)= _1≤ t≤ a-1M_ (a,t). (10) Proof of Lemma A.4. The base case Mmin(1)=0M_ (1)=0 is immediate. We prove the recurrence by two inequalities. First, for any fixed t∈1,2,…,a−1t∈\1,2,…,a-1\ take a tree Tt∈argminT∈tS(T)T_t∈ _T _tS(T) and a tree Ta−t∈argminT∈a−tS(T)T_a-t∈ _T _a-tS(T). We join them under a new root, with TtT_t as the left subtree and Ta−tT_a-t as the right subtree, and call the resulting tree Tt,a−tT_t,a-t. By definition, S(Tt)=Mmin(t)S(T_t)=M_ (t) and S(Ta−t)=Mmin(a−t)S(T_a-t)=M_ (a-t), hence S(Tt,a−t) S(T_t,a-t) =Lemma A.3F(a,t)+(at)⋅(a−t)!⋅S(Tt)+(a−t)⋅t!⋅S(Ta−t) @crefcreftypecap~refnumlem:sx-recurrence=F(a,t)+ at·(a-t)!· S(T_t)+ aa-t· t!· S(T_a-t) =F(a,t)+(at)⋅(a−t)!⋅Mmin(t)+(a−t)⋅t!⋅Mmin(a−t) @crefcreftypecap~refnumlem:sx-recurrence=F(a,t)+ at·(a-t)!· M_ (t)+ aa-t· t!· M_ (a-t) =(9)Mmin(a,t). 12.0pt eq:def-m-min-a-t= 12.0ptM_ (a,t). (11) Since Tt,a−t∈aT_t,a-t _a for every t∈1,2,…,a−1t∈\1,2,…,a-1\, we have Mmin(a)≤S(Tt,a−t)=(11)Mmin(a,t)∀t∈1,2,…,a−1. M_ (a)≤ S(T_t,a-t) eq:s-of-t-split-to-t-and-a-minus-t=M_ (a,t) ∀ t∈\1,2,…,a-1\. Taking the minimum over all t∈1,2,…,a−1t∈\1,2,…,a-1\ gives the inequality Mmin(a)≤min1≤t≤a−1Mmin(a,t). M_ (a)≤ _1≤ t≤ a-1M_ (a,t). Conversely, let T∗∈argminT∈aS(T)T^*∈ _T _aS(T). Let the two subtrees of the root of T∗T^* be Tℓ∗T_ ^* and Tr∗T_r^*, and suppose that they have t∗t^* and a−t∗a-t^* leaves, respectively. Since S(Tℓ∗)≥Mmin(t∗)S(T_ ^*)≥ M_ (t^*) and S(Tr∗)≥Mmin(a−t∗)S(T_r^*)≥ M_ (a-t^*), we have Mmin(a)=(8)S(T∗) M_ (a) eq:def-m-min-a=S(T^*) =Lemma A.3F(a,t∗)+(at∗)⋅(a−t∗)!⋅S(Tℓ∗)+(a−t∗)⋅(t∗)!⋅S(Tr∗) @crefcreftypecap~refnumlem:sx-recurrence=F(a,t^*)+ at^*·(a-t^*)!· S(T_ ^*)+ aa-t^*·(t^*)!· S(T_r^*) ≥F(a,t∗)+(at∗)⋅(a−t∗)!⋅Mmin(t∗)+(a−t∗)⋅(t∗)!⋅Mmin(a−t∗) @crefcreftypecap~refnumlem:sx-recurrence≥F(a,t^*)+ at^*·(a-t^*)!· M_ (t^*)+ aa-t^*·(t^*)!· M_ (a-t^*) =(9)Mmin(a,t∗)≥min1≤t≤a−1Mmin(a,t). 12.0pt eq:def-m-min-a-t= 12.0ptM_ (a,t^*)≥ _1≤ t≤ a-1M_ (a,t). This proves the reverse inequality, and hence the equality. ∎ We fill the table MminM_ in increasing order of a. For every a, we also store a value of t achieving the minimum in (10). Then a tree achieving Mmin(m)M_ (m) can be reconstructed recursively from the stored splits. By the equivalence at the beginning of the proof, this tree maximizes out-div(GS(T))out -div(GS(T)). It remains to bound the running time. The values F(a,t)F(a,t) for all a≤ma≤ m and 1≤t≤a−11≤ t≤ a-1 are obtained using the same preprocessing as in the proof of Theorem 4.3: we compute the table A(a,t,s)A(a,t,s) and then apply Lemma A.2. As argued there, this takes O(m4)O(m^4) time in total. Once all values F(a,t)F(a,t) are known, filling the table MminM_ takes O(m2)O(m^2) time, since for every a we try all t∈1,2,…,a−1t∈\1,2,…,a-1\. Thus, the overall running time is O(m4)O(m^4). To find a tree minimizing out-div(GS(T))out -div(GS(T)), we use the same dynamic program with maxima instead of minima. Hence we can find both a tree maximizing and a tree minimizing out-div(GS(T))out -div(GS(T)) in O(m4)O(m^4) time. A.5 Proof of Theorem 4.6 We fix an integer m≥2m≥ 2. Let T be the caterpillar tree defining GS/catmGS/cat_m. We compute out-div(GS/catm)out -div(GS/cat_m) by applying the algorithm from Theorem 4.3 to the tree T. Thus, throughout the proof, we use the notation from the proof of Theorem 4.3. For every q∈2,…,mq∈\2,…,m\, let xqx_q be the unique node of T whose subtree has exactly q leaves, and let x1x_1 be an arbitrary child of x2x_2. In particular, xmx_m is the root of T and x1x_1 is a leaf. For every q∈2,…,mq∈\2,…,m\, the node xqx_q is internal: it has one child that is a leaf and the other child is xq−1x_q-1. Since swapping the two children of an internal node does not change the induced GSGS domain, we may assume that the leaf child is the left child. Thus, we have mxq=qm_x_q=q and t=1t=1. To compute the outer diversity, we first compute the local contribution F(xq)F(x_q). This value will then be used in the recurrence for S(xq)S(x_q). Since A(q,1,s)=1A(q,1,s)=1 and fxq(s)=mins−1,q−sf_x_q(s)= \s-1,q-s\ for every s∈1,…,qs∈\1,…,q\, we get F(xq) F(x_q) =Lemma A.2∑s=1qfxq(s)⋅A(q,1,s)⋅1!⋅(q−1)!=(q−1)!⋅∑s=1qmins−1,q−s. @crefcreftypecap~refnumlem:fx-formula= _s=1^qf_x_q(s)· A(q,1,s)· 1!·(q-1)!=(q-1)!· _s=1^q \s-1,q-s\. (12) Applying Lemma A.3 to xqx_q, and using the fact that the leaf child contributes zero, gives S(xq)q! S(x_q)q! =1q!⋅F(xq)+1q!⋅(q1)⋅(q−1)!⋅0+1q!⋅(q−1)⋅1!⋅S(xq−1) = 1q!· F(x_q)+ 1q!· q1·(q-1)!· 0+ 1q!· qq-1· 1!· S(x_q-1) =F(xq)q!+S(xq−1)(q−1)!=(12)1q⋅∑s=1qmins−1,q−s+S(xq−1)(q−1)!. = F(x_q)q!+ S(x_q-1)(q-1)! eq:fxq-formula= 1q· _s=1^q \s-1,q-s\+ S(x_q-1)(q-1)!. Since S(x1)=0S(x_1)=0, iterating the above recurrence gives S(xm)m!=∑q=2m1q⋅∑s=1qmins−1,q−s. S(x_m)m!= _q=2^m 1q· _s=1^q \s-1,q-s\. (13) Now we analyze the term 1q⋅∑s=1qmins−1,q−s 1q· _s=1^q \s-1,q-s\. If q is even, then we have 1q⋅∑s=1qmins−1,q−s=1q⋅∑s=0q2−12s=(q2−1)q2q=q−24. 1q· _s=1^q \s-1,q-s\= 1q· _s=0 q2-12s= ( q2-1) q2q= q-24. If q is odd, then q=2i+1q=2i+1 for some integer i and we have 1q⋅∑s=1qmins−1,q−s=1q⋅(i+∑s=0i−12s)=i2q=q2−2q+14q=q−24+14q. 1q· _s=1^q \s-1,q-s\= 1q· (i+ _s=0^i-12s )= i^2q= q^2-2q+14q= q-24+ 14q. Hence we obtain 4⋅S(xm)m! 4· S(x_m)m! =(13)∑q=2m4q⋅∑s=1qmins−1,q−s eq:sxm-over-m-factorial= _q=2^m 4q· _s=1^q \s-1,q-s\ =∑q=2m(q−2)+∑2≤q≤mq is odd1q=(m−1)(m−2)2+(Hm−1−12H⌊m/2⌋), = _q=2^m(q-2)+ _ subarrayc2≤ q≤ m\\ q is odd subarray 1q= (m-1)(m-2)2+ (H_m-1- 12H_ m/2 ), (14) since the second sum is the sum of reciprocals of odd integers between 33 and m. Substituting this expression into the formula for out-div(GS/catm)out -div(GS/cat_m) gives out-div(GS/catm) out -div(GS/cat_m) =(6)1−2⋅S(xm)(m2)⋅m!=1−1(m−1)m⋅4⋅S(xm)m! eq:outdiv-gst=1- 2· S(x_m) m2· m!=1- 1(m-1)m· 4· S(x_m)m! =(14)1−1(m−1)m⋅((m−1)(m−2)2+Hm−1−12H⌊m/2⌋) eq:sxm-over-m-factorial-final=1- 1(m-1)m· ( (m-1)(m-2)2+H_m-1- 12H_ m/2 ) =12+1m−1−1(m−1)m⋅(Hm−12H⌊m/2⌋), = 12+ 1m-1- 1(m-1)m· (H_m- 12H_ m/2 ), which finishes the proof. A.6 Proof of Theorem 4.8 We will prove the thesis by showing that there exists a constant β∈ℝβ such that ansd(GS/bal)=1/2−β/m.ansd(GS/bal)=1/2-β/ m. (15) For a rooted binary tree T with C as a set of leaves, let I(T)I(T) denote the set of internal nodes with exactly two children in T. Then, for every x∈I(T)x∈ I(T) by d1(x)d_1(x) and d2(x)d_2(x) let us denote the two children of x, and let Di(x)⊆CD_i(x) C be a subset of all leaves in the subtree rooted in di(x)d_i(x) for both i∈1,2i∈\1,2\ (note that Di(x)=di(x)D_i(x)=\d_i(x)\ if di(x)d_i(x) is a leaf). For clarity, we will assume that |D1(x)|≥|D2(x)||D_1(x)|≥|D_2(x)|. Let A and B be arbitrary disjoint subsets that form a 2-partition of the set of candidates C, and let us denote a=|A|a=|A| and b=|B|b=|B|. By A,BA,B-score of a vote v let us denote the number of pairs of candidates c∈Ac∈ A and c′∈Bc ∈ B, such that c is before c′c , i.e., σA,B(v)=∑c∈A,c′∈B[c≻vc′], _A,B(v)= _c∈ A,c ∈ B[c _vc ], where [φ][ ] is an Iverson bracket giving value 11 if φ is true. Observe that σA,B(v) _A,B(v) is between 00, which is obtained when every candidate in B is before every candidate in A, and a⋅ba· b, which we get when all candidates in A are before that in B. Furthermore, observe that for a vote v taken from ℒ(C)L(C) uniformly at random, the expected value of its A,BA,B-score is equal to (σA,B(v))=∑c∈A,c′∈B([c≻vc′])=∑c∈A,c′∈B1/2=a⋅b/2.E( _A,B(v))= _c∈ A,c ∈ BE([c _vc ])= _c∈ A,c ∈ B1/2=a· b/2. (16) This corresponds to the expected number of swaps needed to put all candidates in A before that in B. However, we are interested in expected number of swaps needed to separate candidates A and B, which is what we need to put candidates in A before that in B or vice versa, whichever requires less swaps. Let us denote this value by X(a,b)=(min(σA,B(v),a⋅b−σA,B(v))).X(a,b)=E( ( _A,B(v),a· b- _A,B(v))). Note that we use a and b as the arguments for X, as its value depends only on the sizes of A and B, not on the sets themselves. Lemma A.5. For every binary tree T with m leaves it holds that ansd(GS(T))=1(m2)∑x∈I(T)X(|D1(x)|,|D2(x)|).ansd(GS(T))= 1 m2 _x∈ I(T)X(|D_1(x)|,|D_2(x)|). Proof. Let C be a set of m candidates, and let T be an arbitrary binary tree over C. Consider an arbitrary vote u∈ℒ(C)u (C). From the definition of the swap distance we have swap(GS(T),u) swap(GS(T),u) =minv∈GS(T)swap(v,u) = _v∈GS(T)swap(v,u) =minv∈GS(T)∑c,c′⊆C[(c≻vc′∧c′≻uc)∨(c′≻vc∧c≻uc′)]. = _v∈GS(T) _\c,c \ C[(c _vc c _uc) (c _vc c _uc )]. Now, observe that for every u,v∈ℒ(C)u,v (C) it holds that ∑c,c′⊆C2[(c≻vc′∧c′≻uc)∨(c′≻vc∧c≻uc′)]=∑x∈I(T)∑c∈D1(x),c′∈D2(x)[(c≻vc′∧c′≻uc)∨(c′≻vc∧c≻uc′)], _\c,c \ C^2[(c _vc c _uc) (c _vc c _uc )]=\\ _x∈ I(T) _c∈ D_1(x),c ∈ D_2(x)[(c _vc c _uc) (c _vc c _uc )], as for every pair of candidates c,c′∈Cc,c ∈ C there is exactly one pair of sets D1(x),D2(x)D_1(x),D_2(x) in which they are counted—the ones in which x is their closest common ancestor. Therefore, swap(GS(T),u)=minv∈GS(T)∑x∈I(T)∑c∈D1(x),c′∈D2(x)[(c≻vc′∧c′≻uc)∨(c′≻vc∧c≻uc′)].swap(GS(T),u)= _v∈GS(T) _x∈ I(T) _c∈ D_1(x),c ∈ D_2(x)[(c _vc c _uc) (c _vc c _uc )]. Moreover, observe that for a vote v in GS(T)GS(T) domain, the decision whether D1(x)D_1(x) is to be placed before D2(x)D_2(x) or after it, is independent from the decision how D1(y)D_1(y) and D2(y)D_2(y) are to be arranged for any other internal node y (as they are either pairwise disjoint, or D1(y),D2(y)⊆Di(x)D_1(y),D_2(y) D_i(x) for i=1i=1 or i=2i=2). Hence, we can exchange the minv∈GS(T) _v∈GS(T) and ∑x∈I(T) _x∈ I(T) quantifiers, yielding swap(GS(T),u)=∑x∈I(T)minv∈GS(T)∑c∈D1(x),c′∈D2(x)[(c≻vc′∧c′≻uc)∨(c′≻vc∧c≻uc′)].swap(GS(T),u)= _x∈ I(T) _v∈GS(T) _c∈ D_1(x),c ∈ D_2(x)[(c _vc c _uc) (c _vc c _uc )]. Furthermore, since in v, for every x∈I(T)x∈ I(T), either every candidate in D1(x)D_1(x) is before every candidate in D2(x)D_2(x) or vice-versa, this is equivalent to swap(GS(T),u)=∑x∈I(T)min(∑c∈D1(x),c′∈D2(x)[c≻uc′],∑c∈D1(x),c′∈D2(x)[c′≻uc])swap(GS(T),u)= _x∈ I(T) ( _c∈ D_1(x),c ∈ D_2(x)[c _uc ], _c∈ D_1(x),c ∈ D_2(x)[c _uc] ) Then, the first argument of the minimum is just (σD1(x),D2(x)(u)CLOSE( _D_1(x),D_2(x)(u), by the definition. By symmetry, the second argument is equal to |D1(x)|⋅|D2(x)|−σD1(x),D2(x)(u)|D_1(x)|·|D_2(x)|- _D_1(x),D_2(x)(u). Therefore, we get swap(GS(T),u)=∑x∈I(T)min(σD1(x),D2(x)(u),|D1(x)|⋅|D2(x)|−σD1(x),D2(x)(u))swap(GS(T),u)= _x∈ I(T) ( _D_1(x),D_2(x)(u),|D_1(x)|·|D_2(x)|- _D_1(x),D_2(x)(u)) Taking the expected value over all u∈ℒ(C)u (C) and dividing by (m2) m2, we obtain the thesis. ∎ Lemma A.6. There exists a constant γ∈ℝγ , such that for every n∈ℕn and k∈0,…,nk∈\0,…,n\, it holds that X(n+k,n)(n+k)n/2≥1−γ/n. X(n+k,n)(n+k)n/2≥ 1-γ/ n. Proof. Let v be a vote drawn uniformly at random from ℒ(C)L(C) for C consisting of 2n+k2n+k candidates, and let A,B⊆CA,B C be such that |A|=n+k|A|=n+k, |B|=n|B|=n, and A∩B=∅A∩ B= . Then, using min(x,y)=x+y2−|x−y|2 (x,y)= x+y2- |x-y|2 transformation, we obtain that X(n+k,n) X(n+k,n) =(min(σA,B(v),(n+k)n−σA,B(v))) =E( ( _A,B(v),(n+k)n- _A,B(v))) =(n+k)n2−(|σA,B(v)−(n+k)n2|). = (n+k)n2-E ( | _A,B(v)- (n+k)n2 | ). From Cauchy-Schwarz inequality we get that (|σ(v)−(n+k)n/2|)≤((σ(x)−ab/2)2),E(|σ(v)-(n+k)n/2|)≤ E((σ(x)-ab/2)^2), which yields X(n+k,n)≥(n+k)n2−((σA,B(v)−(n+k)n2)2).X(n+k,n)≥ (n+k)n2- E ( ( _A,B(v)- (n+k)n2 )^2 ). Since (n+k)n/2(n+k)n/2 is the mean of σA,B(v) _A,B(v) by Equation (16), this gives us X(n+k,n)≥(n+k)n2−Var(σA,B(v)).X(n+k,n)≥ (n+k)n2- Var ( _A,B(v) ). (17) In order to compute the variance of σA,B(v) _A,B(v), we use the formula for the variance of the sum, which gives us Var(σA,B(v))=∑c∈A,c′∈B∑d∈A,d′∈BCov([c≻vc′][d≻vd′]).Var( _A,B(v))= _c∈ A,c ∈ B _d∈ A,d ∈ BCov([c _vc ][d _vd ]). Now, if c=dc=d and c′=d′c =d , we get Cov([c≻vc′][d≻vd′])=Var([c≻vc′])=(([c≻vc′]−1/2)2)=(1/2)2=1/4.Cov([c _vc ][d _vd ])=Var([c _vc ])=E(([c _vc ]-1/2)^2)=(1/2)^2=1/4. If c≠dc≠ d and c′≠d′c ≠ d , the variables [c≻vc′][c _vc ] and [d≻vd′][d _vd ] are independent, thus Cov([c≻vc′][d≻vd′])=0.Cov([c _vc ][d _vd ])=0. If c=dc=d but c′≠d′c ≠ d , then Cov([c≻vc′][d≻vd′])=(([c≻vc′]−1/2)([c≻vd′]−1/2)).Cov([c _vc ][d _vd ])=E (([c _vc ]-1/2)([c _vd ]-1/2) ). Observe that ([c≻vc′]−1/2)([c≻vd′]−1/2)([c _vc ]-1/2)([c _vd ]-1/2) is equal to 1/41/4 if c is either before or after both c′c and d′d while it is equal to −1/4-1/4 if c is between c′c and d′d . Hence, out of all 66 orderings of these 33 candidates, 1/41/4 is given in 44 cases and −1/4-1/4 in 22. Thus, Cov([c≻vc′][d≻vd′])=14⋅46−14⋅26=14⋅26=112.Cov([c _vc ][d _vd ])= 14· 46- 14· 26= 14· 26= 112. If c≠dc≠ d but c′=d′c =d , the situation is analogous and Cov([c≻vc′][d≻vd′])=112.Cov([c _vc ][d _vd ])= 112. It remains to count the multiplicity of each case with non-zero covariance. The number of cases when c=dc=d and c′=d′c =d is the number of pairs c∈Ac∈ A, c′∈Bc ∈ B, which is (n+k)n(n+k)n. Each case in which c=dc=d but c′≠d′c ≠ d corresponds to picking one candidate from A and two distinct ones from B, but we count (c′,d′)(c ,d ) and (d′,c′)(d ,c ) both times, which gives 2(n+k2)n=(n+k)(n+k−1)n2 n+k2n=(n+k)(n+k-1)n cases. Analogously, there are 2(n+k)(n2)=(n+k)n(n−1)2(n+k) n2=(n+k)n(n-1) cases in which c≠dc≠ d but c′=d′c =d . Thus, we get Var(σA,B(v)) ( _A,B(v)) =(n+k)n4+(n+k)(n+k−1)n+(n+k)n(n−1)12 = (n+k)n4+ (n+k)(n+k-1)n+(n+k)n(n-1)12 =(3n2+3nk)+(n3+2n2k+nk2−n2−nk)+(n3+n2k−n2−nk)12 = (3n^2+3nk)+(n^3+2n^2k+nk^2-n^2-nk)+(n^3+n^2k-n^2-nk)12 =2n3+n2+nk+3n2k+nk212 = 2n^3+n^2+nk+3n^2k+nk^212 Combining this with Equation (17), gives us X(n+k,n) X(n+k,n) ≥(n+k)n2−2n3+n2+nk+3n2k+nk212 ≥ (n+k)n2- 2n^3+n^2+nk+3n^2k+nk^212 ≥(n+k)n2−6n3+2n212 ≥ (n+k)n2- 6n^3+2n^212 =(n+k)n2−3n3+n26, = (n+k)n2- 3n^3+n^26, where the second inequality comes from the fact that k≤nk≤ n. Dividing it by (n+k)n/2(n+k)n/2 we obtain X(n+k,n)(n+k)n/2 X(n+k,n)(n+k)n/2 ≥1−3n3+n26⋅2(n+k)n ≥ 1- 3n^3+n^26· 2(n+k)n ≥1−3n3+n26⋅2n2 ≥ 1- 3n^3+n^26· 2n^2 =1−O(1/n), =1-O(1/ n), where the second inequality comes from the fact that k≥0k≥ 0. This concludes the proof of the lemma. ∎ Lemma A.7. For every binary tree T with m leaves it holds that ∑x∈I(T)|D1(x)|⋅|D2(x)|=(m2). _x∈ I(T)|D_1(x)|·|D_2(x)|= m2. Proof. Let T be an arbitrary tree with a set of leaves C, and let m=|C|m=|C|. Observe that ∑x∈I(T)|D1(x)|⋅|D2(x)|=|c,c′⊆C|=(m2), _x∈ I(T)|D_1(x)|·|D_2(x)|=|\c,c \ C|= m2, as each pair c,c′∈Cc,c ∈ C is counted exactly once in the sum on the left-hand-side, for x that is the closest common ancestor of c and c′c . This concludes the proof. ∎ Having Lemmas A.5, A.6 and A.7, we are now ready to prove the main thesis. Fix an arbitrary balanced binary tree T with m leaves. Observe that in a binary tree, it holds that |D1(x)|≤2⋅|D2(x)||D_1(x)|≤ 2·|D_2(x)|, for every internal node x. Thus, we obtain ansd(GS(T)) ansd(GS(T)) =1(m2)∑x∈I(T)X(|D1(x)|,|D2(x)|) = 1 m2 _x∈ I(T)X(|D_1(x)|,|D_2(x)|) (by Lemma A.5) =1(m2)∑x∈I(T)|D1(x)|⋅|D2(x)|2⋅X(|D1(x)|,|D2(x)|)|D1(x)|⋅|D2(x)|/2 = 1 m2 _x∈ I(T) |D_1(x)|·|D_2(x)|2· X(|D_1(x)|,|D_2(x)|)|D_1(x)|·|D_2(x)|/2 ≥1(m2)∑x∈I(T)|D1(x)|⋅|D2(x)|2⋅(1−γ|D2(x)|) ≥ 1 m2 _x∈ I(T) |D_1(x)|·|D_2(x)|2· (1- γ |D_2(x)| ) (by Lemma A.6) ≥1(m2)∑x∈I(T)(|D1(x)|⋅|D2(x)|2−γ⋅|D2(x)|2|D2(x)|) ≥ 1 m2\! _x∈ I(T)\! ( |D_1(x)|\!·\!|D_2(x)|2\!-\!γ· |D_2(x)|^2 |D_2(x)|\! ) (as |D1(x)|≤2|D2(x)||D_1(x)|≤ 2|D_2(x)|) =121(m2)(∑x∈I(T)|D1(x)|⋅|D2(x)|−γ⋅∑x∈I(T)|D2(x)|3/2) = 12 1 m2 ( _x∈ I(T)|D_1(x)|·|D_2(x)|-γ· _x∈ I(T)|D_2(x)|^3/2 ) =121(m2)(∑x∈I(T)|D1(x)|⋅|D2(x)|−γ(∑x∈I(T)|D2(x)|)3/2) = 12 1 m2 ( _x∈ I(T)|D_1(x)|·|D_2(x)|-γ ( _x∈ I(T)|D_2(x)| )^3/2 ) (by superadditivity) =121(m2)(∑x∈I(T)|D1(x)|⋅|D2(x)|)−γ⋅m3/2m2−m = 12 1 m2 ( _x∈ I(T)|D_1(x)|·|D_2(x)| )-γ· m^3/2m^2-m (as ∑x∈I(T)|D2(x)|≤m _x∈ I(T)|D_2(x)|≤ m) =12−γ(1+m2−m)1m = 12-γ (1+ mm^2-m ) 1 m (by Lemma A.7) =12−2γm. = 12- 2γ m. (as m/(m2−m)≤1m/(m^2-m)≤ 1 for m≥2m≥ 2) This proves Equation 15 for β=2γβ=2γ and concludes the proof. A.7 Proof of Theorem 4.10 Let C be a set of m candidates, and let SP/starmSP/star_m be the domain over C. Let c∈Cc∈ C be the candidate corresponding to the center of the star. We observe that SP/starmSP/star_m is exactly the set of votes in ℒ(C)L(C) in which c is ranked first or second. Moreover, distance from any vote v∈ℒ(C)v∈L(C) to SP/starmSP/star_m is simply max(v[c]−2,0) (v[c]-2,0), where v[c]v[c] is the position of candidate c in vote v. This comes from the fact that it is enough and necessary to move candidate c to the 2nd position (in cases it is not on the 1st or the 2nd position in v—then the distance from v to SP/starSP/star is 00). For a given position i∈[m]i∈[m], there are (m−1)!(m-1)! many votes in ℒ(C)L(C) with candidate c on position i. This gives (swap(v,SP/starm))=(m−1)!m!⋅∑i=3m(i−2)=(m−1)(m−2)2m.E(swap(v,SP/star_m))= (m-1)!m!· _i=3^m(i-2)= (m-1)(m-2)2m. This implies ansd(SP/starm)=(swap(v,SP/starm))(m2)=(m−2)/m2,ansd(SP/star_m)= E(swap(v,SP/star_m)) m2=(m-2)/m^2, which gives out-div(SP/starm)=1−2/m+4/m2out -div(SP/star_m)=1-2/m+4/m^2. Appendix B Condorcet Domains with Seven Candidates (a) Every maximal nonisomorphic Condorcet domain with seven candidates is placed as a dot, with its x coordinate giving the domain’s size, and its y coordinate giving its outer diversity. If a domain belongs to a certain class of domains, such as peak-pit, then its dot is colored accordingly; otherwise it is gray. We additionally include a sample of 200 single-crossing domains. (b) Outer diversity of maximal nonisomorphic Condorcet domains depending on the number of satisfied never-bottom (x-axis) and never-middle (y-axis) conditions. The size of each square reflects the number of domains satisfying given numbers of conditions, and the horizontal color gradient presents the distribution of outer diversity values for these domains. Figure 4: Analysis of all of the maximal Condorcet domains for seven candidates. In Figure 4 we show a plot analogous to Figure 1, but for the case of seven candidates. Since there are over 172 million maximal nonisomorphic Condorcet domains with seven candidates, we included each such domain provided by Akello-Egwel et al. [2025] with probability 1%1\%. However, in Figure 4(a) (but not Figure 4(b)) we did include all peak-pit domains, all Arrow’s SP domains (including Black’s SP one), all domains that only satisfy never-middle conditions (including group-separable ones) and the Fishburn domain. We see that the overall conclusions one can draw for the case of seven candidates are similar as those for six. Appendix C Outer Diversity of Euclidean Domains Let us formally introduce the Euclidean domains. tD-Euclidean. Let x:C→ℝtx C ^t be a function that places the candidates as distinct points in ℝtR^t. We call a vote v consistent with x if there is a point xv∈ℝtx_v ^t from which the candidates appear in the order prescribed by v when sorted by distance. A t-dimensional Euclidean domain defined by x contains exactly the votes consistent with x. Aside from the 1D case, ttD Euclidean domains are typically neither Condorcet nor weak Condorcet. In the 1D case they are, however, special cases of both SPSP and SCSC ones. There are very many different Euclidean domains that depend on exact locations of the candidates. Further, we occasionally restrict them to only include those votes that can be generated by points in some subarea of ℝtR^t. For our experimental analysis, we consider two distinct subareas of ℝtR^t to serve as the sampling space for candidate locations. The first is the standard square-shaped subarea, typically defined as [−1,1]t[-1,1]^t. However, this geometry may introduce unwanted artifacts due to its lack of rotational symmetry; specifically, the increased distance from the center to the vertices can bias the resulting domain. For instance, a rotation of the candidate set x could shift the regions associated with certain consistent votes in or out of the subarea, thereby altering the domain. To mitigate these effects, we also consider a circular subarea, which ensures rotational invariance. To investigate how the spatial concentration of candidates influences the outer diversity of the induced domain, we utilize a symmetric Beta distribution B(α,β)B(α,β), where α=βα=β. By varying the parameter α, we can smoothly transition between distributions that are concentrated at the center of the subarea (α>1α>1) and those that are concentrated at the edges (α<1α<1). The points are generated according to the following procedures: Circular Subarea. To maintain radial consistency, for each point we sample an angle θ uniformly from [0,2π)[0,2π) and a radial distance r as the square root of a value sampled from B(α,α)B(α,α). Square Subarea. The generation method adapts to the concentration parameter. For α>1α>1, both coordinate axes are sampled independently from B(α,α)B(α,α) and scaled to the interval [−1,1][-1,1]. For α≤1α≤ 1, to prevent over-concentration in the corners, we sample one axis from B(α,α)B(α,α) and the other from a uniform distribution on [−1,1][-1,1]. To maintain symmetry, this assignment of distributions to axes is swapped for exactly half of the generated points. (a) Distribution of points on a circular subarea with chosen parameters. (b) Distribution of points on a square subarea with chosen parameters. Figure 5: Candidate distributions within circular and square subareas using a sample size of 500,000500,000 points. (a) 2D-Euclidean circular subarea (b) 2D-Euclidean square subarea 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%95\% confidence interval indicates a margin of error of at most 0.002620.00262, with only two exceptions reaching 0.009280.00928 and 0.008170.00817 for the square subarea at α=β=0.1α=β=0.1 with 4 and 3 candidates, respectively. The number of generated samples per candidate count is 60006000, 40004000, 20002000, 10001000, 500500, and 200200 for 3,4,5,6,73,4,5,6,7, and 88 candidates, respectively. In Figure 5, we present the spatial distributions as described above for the parameter settings utilized in our subsequent experiments. As illustrated, for identical parameter values, the distributions exhibit different point concentrations between the circular and square subareas — an effect particularly noticeable at α=β=10.0α=β=10.0. However, this discrepancy does not affect our conclusions, as we focus on the change in outer diversity relative to the shift in distribution, rather than absolute values for specific parameter configurations. We calculated the mean outer diversity for both circular and square subareas, generating candidate positions from distributions described above for m∈3,…,8m∈\3,…,8\ candidates. The results, presented in Figure 6, show that regardless of the subarea’s geometry, the outer diversity is higher when candidates are more concentrated at the center compared to the uniform distribution observed at α=β=1.0α=β=1.0. This result is expected, as a higher concentration of candidates near the center increases the number of geometric regions corresponding to individual votes that lie at least partially within the chosen subarea. Surprisingly, an analysis of the heatmaps reveals a local minimum in the mean outer diversity to be likely for parameters between 0.220.22 and 1.01.0. Contrary to intuitive expectations of a monotonic increase as concentration in the center intensifies, the mean outer diversity rises again as the parameters decrease further toward 0.10.1. This non-monotonic behavior is consistent across both the circular and the square subareas. In the square subarea for 3 and 4 candidates, the lowest mean outer diversity is observed for α=β=1.0α=β=1.0, yet the results for α=β=0.46α=β=0.46 remain very close, confirming that the slight, negligible variations do not alter the overall trend. We also checked the variety of domains that can be obtained. Figure 7 presents the variety of 2D Euclidean domains in terms of outer diversity and the number of votes, obtained by generating candidates uniformly at random. Figure 7: 100,000100,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. Appendix D Microscope Visualizations of the Domains Figures 8 and 9 show microscope visualizations of Condorcet domains on 6 candidates. For each domain size, we display the domains with maximum (Fig. 8) and minimum (Fig. 9) outer-diversity. Each domain is represented as a point cloud where votes are embedded via MDS under swap distance, with point color indicating the top-ranked candidate. Domains with high outer-diversity appear geometrically spread out with colors well-separated across the embedding, while low-diversity domains of the same size are more clustered, reflecting that their votes occupy a narrower portion of the space. (Note that for n=45n=45, there is only one domain, which has both the minimal and maximal outer-diversity). Figures 11 and 12 shows microscope domains satisfying never-middle conditions. Note that the domains presented in Fig. 12 are at the same time GSGS domains, and consist of 32 votes, each; while domains presented in Fig. 12 are not GSGS and consist only of 16 votes, each. Finally, figure 10 presents analogous microscope visualizations for SP/T domains with up to 9 candidates and up to 1000 votes. 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 GSGS. Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate. Figure 12: Microscope visualizations of GSGS domains. Points represent distinct votes embedded via MDS under swap distance; color encodes the top-ranked candidate.