In social choice theory, we often want to know how "close" an election is to an ideal state. Theoretical models are clean: in a perfectly single-peaked electorate, candidates can be arranged along a single axis (such as a left-to-right political spectrum) so that every voter has a single favorite and their preference drops off monotonically as candidates move further away.
In reality, real-world voting data is noisy and rarely fits these clean mathematical definitions perfectly. To make sense of this mess, researchers try to measure the distance between an observed preference profile and a structured one, or between two different election datasets entirely. This geometric view allows us to build a "map of elections" to visualize and evaluate voting behaviors.
However, a fundamental computational barrier stands in the way: while checking if two elections are exactly identical (isomorphic) is computationally easy, calculating the distance between them—or finding the minimal changes needed to reveal their underlying structure—is almost always NP-hard.
The Cost of Cleaning Noisy Profiles
Imagine you have an election profile that is almost single-peaked, except for a few erratic voters or anomalous candidates. If you could just remove them, you could use fast, elegant algorithms designed for structured domains. How hard is it to find the minimum number of modifications required to restore this structure?
As it turns out, it is very hard. Gábor Erdélyi et al. in Computational Aspects of Nearly Single-Peaked Electorates demonstrated that calculating the distance to a single-peaked state using voter removals or preference swaps is NP-complete. Interestingly, they found an asymmetry: deleting candidates to achieve consistency can sometimes be done in polynomial time, whereas deleting voters cannot.
This asymmetry is a recurring theme across the literature. Edith Elkind et al. in On Detecting Nearly Structured Preference Profiles formalized this by showing that the computational difficulty of cleaning a profile heavily depends on whether the cleaning process involves removing voters or removing candidates.
To map this boundary across various structural properties (such as value-restricted or best-restricted profiles), Robert Bredereck et al. in Are there any nicely structured preference profiles nearby? analyzed formal problems like $\Pi$ Maverick Deletion (voter removal) and $\Pi$ Alternative Deletion (candidate removal), proving a widespread pattern of NP-hardness. Whether dealing with single-crossing profiles as explored by Foram Lakhani et al. in Correlating Preferences and Attributes: Nearly Single-Crossing Profiles or master lists as analyzed by Ildikó Schlotter in Recognizing when a preference system is close to admitting a master list, even minor deviations from ideal structures introduce severe computational bottlenecks.
The Combinatorial Explosion of Relabeling
The problem becomes even more complex when comparing two entirely different elections to see if they share the same underlying behavior. If we want a distance metric to be meaningful, it must be mapping-invariant (or isomorphic). This means that if we simply swap the names of the candidates or change the order of the voters, the distance between the two elections should remain zero.
As Piotr Skowron 0001 et al. point out in How similar are two elections?, this requirement creates a striking paradox: testing whether two elections are perfectly isomorphic is computationally easy, but computing the isomorphic distance between two non-identical elections is NP-complete.
Why does this happen? To compute an isomorphic distance (such as a swap or Spearman distance), an algorithm cannot just compare the profiles directly. It must find the absolute best alignment out of all possible permutations of candidates and voters. As Stanislaw Szufa et al. explain in Drawing a Map of Elections in the Space of Statistical Cultures, this combinatorial explosion prevents straightforward comparisons when mapping out different "statistical cultures" of voting.
Substructures and the Limits of Approximation
What if we don't look at the whole election, but try to find a smaller, shared sub-component? This is the core of the subelection isomorphism problem.
The authors of The Complexity of Subelection Isomorphism Problems, Piotr Faliszewski et al., showed that while finding an exact match for an entire election is easy, determining if a smaller election is isomorphic to a sub-part of a larger one is generally NP-complete.
One might hope that if we are given a partial hint—like a pre-defined matching between candidates or voters—the problem would simplify. However, Stanislaw Szufa et al. in another paper titled The Complexity of Subelection Isomorphism Problems proved that finding the Maximum Common Candidate-Subelection remains NP-hard even when explicit mapping information is provided. The underlying combinatorial conflict is deeply embedded in the candidate preference structures themselves, meaning that hints about voter alignments do not resolve the difficulty.
Worse yet, we cannot easily bypass this hardness with approximation algorithms. The authors of How similar are two elections? proved that achieving good polynomial-time approximation ratios for isomorphic election distances is impossible unless P=NP.
Finding Paths to Tractability
Faced with total NP-hardness, how do researchers actually build maps of the election space? They use two primary strategies: finding efficient surrogate metrics or leveraging parameterized tractability.
Instead of computing the exact, intractable swap distance, Niclas Boehmer et al. in Understanding Distance Measures Among Elections introduced the EMD-positionwise metric (Earth Mover's Distance applied to position matrices). This metric bypasses the need to check every permutation of candidates by aggregating preferences into a position matrix (recording how many voters put candidate $X$ in position $Y$) and computing the distance between these matrices. This completely sidesteps the permutation problem, turning an NP-hard problem into a polynomial-time one while retaining structural meaning. Similarly, when extending these maps to approval-based voting, Stanisław Szufa et al. in How to Sample Approval Elections? designed an "approvalwise distance" metric to navigate large datasets efficiently.
Alternatively, researchers look for specific parameters that confine the hardness. For instance, Ildikó Schlotter demonstrated that while calculating vertex or edge deletions to find a master list is highly complex, calculating the minimum number of adjacent swaps is fixed-parameter tractable (FPT). By isolating the exact source of combinatorial complexity, these approaches allow social choice theorists to navigate the messy geometry of real-world preferences.
Key Foundational Work
Computational Aspects of Nearly Single-Peaked Electorates (2013) — contributed 3 concept elements to this direction.
On Detecting Nearly Structured Preference Profiles (2014) — contributed 2 concept elements to this direction.