Metric geometry for ranking-based voting: Tools for learning electoral structure Moon Duchin, Kristopher Tapp Abstract . In this paper, we develop the metric geometry of ranking statistics, proving that the two major permutation distances in the statistics literature—Kendall tau and Spearman footrule—extend naturally to incomplete rankings with both coordinate embeddings and graph realizations . This gives us a unifying framework that allows us to connect popular topics in computational social choice: metric preferences (and metric distortion), polarization, and proportionality. As an important application, the metric structure enables efficient identification of blocs of voters and slates of their preferred candidates. Since the definitions work for partial ballots, we can execute the methods not only on synthetic elections, but on a suite of real-world elections. This gives us robust clustering methods that often produce an identical grouping of voters—even though one family of methods is based on a Condorcet-consistent ranking rule while the other is not. 2020 Mathematics Subject Classification Primary 05C12; Secondary 91B12, 91B14 1. Introduction A major research direction in computational social choice theory has been the study of metric preferences: both candidates and voters are thought to be embedded in a common (unobserved) metric space, and the “cost” of a candidate is the sum of their distances to the voters. In this framework, each metric embedding has an optimal winner (the lowest-cost candidate); however, many metrics are consistent with a given preference profile that records the ordinal preferences of the voters, and the identity of the optimal winner may vary. Numerous works have studied the metric distortion for voting rules, defined as the worst-case cost ratio over all metric realizations. A second strand of research has aimed to provide descriptive measures of preference, such as by measuring the level of polarization for a ranked choice election, the level of preference diversity , or the degree of proportionality for multi-winner elections. All of these have natural interpretations in the metric framework presented here. The purpose of this paper is to build out the metric theory for elections, not through a worst-case analysis but by a close study of two choices of metric. As an application, we obtain natural methods for grouping similar voters and candidates, respectively, and identifying them as voter blocs and candidate slates . We test the methods on synthetic preference profiles and on a real-world dataset of over 1000 ranked-choice local government elections in Scotland from 2012 to 2022, which feature five major parties and dozens of minor ones. Because our methods do not make use of party labels, we are able to identify patterns that might be otherwise missed by party-focused analysis. By a ballot , we mean a complete or partial ranking of m candidates. (In places, we also consider the fuller setting of weak rankings, allowing arbitrary ties.) We will introduce coordinate embeddings that correspond to the two most important notions of ranking distance in the statistics literature, defined for complete and partial ballots. A preference profile is a finite set of ballots. The first metric embedding assigns a ballot to a point in \mathbb{R}^{m} by taking each candidate’s coordinate to be the reverse of their ranking, so that a candidate earns a score of m-j from a voter who ranks them j th. Because this system of scoring is sometimes called (standard) Borda points in the context of voting, we call this the Borda embedding . An alternative system of coordinates maps a ballot to \{-1,0,1\}^{\binom{m}{2}}\subset\mathbb{R}^{\binom{m}{2}} , where each pairwise comparison is recorded as favoring one of the two candidates ( \pm 1 ) or as a tie ( 0 ). We call this the head-to-head embedding . We then define the distances d_{B} and d_{H} between ballots as half the L^{1} distance between the corresponding vectors. These recover Spearman footrule and Kendall tau (also known as swap distance, or bubble sort distance), respectively. A preference profile sits as a point cloud in the associated coordinate space. An optimal center under the L^{1} metric in the head-to-head embedding is precisely the Kemeny ranking, and k -clustering in this setting is the k -Kemeny problem. In the Borda embedding, it is the L^{2} minimizer that would recover the usual Borda ranking rule—the coordinates record average Borda score for candidates. L^{1} minimizers give a Borda median ranking; this has been studied under the heading of rank aggregation but not fully embraced in social choice theory as a voting rule. As an alternative to coordinate embeddings, we realize d_{B} and d_{H} as graph metrics. We define a sparse graph called the ballot graph whose nodes are partial rankings and whose path metric recovers d_{H} ; by adding edges, we obtain a shortcut ballot graph that recovers d_{B} . There are several main contributions, including: Extension of metric results. Not only complete rankings, but partial rankings, candidates, and slates all receive assigned locations in a common space. Graph realizations. We build graphs that incorporate partial rankings, with results connecting them to the principal ranking metrics (Kendall and Spearman). Notably, the Borda graph realization works with some partial-ballot conventions and not others. Empirical methods. The incorporation of partial ballots lets us deploy our methods on real elections. We use both synthetic and real-world elections for validation, and show empirical robustness to modeling choices. Sometimes, the extension of complete-ranking results to partial rankings can be done with essentially routine constructions. But that is not the case here, where the arguments are far from trivial and the extension to partial rankings forces certain choices that are not obvious; this can be thought of as revealing structure that was already present in the setting of full permutations. Overall, we develop fundamental tools in the geometry of rankings, apply these tools to the unsupervised learning problem of detecting blocs and slates, and show that we get stable and interpretable results. All data and code used in this paper are available at https://github.com/mggg/ballot-clustering 1.1. Related work Well-studied metrics on full permutations (i.e., complete ballots) include the Spearman footrule and the Kendall tau distance 17 ; 16 . The classic paper of 5 calls them D and I , respectively, and establishes that the two metrics are mutually bounded. These agree with our metrics via d_{H}=I and d_{B}=\frac{1}{2}D . In our notation, the (sharp) bounds are \frac{1}{2}d_{H}\leq d_{B}\leq d_{H}. The same bounds were generalized to partial permutations of fixed length (that is, top- k rankings) by 9 and then to more general ballots by a larger set of co-authors in 8 . These papers employ the averaged Borda convention for ballots that are short or allow general ties, awarding the candidates in a tied ranking the average of the Borda points they would receive in any resolution of ties. We consider an alternative, sometimes called the pessimistic Borda convention, that awards the fewest points over all resolutions—i.e., zero points for all unmentioned candidates 14 . Not only do the Diaconis–Graham bounds extend to pessimistic Borda distance on partial ballots, but that metric is well adapted to a sparse graph realization, whereas averaged Borda is not. The idea of a ballot graph has been used by several authors; see for example the beautiful illustrations in 18 . However, to our knowledge, previous work is limited to d_{H} distances between complete ballots. An application of these metrics in the literature that closely aligns with our centroid-based clustering methods is what is known as the rank aggregation problem. In the context of rank aggregation, the center is required to be a full ranking (whose summed distance to the input rankings is minimized) and is viewed as "consensus" ranking 6 ; 20 , so that rank aggregation can be viewed as a voting method. For example, 11 explores which Arrow-style axioms are satisfied by various methods of rank aggregation. In our work, we find it productive to use a slightly different interpretive framework: the center of each cluster is a useful summary statistic of the voting behavior within that cluster, whether or not it is a ranking and whether or not the voters are closely concentrated nearby. We connect to the extensive literature on metric preferences and distortion in social choice, surveyed in 1 . The identification of blocs and slates will give strong grounding for the measurement of proportionality, diversity, and polarization, which are topics of longstanding interest (and current activity) in computational social choice 19 ; 13 ; 12 ; 15 . For polarization in particular, axiomatic developments are found in classic economics papers like 7 and 3 . The work most closely aligned with ours is 10 , whose authors define diversity and polarization indices for an election (with complete rankings) in terms of the k -clusterings that minimize the ballots’ summed d_{H} -distances to k centers. With our tools, their definitions can be extended to partial ballots and executed at scale. The authors of 2 cluster the ballots of an election by fitting the parameters of a Mallows model. By contrast, we identify clusters without assuming that the ballots follow any particular distribution. 2. Ballot graphs and coordinate embeddings Let \Omega_{m} be the set of possible partial or complete ballots in an election with m candidates. The candidates can be denoted \{A,B,\dots\} or \{A_{1},\dots,A_{m}\} . We will adopt flexible notation for ballots, so that (A,C,D,B),\quad A>C>D>B,\quad ACDB,\quad\hbox{\rm and}\quad\begin{pmatrix}A\\ C\\ D\\ B\end{pmatrix} all denote the same ballot. We will record partial ballots as having unmentioned candidates tied at the end of the ballot, so that (A,B) or (A,B,-,-) is identified with (A,B,\{C,D\}) . Partial ballots therefore only allow ties at the end of the ballot; generalized ballots would allow ties in arbitrary positions. 2.1. Coordinate embeddings Definition 2.1 ( Borda and head-to-head distance ) . Suppose \sigma is a permutation of the symbols 1,\dots,m , with the convention that \sigma maps a candidate index to the rank of that candidate on the ballot, i.e., for candidates A_{1},\dots,A_{m} , we have that \sigma(i) is the position in which the voter ranked A_{i} . In this notation, the ranking corresponding to \sigma is \begin{pmatrix}\sigma^{-1}(1)\\ \vdots\\ \sigma^{-1}(m)\end{pmatrix}. Extend this to partial ballots by the pessimistic convention: if j is an unlisted candidate, then \sigma(j)=m . In places, we will also refer to the averaged convention whereby \sigma(j) equals the average of the rankings that all of the unlisted candidates would have received if they had been ranked. Averaging maintains the total sum of ranks for any ballot, complete or partial, as \sum_{i}\sigma(i)=\binom{m+1}{2} , while the pessimistic convention lets that sum vary—in other words, embedding with the averaged convention sends all ballots onto a common hyperplane. Define functions \mathfrak{b}:\Omega_{m}\to\mathbb{R}^{m} and \mathfrak{h}:\Omega_{m}\to\mathbb{R}^{\binom{m}{2}} by \mathfrak{b}(\sigma)(i)=m-\sigma(i),\qquad\mathfrak{h}(\sigma)(\{i,j\})=\begin{cases}+1&\sigma(i)>\sigma(j)\\ 0&\sigma(i)=\sigma(j)\\ -1&\sigma(i)<\sigma(j)\end{cases}\,\,\,(\text{assuming }i\mathcal{B} can be considered as a generalized ballot. Without loss of generality, every candidate appears once in a generalized ballot; complete and partial ballots are both special cases, since partial ballots were already interpreted as having a tie in the last position. Let \widetilde{\Omega}_{m} denote the set of generalized ballots in an election with m candidates. The generalized ballot graph \widetilde{\mathcal{G}}_{m} is a graph on these nodes. There is an edge between two nodes whenever one ballot is obtained from the other by merging the candidate sets in adjacent positions, and the length of that edge is \frac{1}{2} times the product of their orders. This simple edge rule correctly generalizes both edge rules for \mathcal{G}_{m} . Example 2.6 . The graph \widetilde{\mathcal{G}}_{4} contains the unit-length path (A,B,C,D)\stackrel{{\scriptstyle.5}}{{\rightarrow}}(A,\{B,C\},D)\stackrel{{\scriptstyle.5}}{{\rightarrow}}(A,C,B,D). Swapping any pair of adjacent singleton candidates similarly has cost 1. We enlarge the domain of \mathfrak{h} to \widetilde{\mathcal{G}}_{m} accordingly: as before, its {\binom{m}{2}} coordinates represent ordered pairs of candidates, and the value of each coordinate is -1 (lose), 0 (tie), or 1 (win). Here a tie means that the candidates belong to the same candidate set. Note that these generalized ballot graphs have a super-factorial number of nodes (counted by the Fubini numbers) and now have exponentially growing degree. That is because each generalized ballot has at most m-1 ways to merge neighboring candidate sets, but if a candidate set has k elements then there are 2^{k} ways to split it, so for instance a bullet vote has many neighbors. 2.4. Relating the ballot graphs to coordinate embeddings Theorem 2.7 (Graphs match L^{1} distances) . The distance d_{H} is realized as the path metric on the basic ballot graph \mathcal{G}_{m} , while d_{B} is realized as the path metric on the shortcut ballot graph \mathcal{G}_{m}^{+} . To prove this, it is convenient to introduce notions of strong and weak disagreement. We say that ballots \sigma,\tau have a strong disagreement on candidates i,j if one candidate is ranked higher on \sigma while the other is ranked higher on \tau ; a weak disagreement occurs when one ballot expresses a preference where the other ballot records a tie. Then for a pair of ballots \sigma,\tau we can define \mathop{\rm str}(\sigma,\tau) and \mathop{\rm wk}(\sigma,\tau) as the total number of strong and weak disagreements, respectively. For example, if \sigma=(A,B,C) and \tau=(A,E) in \Omega_{5} , then \mathop{\rm str}(\sigma,\tau)=2 and \mathop{\rm wk}(\sigma,\tau)=4 . Since a strong disagreement occurs when a coordinate of the head-to-head vector is +1 in one ballot and -1 in the other, it contributes 2 to the L^{1} difference; similarly, a weak disagreement contributes 1. It is therefore immediate that d_{H}=\mathop{\rm str}+\frac{1}{2}\mathop{\rm wk} for any pair of ballots. To prove that the graph distance matches d_{H} , it suffices to describe graph distance in terms of strong and weak disagreements. Proof. We begin with d_{H} . For a pair of ballots \sigma,\tau that are adjacent in \mathcal{G}_{m} , we verify that the weight of the edge between them equals w(\sigma,\tau)=\mathop{\rm str}+\frac{1}{2}\mathop{\rm wk}=d_{H}(\sigma,\tau) by checking the cases of neighbor-swap and extension. Now consider a geodesic in \mathcal{G}_{m} visiting vertices \sigma_{1},\dots,\sigma_{r} and note that the graph distance equals \sum w(\sigma_{i},\sigma_{i+1}) by definition of geodesic. On the other hand, d_{H}(\sigma_{1},\sigma_{r}) is less than or equal to this sum, because d_{H} is defined as an L^{1} difference, so it satisfies the triangle inequality. Thus d_{H} is less than or equal to the graph distance. To show that this is an equality, we construct a path realizing the distance equality between arbitrary ballots \sigma,\tau . To do this, we construct "waypoints": if \sigma is a partial ballot, let \sigma^{\prime} be the possibly longer ballot which agrees with \sigma on all listed candidates, then ranks candidates that were mentioned in \tau but not \sigma in the order in which they appear in \tau ; likewise, \tau^{\prime} starts like \tau but adds missing candidates in the order of appearance in \sigma . Consider the path from \sigma to \sigma^{\prime} via extensions, continuing to \tau^{\prime} by a minimal sequence of neighbor swaps, then extending to \tau by truncation. To see that this suffices, note that for two distinct ballots that are complete (or more generally that have the same candidate set), there must be at least one neighboring pair of candidates that witnesses the strong disagreement. Otherwise, every X ranked above Y by the first ballot would also be ranked above Y by the second ballot, forcing the ballots to be identical. This means that there is always a neighbor swap that reduces the strong disagreement count by 1 , until that count is zero. Thus the length of the path \sigma^{\prime}\rightarrow\tau^{\prime} is \mathop{\rm str}(\sigma,\tau) . Suppose there are k candidates mentioned in \tau but not \sigma and l candidates mentioned in neither ballot. Then the path distance from \sigma to \sigma^{\prime} is \frac{l+\dots+(l+k)}{2}=\frac{1}{2}\left(\binom{k}{2}+kl\right) . The number of weak disagreements involving those candidates is \binom{k}{2}+kl . Similarly between \tau and \tau^{\prime} the total edge weight is one-half of the number of weak disagreements involving candidates unmentioned in \tau but mentioned in \sigma . Taken together, we’ve shown that the natural path \sigma\to\sigma^{\prime}\to\tau^{\prime}\to\tau has total edge weight \mathop{\rm str}(\sigma,\tau)+\frac{1}{2}\mathop{\rm wk}(\sigma,\tau) , as desired. Next, to prove that d_{B}(\sigma,\tau) equals the path distance in \mathcal{G}^{+}_{m} , we use the same waypoints \sigma^{\prime},\tau^{\prime} and the same path segments \sigma\rightarrow\sigma^{\prime} and \tau\rightarrow\tau^{\prime} , whose lengths also realize the d_{B} -distance. It remains to construct a d_{B} -geodesic \sigma^{\prime}\rightarrow\tau^{\prime} in \mathcal{G}_{m}^{+} ; that is, a path in \mathcal{G}_{m}^{+} that realizes the d_{B} distance. Note that a path from \sigma^{\prime} to \tau^{\prime} is a d_{B} -geodesic if and only if each candidate’s Borda score changes monotonically between its starting score in \sigma^{\prime} and ending score in \tau^{\prime} . From its position in \sigma^{\prime} , every candidate needs to shift either to a lower position ( \downarrow ), higher ( \uparrow ) or neither ( \square ) to reach its target position in \tau^{\prime} . We represent this as a state vector as in Figure 4 . We proceed in steps, each time swapping the candidates corresponding to the first \uparrow symbol and the last \downarrow symbol before it. Repeating this process until reaching \tau^{\prime} produces a Borda geodesic because each candidate can only move toward its target position; the move never overshoots the target position because the candidates in between those who swapped were already in their final positions. ∎ Figure 4 . For ballots \sigma=(A,C,B) and \tau=(D,C,A,E,B) , we first complete \sigma to \sigma^{\prime} and then make swaps as indicated (in red) for a total Borda distance of d_{B}(\sigma^{\prime},\tau^{\prime})=1+2+1=4 . This correctly matches half the L^{1} difference of \mathfrak{b}(\sigma^{\prime})=(4,2,3,1,0) and \mathfrak{b}(\tau^{\prime})=(2,0,3,4,1) . Remark 2.8 . This proof fails for the averaged Borda convention. With the pessimistic convention, moving a candidate from \sigma out of a tie at the end does not change the position of the remaining unmentioned candidates, so it moves \sigma closer to \sigma^{\prime} . But under averaging, the extension move can improve the position of one candidate but worsen the position of others. In fact, a simple example of this kind suffices to show that our local moves are not enough to realize averaged Borda with graph distance. Consider what is needed to transform a bullet vote for A to a bullet vote for B when there are many candidates. In the averaged convention, all other candidates have the same Borda score in the initial and terminal ballot. But extending A to AB changes the average score of the others, and we easily see that a direct edge from A to B would be needed. Similar arguments force an explosion of degree. The following is a simple application of the strong and weak disagreement count. Proposition 2.9 . d_{H}(\sigma,\tau) equals the average (over all extensions of \sigma and \tau to complete ballots) of the number of adjacent swaps needed to convert \sigma into \tau . Proof. If \sigma or \tau is an incomplete ballot, then randomly completing them resolves each weak disagreement into either an agreement or a strong disagreement, with equal likelihood. Thus, the expected number of strong disagreements between their completions equals \mathop{\rm str}+\frac{1}{2}\mathop{\rm wk} . ∎ Theorem 2.10 . \frac{1}{2}\mathop{\rm str}+\frac{1}{2}\mathop{\rm wk}R and all cast ballots lie within distance r of either x or y . Then if R>4r , any (R,r) –polarized election has a unique optimal clustering. Furthermore, if R>10r , then the same clustering is also optimal with respect to any 2-biLipschitz-equivalent d^{\prime} . Proof. Suppose an election is (R,r) –polarized with respect to d and let x,y be centers that witness the polarization. Then the cost of assigning points in B_{r}(x) to any center in the ball is at most 2r , and the cost of assigning them to any center in B_{r}(y) is at least R-2r . The classification is determined as long as R-2r>2r . With respect to d^{\prime} , the within-ball distance is at most 4r and the between-ball distance is at least \frac{1}{2}R-r , so we need \frac{1}{2}R-r>4r . ∎ The bounds d_{B}\leq d_{H}<2d_{B} (Corollary 2.11 ) let us apply this to our principal metrics. Clearly, if we weaken the hypotheses by allowing only a share of points to lie in the neighborhoods of fixed centers, we obtain a still-meaningful statement requiring the clusterings to substantially agree. The coordinate embeddings enable us to use standard heuristic clustering algorithms to find approximate centers. Furthermore, at the scale of Scottish elections, we can certify globally optimal 1-Kemeny centers in all 1070 elections and globally optimal 2-Kemeny solutions in virtually all elections with up to 10 candidates. The most popular class of clustering methods is k -means, which seeks to minimize the sums of squares of L^{2} distances to k centers in \mathbb{R}^{n} . For instance, Lloyd’s algorithm is an iterative method that is computationally lightweight. But the standard cost-minimizing formulation relates to L^{1} rather than L^{2} distances, suggesting use of the PAM (Partitioning Around Medoids) algorithm, which addresses exactly that minimization problem over candidate centers within the dataset. (That is, in our setting, PAM centers must correspond to ballots that were actually cast in the election.) We can also consider allowing centers to vary over valid ballots, whether chosen by voters or not; and the computationally simplest problem of all would be to simply take coordinatewise medians, which may not correspond to ballots at all. 3.2. Grouping the candidates Another perspective on the problem is to introduce notions of similarity and dissimilarity on the candidates based on the preference profile. By slate clustering , we mean any method that partitions the candidates into k slates . If desired, this can be used to induce a partition of the voters into blocs by associating each ballot with the slate to which it is (in some sense) closest. One very reasonable approach is to regard candidates as more similar when they tend to be ranked in closer positions by votes. Definition 3.2 (Candidate dissimilarity by rank difference) . For any candidates A_{i},A_{j}\in\mathcal{C} , set D_{B}(A_{i},A_{j}):=\avg_{\sigma}\left|\mathfrak{b}(\sigma)_{i}-\mathfrak{b}(\sigma)_{j}\right|. The notation D_{B} for a metric on candidates is used to emphasize that, like d_{B} as a metric on ballots, this definition is constructed through rank differences. As usual, we can apply this with either pessimistic or averaged convention. If we use the pessimistic convention, then unmentioned candidates all have a rank of zero, so unpopular candidates will be considered highly similar. Depending on the application, this may or may not be desired behavior. Under the averaged convention, the point \mathfrak{b}(\sigma) is the centroid of the set of completions \overline{\sigma} that extend \sigma to a complete ballot. For most of this paper, we have been content to work with the centroid. For this application, we may learn more by dealing with the whole point cloud. Definition 3.3 (Candidate dissimilarity with point clouds) . For a ballot \sigma , let \overline{\sigma} be the set of complete ballots that can be reached from \sigma by a sequence of extensions. Then for any candidates A_{i},A_{j}\in\mathcal{C} , set \overline{D}_{B}(A_{i},A_{j}):=\avg_{\sigma}\avg_{\tau\in\overline{\sigma}}\left|\tau(i)-\tau(j)\right|. It is clear that D_{B} is a metric on candidates who receive rankings, but for \overline{D}_{B} this requires proof. Proposition 3.4 . \overline{D}_{B} is a metric on the set of candidates. Proof. Clearly \overline{D}_{B} is symmetric and positive definite. To verify the triangle inequality, let S denote the set of all completions of all cast ballots with the following redundancy convention. If the ballot \sigma from a given voter has length k , then the (m-k)! distinct completions of \sigma will each appear \frac{m!}{(m-k)!} times in S . Thus each voter is represented m! times in S . Notice that \overline{D}_{B}(A,B) equals the average over all \tau\in S of |\tau(A)-\tau(B)| . The triangle inequality follows. ∎ Now that we have inter-candidate distances, we can use a variety of methods to group the candidates into slates, and from there to assign corresponding blocs of voters. We will focus on two among many possible methods. • Centers. First cluster the candidates: given k , identify the k candidates as centers that minimize the summed D_{B} -distances to the centers. The i th slate \mathcal{C}_{i} includes those candidates closest to center i . This slate embeds in \mathbb{R}^{m} by applying \mathfrak{b} to the generalized ballot (\mathcal{C}_{i},\ \mathcal{C}\setminus\mathcal{C}_{i}) . Now partition the voters by associating each ballot \sigma to its closest slate point \mathfrak{b}(\mathcal{C}_{i}) . • Agglomeration. Agglomerate the candidates with respect to \overline{D}_{B} and average linkage. 2 2 2 Agglomerative, or hierarchical, clustering requires a linkage choice: single, average, or complete. These merge point clouds successively by looking at their mutual distances as measured by minimum, average, or maximum distance of their constituent points, respectively. An example is carried out below in Figure 10 . To obtain k slates, stop after the appropriate number of agglomeration steps. Now associate each ballot \sigma to the slate to which it awards the most Borda points per candidate. The first method is the most in keeping with our primary clustering methods for voters. Since the set of candidates is small, the agglomerative clustering used in the second method is also attractive, because it yields an interpretable sequence of merges starting from the candidates as singletons and ending with a pair of slates. 3.3. Synthetic elections One challenge for testing clustering methods on real-world data is the lack of ground truth about whether voter behavior was polarized—not finding a good nontrivial clustering can indicate a poor clustering method or an unpolarized election. It is therefore desirable to build a test set of synthetic elections with controlled polarization attributes. Given n\in\mathbb{N} , p\in(0,1) , and a complete ballot \sigma\in\Omega_{m} , we randomly generate a cluster \mathcal{C}(\sigma,n,p)\subset\Omega_{m} comprised of n complete ballots, each obtained from \sigma by performing a number of random adjacent swaps that is drawn from the geometric random variable with parameter p , in the style of a Mallows model. In other words, each ballot is obtained via a random walk on the complete portion of the ballot graph starting from \sigma , with as many steps as a p -weighted coin comes up tails. A higher p value corresponds to a tighter cluster (because the coin lands heads more quickly so the walks are shorter). A simple polarized election can then be formed from two or more such clusters, amounting to a mixed Mallows model. We first consider an election-valued random variable \mathcal{E}=\mathcal{C}(\text{ABCDE},300,0.3)\cup\mathcal{C}(\text{EDCBA},700,0.3)\subset\Omega_{5}. An instance is shown in Figure 5 . Here, we use a standard technique called multidimensional scaling (MDS) for the visualization: from the full matrix of pairwise distances between points, we find a low-distortion planar embedding in order to visualize the metric. We will employ MDS for visualization throughout the empirical sections of the paper. Figure 5 . MDS plot of the ballots in a synthetic election \mathcal{E} . Ballots marked green were hit from both centers. All of our modeling choices for 2 -clustering the voters pick out the ground-truth clusters in this election, even though the cluster sizes are unbalanced. For example, over several instances of \mathcal{E} and several runs of PAM, the identified centers are always \{ABCDE,EDCBA\} , with cluster sizes close to \{300,700\} . That is, it finds the correct centers and identifies each ballot with its closest center rather than the site from which it originated. Even though Lloyd’s algorithm for the 2 -means problem targets minimal L^{2} cost rather than L^{1} , it gives clusters that differ by only about 1\% from the L^{1} clusters. 3 3 3 Two partitions differ by 1\% if 1\% of the points must be reclassified to convert one partition into the other. The agglomerative method discussed in the previous section yields the reasonable slates \{\{A,B,C\},\{D,E\}\} and produces voter clusters that differs by only about 4\% from the previous ones, with cluster sizes (in one instance of \mathcal{E} ) of \{317,683\} . Figure 6 . MDS plots of the ballots in \mathcal{E}_{2}(p) and \mathcal{E}_{3}(p) for three values of p . Figure 7 . Silhouette scores for Lloyd’s k -means clusterings of \mathcal{E}_{2}(p) (left) and \mathcal{E}_{3}(p) (right) for values of p from .02 to .5 by steps of .02 . (We show k -means instead of PAM clusters for computational efficiency.) Next, consider 9 -candidate elections \mathcal{E}_{2}(p) and \mathcal{E}_{3}(p) , with instances shown in Figure 6 . \displaystyle\mathcal{E}_{2}(p) \displaystyle=\mathcal{C}(\text{ABCDEFGHI},300,p)\cup\mathcal{C}(\text{HGEIFCBAD},700,p); \displaystyle\mathcal{E}_{3}(p) \displaystyle=\mathcal{C}(\text{ABCDEFGHI},200,p)\cup\mathcal{C}(\text{DFEAHBGCI},200,p)\cup\mathcal{C}(\text{HIGDEFCBA},600,p) For all values of p between 0.02 and 0.5 by steps of 0.02 , the PAM 2-medoids algorithm correctly identified the two centers of \mathcal{E}_{2}(p) as ABCDEFGHI and HGEIFCBAD . This remained true over multiple runs of PAM and multiple instances of \mathcal{E} . For almost all values of p in this same range, the PAM 3-medoids algorithm correctly identified the three centers of \mathcal{E}_{3}(p) ; The only discrepancies occurred with p=0.02 and p=0.04 ; in some trials with these values, one or two of the medoids were off by a single swap move. There are several common methods for identifying the "best" choice for the number of clusters in a dataset. One common method is to construct silhouette scores , which compare a point’s average distance to other points within its cluster against the average distance to points in the nearest other cluster. These are thought to be normalized so that if the silhouette score for the best 3-clustering is larger than the score for the best 2-clustering, it signals that the data is better described by three clusters. Figure 7 shows that this silhouette scores in our synthetic elections. For \mathcal{E}_{2}(p) , the silhouette method clearly picks out two clusters, even at very low values of p . However, for \mathcal{E}_{3}(p) , two or three clusters looks equally apt for p\leq 0.14 , and better than four or five. 4. Results on Scottish elections We begin with a detailed walk-through of implementing the clustering methods on a particular (arbitrary) contest from the Scottish local government elections: Ediburgh Ward 2 (Pentland Hills), 2017. From there, we will zoom out to an overview of the whole Scottish dataset. 4.1. Learning voter blocs in Pentland Hills The Pentland Hills election had seven candidates competing for three seats. 1=Graeme Bruce ( Con ), 2 = Emma Farthing ( LD ), 3 = Neil Gardiner ( SNP ), 4 = Ricky Henderson ( Lab ), 5 = Ernesta Noreikiene ( SNP ), 6= Susan Webber ( Con ), 7 = Evelyn Weston ( Grn ). Here, Con is the Conservative and Unionist Party, LD is Liberal Democrats, SNP is the (ruling, centrist) Scottish National Party, Lab is Labour, and Grn is the Green Party. These five are the most important players in local government, together holding 1071 out of 1227 seats at the time of writing. Independent candidates, not to be confused with candidates for the Independence for Scotland Party (ISP), also receive significant support. Figure 8 . Borda plots (top) and mentions plots (bottom) of the optimal k -clusterings using Borda distance with k=2 and k=3 . The total height of each bar in a "mentions" plot is the number of ballots in the cluster that ranked the candidate in any position, with first-place rankings represented by the darkest shade and so on. First, we describe the preference profile. The 11,315 cast ballots in this contest ranged from bullet votes (length 1 , occurring 967 times) to complete ballots (length 7 , occurring 1431 times). Overall, the average ballot length was 3.2 . There are 18 ballots cast over 100 times each, led by the ballot (1,6) ranking the conservatives in alphabetical order and leaving the rest blank—that ballot was cast by 1342 voters, about 11.8% of the electorate. Together, the ones receiving at least 100 votes account for more than half of the votes, but there is an extremely long tail, with 660 ballots receiving exactly one vote. Overall, 1238 different types were cast out of 8659 possible valid ballots. In Figure 8 , we show the global d_{B} optima for minimizing cost over all ballots for k=2 and k=3 . The k=2 solution partitions the voters into two clusters of roughly equal size ( 6513 in Cluster 1 and 4802 in Cluster 2). The k=3 solution has clusters of size 3798 , 2565 and 4955 . Figure 9 . Visualization of the ballots in Pentland Hills with respect to \mathfrak{b} . All three images use the same low-distortion MDS embedding of the ballots, approximating their d_{B} distances. Each marker’s area is proportional to the number of voters who cast that ballot. In the top plot, the ballots are colored by the party of the first-place vote, and on the bottom they are colored by their cluster assignment for k=2 and k=3 clusters. Whether we use head-to-head, pessimistic, or averaged Borda, whether we use L^{2} or L^{1} methods, and whether we require cast-ballot centers, valid ballots, or allow arbitrary centers in coordinate space, we obtain very similar centers and very similar groupings of voters. The k=2 cast-ballot centers (the pair of ballots that minimize the cost) always includes (1,6) as one center. The other center always begins with (3,5) and may be (3,5,7,4) , (3,5,7) , or (3,5,4) depending on the method. For k=3 , all of the embedding choices produce the same centers: (1,6),(3,5,7),(2,4) . What is the right choice for the number of clusters in this Pentland Hills example? Silhouette scores identify k=2 . However, the choice k=3 also scores well and is compelling because, as illustrated in Figure 9 , the 3 -clustering assignments look reasonable and align closely with the party of the first-place vote; that is, the choice k=3 best encodes the SNP – Lab – Con triangle that stands out in the party labeling (Figure 9 ). 4.2. Learning candidate slates in Pentland Hills Next, we sort the candidates rather than the voters. As illustrated in Figure 10 , the slate clusters are identical whether we use the centers method based on raw rank difference ( D_{B} ) or the agglomerative method with ballot completion ( \overline{D}_{B} ). 4 4 4 Switching to complete or single linkage instead of average linkage makes only small changes. At k=2 partition, the slating remains unchanged under all linkage methods. The k=3 partition remains the same using complete linkage, whereas single linkage produces the slates \{1,6\},\{4\},\{2,3,5,7\} . A comparison of Figures 9 and 10 also shows that these inter-candidate differences echo the embedded structure of the full preference profile. The candidate-centric methods agree that \{1,6\} is a candidate cluster whether there are two clusters or three. That squares well with the identification of (1,6) as a ranked ballot appearing as central to blocs across all voter clustering methods in the previous section. One difference is whether the Green candidate (7) is grouped with SNP candidates (3 and 5) or with the Labour/Liberal Democrat candidates (2 and 4). As Figure 10 shows, either choice is close to optimal in the space of candidates. 1 2 3 4 5 6 7 \mathbf{D_{B}} \mathbf{\overline{D}_{B}} 1 2 3 4 5 6 7 k=7:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{3}}\},\{{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{5}}\},\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\} k=6:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{3}}\},\{{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{5}}\},\{{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\} k=5:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}}\},\{{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}}\},\{{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\} k=4:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}},{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}}\},\{{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}}\} k=3:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}},{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}},{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}}\} k=2:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}},{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}},{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\} k=1:\{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{1,0.6016,0.1992}\mathbf{2}},{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}},{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\} k=2: Centers {\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}} and {\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}} are optimal, giving slates \{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}},{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}},{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\} k=3: Centers {\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}} , {\color[rgb]{1,0.6016,0.1992}\mathbf{2}} , and {\color[rgb]{1,0.8828,0.207}\mathbf{5}} are optimal, giving slates \{{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{1}},{\color[rgb]{0.0586,0.3008,0.5742}\mathbf{6}}\},\{{\color[rgb]{1,0.6016,0.1992}\mathbf{2}},{\color[rgb]{0.8906,0.1484,0.2109}\mathbf{4}},{\color[rgb]{0.2969,0.7344,0.0898}\mathbf{7}}\},\{{\color[rgb]{1,0.8828,0.207}\mathbf{3}},{\color[rgb]{1,0.8828,0.207}\mathbf{5}}\} Figure 10 . MDS plots of the Pentland Hills candidates by D_{B} and \overline{D}_{B} , colored by party and sized by the number of mentions received. The optimal centers for D_{B} slate clustering are shown, as well as the successive steps for agglomerative \overline{D}_{B} slate clustering. The k=2 and k=3 slates match exactly across the two methods. 4.3. Overview across dataset To approach clustering on the Scottish dataset, we first compare 2 -clustering methods. We can efficiently sweep the dataset with the heuristic methods described above.Then, with integer programming methods described in forthcoming work with David Shmoys and Peter Rock, we can confirm that the heuristic optima are often in fact globally optimal. In over 90\% of Scottish elections ( 981 matches with Borda embeddings and 1010 with head-to-head), the PAM heuristic finds precisely optimal centers. Appendix A offers a fuller discussion of comparison for the approximate methods. More fundamentally, we can study the degree of agreement of exact optima across methods. To evaluate this, we can start by regarding the center of the whole election as a summary of the preference profile—the minimum-cost cast ballot. For k=1 , 74.6% of the elections have matching head-to-head and Borda centers, meaning that the Kemeny rule would give the same output ranking as the Borda median rule, even with partial ballots available. This is notable because Kemeny is strongly Condorcet consistent—if any candidate is preferred head-to-head to all others, they rank first; if any candidate is preferred to all but the first, they rank second, and so on. Rules based on positional scores like Borda count have no such guarantee and are a priori very different. When we pass to optimal pairs under cost-minimization, the exact agreement of centers is significantly more demanding. But for k=2 , the degree of agreement is almost as high: 73.5% of the elections have perfectly matching d_{H} and d_{B} centers (i.e., both centers agree). Though our methods for grouping candidates are party-agnostic, we can use party labels as a partial ground-truth validation. Both methods of slate clustering perform well at keeping political parties together. Among the 1070 Scottish elections, 855 of them include more than one candidate from at least one of the five major parties ( SNP , Lab , Con , LD , Grn ). It is extremely rare (occurring eight times for the centers method and just three for the agglomerative method) for the k=2 slates to split any pairs of candidates from the same party. But beyond recovering parties, we can discover inter-party structure: for instance, the two most consistently close parties across this dataset are the Scottish National Party and the Greens (rather than pairing the ruling SNP party with Labour or Liberal Democrats, as might have been expected). 5. Conclusion Although aggregating rankings is an extremely popular topic in the computing literature, surprisingly little of that work is adapted to the real-world setting of ranked choice elections for political office, where an extension to partial rankings is a practical necessity. First and foremost, this paper develops metric theory that situates ballots, candidates, and slates (or sets of candidates) all in common spaces that admit natural extensions of the Kendall tau and Spearman footrule metrics. This enables the use of coordinate tools, on one hand, and graph/network-based tools, on the other. Building on this foundation, we give detailed methods for grouping voters into like-minded blocs and for grouping candidates according to voter preference. Bloc and slate identification then unlocks the measurement of key descriptive statistics: to measure the polarization of an election, we look at the diffusion of blocs about their centers and the distance between those centers. As a direct consequence of inequalities connecting the principal metrics under study, sufficiently polarized elections must give consistent partitions of voters by either ranking metric. Given blocs and slates, it is now straightforward to assess the proportionality of a voting rule by whether the slates receive representation in shares aligned with the sizes of voter blocs. The techniques developed here broadly enable visualization and hands-on data analysis, while giving a strong foundation for unsupervised techniques to learn structural information about observed elections. Appendix A Comparing heuristic methods Table 1 indicates a high degree of concordance among outputs over our database of 1070 Scottish council elections between 2012 and 2022. In particular, the choice of embedding ( \mathfrak{b} or \mathfrak{h} ) is generally of fairly mild consequence. Although we did not included in the table, \mathfrak{b}_{\text{avg}} performed very similarly to \mathfrak{b} . Figure 11 (left) uses MDS to visualize the distances reported in the table. Recall that since Lloyd’s is solving the L^{2} problem, it’s giving back the standard Borda ranking (ranking candidates by their total Borda score) while PAM is giving a median in place of an average. Lloyd \mathfrak{b} Lloyd \mathfrak{h} PAM \mathfrak{b} PAM \mathfrak{h} Lloyd \mathfrak{b} 0.00 0.02 0.07 0.07 Lloyd \mathfrak{h} - 0.00 0.07 0.07 PAM \mathfrak{b} - - 0.00 0.04 PAM \mathfrak{h} - - - 0.00 Table 1 . The average over 1070 elections of the differences between the 2 -clustering methods. Each cell represents the portion of ballots in the election for which the two partitions disagree on average. Diagonal cells represent the average disagreement between two runs of the same method. All cells are rounded to 2 decimals. Next, we compare the results of slate clustering by the two methods emphasized above. To compare the sizes of slates in an apples-to-apples fashion, we restrict to the 282 Scottish elections that have seven candidates (the most common number of candidates). For the separation of candidates into two slates, we report the size of the smaller slate. • Via centers: 35 slates of size 1, 164 slates of size 2, 83 slates of size 3 • Via agglomeration: 23 slates of size 1, 185 slates of size 2, 74 slates of size 3 Figure 11 (right) shows the distribution of bloc sizes for each 2 -clustering method. None of the clustering methods specifically target balanced bloc sizes, but the results in Scotland tend toward balanced blocs for all clustering methods. Figure 11 . LEFT: MDS plot of distances between clustering methods from Table 1 . RIGHT: A visualization of how balanced the cluster sizes are in the 2-bloc case. Smaller bloc shown. Appendix B Visualizing polarization The agglomerative slates for k=2 and 3 in the Pentland Hills election are pictured in Figure 12 in a way that illustrates the election’s level of polarization with respect to these slates. The idea of this visualization is that the k vertices of the simplex \Delta^{k-1}=\left\{(x_{1},...,x_{k})\mid\sum x_{i}=1,\text{all }x_{i}\geq 0\right\} represent the k slates. Each ballot \sigma cast in the election has a position f(\sigma)\in\Delta^{k-1} determined so that a ballot is positioned closer to a slate that it more strongly supports, and the plots illustrate the density of the cast ballot images over the simplex. More precisely, we used the function (1) f(\sigma)=\frac{(v_{1},...,v_{k})}{v_{1}+\cdots+v_{k}}, where v_{i} is the average number of (pessimistic) Borda points that \sigma awards to the candidates in the i^{\text{th}} slate. This definition of f is consistent with our agglomerative slate-clustering method of assigning ballots to slates; that is, the agglomerative method was defined to assign each ballot \sigma to the slate corresponding to the vertex of \Delta^{k-1} closest to f(\sigma) . Figure 12 . Plots showing the density of ballots cast in the Pentland Hills election with respect to the k=2 and k=3 slates obtained from either clustering method. On the right, the triangle represents \Delta^{2} and the area of each circle is proportional to the number of ballots \sigma mapped to f(\sigma) . For both k=2 and k=3 , the set of slates in Figure 12 arose from agglomerative clustering of the candidates, but it happens to also be the partition of the candidates that minimize the sum over the ballots \sigma of the Euclidean distance in \Delta^{k} from f(\sigma) to the nearest vertex (slate). In other words, Figure 12 helps to visualize the profile’s level of polarization with the choice of slates maximizing that polarization. This observation suggests another reasonable slate clustering method: directly select the slates that solve this optimization problem. Compared to the agglomerative method, this alternative version is computationally more demanding but yields an interpretable visualization. The two method agree in the Pentland Hills election (because they turn out to yield the same slates, and they use the same method of associating ballots to slates).