Metric geometry for ranking-based voting: Tools for learning electoral structure

Technical Summary: Metric Geometry for Ranking-Based Voting

Authors: Moon Duchin and Kristopher Tapp
Core Objective: To develop a unified metric geometric framework for analyzing ranking-based elections, specifically extending classical permutation distances to accommodate partial ballots (incomplete rankings), which are common in real-world voting.

---

1. The Problem: Limitations of Classical Ranking Metrics

In computational social choice, two primary metrics are used to measure the distance between complete rankings: Kendall tau (measuring pairwise swaps) and Spearman footrule (measuring positional shifts). However, these metrics are traditionally defined for full permutations.

In real-world elections, voters often submit partial ballots (e.g., ranking only 2 out of 10 candidates). Standard methods struggle to incorporate these "bullet votes" or incomplete lists without making arbitrary assumptions. Furthermore, there is a need for descriptive tools to identify voter blocs (groups of similar voters) and candidate slates (groups of similar candidates) to measure polarization and proportionality.

2. Methodology: Coordinate Embeddings and Graph Realizations

The authors propose two mathematical ways to represent ballots in a metric space, allowing for both complete and partial rankings:

A. Coordinate Embeddings (Vector Space Approach):
The paper introduces two embedding functions that map ballots into $\mathbb{R}^m$ or $\mathbb{R}^{\binom{m}{2}}$:

• Borda Embedding ($d_B$): Maps a ballot to a vector where each candidate's coordinate is their Borda score. The authors use a "pessimistic convention" for partial ballots, where unmentioned candidates receive zero points. This allows the Spearman footrule to be extended naturally.
• Head-to-Head Embedding ($d_H$): Maps a ballot to a vector of pairwise comparisons ($\pm 1$ for a win/loss, $0$ for a tie). This extends the Kendall tau distance to partial ballots.

B. Ballot Graphs (Graph Theory Approach):
The authors realize these distances as path metrics on weighted graphs:

• Ballot Graph ($G_m$): A sparse graph where edges represent neighbor swaps or the truncation/extension of ballots. The path metric on this graph recovers $d_H$.
• Shortcut Ballot Graph ($G^+_m$): Adds "general swap" edges (allowing candidates to jump multiple positions at once). The path metric on this graph recovers $d_B$.
• Generalized Ballot Graphs: An extension that allows for ties (sets of candidates ranked equally), enabling the study of "slates."

3. Key Contributions

• Mathematical Extension: Proved that the Diaconis–Graham bounds ($\frac{1}{2}d_H \leq d_B \leq d_H$) and other metric properties hold for partial ballots under the pessimistic Borda convention.
• Unifying Framework: Connected the geometry of rankings to three major social choice topics: metric distortion, polarization, and proportionality.
• Stability Theorem: Proved that in "polarized" elections (where voter clusters are sufficiently far apart), the resulting voter groupings are stable and consistent regardless of whether one uses $d_B$ or $d_H$.
• New Clustering Algorithms: Developed methods for:
  • Voter Blocs: Using $k$-medoids (PAM) on the embedding coordinates.
  • Candidate Slates: Using candidate dissimilarity metrics ($D_B$) via agglomerative clustering.

4. Results and Validation

The authors validated their framework using two methods:

• Synthetic Validation: Using a mixed Mallows model (simulating polarized clusters), they demonstrated that their clustering methods (PAM and Agglomerative) accurately recovered the "ground truth" centers and cluster sizes, even with unbalanced populations.
• Real-World Application (Scottish Elections): They analyzed over 1,000 local government elections (2012–2022).
  • Robustness: They found that different mathematical choices (L1 vs. L2, Borda vs. Head-to-Head) produced nearly identical voter groupings.
  • Party-Agnostic Discovery: While the methods successfully grouped candidates from the same political parties, they also uncovered inter-party structures (e.g., the close relationship between the SNP and Green parties) that party-label-focused analysis might miss.
  • Computational Efficiency: They showed that heuristic clustering is highly effective, matching globally optimal solutions in over 90% of cases.

5. Significance

This paper provides a rigorous mathematical foundation for unsupervised learning in elections. By treating elections as "point clouds" in a metric space, researchers can move beyond simple winner-take-all counts to understand the underlying structural geometry of political preference. This has profound implications for measuring how polarized a society is and determining if an electoral system provides fair, proportional representation to different voter blocs.