Research map / Learning theory and algorithms / Submodular and game algorithms
Distances Between Top-Truncated Elections of Different Sizes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the map-of-elections framework to elections of different sizes and top-truncated votes by proposing a positionwise extension (via Wasserstein distance) and a feature-based DAP distance, and uses DAP to map Preflib.
Problem
Map-of-elections visualizations were restricted to equal-sized, complete elections, so real-world elections with different candidate/voter counts and top-truncated votes (e.g., Preflib, Formula 1) could not be compared natively.
Approach
Define a positionwise extension using Wasserstein distance between stretched frequency matrices that handles different sizes and truncated votes natively, and a feature distance DAP built on diversity, agreement, and polarization indices that is ID- and AN-consistent; argue via axioms that no swap extension can satisfy ID-, AN-, and UN-consistency simultaneously.
Key results
- DAP distance keeps ID and AN elections at distance zero across sizes, while positionwise is UN-consistent; the paper states the DAP scaled values are significantly smaller than positionwise in size-variation experiments.
- Truncated elections where voters rank at least half the candidates are less than 5% of the diameter from their complete variant under DAP (AN and IC exceptions up to 30% and 15%).
- Map of Preflib (raw, 3 to ~2600 candidates) shows most Preflib elections lie between Euclidean, Mallows, and urn models, with the AN region empty.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DAP distance rather than positionwise distance to compare same-culture elections with different candidate counts | Election maps · Synthetic elections from the same culture with different candidate counts | scaled distance | Helped |
| Use DAP distance rather than positionwise distance for top-k-truncated elections | Election maps · Top-k truncation; at least half of candidates ranked | normalized distance from the complete election: less than 20% of the diameter; less than 5% of the diamater | Helped |
| Use DAP distance for elections truncated by random cut or random drop rather than positionwise distance | Election maps · Random cut and random drop truncation | distance from the complete election | No clear effect |
| Use random drop truncation | Synthetic elections · Random drop truncation with dropping probability 0.5 | map separation of generated elections | Hurt |
Surprising findings
- No swap extension or positionwise extension can simultaneously satisfy ID-, AN-, and UN-consistency.
- The deleted-candidate swap extension fails the triangle inequality, and such violations are common in experiments.
Limitations
- No swap extension satisfying the desired axioms was found; this is left as an open problem.
- DAP is not UN-consistent, only approximately so as candidate counts grow.
- Random drop truncation yields elections that all collapse into a single cluster near UN, so such data is hard to analyze.
Experimental setup
Datasets: Preflib synthetic statistical cultures (IC, Mallows, urn, Euclidean, single-peaked, SPOC, group-separable)
Benchmarks: Preflib
Metrics: average normalized distance across sizes distance from complete to truncated elections axiom satisfaction (ID/AN/UN consistency, triangle inequalit
Baselines: isomorphic swap distance positionwise distance (EMD-based) truncated swap extension deleted swap extension
Builds on: isomorphic swap distance positionwise distance map of elections framework Kamada-Kawai embedding multidimensional scaling
Closest papers by meaning
- Implications of Distance over Redistricting Maps: Central and Outlier Maps (AAAI 2024 · similarity 0.85)
- Proportional Representation in Practice: Quantifying Proportionality in Ordinal Elections (AAAI 2025 · similarity 0.82)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.82)
- Proportional Representation in Metric Spaces and Low-Distortion Committee Selection (AAAI 2024 · similarity 0.80)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.79)
- Temporal Fairness in Multiwinner Voting (AAAI 2024 · similarity 0.79)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.